A locally adaptive data compression scheme
Jon Louis Bentley, Daniel D. Sleator, Robert Endre Tarjan et al. · Communications of the ACM · 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 compressed (static Huffman coding takes two passes).
Cited by 523 works. doi:10.1145/5684.5688 Open-access PDF
Authors
References
- Information Theory and Reliable Communication.
- A Method for the Construction of Minimum-Redundancy Codes
- The Art of Computer Programming: Volume 3: Sorting and Searching
- A Discipline of Programming
- Compression of individual sequences via variable-rate coding
- Data Structures and Network Algorithms
- Amortized efficiency of list update and paging rules
- Universal codeword sets and representations of the integers
- Self-adjusting binary search trees
- Variations on a theme by Huffman