Быстро найти различия между двумя большими текстовыми файлами

Question

У меня есть два текстовых файла 3GB, каждый файл имеет около 80 миллионов строк. И они имеют 99,9% идентичных строк (файл A имеет 60 000 уникальных строк, файл B содержит 80 000 уникальных строк).

Как я могу быстро найти эти уникальные строки в двух файлах? Есть ли готовые к использованию средства командной строки для этого? Я использую Python, но я думаю, что найти эффективный метод Pythonic для загрузки файлов и сравнения можно.

Любые предложения приветствуются.

Answer 1

Если у вас есть вопросы, попробуйте утилиту comm. Если заказ не имеет значения, sort file1 file2 | uniq -u.

Answer 2

http://www.emeditor.com/ может обрабатывать большие файлы, а также сравнивать их.

Answer 3

С 60 000 или 80 000 уникальными строками вы можете просто создать словарь для каждой уникальной строки, сопоставляя его с числом. mydict["hello world"] => 1 и т. Д. Если ваша средняя строка составляет около 40-80 символов, это будет около 10 МБ памяти.

Затем прочитайте каждый файл, преобразуя его в массив чисел через словарь. Они будут легко вписываться в память (2 файла из 8 байтов * 3 ГБ/60 тыс. Строк меньше 1 МБ памяти). Затем разберите списки. Вы можете использовать invert the dictionary и использовать его для распечатки текста строк, которые отличаются.

EDIT:

В ответ на ваш комментарий, вот пример сценария, который присваивает номера уникальных линий, как он читает из файла.

#!/usr/bin/python 

class Reader: 

    def __init__(self, file): 
     self.count = 0 
     self.dict = {} 
     self.file = file 

    def readline(self): 
     line = self.file.readline() 
     if not line: 
      return None 
     if self.dict.has_key(line): 
      return self.dict[line] 
     else: 
      self.count = self.count + 1 
      self.dict[line] = self.count 
      return self.count 

if __name__ == '__main__': 
    print "Type Ctrl-D to quit." 
    import sys 
    r = Reader(sys.stdin) 
    result = 'ignore' 
    while result: 
     result = r.readline() 
     print result 

Answer 4

Если я правильно понял, вам нужны строки этих файлов без дубликатов. Это делает работу:

uniqA = set(open('fileA', 'r')) 

Answer 5

Я думаю, что это самый быстрый способ (будь то в Python или другой язык, вопрос не должен иметь слишком много ИМО).

Примечание:

1.I только хранить хэш каждой строки, чтобы сэкономить место (и время, если может произойти пейджинг)

2.Because вышеперечисленного, я печатаю только номера строк; если вам нужны реальные строки, вам просто нужно будет снова прочитать файлы

3. Я предполагаю, что хеш-функция не вызывает конфликтов. Это почти, но не совсем точно.

4.I import hashlib потому что встроенная функция hash() слишком короткая, чтобы избежать конфликтов.

import sys 
import hashlib 

file = [] 
lines = [] 
for i in range(2): 
    # open the files named in the command line 
    file.append(open(sys.argv[1+i], 'r')) 
    # stores the hash value and the line number for each line in file i 
    lines.append({}) 
    # assuming you like counting lines starting with 1 
    counter = 1 
    while 1: 
     # assuming default encoding is sufficient to handle the input file 
     line = file[i].readline().encode() 
     if not line: break 
     hashcode = hashlib.sha512(line).hexdigest() 
     lines[i][hashcode] = sys.argv[1+i]+': '+str(counter) 
     counter += 1 
unique0 = lines[0].keys() - lines[1].keys() 
unique1 = lines[1].keys() - lines[0].keys() 
result = [lines[0][x] for x in unique0] + [lines[1][x] for x in unique1] 

Answer 6

Python имеет difflib, который утверждает, что вполне конкурентоспособен с другими дифф утилитами см: http://docs.python.org/library/difflib.html