algorithm - 在大词流中查找前 K 个频繁词

Question

给定一个未知大小的单词流，我需要在任何给定时间找到 k 个最频繁出现的单词，并且该程序应该能够运行很长时间。

我看到一个帖子和我想的解决方案很相似
The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
How to find the most frequent element in a stream of numbers with additions and deletions allowed
但我的问题是我如何处理内存不足的问题
在帖子中，他们没有提到这个问题。

所以我打算存储一个散列，其中键作为词，值作为词频和一个大小为 k 的最小堆，它将容纳最频繁出现的单词
对于每个单词，我将增加哈希中的计数并检查是否可以将其输入到堆中

问题是该程序应该能够运行很长时间，所以有可能我会以较小的频率得到不同的单词
我需要将它们保存在散列中，以防以后流中的频率增加
这会造成内存问题，因为随着时间的推移，散列会变得非常大

我想知道是否唯一的解决办法是删除某些单词
(但这会改变计数)

我不确定如何处理，有什么建议吗？

Answer 1

您可以使用 trie .并存储到目前为止出现的次数。

下面的树对应下面的输入:

ABL ABO AC AC AC ACR ACR

然后完成当前单词，增加相应的计数器并检查它是否大于 k-最频繁列表中最小的一个，如果是 - 替换。

因此，您需要 O(1) 时间来处理每个传入的字符。