高效最常用的後綴算法？

Question

我有幾個GB值得的字符串，每個前綴我想找到10個最常見的後綴。有沒有一個有效的算法呢？

一個顯而易見的解決辦法是：

• 商店排序<string, count>雙名單。
• 通過二進制搜索範圍標識我們正在搜索的前綴。
• 在這個範圍內找到10個最高的count s。
• 可能預先計算所有短前綴，因此它不需要查看大部分數據。

我不確定這是否真的有效。有沒有更好的方式我忽略了？

答案必須是實時的，但它可能需要儘可能多的預處理。

Answer 1

將單詞放在樹中，例如trie或radix，爲每個完整單詞放置一個「出現次數」計數器，這樣您就知道哪些節點是結尾，以及它們有多普遍。

通過迭代找到前綴/後綴組合。

這兩個操作都是O（n * k）其中k是最長單詞的長度;這是作爲散列表的same complexity。

HAT-trie是一個高速緩存意識的版本，可以保證高性能。