Delta encoding

Delta encoding is a way of storing data in form of differences (deltas) between sequential data rather then data themselves. It is sometimes called delta compression because some instances of the encoding can make encoded data shorter then non-encoded data.

Perhaps the simplest example is storing values of bytes as differences (deltas) between sequential values, rather then the values themselves. So, instead of 2,4,6,9,7 we would store 2,2,2,3,-2. This is not very useful when used alone, but it can help further compression of data in which sequential values occur oftenly. 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.

Example algorhitms for this encoding:

void delta_encode(char *buffer,int length)
{
  char t;
  int i;

  t=0;
  for(i=0;i
void delta_decode(char *buffer,int length)
{
  char t;
  int i;

  t=0;
  for(i=0;i

As another example, entries in a dictionary can be stored in such a way. Consider the following word list (abbreviations and names are not in the list for the sake of simplicity), on the left stored normally and on the right in form "#letters" where '#' is the number of letters that should be substracted from previous word and 'letters' are letters that are to be added to the so created base in order to form the next word:

a
aardvark
aardwolf
abaca
abaciscus
aback
abacus
abaft
abandon
abandoned
abandonee
abandonment
abase
abasement
abash
0a
0ardvark
4wolf
7baca
1iscus
5k
1us
3ft
2ndon
0ed
1e
2ment
7se
0ment
5sh

As could be seen, list of word deltas is much shorter. But it would probably be longer for unsorted list of words!

RFC 3229 - Delta encoding in HTTP proposes that HTTP should be able to send updated Web pages in form of differences between versions (deltas), which should decrease Internet traffic, as most pages change slowly over time, rather then being completely overwritten repeatedly:

This document describes how delta encoding can be supported as a compatible extension to HTTP/1.1.

Many HTTP (Hypertext Transport Protocol) requests cause the retrieval of slightly modified instances of resources for which the client already has a cache entry. Research has shown that such modifying updates are frequent, and that the modifications are typically much smaller than the actual entity. In such cases, HTTP would make more efficient use of network bandwidth if it could transfer a minimal description of the changes, rather than the entire new instance of the resource. This is called "delta encoding."

Does Wikipedia store page revisions in forms of differences between revisions? If so, that is also an instance of Delta encoding. If not, perhaps it should.