algorithm - 许多文件中出现频率最高的单词是什么

Question

在许多文件(分布在多台机器上)中找到最常见单词的最有效算法是什么？

每台机器都可以给出其文件中出现频率最高的单词或任何单词的数量。

是否有一种算法或技术可以找到答案 - 确定性 - 而无需向每台机器询问所有单词？如果不是，最好的方法是用尽可能少的机器查询数量给出接近的答案。

Answer 1

假设您有 K 台机器。从每台机器请求最频繁的单词，将这 K 个单词发送到每台机器并计算它们在所有机器上的频率。令最常见的词出现频率为 N。

下一步，从每台机器请求列表中出现频率至少为 N/K 的所有单词。汇总此列表并发送到每台机器。收集跨机器的反向频率，将它们相加并找到总体上出现频率最高的单词。这个词保证是出现频率最高的词。