我需要从一个超大文本文件(100GB+)中删除重复的字符串。
由于内存中进行去重是不可能的,因为数据量太大,所以我尝试了布隆过滤器,但是在处理超过5000万个字符串时就没有用了。
总共有1万亿+个字符串。
我想知道解决这个问题的方法是什么。
我的初步尝试是将文件分成多个子文件,对每个文件进行排序,然后合并所有文件...
如果您有比这更好的解决方案,请告诉我,谢谢。
我需要从一个超大文本文件(100GB+)中删除重复的字符串。
由于内存中进行去重是不可能的,因为数据量太大,所以我尝试了布隆过滤器,但是在处理超过5000万个字符串时就没有用了。
总共有1万亿+个字符串。
我想知道解决这个问题的方法是什么。
我的初步尝试是将文件分成多个子文件,对每个文件进行排序,然后合并所有文件...
如果您有比这更好的解决方案,请告诉我,谢谢。
你可以创建第二个文件,其中包含记录,每个记录都是64位CRC加上字符串的偏移量,并且应该为快速搜索进行索引。 像这样:
ReadFromSourceAndSort()
{
offset=0;
while(!EOF)
{
string = ReadFromFile();
crc64 = crc64(string);
if(lookUpInCache(crc64))
{
skip;
} else {
WriteToCacheFile(crc64, offset);
WriteToOutput(string);
}
}
}
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,则表示字符串已经存储。