通過子串快速過濾字符串集合？

Question

您是否知道一種快速過濾字符串列表以獲取包含指定字符串的子集的方法？顯而易見的實現是遍歷整個列表，檢查每個字符串是否包含搜索字符串。有沒有一種方法來索引字符串列表，以便可以更快地完成搜索？

Answer 1

Wikipedia article列舉了子索引索引的幾種方法。你有：

• Suffix tree
• Suffix array
• 的N-gram指數，對全部N-gram文本的反向文件
• 壓縮後綴數組1
• FM-index
• LZ指數

Answer 2

沒有什麼可行的，除非你有更多關於你的數據和/或搜索詞的先驗知識 - 例如，如果你只是在你的字符串的開始處搜索匹配，那麼你可以對字符串進行排序，只查看搜索字詞範圍內的字符串（或者甚至將它們存儲在二叉樹中，只查看可能匹配的分支）。同樣，如果您的潛在搜索條件有限，則可以在最初輸入時針對字符串運行所有可能的搜索，然後僅存儲一個匹配項和不匹配項的表。

除了這種事情，只是迭代基本上就是這樣。

Answer 3

這取決於子字符串是在字符串的開頭還是可以在字符串中的任何位置。

如果它在任何地方，那麼你幾乎需要迭代整個列表，除非你的列表太大並且查詢經常發生，因此值得構建更復雜的索引解決方案。

如果子字符串在字符串的開頭，那麼很容易。對列表進行排序，通過biseciton搜索找到開始/結束並獲取該子集。

Answer 4

是的，你可以爲字符串中的所有字符組合創建一個索引。像「hello」這樣的字符串將被添加到「he」，「el」，「ll」和「lo」的索引中。要搜索字符串「hell」，您將獲得所有「he」，「el」和「ll」索引中存在的所有字符串的索引，然後遍歷這些字符串以檢查字符串中的實際內容。

Answer 5

如果你可以預處理集合，那麼你可以做很多不同的事情。

例如，您可以構建一個包含所有字符串後綴的trie，然後使用它進行非常快速的匹配。

Answer 6

如果您要重複搜索相同的文本，那麼suffix tree可能是值得的。如果仔細應用，您可以針對大多數字符串問題實現線性時間處理。如果沒有，那麼在實踐中，你將無法做得比基於散列法的Rabin-Karp好得多，並且在預期時間內是線性的。

後綴樹有許多免費可用的實現。例如，參見C implementation或Java，請查看Biojava框架。