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

本文关键字：删除 字符串 文件 非常 文本 | 更新日期: 2023-09-27 18:28:31

我必须从超大的文本文件（100 Gb以上）中删除重复的字符串

由于数据的大小，内存中的重复消除是没有希望的，我尝试过bloomfilter，但除了5000万个字符串之外没有任何用处。。

字符串总数约为1万亿+

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

我最初的尝试是，将文件划分为多个子文件，对每个文件进行排序，然后将所有文件合并在一起。。。

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

谢谢。。

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

您在这里寻找的关键概念是外部排序。您应该能够使用本文中描述的技术对整个文件进行合并排序，然后依次运行以删除重复项。

如果这篇文章不够清晰，请看一下引用的实现，比如这篇。

您可以制作第二个文件，其中包含记录，每个记录都是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)
}

和函数查找；Shuld不使用映射（因为每个窗口切换都会将100Mb保存到HDD，并加载100Mb的下一个窗口）。只在CRC64的100Mb树中查找，如果CRC64找到->字符串，则已存储

相关文章：