A locally adaptive data compression scheme

Jon Louis Bentley, Daniel D. Sleator, Robert E. Tarjan, Victor K. Wei

Research output: Contribution to journalArticlepeer-review

339 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)320-330
Number of pages11
JournalCommunications of the ACM
Volume29
Issue number4
DOIs
StatePublished - Apr 1 1986

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A locally adaptive data compression scheme'. Together they form a unique fingerprint.

Cite this