算法來搜索文本中的單詞列表

Question

我有一個單詞列表，相當小，大約1000左右。我想檢查該列表中的任何單詞是否出現在輸入文本中。如果是這樣，我想知道哪些發生。輸入文本每個都有幾百字，這些是來自網絡的文本段落 - 這意味着來自不同站點的文本段落很多。我正試圖爲它找到最好的算法。

我可以看到兩個明顯的方式來做到這一點 -

1. 搜索從文本列表中每個單詞的強制方法。

2. 從輸入文本中創建單詞的散列表，然後從散列表中的列表中搜索每個單詞。這很快。

有沒有更好的解決方案？

我正在使用python，但我不確定是否會改變算法。

此外，作爲上述解決方案2的優化，我想將生成的哈希表存儲到持久性存儲（DB），以便如果單詞列表發生更改，我可以重新使用哈希表而不必創建它再次。當然，如果輸入文本發生變化，我必須生成哈希表。是否有可能將散列表保存到數據庫？任何建議？我目前正在爲我的項目使用MongoDB，並且我只能將json文檔存儲在其中。我是MongoDB的新成員，剛剛開始使用它，但仍未完全瞭解它的全部潛力。

我已經搜索過，看到兩個類似的問題，其中一個提出了一個哈希表，但我想獲得任何指向我想到的優化。

這裏是以前提出的問題對SO -

Is there an efficient algorithm to perform inverted full text search?

Searching a large list of words in another large list

編輯：我剛剛發現SO另一個問題是關於同樣的問題。

Algorithm for multiple word matching in text

我想沒有比一個哈希表更好的解決方案。但我真的想優化它，以便對單詞列表進行更改可以讓我快速運行所有存儲的文本。我是否應該將添加到問題中的標籤更改爲包含某些數據庫技術？

Answer 1

還有是比散列表更好的解決方案。如果您想要在大量文本中搜索一組固定的單詞，則執行此操作的方法是使用Aho-Corasick string matching algorithm。

該算法構建了一個狀態機，你要搜索的詞，然後運行通過狀態機輸入的文本，輸出的匹配，而他們發現。因爲構建狀態機需要一些時間，所以該算法最適合於搜索非常大的文本體。

你可以用正則表達式類似的東西。例如，您可能希望找到一些文字寫着「狗」，「貓」，「馬」和「臭鼬」。你可以建立一個正則表達式：

"dog|cat|horse|skunk" 

然後運行上的文字正則表達式匹配。如何獲得所有匹配將取決於您的特定正則表達式庫，但它確實有效。對於非常大的單詞列表，您需要編寫讀取單詞並生成正則表達式的代碼，但這並不難，而且工作得很好。

儘管如此，正則表達式的結果和Aho-Corasick算法的結果有所不同。例如，如果你在字符串「我的業力吃了你的教條」中搜索「狗」和「教條」這兩個字。正則表達式庫搜索將報告找到「教條」。 Aho-Corasick的實施將報告在同一位置發現「狗」和「教條」。

如果您希望Aho-Corasick算法僅報告整個單詞，則必須稍微修改算法。

正則表達式也會報告部分單詞的匹配。也就是說，如果你正在尋找「狗」，它會在「教條」中找到它。但是你可以修改正則表達式只給出整個單詞。通常，這是與\b完成，如：

"\b(cat|dog|horse|skunk)\b" 

您選擇的算法依賴於輸入文本多麼大了很多。如果輸入的文本不太大，可以創建一個你正在查找的單詞的哈希表。然後通過輸入文本，將其分解成單詞，並檢查散列表以查看單詞是否在表格中。在僞代碼：

hashTable = Build hash table from target words 
for each word in input text 
    if word in hashTable then 
     output word 

或者，如果你想匹配的單詞在輸入文本列表：

hashTable = Build hash table from target words 
foundWords = empty hash table 
for each word in input text 
    if word in hashTable then 
     add word to foundWords