# How do you write a diff algorithm given limited amount of RAM?

Say you have two large files (100 TB each) and only 1 MB of RAM. What's an efficient algorithm that will print the missing lines (diff)? The files don't necessarily contain duplicates.

The two files are not sorted and could have different ordering in both files.

e.g.:

File1  File2
A      B
B      A
C      C
D      E
F      D
F

Output:
File 2: E


The input are two large files (containing strings).

The output is a list of strings telling you the presence of a line in File X and not in File Y.

• Can you define your problem more formally? I don't understand it. – Yuval Filmus Jun 12 at 20:30
• @YuvalFilmus, which part are you confused about? – TheOne Jun 12 at 20:31
• The definition of the problem. What is the input, and what is the required output? – Yuval Filmus Jun 12 at 20:32
• The files don't necessarily contain duplicates String/line A in both X and Y (inter-file duplicates - the output would be huge) or more than once in one file (internal)? list of strings telling you the presence of a line in File X and not in File Y Any requirement on the order of reports? From the "example", a report doesn't need to show the position of occurrence. In case there are internal duplicates: one report, or as many as there are occurrences of the same line? – greybeard Jun 13 at 1:45
• Assuming a "line" length of about 100, there are on the order of $2^{40}$ lines in each file, and alphabet size is not a problem. There have been diff implementations using non-cryptographic digests, you'd need about 10 bytes here to keep collisions low and about 7 to tell a position in one of the files: reduces the size problem by no more than a factor of six incurring a time penalty. – greybeard Jun 13 at 1:47