给定一本有数百万字的书。所有的单词一次都无法容纳在记忆中。给出一个有效的算法(空间和时间)来找到 10 个最常用的词。
我的方法是使用哈希并存储所有单词。通常哈希取值并将其乘以素数(使其更有可能生成唯一哈希)所以你可以这样做:
int hash=7;
for (int i=0; i < strlen; i++) {
hash = hash*31+charAt(i);
}
如果一个单词已经存在,则增加相应的计数。维护一个大小为 10 的最小堆。扫描一个单词时,找到它的频率。如果它大于堆中的最小值,则删除最小值并插入并更新堆。最后,我们得到了堆中出现频率最高的 10 个单词。有什么问题?这种方法只有在所有单词都可以同时容纳在内存中时才有效。
另一种方法是使用外部排序,因为书籍的大小与物理内存相比要大得多。排序后,线性搜索就可以完成我们的工作。但是,从磁盘访问的时间呢?寻道时间和延迟时间可以增加访问时间。因此,这种方法也效率不高。
我可以想到另一种方法:分布式哈希(仅当我们有 n 台机器时才有效)。在 n 台机器之间分布散列。我们可能会执行不同的策略,假设我们有 26 台机器,然后我们可能会对机器 1 中所有以字母 'a'('A') 开头的单词、以 'b'('B') 开头的单词等进行哈希处理。然后我们可以执行排序或者可以使用 TRIE 数据结构。
有没有更好的方法来查找前十个最常用的单词?