A technique for isolating differences between files

ABSTRACT

A simple algorithm is described for isolating the differences between two files. One application is the comparing of two versions of a source program or other file in order to display all differences. The algorithm isolates differences in a way that corresponds closely to our intuitive notion of difference, is easy to implement, and is computationally efficient, with time linear in the file length. For most applications the algorithm isolates differences similar to those isolated by the longest common subsequence. Another application of this algorithm merges files containing independently generated changes into a single file. The algorithm can also be used to generate efficient encodings of a file in the form of the differences between itself and a given “datum” file, permitting reconstruction of the original file from the diference and datum files.

REFERENCES

• 1: J. D. Ullman , A. V. Aho , D. S. Hirschberg, Bounds on the Complexity of the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.23 n.1, p.1-12, Jan. 1976 [doi>10.1145/321921.321922]
• 2: L. Peter Deutsch , Butler W. Lampson, An online editor, Communications of the ACM, v.10 n.12, p.793-799, Dec. 1967 [doi>10.1145/363848.363863]
• 3: Digital Equipment Corp. DEC System 10 Assembly Language Handbook, 3d ed., 1972, pp. 931-942.
• 4: Roger Fajman , John Borgelt, WYLBUR: an interactive text editing and remote job entry system, Communications of the ACM, v.16 n.5, p.314-322, May 1973 [doi>10.1145/362041.362234]
• 5: Heckel, P. A technique for isolating differences between files. Tech. Pub. 73, Interactive Systems Consultants, Palo Alto, Calif.
• 6: D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
• 7: Hunt, J., and McIlroy, M. An algorithm for differential file comparison. Compt. Sci. Techn. Rep. 41, Bell Telephone Labs, Murray Hill, N.J., Aug. 1976.
• 8: IBM Corp. IBM Virtual Machine Facility/370 Command Language Guide for General Users, Release 2,225-226.1 (UPDATE).
• 9: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 10: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.1 Office Automation
          Subjects: Word processing

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING

General Terms:
Algorithms, Design, Documentation, Management, Performance

Keywords:
bandwidth compression, difference isolation, file comparison, file compression, hashcoding, longest common subsequence, molecular evolution, program maintenance, text editing, word processing