按频率降序列出以固定前缀开头的“k”字

Question

我有一个大约10^5英语单词及其初始频率的列表。我想写一个单词完成建议程序，它将返回一个最大k单词列表，从给定前缀开始，按频率降序排序。数据结构还应该能够将一个单词的频率计数更新1（无论何时使用一个单词）。

例如，给定'engin'作为前缀，并且k=3，它应该返回这样的列表-{17，“engine”}、{10，“engineer”}、{4，“engineering”}

k的值应在[1,15]范围内。

Trie如果按频率排序不是一个问题，那么数据结构应该足够了，但它确实是一个问题。有人能给我一些数据结构或解决这个问题的方法吗？

注意：Trie数据结构占用太多空间。似乎我负担不起这个数据结构超过10MB的开销。另外，如果我使用与trie节点相关的最大堆（至少高达3/4深度），内存消耗将变得巨大。

现在我已经试过了——维护4个排序集（指针，指向字符串）。Seti是指向字符串长度的字符串的指针列表

• 字符串的首字母i的字典顺序
• 如果发生冲突，则按频率降序排列
• 如果再次发生冲突，以任何顺序（无关紧要）

考虑到我需要O（4nlog2（n））时间和O（nlog2（n））空间进行初始化，这工作得很好。对于每个查询，我的查找时间复杂度为O（log2（n）），再加上最坏情况下最多大约100个单词的遍历。为了更新一个单词的频率，需要O（8*log2（n））时间。




Answer 1

为什么不是trie呢？您可以为计数器使用额外的数据栏并将排序算法添加到搜索算法中。更新计数器和trie也很快。如果您只想要k个最大值/顶部边缘，那么它会更快，因为您不需要对所有边缘进行排序。

Answer 2

这可以通过组合两种数据结构来完成：trie和段树。（如果字典是静态的并且k不是很大）。

为字典构造trie后，使用属于该节点的第一个/最后一个单词的索引来扩充每个trie节点。例如，节点“engin”可以存储“engine”的索引1001和“engineering”的索引1003。

在搜索k单词列表时，首先在trie中搜索给定的前缀。然后使用第一个/最后一个单词索引执行k范围最大查询。每次查询后，将找到的单词的频率计数临时设置为-1。

使用段树数据结构进行范围最大查询。（有关详细信息，请参阅TopCoder上的教程）。

这种方法允许在时间O（前缀大小k*log（dict大小））内处理每个查询。计数器更新需要O（日志（dict_size））时间。初始频率以O（dict_size）时间加载。

另一种选择是在trie的每个节点中存储一个排序数组，数组中包含k_max{counter，index}对。

初始频率应在O（k_max*dict_size）时间内以自下而上的顺序（使用DFS）在每个节点上进行合并更新。每个计数器更新需要O（k_max*word_length）时间。Top-k查询在O（prefix_size）时间内提供。缺点是内存要求更高。