algorithm - 在大词流中查找前 K 个常用词

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

我看过一篇类似于我正在考虑的解决方案的帖子
The Most Efficient Way To Find Top Kfrequent Words In A Big Word Sequence
How to find the mostfrequent element in a number of Streams with add and deletes allowed
但我的问题是我如何处理
帖子中的内存不足问题，他们没有提到这个问题。

所以我打算存储一个散列，其中键作为单词，值作为单词频率，大小为 k 的最小堆将保存最常用的单词
，对于每个单词，我将增加散列中的计数并检查如果我能把它输入堆

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

我想知道是否唯一的解决方案是删除某些单词
（但这会改变计数）

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

标签： algorithmhashmapout-of-memoryheap

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

以下树对应于以下输入：

ABL ABO AC AC AC ACR ACR

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

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