用於測試多個字符串中的多重子字符串的算法

Question

我有幾百萬字符串X，每個字符串少於20個單詞。我也有一個數列候選子串C的列表，對於X中的每個x，我想看看C中是否有任何包含在x中的字符串。現在我正在使用一個天真的雙循環，但它已經有一段時間了，它還沒有完成...有什麼建議嗎？如果任何人知道一個很好的實現，我使用python，但任何語言或一般算法的鏈接也會很好。

Answer 1

將其中一組字符串編碼爲trie（我建議使用更大的集合）。查找時間應該比不完美的散列更快，並且您也會節省一些內存。

Answer 2

這將是一個長 while。你必須對數千個候選子串中的每一個檢查數百萬個字符串中的每一個，這意味着你將會進行（幾百萬*幾千個）字符串比較。是的，這需要一段時間。

如果這是你只打算做一次或偶爾做的事情，我會建議使用fgrep。如果這是你經常要做的事情，那麼你需要考慮實施諸如Aho-Corasick string matching算法。

Answer 3

如果您在X X只包含文字，你只想匹配的話，你可以做到以下幾點：

插入關鍵字，一組，這使得訪問日誌（N），然後檢查x中的每個單詞如果包含在該集合中。

，如：

keywords = set(['bla', 'fubar']) 
for w in [x.split(' ') for x in X]: 
    if w in keywords: 
     pass # do what you need to do 

一個很好的選擇是使用谷歌RE2庫，使用超好看的自動機理論產生有效的匹配。 （http://code.google.com/p/re2/）

編輯：請確保您使用適當的緩衝和某種編譯語言，使它快得多。如果它少於幾GB，它應該與Python一起工作。

Answer 4

，你可以嘗試使用正則表達式

subs=re.compile('|'.join(C)) 
for x in X: 
    if subs.search(x): 
     print 'found' 

Answer 5

看一看http://en.wikipedia.org/wiki/Aho-Corasick。您可以爲一組固定字符串構建一個模式匹配程序，以時間線性的方式在字符串的總大小上進行搜索，然後在文本或文本的多個部分中搜索文本長度的線性時間+找到的匹配數量。

另一個快速確切模式匹配器是http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm