1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Can you define your problem more formally? I don't understand it. $\endgroup$ – Yuval Filmus Jun 12 at 20:30
  • $\begingroup$ @YuvalFilmus, which part are you confused about? $\endgroup$ – TheOne Jun 12 at 20:31
  • 2
    $\begingroup$ The definition of the problem. What is the input, and what is the required output? $\endgroup$ – Yuval Filmus Jun 12 at 20:32
  • 1
    $\begingroup$ 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? $\endgroup$ – greybeard Jun 13 at 1:45
  • $\begingroup$ 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. $\endgroup$ – greybeard Jun 13 at 1:47
0
$\begingroup$

Implying that they have usual line length (10-100 chars on average), I will sort both files. It can be done almost in-place using technique Fast, stable, almost in-place radix and merge sorts

$\endgroup$
0
$\begingroup$

Finding the longest common subsequence (LCS) is quite a famous problem in computer science (and applications to e.g. biology, in comparing gene sequences). See for instance Bergroth, Hakonen and Raita, "A Survey of Longest Common Subsequence Algorithms", Proc. Intl. Symposium on String Processing and Information Retrieval (2000), pp 39-48 (DOI 10.1109/SPIRE.2000.878178). The algorithm in common use is by Myers, "An O(N D) Difference Algorithm and Its Variations", Algorithmica 1:1-4 (1986), pp. 251-266 (DOI 10.1007/BF01840446, find it at http://www.xmailserver.org/diff2.pdf), the one by Wu, Manber, Myers and Miller "An O(N P) Sequence Comparison Algorithm", Information Procession Letters 35:6 (1990), pp. 317-323 (DOI 10.1016/0020-0190(90)90035-V, find it at https://publications.mpi-cbg.de/Wu_1990_6334.pdf) should be somewhat faster.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.