Удалить дубликаты строк из очень большого текстового файла - PullRequest
Новая
       1

Удалить дубликаты строк из очень большого текстового файла

15 голосов
/ 22 марта 2012

Я должен удалить дублирующиеся строки из очень большого текстового файла (100 Гб +)

Поскольку удаление дубликатов в памяти безнадежно из-за размера данных, я пробовал bloomfilter, но бесполезно, за исключением 50 миллионов строк

всего строки равны 1 триллиону +

Я хочу знать, как решить эту проблему ..

Моя первоначальная попытка состоит в том, чтобы разделить файл на количество вложенных файлов, отсортировать каждый файл и затем объединить все файлы вместе ...

Если у вас есть лучшее решение, чем это, пожалуйста, дайте мне знать,

Спасибо ..

Ответы [ 2 ]

3 голосов
/ 22 марта 2012

Ключевой концепцией, которую вы ищете здесь, является внешняя сортировка .Вы должны иметь возможность объединить сортировку всего файла, используя методы, описанные в этой статье, а затем последовательно выполнить его, чтобы удалить дубликаты.

Если статья недостаточно ясна, взгляните на ссылочные реализации, такие как это .

1 голос
/ 22 марта 2012

Вы можете сделать второй файл, который содержит записи, каждая запись является 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 МБ на жесткий диск и загружает 100 МБ следующего окна).Просто ищет в 100 Мб деревьях CRC64, и если CRC64 найден -> строка уже сохранена

...