从非常大的文本文件中删除重复字符串

Question

我需要从一个超大文本文件（100GB+）中删除重复的字符串。

由于内存中进行去重是不可能的，因为数据量太大，所以我尝试了布隆过滤器，但是在处理超过5000万个字符串时就没有用了。

总共有1万亿+个字符串。

我想知道解决这个问题的方法是什么。

我的初步尝试是将文件分成多个子文件，对每个文件进行排序，然后合并所有文件...

如果您有比这更好的解决方案，请告诉我，谢谢。

- Shivraj

---

你走在正确的道路上；基于磁盘的归并排序可以帮你完成这个任务。之后只需对文件进行单次遍历即可。 - Brian Roach

也许所有计算机科学专业的学生都会在第一年学习一些高级算法，但如果我不想太费脑子的话，我可能会考虑实现一个基于磁盘的哈希集合。选择一个有意义的桶数值，称之为 n。创建 n 个文件。获取每个字符串的哈希码，并将该值 % n（称结果为 m）以查看它属于哪个桶。然后检查对应于 m 的文件，以查看其中是否存在该字符串。如果不存在，则添加它。继续下一个字符串。完成此过程后，您可以合并这些文件。 - Anthony Pegram

基本思路是忘记排序。只需创建大量的桶，越大越好，然后扫描这些桶。 - Anthony Pegram

我既不是硬件专家，也没有计算机科学背景。正如我所说的，我完全希望任何真正了解这两个领域的人都会嗤之以鼻我的建议。幸运的是，我在日常工作中不必从100GB文件中删除重复字符串。 - Anthony Pegram

其他好奇心，重复出现的频率有多高？是经常出现，还是只有一些奇怪的情况，或者真的不知道？我曾经遇到过一个较小的案例（约10个Go文件），其中大部分相同的消息都被聚集在一起，大多数已经预先排序。找到唯一的消息很容易，只需查看下一行，看它是否相同即可。最后，少数罕见的重复并不太重要。 - MPelletier

Answer 1

您要了解的关键概念是外部排序。您应该能够使用该文章中描述的技术对整个文件进行合并排序，然后顺序遍历以删除重复项。如果该文章不够清晰，请查看此类实现。

- Slugart

---

没错。计算机科学基础和维基百科可以提供帮助。 - Eugene Y.

Answer 2

你可以创建第二个文件，其中包含记录，每个记录都是64位CRC加上字符串的偏移量，并且应该为快速搜索进行索引。 像这样：

ReadFromSourceAndSort()
{
   offset=0;
   while(!EOF)
   {
      string = ReadFromFile();
      crc64 = crc64(string);
      if(lookUpInCache(crc64))
      {
         skip;
      } else {
         WriteToCacheFile(crc64, offset);
         WriteToOutput(string);
      }
   }
}

如何制作好的缓存文件？它应该按照CRC64进行排序以便快速搜索。因此，您应该像二叉搜索树一样构建此文件的结构，但是可以快速添加新项目而无需移动现有项目。为了提高速度，您需要使用内存映射文件。

可能的答案：

memory = ReserveMemory(100 Mb);
mapfile= MapMemoryToFile(memory, "\\temp\\map.tmp"); (File can be bigger, Mapping is just window)
currentWindowNumber = 0;

while(!EndOfFile)
{
  ReadFromSourceAndSort(); But only for first 100 Mb in memory
  currentWindowNumber++;
  MoveMapping(currentWindowNumber)
}

查找函数；不应使用映射（因为每次窗口切换都会保存100 Mb到硬盘并加载下一个窗口的100 Mb）。只需在100Mb的CRC64树中查找，如果找到CRC64，则表示字符串已经存储。

- Alexus

---

感谢二分搜索树的想法。我还在验证不同的方法，1）基于磁盘的Bloom过滤器（每个字符串需要1字节），2）基于磁盘的Hashset/SortedSet，基于.NET Hashset/SortedSet类，3）外部排序，4）数据库（sqlite /sql server等）。 - Shivraj