在文件内存使用中查找k个最常见的单词

Question

假设你得到了一个巨大的文件，比如1GB。该文件每行包含一个单词（总共n个单词），您希望在该文件中找到k个最常见的术语。

现在，假设您有足够的内存来存储这些单词，那么在减少内存使用量和Big-O复杂性中的恒定开销方面，什么是更好的解决问题的方法？我相信有两种基本算法可以使用：

1. 使用一个哈希表和一个最小堆来存储出现的次数和前K个单词。这是O（n nlogk）~O（n）
2. 使用trie存储单词和出现的次数，然后遍历trie以计算最频繁的单词。这是O（n*p）~O（n），其中p是最长单词的长度

哪种方法更好？

另外：如果您没有足够的内存用于哈希表/trie（即10MB左右的有限内存），那么最好的方法是什么？

Answer 1

您是否开车去存储中间结果？如果为真：

你可能有一些元结构。和一组哈希表。读取一部分数据（而散列数据的大小

描述你的哈希表。在meta中，您可以存储唯一单词的数量和此哈希中所有单词的计数以及一个世界的最大计数！！！我

在这之后。您可以从磁盘加载哈希表并合并。

例如，您可以按唯一单词的升序加载哈希表，或按哈希中一个世界的最大计数加载哈希表。在这一步中，您可以使用一些启发式方法。

Answer 2

对于有限内存选项，您可以先对列表进行快速排序，然后简单地用k个项目填充一个哈希表。然后，您还需要一个计数器来知道您正在检查当前单词中有多少项-如果它更高，则用当前项替换哈希表中最低的项。

这可能对初始列表有效，但比只扫描完整列表并用计数填充哈希表要慢。

Answer 3

关于常数，哪个更有效是非常依赖的。一方面，trie为插入所有元素提供了严格的O（N）时间复杂度，而哈希表在最坏的情况下可能会退化为二次时间
另一方面，当涉及到缓存时，尝试并不是非常有效-每个搜索都需要O（| S |）随机访问内存请求，这可能会导致性能显著下降。

这两种方法都是有效的，我认为在选择其中一种时应该考虑多种因素，比如最大延迟（如果是实时系统）、吞吐量和开发时间。

如果平均案例性能是最重要的，我建议生成一堆文件并运行统计分析哪种方法更好。威尔科克森签名检验是目前使用的最先进的假设检验。

关于嵌入式系统：这两种方法仍然有效，但是在这里：trie中的每个节点（或一堆节点）将在磁盘上，而不是在RAM上。注意，这意味着对于trie O（|S|）随机访问磁盘寻求每个条目，这可能是慢的。

对于哈希解决方案，您有10MB，假设他们可以将其中的5MB用于磁盘指针的哈希表。让我们也假设你可以在这5MB上存储500个不同的磁盘地址（这里是悲观分析），这意味着你在每次哈希搜索后还有5MB要加载一个桶，如果你有500个桶，负载因子为0.5，这意味着你可以存储500*5MB*0.5~=1.25GB

注意，如果仍然不够，我们可以重新刷新指针表，这与在虚拟内存机制中的分页表中所做的非常类似。

由此我们可以得出结论，对于嵌入式系统，哈希解决方案在大多数情况下更好（请注意，在最坏的情况下，它可能仍然存在高延迟，这里没有银弹）。

另外，基数树通常比trie更快、更紧凑，但与哈希表相比，trie的副作用相同（当然不太明显）。