The zdelta Home Page



NOTE:

zdelta-2.1 is now available! (download here)

23.Feb.2004 - A bug is removed from the multiple reference file version of zdelta-2.1!

Modifications:
zdelta-2.0 (download here)

Modifications:


Abstract

zdelta is a general purpose lossless delta compression library developed at Polytechnic University. It is implemented by modifying the zlib 1.1.3 compression library (the modifications are marked in all of the original zlib 1.1.3 files). With its version 2.0, however, the library has significantly deviated from zlib, though it still uses a lot of the zlib code and structure. The zdelta algorithm was designed by Nasir Memon, Torsten Suel, and Dimitre Trendafilov, and implemented by Dimitre Trendafilov. The work on the library was supported by a grant from Intel Corporation. Torsten Suel was also supported by NSF CAREER Award NSF CCR-0093400.

Applications

The possible applications for zdelta include: or many other applications involving sets of similar files or different versions of a file.

Characteristics

The initial motivation for developing zdelta was the need for a utility that efficiently generates deltas of HTML pages. The library, however, is more general and could be successfully applied on files with any structure and any size. zdelta shares many of the zlib characteristics: However, there are also some differences: For more details visit the list of FAQ and the library online manual. Please note that this software is provided as is, with absolutely no express or implied warranty.

Algorithm

The zdelta algorithm is a variation of LZ77 (Lempel-Ziv 1977). The target data is compressed by finding duplicated strings in the already compressed data or in the explicitly provided reference data. Note that zdelta differs from applying zlib with a dictionary!
A complete description of zdelta-1.0 algorithm is given in the article zdelta: an Efficient Delta Compression Tool available here.
An article on zdelta-2.0 will be available soon.

Source and Executables

The complete zdelta sources are available here.

Experimental Results and Benchmark Data

zdelta was tested on the following benchmarks:
Note: All experiments were run by compressing each individual file from the target data set in relation to the corresponding file in the reference data set. Compressing large files, like large tar files, is still an active research. The following experiments were run only with zdelta-2.0. The purpose of those experiments was to test zdelta, and also to explore potential applications for delta compression in general.
The experimental results for zdelta-2.0 are available here.

The experimental results for zdelta-1.0 are available here.
For more information on the conducted experiments refer to the results section of zdelta: an Efficient Delta Compression Tool.

The Perl scripts used for the experiments are available here.


Copyright © Dimitre Trendafilov 2002.
dtrend01@utopia.poly.edu