Delta algorithms
- 1 April 1998
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Software Engineering and Methodology
- Vol. 7 (2), 192-214
- https://doi.org/10.1145/279310.279321
Abstract
Delta algorithms compress data by encoding one file in terms of another. This type of compression is useful in a number of situations: strong multiple versions of data, displaying differences, merging changes, distributing updates, storing backups, transmitting video sequences, and others. This article studies the performance parameters of several delta algorithms, using a benchmark of over 1,300 pairs of files taken from two successive releases of GNU software. Results indicate that modern delta compression algorithms based on Ziv-Lempel techniques significantly outperform diff , a popular but older delta compressor, in terms of compression ratio. The modern compressors also correlate better with the actual difference between files without sacrificing performance.Keywords
This publication has 9 references indexed in Scilit:
- Application of splay trees to data compressionCommunications of the ACM, 1988
- A file comparison programSoftware: Practice and Experience, 1985
- Rcs — a system for version controlSoftware: Practice and Experience, 1985
- The string-to-string correction problem with block movesACM Transactions on Computer Systems, 1984
- A longest common subsequence algorithm suitable for similar text stringsActa Informatica, 1982
- A redisplay algorithmPublished by Association for Computing Machinery (ACM) ,1981
- A fast algorithm for computing longest common subsequencesCommunications of the ACM, 1977
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976
- The source code control systemIEEE Transactions on Software Engineering, 1975