A Locally Adaptive Data Compression Scheme

J. L. Bentley, D. D. Sleator, R. E. Tarjan, V. K. Wei, A Locally Adaptive Data Compression Scheme, Communications of the ACM-Vol. 29, No. 4, 1986

Full Text (PDF)


A data compression scheme that exploits locality of reference, such as occurs when words are used
frequently over short intervals and then fall into long periods of disuse, is described. The scheme is based on a
simple heuristic for self-organizing sequential search and on variable-length encodings of integers. We prove that it
never performs much worse than Huffman coding and can perform substantially better; experiments on real files
show that its performance is usually quite close to that of Huffman coding. Our scheme has many implementation
advantages: it is simple, allows fast encoding and decoding, and requires only one pass over the data to be com-
pressed (static Huffman coding takes huo passes).

Daniel Sleator: Email, Home Page, Papers
Last modified: Sat Jan 21 07:15:44 EST 2006