algorithm - 在大文件中查找重复的字符串

Question

一个文件包含大量(例如100亿)个字符串，您需要查找重复的字符串。您有 N 个系统可用。你将如何找到重复项

Answer 1

erickson 的回答可能是出题者所期望的。

您可以将 N 台机器中的每台机器都用作哈希表中的一个桶:

• 对于每个字符串，(假设序列中的字符串编号 i)计算其哈希函数 h。
• 将i和h的值发送到n号机器进行存储，其中n = h % N。
• 从每台机器上，检索一个包含多个索引的所有哈希值 h 的列表，以及索引列表。
• 检查具有相等散列值的字符串集，看它们是否真的相等。

但老实说，对于 100 亿个字符串，您可以在一台 PC 上完成此操作。哈希表可能占用 80-120 GB 和 32 位哈希，具体取决于具体的哈希表实现。如果您正在寻找一种高效的解决方案，则必须更加具体地说明“机器”的含义，因为这取决于每个机器的存储量以及网络通信的相对成本。