home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d1xx / d142 / diff.lha / Diff / tech.doc < prev    next >
Text File  |  1988-05-22  |  8KB  |  290 lines
  1.  
  2.  
  3. Jan 13 13:00 1988  DIFF.MEM Page 1
  4.  
  5.  
  6.  
  7.      Diff maintains all information needed to compare the two files in
  8.      main memory. This means that very large files (or fairly large
  9.      files with many differences) will cause the program to abort with
  10.      an "out of space" error. Main memory requirements (in words) are
  11.      approximately:
  12.  
  13.       2 * (length of file1 + length of file2) + (3 * number of changes)
  14.  
  15.      The diff algorithm reads each file twice (once to build hash
  16.      tables and a second time to check for fortuitous matches), then
  17.      reads the differences by seeking randomly within the files. CPU
  18.      time requirements include sorting the two hash vectors and
  19.      randomly searching memory tables for equivalence classes. For
  20.      example, running in Vax compatibility mode, two 1000 line files
  21.      with a fair number of differences took about 25 seconds (elapsed
  22.      wall clock time) for processing. Most of this time was spent in
  23.      the file read routines. This test required slightly more than
  24.      6000 words of memory for internal tables.
  25.  
  26.      The diff algorithm was developed by J. W. Hunt and M. D. McIlroy,
  27.      using a central algorithm defined by H. S. Stone. The algorithm
  28.      was described in:
  29.  
  30.           Hunt, J. W., and McIlroy, M. D.,
  31.           An Algorithm for Differential File Comparison,
  32.           Computing Science Technical Report #41,
  33.           Bell Laboratories, Murray Hill, NJ  07974
  34.  
  35.      The following description is summarized from that document. While
  36.      it has been slightly modified to correspond to the program
  37.      source, the algorithm is essentially identical.
  38.  
  39.      1. Read the input files, building two vectors containing the line
  40.      number (serial) and hash value (hash) of each line. Data for
  41.      fileA will be in a vector pointed to by fileA[], while data for
  42.      fileB will be pointed to by fileB[]. The lengths (number of
  43.      lines) of the files will be represented by lenA and lenB
  44.      respectively. [This is slightly different from the published
  45.      algorithm.]
  46.  
  47.      2. Note initial and final sequences that have identical hash
  48.      values to shorten subsequent processing. Note that the "jackpot"
  49.      phase (step 9.) will examine all lines in the file. Next, sort
  50.      each file using hash as the primary key and serial as the
  51.      secondary key.
  52.  
  53.      3. Construct an array of equivalence classes (member[1..lenB])
  54.      where each element contains the line number in fileB and a flag
  55.      which is True if the indicated line is the first member of an
  56.      equivalence class. (An equivalence class is a set of lines which
  57.      all hash to the same value. The lines themselves are not
  58.      necessarily identical.)
  59.  
  60.      4. Construct an array, class[1..lenA], where each element, I, is
  61.      set to the index of a line, J, in fileB if member[J] is the first
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69. Jan 13 13:00 1988  DIFF.MEM Page 2
  70.  
  71.  
  72.      element in an equivalence class and the hash code of line[I] in
  73.      fileA is the same as the hash code of line[J] in fileB. Class[I]
  74.      is set to zero if no such line exists.
  75.  
  76.      If non-zero, class[I] now points in member[] to the beginning of
  77.      the class of lines in fileB equivalent to line[I] in fileA.
  78.  
  79.      The next two steps implement the longest common subsequence
  80.      algorithm.
  81.  
  82.      5. Structure CANDIDATE { a, b, previous }, where a and b are line
  83.      numbers and previous a reference to a candidate, will store
  84.      candidate lists as they are constructed.
  85.  
  86.      Vector clist[] stores references to candidates. It is dimensioned
  87.      (0..min(lenA, lenB) + 1)
  88.  
  89.       Initialize
  90.           clist[0] = CANDIDATE {   0,   0, -1 };
  91.           clist[1] = CANDIDATE { A+1, B+1, -1 };
  92.           ktop = 1;
  93.  
  94.      clist[1] is a fence beyond the last usefully filled element and
  95.      -1 is an out-of-range clist index. Ktop is the index of the
  96.      fence. Note, because of the memory allocation used, clist[] is
  97.      actually composed of two vectors, clist[] containing the
  98.      candidate reference, and klist[] containing pointers to clist.
  99.  
  100.      6.  For (A = 1 to lenA) {
  101.           I = class[A];  -- the index in member[]:  beginning of
  102.                 -- the class of lines in fileB equivalent
  103.                 -- to this line in fileA.
  104.           if (I is non-zero) {
  105.             Merge each member into the candidate list
  106.             as discussed below.
  107.           }
  108.  
  109.      Unravel the chain of candidates, getting a vector of common
  110.      subsequences:
  111.  
  112.      7.  Set all elements of match[0..lenA] to zero.
  113.  
  114.      8. clist[ktop-1] points to the subsequence chain head. For each
  115.      element in the chain, let A and B be the line number entries.
  116.      Then, set
  117.  
  118.           match[A] = B;
  119.  
  120.      The non-zero elements of match[] now pick out a longest common
  121.      subsequence chain, possibly including spurious matches due to
  122.      hash coincidences. The pairings between the two files are:
  123.  
  124.       if (match[A] is non-zero) {
  125.           line A in fileA matches line match[A] in fileB;
  126.       }
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135. Jan 13 13:00 1988  DIFF.MEM Page 3
  136.  
  137.  
  138.      Now, read each line of fileA and fileB to check for jackpots:
  139.  
  140.      9.  for (A = 1 to lenA) {
  141.           if (match[A] is nonzero) {
  142.             if (fileA[A] is not identical to fileB[match[A]])
  143.                 match[A] = 0;  -- Hash congruence
  144.           }
  145.       }
  146.  
  147.      Ignoring "squish" complications, the merge step may be defined as
  148.      follows:
  149.  
  150.       Entry:
  151.           clist[]      Candidate pointer array
  152.           ktop      Fence beyond last filled index
  153.           A      Current index in fileA
  154.           member[]  Equivalence vector
  155.           I      The index in member[] of the first element
  156.                   of the class of lines in fileB that are
  157.                   equivalent to line[A] in fileA.
  158.  
  159.      1. Let clist[R] be "an r-candidate" and C a reference to the last
  160.      candidate found, which will always be an r-candidate. clist[R]
  161.      will be updated with this reference once the previous value of
  162.      clist[R] is no longer needed. Initialize:
  163.  
  164.          R = 0; C = clist[0];
  165.  
  166.      2.  Do steps 3 through 6 repeatedly:
  167.  
  168.      3. set B to the line number in member[I]; search clist[R..ktop]
  169.      for an element, clist[S], such that
  170.  
  171.           clist[S-1].b < B and clist[S].b >= B
  172.  
  173.      Note that clist[] is ordered on clist[].b so that binary search
  174.      will work. The search algorithm used requires the two "fence"
  175.      entries described above.
  176.  
  177.      If such an element is found, perform steps 4. and 5.
  178.  
  179.      4. Extend the longest common subsequence chain:
  180.  
  181.           If (clist[S].b > B) {
  182.             clist[R] = C;
  183.             R = S;
  184.             C = candidate(A, B, clist[S - 1]);
  185.           }
  186.  
  187.      5. Extend the number of subsequences, moving the fence:
  188.  
  189.           If (S == ktop) {
  190.             clist[ktop + 1] = clist[ktop]
  191.             ktop = ktop + 1;
  192.             break out of step 2's loop;
  193.           }
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201. Jan 13 13:00 1988  DIFF.MEM Page 4
  202.  
  203.  
  204.  
  205.       6.  I = I + 1;
  206.           if (member[I] is the first element in another class) {
  207.               break out of step 2's loop;
  208.            }
  209.           else {
  210.               continue at step 2.
  211.            }
  212.  
  213.      7. clist[R] = C; exit merge subroutine.
  214.  
  215.      To illustrate vector contents, here is a sample run:
  216.  
  217.      File A:
  218.       line 1
  219.       line 2
  220.       line 3
  221.       line 4
  222.       line 5 gets deleted
  223.       line 6
  224.  
  225.      File B:
  226.       line 1
  227.       line 1.5 inserted
  228.       line 2
  229.       line 3 changed
  230.       line 4
  231.       line 6
  232.  
  233.      (For clarity, the "squish" step is omitted from the following)
  234.  
  235.      On entry to equiv() (after readin and sorting), the file[] vector
  236.      is as follows (the first entry in each pair is the line number,
  237.      the second is the hash value. Entries are sorted on hash value):
  238.  
  239.      FileA[] (1..lines in fileA):
  240.        line   hash
  241.       3 042400  6 043300  5 050026  1 102201  2 102701  4 103501
  242.      FileB[] (1..lines in fileB):
  243.       6 043300  2 045600  1 102201  3 102701  5 103501  4 147166
  244.  
  245.  
  246.      After Equiv has processed file[]:
  247.  
  248.      FileA[] (1..lines in fileA):
  249.        line value
  250.       3 0  6 1  5 0  1 3  2 4  4 5
  251.      Member[] (0..lines in fileB)
  252.       0  -6  -2  -1  -3  -5  -4
  253.  
  254.      After unsort() has unwound fileB:
  255.  
  256.      Class[] (1 .. lines in fileA):
  257.       3   4  0  5  0  1
  258.  
  259.      Within unravel(), match is built in the following order:
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267. Jan 13 13:00 1988  DIFF.MEM Page 5
  268.  
  269.  
  270.  
  271.       match[6] := 6
  272.       match[4] := 5
  273.       match[2] := 3
  274.       match[1] := 1
  275.  
  276.      Match[] (0 .. lines in fileA):
  277.  
  278.        0  1  3  0  5  0  6
  279.  
  280.      Output is as follows:
  281.  
  282.       1a2
  283.       > line 1.5 inserted
  284.       3c4
  285.       < line 3
  286.       ---
  287.       > line 3 changed
  288.       5d5
  289.       < line 5 gets deleted
  290.