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
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).