A file comparison program

1 November 1985

journal article
research article
Published by Wiley in Software: Practice and Experience

Vol. 15 (11) , 1025-1040
https://doi.org/10.1002/spe.4380151102

Abstract

This paper presents a simple method for computing a shortest sequence of insertion and deletion commands that converts one given file to another. The method is particularly efficient when the difference between the two files is small compared to the files' lengths. In experiments performed on typical files, the program often ran four times faster than the UNIX diff command.

Keywords

This publication has 11 references indexed in Scilit:

Rcs — a system for version control
Software: Practice and Experience, 1985
The string-to-string correction problem with block moves
ACM Transactions on Computer Systems, 1984
A longest common subsequence algorithm suitable for similar text strings
Acta Informatica, 1982
A redisplay algorithm
ACM SIGPLAN Notices, 1981
Approximate String Matching
ACM Computing Surveys, 1980
A fast algorithm for computing longest common subsequences
Communications of the ACM, 1977
Optimal Code Generation for Expression Trees
Journal of the ACM, 1976
Bounds on the Complexity of the Longest Common Subsequence Problem
Journal of the ACM, 1976
A linear space algorithm for computing maximal common subsequences
Communications of the ACM, 1975
The String-to-String Correction Problem
Journal of the ACM, 1974