A locally adaptive data compression scheme
- 1 April 1986
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 29 (4) , 320-330
- https://doi.org/10.1145/5684.5688
Abstract
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).Keywords
This publication has 16 references indexed in Scilit:
- Interval and recency rank source coding: Two on-line adaptive variable-length schemesIEEE Transactions on Information Theory, 1987
- Self-adjusting binary search treesJournal of the ACM, 1985
- Dynamic huffman codingJournal of Algorithms, 1985
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- A new data structure for representing sorted listsActa Informatica, 1982
- Hysterical B-treesInformation Processing Letters, 1981
- Variations on a theme by HuffmanIEEE Transactions on Information Theory, 1978
- Compression of individual sequences via variable-rate codingIEEE Transactions on Information Theory, 1978
- An almost optimal algorithm for unbounded searchingInformation Processing Letters, 1976
- Universal codeword sets and representations of the integersIEEE Transactions on Information Theory, 1975