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

Question

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

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

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

Answer 1

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

Answer 2

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

Примечания:

1. Я сохраняю хэш каждой строки для экономии места (и время, если может произойти подкачка)

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

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

4. Я импортирую 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 3

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

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

РЕДАКТИРОВАТЬ:

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

#!/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 есть difflib, который заявляет о своей конкурентоспособности с другими утилитами diff: http://docs.python.org/library/difflib.html

Answer 6

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