查找大量文本中最常用短語的高效算法

Question

我正在考慮編寫一個程序來爲我收集大量文本中最常見的短語。如果將問題簡化爲只是查找單詞，那麼將這些問題簡單到將每個新單詞存儲在散列映射中，然後在每次出現時增加計數。但用短語來說，將每個句子的排列作爲關鍵詞來存儲似乎是不可行的。

基本上，問題被縮小到了解如何從足夠大的文本中提取每個可能的短語。對短語進行計數，然後按出現次數進行排序變得微不足道。

Answer 1

我假定你正在尋找出現在相同順序中的連續詞的常見模式（例如，「世界之巔」不會被視爲與「世界之巔」或「世界之巔」相同的詞組「）。

如果是這樣的話，我會建議以下線性時間的方法：

1. 分裂您的文字到文字和刪除的東西，你不考慮顯著（即除去大寫，標點，字符等）
2. 將您的文本轉換爲一個整數數組（每個唯一字一個整數）（例如，每個「貓」實例變爲1，每個「狗」變爲2）這可以通過使用基於散列的字典在線性時間內完成存儲從單詞到數字的轉換。如果單詞不在字典中，則分配一個新的ID。
3. 構造一個後綴陣列爲整數數組（這是您的陣列的所有後綴的排序列表，並且可以通過線性時間來構造 - 例如，使用算法和C代碼here）
4. 構建最長公共前綴數組作爲後綴數組。 （這也可以用線性時間完成，例如使用這個C code）。這個LCP數組給出了後綴數組中連續對之間每個後綴開始處的常用單詞數。

你現在可以收集你的常用短語。

如何確定短語的結尾並不十分清楚。一種可能性是簡單地收集重複4個單詞的所有序列。
這可以在線性時間內完成，通過查看最長公共前綴數組大於或等於4的地方來處理後綴數組。每次在範圍[start + 1 ... start + len]中運行索引x，其中LCP [x]> = 4（除x的最後一個值外）對應於重複len次的短語。這個短語本身由前4個單詞給出，例如後綴start + 1。

請注意，這種方法可能會發現跨越句子結尾的短語。您可能更願意將一些標點符號（如句號）轉換爲唯一整數以防止出現這種情況。