Quickly find differences between two large text files

Question

I have two 3GB text files, each file has around 80 million lines. And they share 99.9% identical lines (file A has 60,000 unique lines, file B has 80,000 unique lines).

How can I quickly find those unique lines in two files? Is there any ready-to-use command line tools for this? I'm using Python but I guess it's less possible to find a efficient Pythonic method to load the files and compare.

Any suggestions are appreciated.

Solution 1

If order matters, try the comm utility. If order doesn't matter, sort file1 file2 | uniq -u.

Solution 2

I think this is the fastest method (whether it's in Python or another language shouldn't matter too much IMO).

Notes:

1.I only store each line's hash to save space (and time if paging might occur)

2.Because of the above, I only print out line numbers; if you need actual lines, you'd just need to read the files in again

3.I assume that the hash function results in no conflicts. This is nearly, but not perfectly, certain.

4.I import hashlib because the built-in hash() function is too short to avoid conflicts.

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]

Solution 3

With 60,000 or 80,000 unique lines you could just create a dictionary for each unique line, mapping it to a number. mydict["hello world"] => 1, etc. If your average line is around 40-80 characters this will be in the neighborhood of 10 MB of memory.

Then read each file, converting it to an array of numbers via the dictionary. Those will fit easily in memory (2 files of 8 bytes * 3GB / 60k lines is less than 1 MB of memory). Then diff the lists. You could invert the dictionary and use it to print out the text of the lines that differ.

EDIT:

In response to your comment, here's a sample script that assigns numbers to unique lines as it reads from a file.

#!/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

Comments

[bstpierre]

How will sorting two 3G files be faster than diff?

[Blemone]

@Harold L, I'm confused. How can I map 60,000 or 80,000 unique lines to a dictionary before knowing what lines are contained in both files.

[Harold L]

You can just build the dictionary as you read the files. I'll add code for a helper function above.

[Asaf]

Can this lib handle 3gb text files?! Even good databases have hard time with this kind of task... They need indexing and other optimization to get the result in reasonable time.

[tonfa]

@bstpierre: a diff implementation is usually quadratic, while sort is usually n log n in the average case (quicksort).

[Tony Veijalainen]

Looks good answer for me, I would only suggest to save the seek position of each line while reading to recover them for result quickly.

[Tony Veijalainen]

As the lines are in random order and there is not need to find the changes of lines, probably not best approach. Would be appropriate if two files are versions of same file (was possibility because of high similarity in lines between them).

[Tony Veijalainen]

dict.keys() with 3 GB? I do not believe that you can save hash only with seff.dict[line] but it saves the whole line in keys + hashes.

[Harold L]

@Tony Veijalainen, Yes, the dict will save the whole lines, but it will only save each line once. So this technique works well here only because Jack has many duplicate lines: 3GB might be 100 million lines of text, say, but only 80,000 unique lines will be stored in the dictionary's key set.

[Tony Veijalainen]

"There are no repeated lines in both files". See the poster's comment to his post in answer to me. Maybe I do not understand his English properly.

[max]

Unfortunately, based on the clarification from OP (in response to Tony), the original files do not have repeated lines. The "99.9% identical lines" only refers to the fact that each of those lines is present in both files. With that clarification, your approach won't work, unfortunately.