我有一个巨大的文本文件（比可用的RAM内存还大）。我需要计算所有单词的频率，并将单词和频率计数输出到一个新文件中。结果应按频率计数的降序进行排序。
我的方法：
- 对给定文件进行排序-外部排序
- 按顺序计算每个单词的频率，将计数与单词一起存储在另一个文件中
- 根据频率计数对输出文件进行排序-外部排序
我想知道是否有更好的方法。我听说过基于磁盘的哈希表？或B+树，但以前从未尝试过。
注意：我在SO上看到过类似的问题，但没有一个问题必须解决数据大于内存的问题。
编辑：根据评论，同意词典在实践中应该适合当今计算机的记忆。但让我们假设一本单词词典，它足够大，不适合记忆。
我会采用map reduce方法：
- 将文本文件分布在节点上，假设节点中的每个文本都可以放入RAM
- 计算节点内的每个单词频率。（使用
hash tables） - 在主节点中收集每个结果，并将它们全部合并
所有唯一的单词都可能存储在内存中，所以我会使用这种方法：
- 创建一个字典（
HashMap<string, int>） - 逐行阅读庞大的文本文件
- 将新词添加到词典中，并将值设置为1
- 将现有单词的值加1
在你解析了整个巨大的文件之后：
- 按频率对字典排序
- 将已排序的词典连同单词和频率一起写入一个新文件
不过，请注意将单词转换为小写或大写。
实现这一点的最佳方法是逐行读取文件并将单词存储到Multimap（例如Guava）中。如果这个Map扩展了你的内存，你可以尝试使用键值存储（例如Berkeley JE DB或MapDB）。这些键值存储的工作原理类似于地图，但它们将值存储在HDD上。我用MapDB解决了类似的问题，而且速度很快。
如果唯一单词的列表和频率适合内存（而不是文件，只有唯一单词），则可以使用哈希表按顺序读取文件（不存储）。
然后，您可以根据出现的次数对哈希表中的条目进行排序。