Delta encoding


Delta encoding is a way of storing or transmitting data in the form of differences between sequential data rather than complete files; more generally this is known as data differencing. Delta encoding is sometimes called delta compression, particularly where archival histories of changes are required.
The differences are recorded in discrete files called "deltas" or "diffs". In situations where differences are small – for example, the change of a few words in a large document or the change of a few records in a large table – delta encoding greatly reduces data redundancy. Collections of unique deltas are substantially more space-efficient than their non-encoded equivalents.
From a logical point of view the difference between two data values is the information required to obtain one value from the other – see relative entropy. The difference between identical values is often called 0 or the neutral element.

Simple example

Perhaps the simplest example is storing values of bytes as differences between sequential values, rather than the values themselves. So, instead of 2, 4, 6, 9, 7, we would store 2, 2, 2, 3, −2. This reduces the variance of the values when neighbor samples are correlated, enabling a lower bit usage for the same data. IFF 8SVX sound format applies this encoding to raw sound data before applying compression to it. Unfortunately, not even all 8-bit sound samples compress better when delta encoded, and the usability of delta encoding is even smaller for 16-bit and better samples. Therefore, compression algorithms often choose to delta encode only when the compression is better than without. However, in video compression, delta frames can considerably reduce frame size and are used in virtually every video compression codec.

Definition

A delta can be defined in 2 ways, symmetric delta and directed delta. A symmetric delta can be expressed as
where and represent two versions.
A directed delta, also called a change, is a sequence of change operations which, when applied to one version, yields another version . In computer implementations, they typically take the form of a language with two commands: copy data from v1 and write literal data.

Variants

A variation of delta encoding which encodes differences between the prefixes or suffixes of strings is called incremental encoding. It is particularly effective for sorted lists with small differences between strings, such as a list of words from a dictionary.

Implementation issues

The nature of the data to be encoded influences the effectiveness of a particular compression algorithm.
Delta encoding performs best when data has small or constant variation; for an unsorted data set, there may be little to no compression possible with this method.
In delta encoded transmission over a network where only a single copy of the file is available at each end of the communication channel, special error control codes are used to detect which parts of the file have changed since its previous version.
For example, rsync uses a rolling checksum algorithm based on Mark Adler's adler-32 checksum.

Sample C code

The following C code performs a simple form of delta encoding and decoding on a sequence of characters:

void delta_encode
void delta_decode

Examples

Delta encoding in HTTP

Another instance of use of delta encoding is RFC 3229, "Delta encoding in HTTP", which proposes that HTTP servers should be able to send updated Web pages in the form of differences between versions, which should decrease Internet traffic, as most pages change slowly over time, rather than being completely rewritten repeatedly:
The suggested rsync-based framework was implemented in the rproxy system as a pair of HTTP proxies. Like the basic vcdiff-based implementation, both systems are rarely used.

Delta copying

Delta copying is a fast way of copying a file that is partially changed, when a previous version is present on the destination location. With delta copying, only the changed part of a file is copied. It is usually used in backup or file copying software, often to save bandwidth when copying between computers over a private network or the internet. One notable open-source example is rsync.

Online backup

Many of the online backup services adopt this methodology, often known simply as deltas, in order to give their users previous versions of the same file from previous backups. This reduces associated costs, not only in the amount of data that has to be stored as differing versions, but also those costs in the uploading of each file that has been updated.

Delta updates

For large software packages, there is usually little data changed between versions. Many vendors choose to use delta transfers to save time and bandwidth.

Diff

Diff is a file comparison program, which is mainly used for text files. By default, it generates symmetric deltas that are reversible. Two formats used for software patches, context and unified, provides additional context lines that allow for tolerating shifts in line number.

Git

The Git source code control system employs delta compression in an auxiliary "" operation. Objects in the repository that have not yet been delta-compressed are compared against a heuristically chosen subset of all other objects, and the common data and differences are concatenated into a "pack file" which is then compressed using conventional methods. In common use cases, where source or data files are changed incrementally between commits, this can result in significant space savings. The repack operation is typically performed as part of the "" process, which is triggered automatically when the numbers of loose objects or pack files exceed configured thresholds.
The format is documented in the pack-format page of the git documentation. It implements a directed delta.

VCDIFF

One general format for directed delta encoding is VCDIFF, described in RFC 3284. Free software implementations include Xdelta and open-vcdiff.

GDIFF

Generic Diff Format is another directed delta encoding format. It was submitted to W3C in 1997. In many cases, VCDIFF has better compression rate than GDIFF.

bsdiff

Bsdiff is a binary diff program using suffix sorting. For executables that contain many changes in pointer addresses, it performs better than VCDIFF-type "copy and literal" encodings. The intent is to find a way to generate a small diff without needing to parse assembly code. Bsdiff achieve this by allowing "copy" matches with errors, which are then corrected using an extra "add" array of bytewise differences. Since this array is mostly either zero or repeated values for offset changes, it takes up little space after compression.
Bsdiff is useful for delta updates. Google uses bsdiff in Chromium and Android. The deltarpm feature of the RPM Package Manager is based on a heavily-modified bsdiff that can use a hash table for matching. FreeBSD also uses bsdiff for updates.
Since the 4.3 release of bsdiff in 2005, various improvements or fixes have been produced for it. Google maintains multiple versions of the code for each of its products. FreeBSD takes many of Google's compatible changes, mainly a vulnerbility fix and a switch to the faster suffix-sorting routine. Debian has a series of performance tweaks to the program.
ddelta is a rewrite of bsdiff proposed for use in Debian's delta updates. Among other efficiency improvements, it uses a sliding window to reduce memory and CPU cost.