文件支持的trie(或前缀树)实现

如果你能对你的文件排序 包含字符串,然后读取排序列表并对重复项进行计数是很容易的。(您可以保留原始文件并创建一个新的已排序字符串文件。)高效地对大型文件排序是一种古老的技术。你应该能为它找到一个实用程序。

如果你不能分类 ,然后考虑 digesting 琴弦。MD5可能对您的目的是杀伤力过高。你可以把一些东西拼凑起来。对于数十亿个字符串,可以使用8字节的摘要。使用一棵消化树(可能是一个BST)。对于每个摘要,存储生成该摘要的唯一字符串的文件偏移量。

当您读取一个字符串时,计算它的摘要,然后查找它。如果找不到摘要,就知道字符串是唯一的。把它放在树上。如果确实找到了摘要,请检查每个关联的字符串是否匹配,并相应地进行处理。

要比较字符串,您需要转到文件,因为您存储的只是文件偏移量。

重要的是要记住,如果两个摘要是不同的,那么产生它们的字符串一定是不同的。如果摘要相同,则字符串可能不相同,因此需要检查。当重复字符串较少时,此算法将更有效。

如何将30GB同时加载到内存中?因为这是一种基于字典的行为,所以我可以想象每次插入或递增时,都需要加载整个文件(即使是逐段的)进行查找。

我建议使用数据库。这就是他们的目的…