Tunstall coding
Tunstall coding maps variable-length source phrases to fixed-width indices using a probability-based dictionary.
Construction: Start with one leaf per source symbol, then expand the most probable leaf into all symbol extensions while the index budget allows. The leaves form a complete prefix-free phrase dictionary. [1]
Objective: For a known memoryless source and fixed index width, the classical construction maximizes expected phrase length. A two-bit example with P(A)=3/4 has phrases AAA, AAB, AB and B. Its mean length is 37/16 symbols, so its long-stream payload rate is 32/37 bit per symbol, not the phrase-average rate 17/16. [2] [3]
Boundaries: Fixed-width indices can be decoded individually with the correct dictionary and alignment. They do not locate arbitrary uncompressed offsets or prove integrity. In the example, input AA leaves an incomplete phrase requiring a termination rule. [3]
Implementation: A binary memoryless source permits two FIFO queues for leaf selection. Comparing their heads avoids scanning all leaves at every split. Sources with memory need different modelling; classical optimality does not transfer automatically. [2]
Relations
- related
- Huffman coding, Lossless compression, Compression dictionary, Comma-free code, Entropy coding
Limitations
- Dictionary storage, framing and the final partial phrase affect finite-file size; a favourable model rate does not guarantee that every file shrinks. [3]
Citations
- Drmota, Reznik, Savari and Szpankowski: Precise Asymptotic Analysis of the Tunstall Code, ISIT 2006, sections I-II
- Baer: Efficient Implementation of the Generalized Tunstall Code Generation Algorithm, ISIT 2009, sections I-III, arXiv v3
- Hesela: exact Tunstall phrase dictionaries, coding-rate denominators and finite-tail controls
Sources & caveats
- Source synthesis and exact hypothetical arithmetic, not a measured compression ratio or a finite-file codec.
- The ISIT 2006 paper and Baer's 2009 v3 paper were read. Arimura's 2010 work was consulted at abstract level only; the numerical contrast is independently calculated.