查找文件中最常见的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

关于常数更有效率是非常依赖的.一方面,trie O(N)为插入所有元素提供了严格的时间复杂度,而哈希表可能在最坏情况下衰减到二次时间.
另一方面,尝试在缓存方面效率不高 - 每次搜索都需要O(|S|) 随机访问内存请求,这可能会导致性能显着下降.

这两种方法都是有效的,我认为在选择一种方法时应该考虑多种因素,例如最大延迟(如果是实时系统),吞吐量和开发时间.

如果平均案例表现非常重要,我建议生成一堆文件并运行统计分析,哪种方法更好.Wilcoxon签名测试是事实上正在使用的现有技术假设测试.

关于嵌入式系统:两种方法仍然有效,但在这里:trie中的每个"节点"(或节点串)将在磁盘上,而不是在RAM上.请注意,这意味着每个条目的trie O(| S |)随机访问磁盘搜索,这可能会很慢.

对于散列解决方案,你有10MB,假设他们可以使用5MB这些用于磁盘指针的哈希表.我们还假设您可以在这5MB上存储500个不同的磁盘地址(这里是悲观分析),这意味着每次散列搜索后你还有5MB左右加载一个桶,如果你有500个桶,加载因子为0.5,则意味着你可以存储500*5MB*0.5~ = 1.25GB> 1GB的数据,因此使用散列表解决方案,所以使用散列 - 每次搜索只需要O(1) 随机磁盘搜索,以便找到包含相关字符串的存储桶.

请注意,如果仍然不够,我们可以重新发送指针表,非常类似于虚拟内存机制中的分页表中所做的操作.

由此我们可以得出结论,对于嵌入式系统,散列解决方案在大多数情况下更好(注意它可能仍然在最坏的情况下遭受高延迟,这里没有银弹).

PS,基数树通常比trie更快,更紧凑,但与哈希表相比具有相同的trie副作用(当然,虽然不太重要).

Answer 2

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

这对于初始列表可能没问题，但比扫描完整列表并用计数填充哈希表要慢。