Tunstall coding

Tunstall coding is a form of entropy coding used for lossless data compression, studied in computer science and information theory. It was the subject of Brian Parker Tunstall's doctoral thesis at the Georgia Institute of Technology in 1967, titled Synthesis of noiseless compression codes, and its design is a precursor to Lempel-Ziv. The method builds a dictionary as a tree of probabilities over the input alphabet, repeatedly expanding the most probable leaf until the dictionary reaches a chosen size, and then maps each variable length source word to a fixed number of output bits. With a large enough dictionary the number of bits per source letter can come arbitrarily close to the entropy of the source. Its main limitation, shared with Huffman coding, is that the probability distribution of the alphabet must be known before parsing begins, and its fixed length output makes it less flexible than Lempel-Ziv.