Is Tunstall coding lossless?

Yes, when the dictionary, parsing and message-framing rules allow the decoder to reproduce the input exactly.

How does it differ from basic Huffman coding?

Basic symbol Huffman coding uses fixed-size input symbols and variable-length output words. Tunstall coding uses variable-length input phrases and fixed-length output words.

Does a larger dictionary always improve the whole system?

It can improve modeled coding efficiency, but requires more memory and may add overhead or implementation cost. Evaluate the complete tradeoff.

AI Glossary / MLOps and deployment / Intermediate

Tunstall coding

Definition

Tunstall coding is a lossless variable-to-fixed-length coding method. It parses an input stream into dictionary phrases of different lengths and represents each phrase with a fixed-length codeword. For a memoryless source with known probabilities, its dictionary construction maximizes average phrase length within the standard complete prefix-dictionary constraints.

What it means

Many familiar codes give individual source symbols different output lengths. Tunstall coding reverses that arrangement: input phrases vary in length, while their output identifiers all occupy the same number of bits. Frequent patterns can be represented as longer phrases without requiring longer identifiers.

This can make output decoding convenient because codeword boundaries are regular. However, each identifier may expand into a different number of source symbols. Fixed output width therefore does not mean every codeword represents the same duration, number of events or amount of original data.

How it works

Begin with a tree whose leaves represent individual source symbols and carry their probabilities. Repeatedly choose the most probable leaf and replace it with children formed by appending each possible source symbol. Continue while the dictionary remains within the available codeword capacity.

The resulting leaves are dictionary phrases. Because no leaf phrase is a prefix of another, the encoder can read input symbols until it reaches a leaf and then emit that phrase's fixed-width identifier. The decoder maps identifiers back to phrases and concatenates them.

For the standard memoryless model, a phrase probability is the product of its symbol probabilities. Encoder and decoder must share the same dictionary or the information needed to rebuild it. A finite message also needs a rule for termination and any unfinished final phrase; the basic infinite-stream description does not settle that packaging detail.

Three practical examples

1. Skewed event stream: an experiment encodes a binary source in which one event is much more common. Longer frequent phrases may reduce average bits per event compared with one-bit-per-event storage.

2. Decoder design: a system uses a fixed-width identifier as a dictionary lookup key. It must still handle variable numbers of output symbols and the associated buffer requirements.

3. Compression teaching: a team compares Tunstall and Huffman codes on the same probability model. The comparison distinguishes variable input phrase lengths from variable output codeword lengths.

Think of it this way

Think of a catalog where every product number has two digits, but some products are single items and others are multipacks. A fixed-size order code can therefore stand for different amounts of goods.

The analogy's limit is parsing: a Tunstall dictionary must support unambiguous division of the source stream. It cannot be an arbitrary collection of convenient phrases without rules ensuring that the input can be decoded correctly.

Worked example

Assume independent symbols A and B with probabilities 0.8 and 0.2. Allow four dictionary entries, each assigned a two-bit identifier. Start with A and B. Expand A to AA and AB, with probabilities 0.64 and 0.16. The leaves are now AA, AB and B.

Expand the most probable leaf, AA, into AAA and AAB. The final dictionary is AAA with probability 0.512, AAB with 0.128, AB with 0.16 and B with 0.2. Assign them 00, 01, 10 and 11 respectively.

Average phrase length is 3 × 0.512 + 3 × 0.128 + 2 × 0.16 + 1 × 0.2 = 2.44 symbols. The long-run rate under this model is 2 / 2.44 ≈ 0.820 bits per source symbol, excluding overhead.

The eight-symbol message AAAAAAAB parses as AAA | AAA | AB and becomes 00 | 00 | 10, or six bits. This particular message ends at a phrase boundary; arbitrary finite messages require the agreed termination mechanism.

Illustrative case study

Fictional case: PhrasePort tests a fixed dictionary on equipment status logs. The training sample strongly favors one status, so the dictionary assigns long phrases to repeated occurrences. A later operating period has a different distribution and compresses less effectively.

The team compares performance across operating periods and includes dictionary distribution and message-framing costs. It checks exact round-trip reconstruction, especially messages that end partway through a dictionary phrase. Engineers also measure output-buffer handling rather than assuming fixed-width identifiers imply fixed-size decoded chunks.

The fictional lesson is that the probability model and the finite-message format are both part of a usable compressor.

Common misconceptions and mistakes

Tunstall coding does not give every original symbol a fixed-width codeword. The codewords identify phrases that can contain multiple symbols.

Do not assume the standard optimality statement applies unchanged to sources with memory. Dependencies can change phrase probabilities at parsing boundaries, so the memoryless argument has a specific scope.

The dictionary is also not free. For small messages, transmitting it or its construction parameters can outweigh payload savings. A fixed codeword width simplifies one boundary problem but does not automatically provide error correction or complete message framing.

Business use

Businesses evaluating a variable-to-fixed scheme should identify whether regular output words and dictionary lookup suit their processing pipeline. Test the actual source distribution and the memory available for encoding and decoding tables.

Measure complete message size, including model information and termination, together with throughput and buffer usage. Compare against simpler alternatives on representative data. A favorable expected rate from an assumed source is a useful design calculation, but actual logs may contain dependencies, distribution changes and short messages that alter the practical result.

Check your understanding

a two-bit Tunstall codeword expands to three source symbols. Must every other codeword expand to three symbols too?

Answer: no. Two bits identifies a dictionary entry; different entries can contain different numbers of source symbols. Only the encoded identifier width is fixed.

Related terms

Prefix code
Entropy
Parsing
Lossless compression
Variable-to-fixed coding
Huffman coding
dictionary compression
memoryless source

Learn next

Build the four-entry dictionary above and decode several complete phrases. Then test what happens when a finite message ends with an unfinished prefix. Finally, compare modeled long-run rate with total stored size after including dictionary and framing information.

Sources

Primary source: MIT 6.441 supplementary notes, “Variable to Fixed Length Source Coding—Tunstall Codes”: https://web.mit.edu/6.441/spring06/handout/sup/Tunstall_codes_-_Notes_1.pdf . The construction and scope of the memoryless optimality result follow these notes. The 0.8/0.2 example and PhrasePort case are original teaching illustrations.

Previous: Tukey's trend test Next: Tuple