algorithm - 给定前缀，如何有效地找到最频繁出现的单词

Question

这是从这个问题扩展而来的面试问题:http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

但是这个问题需要更多的东西:GIVEN PREFIX

例如，给定“Bl”返回最频繁的词，例如“bloom、blame、bloomberg”等。

所以必须使用 TRIE。但是，如何有效地构造堆呢？在运行时为每个前缀构造堆是不正确或不切实际的。什么是好的解决方案。

[假设这个 TRIE 或数据结构是静态的，预构建的]

谢谢!

Answer 1

为文件中出现的所有单词及其计数保留一个 trie。所以现在如果它要求返回所有前缀为“BI”的单词，那么你可以使用形成的 trie 树高效地完成它。但是由于您有兴趣给出前缀为“BI”的最常出现的词，您现在可以使用最小堆来有效地给出答案，就像在您链接到的帖子中所做的那样。

另请注意，由于 trie 的空间使用量会变得非常大，您可以建议面试官使用 Ternary search tree而不是 trie。