子串索引許多類似的字符串

我有一個大型的數據集合，在這種情況下，想象一下所有包含文件路徑的80,000+數組String。子串索引許多類似的字符串

作爲文件路徑，這意味着它們的大羣組以相同的路徑開始，例如，我有超過50,000個文件從"/dataset1/subsetAA/childX/"開始。

我想允許自由文本搜索這些路徑。現在我做一個簡單的斷言，看起來像這樣：

foreach(String term in terms) 
    if(path.IndexOf(term, StringComparison.OrdinalIgnoreCase) == -1) 
     return false; 
return true;

我保存的搜索結果，因爲它們可以鍵入，所以你越鍵入它變得更快，但是最初的幾個搜索（例如「f」>「fo」>「foo」）在快速機器上可能需要3或4秒。

我想建立一個子串索引，消除了我需要使用IndexOf，最好是利用通用路徑來減少索引大小，我不想消耗太多的內存。

2013-03-14 Dai

瞭解被稱爲特里數據結構：http://en.wikipedia.org/wiki/Trie

這不正是你想要的東西，它需要很多的字符串，並建立一棵樹了常見的前綴，用繩子，每片葉子是下面的字符串系列在其父母的前綴（您可以通過連接其所有的父母對什麼是在葉建，以節省空間）

2013-03-14 05:07:47 Patashu

這有幫助，但是如何從任何節點搜索Trie？例如如果「foo」和「foz」在Trie中，我怎樣才能搜索「oz」，而無需首先爲每個「o」詳盡搜索樹，或者這是不可避免的？（儘管我可以低效地使用'Dictionary >'來查找起點）。有什麼想法嗎？ – Dai 2013-03-14 06:43:43

嘗試不設計爲從任何節點啓動。更多的思考問題，我很喜歡dasblinkenlight的答案:) – Patashu 2013-03-14 07:44:52

但是最初幾個搜索（如「F」>「FO」>「的foo「）甚至可以在快速機器上花費3或4秒。

這是您需要優化的唯一方法。創建一個非常簡單的結構，它由三個散列集組成 - 對於單個字符，對於兩個字符和對於三個字符。單字符散列索引的每個元素都將包含一個包含索引字符的元素列表;雙字符散列索引的每個元素都將包含一個包含索引字符對的元素列表;三字符索引也會這樣做。

當輸入搜索的初始部分時，使用索引查找。例如，當鍵入f時，您將從第一個哈希表中獲取包含f的項目列表。隨着用戶繼續輸入，您將從第二個索引獲取"fo"密鑰的項目，然後從第三個索引獲取"foo"密鑰。

只要您獲得四個或更多字符，就會根據IndexOf返回搜索結果，使用搜索詞的最後三個字符，根據三個字符的子字符串在散列中查找初始列表。您從列表中獲得的項目數量相對較少，因此搜索速度會更快。

另一個優化應該是一旦有足夠的項目顯示給用戶就停止搜索。例如，如果用戶鍵入"tas"（來自"dataset"），那麼您的三個字符的索引會給你50000個點擊。抓住前20個（或者你需要顯示的數量），然後跳過剩下的部分：用戶會盡快完善他們的搜索，所以附加項目很快就會被丟棄。

2013-03-14 05:18:27 dasblinkenlight

回答