Huffman code

The Russian original of War and Peace has 2,904,144 characters, and in UTF-8 they take 5,179,058 bytes: each Cyrillic letter is two bytes, sixteen bits. But the space occurs 452,000 times, the letter «о» 255,033 times, and the capital «Й» once in the whole novel. The Huffman code gives the space three bits, «о» four, «Й» twenty-one, and the novel shrinks to 1.76 megabytes, 2.9 times smaller. Below, the tree of this code grows from the real frequencies: each step glues together the two rarest trees. The height of a node is how many times its characters occur, the depth of a leaf is the length of the code.

Run the building from the start. The first to be glued are the characters that occurred once: accented Latin letters from the French dialogue, «№», «→», that very «Й». Their trees grow long and deep, so their codes are long. The Cyrillic letters join later, and the space and «о» join almost at the root: they have short codes. Switch to lambda DNA: four letters occur almost equally often, the tree degenerates into two levels, and each letter gets exactly two bits. There is nothing to compress there: the frequencies are almost equal.

The idea

A code in which no code word is the beginning of another is called a prefix code. It can be read without separators: collect bits, and when they match a code it is a character, start the next one. A prefix code is the same thing as a binary tree: 0 to the left, 1 to the right, characters in the leaves, and a character’s code is the way to it from the root. The length of a code is the depth of a leaf, and the cost of the whole text is the sum over the characters of “frequency × depth”.

The two rarest letters in the best tree can be made siblings on the deepest branch: if a rare letter sits above a frequent one, swapping them only makes the code cheaper. Glue these siblings into one letter with the combined frequency, and the same problem remains for an alphabet one letter smaller. Repeat until one tree is left.

The whole algorithm follows from this. Put all the characters into a heap by frequency; while the heap holds more than one tree, take out the two lightest, make them the children of a new node with the combined weight, and put the node back. The last tree is the code. The algorithm is greedy: at each step it takes what is best for it now and never reconsiders a decision, and it is a rare case where greed provably leads to the optimum.

There is a handy formula for the cost of a code. Each node of the tree except the leaves lies on the way from the root to all its leaves, so in the sum “frequency × depth” the weight of each node is counted exactly once for each leaf below it. Hence

that is, the sum of the weights of all the gluings. To find out how many bits a text will take, the code itself is not needed: it is enough to add up the sums that appeared in the heap. The first problem is built on this.

Why it is the best code

Notice where greed was right and where it would have been wrong. Huffman’s predecessor, the Shannon–Fano code, is also greedy, but it builds the tree from the top: it splits the characters into two groups with frequencies as close as possible. It makes the most important decision, at the root, first and cannot correct it later. Huffman starts from the end where the greedy step can be proved: the bottom. An example where the top-down way comes out worse, with the Shannon–Fano tree beside the Huffman tree, is in the course chapter on greedy algorithms.

Prefix codes are not the only ones that can be read unambiguously. But that does not help either: by the Kraft–McMillan inequality the lengths of any uniquely decodable code satisfy Σ 2^−ℓ_x ≤ 1, and for such lengths there is always a prefix code. So Huffman is the best among all codes that replace each character with a separate string of bits.

How close to the limit

Claude Shannon proved in 1948 that no such code spends on average fewer than the entropy bits per character, H = −Σ p_x log₂ p_x, while the Huffman code spends less than H + 1. On War and Peace the entropy is 4.825 bits per character, Huffman 4.862, 0.8% more. The gap comes close to a whole bit only when one character is very frequent: if a character occurs 99% of the time, the entropy is 0.08 bits, and no code with a whole number of bits gives less than one bit per character. Then pairs and triples of characters are encoded, or one moves to arithmetic coding, which spends a fractional number of bits per character. How entropy works and why the limit is exactly this is told in the chapter of “Mathematics, the Queen of the Sciences” on the measure of information.

But entropy is a limit only for codes that look at characters one at a time and do not remember their neighbours. Change the alphabet and the limit changes. If a whole word counts as a character, and spaces and punctuation as separate characters, the text becomes a million word-symbols, and the Huffman code for them takes only 2.48 bits per character of text. To the right of each bar is how many bits per character of the novel that is:

The dictionary is not free: to decode the text the recipient needs all 54,169 words and characters, and compressed with zlib they take another 219 thousand bytes. But even with the dictionary, Huffman by words, 1.12 MB, beats zip with its 1.39 MB. zip compresses repeats at a distance of up to 32 kilobytes, while the novel’s words repeat throughout the text. The xz and bzip2 archivers look at an even wider context and beat both. Untick “count the dictionary” and you will see how easy it is to fool yourself: without the dictionary Huffman by words “compresses” the novel better than any archiver.

Code

Building a code from frequencies, decoding, and a canonical code with the same lengths, which the next section is about. The order number in the heap breaks ties: with equal frequencies the tree created earlier comes out first, and the leaves are created in character order. This way Python, Go and the scene above build one and the same tree.

And the whole novel. The program reads War and Peace from the server where the code runs, counts the characters, builds the code lengths and compares with UTF-8 and the entropy; then the same for an alphabet of words:

  1764902 bytes; the longest code: 21 bits, longer than 15 bits: 40 symbols

This line is the occasion for the next section.

How the code is stored and sent

The recipient needs the code itself, otherwise the bits cannot be read. Sending the whole tree is expensive, and compression formats act more cleverly. Note that for compression only the code lengths matter, not the bits themselves: any prefix code with the same lengths compresses just as well. So one can agree on a rule by which codes are restored from lengths, and send the lengths alone. Such a rule defines a canonical code: the characters are sorted by code length, and with equal lengths alphabetically, the first gets a code of zeros, and each next one the previous plus one, with zeros on the right if the length has grown. This is exactly what the canonical function in the listing does: in the table its codes stand next to the tree’s codes, and the lengths are the same.

This is how DEFLATE, the compression inside zip, gzip and PNG (RFC 1951), is built. A block begins with the code lengths for 286 literals and lengths and for 30 distances, and the lengths themselves are compressed with a Huffman code too. And the standard limits a code to 15 bits so that a decoder can read codes with a table of fixed size. The letter-by-letter code of War and Peace is longer: 40 characters got more than 15 bits, «Й» 21 bits. So an optimal Huffman code sometimes does not suit a real archiver, and an optimal code with a length limit is needed. It is built by the package-merge algorithm of Lawrence Larmore and Daniel Hirschberg (1990); zlib does something simpler: it builds an ordinary tree and, if the codes came out too long, moves leaves around until they fit the limit. Compression hardly suffers from this: rare characters account for a negligible share of the bits.

Decoders do not walk the tree bit by bit. They look at, say, the next nine bits at once and from a table of 2⁹ entries learn both the character and the length of its code; long codes are finished with a second table. The canonical code is convenient here too: codes of one length are consecutive numbers, so the character is found by subtraction. Try it in the problem on decoding from lengths.

Where it breaks: one bit

Variable-length codes have a price: an error in one bit throws the decoder off the character boundaries. Below is a sentence from the novel written in its code. Flip any bit.

In a fixed-length code a flipped bit would spoil exactly one character. Here the decoder reads on from a wrong boundary and puts out wrong characters until the boundaries happen to coincide again. Usually this happens quickly: of 296 possible errors in this sentence, 83 spoil one character, and on average six or seven. But in 34 cases the decoder never gets back into step before the end of the sentence. That is why compression formats split data into blocks and check them with checksums: zip and gzip store the CRC-32 of each file and notice corruption rather than try to fix it.

What it costs

An alphabet of n characters needs n − 1 gluings, each two extractions from the heap and one insertion, at O(log n) each. O(n log n) in all to build, and O(n) memory. Encoding and decoding a text is O(N), where N is the number of bits or characters; for texts this is the main time, while building the code for 165 characters takes microseconds.

If the frequencies are already sorted, the heap can be replaced with two queues (Jan van Leeuwen, 1976). The first holds the leaves in increasing order, the glued trees go into the second. The gluing sums come out non-decreasing, so the second queue is sorted by itself, and the two lightest trees always stand at the front of the queues. Each gluing is O(1), and the whole building after sorting is O(n). A benchmark: a heap, two queues (including the sort) and finding the two minima by a plain scan.

The scan has slope 2: ten times the characters, a hundred times as long. The heap and the queues grow almost linearly, and the queues are twice as fast as the heap in Python and several times as fast in Go. On the alphabet of the novel’s 54 thousand words there are 18 times as many characters as at the last point of the scan, so the scan would take more than three hundred times as long.

Where it works

On its own the Huffman code compresses poorly: it sees no repeats and no context. But it finishes the job well after other methods that turn data into a stream of characters with unequal frequencies.

• DEFLATE (zip, gzip, PNG, website compression): LZ77 replaces repeats with back references, and the literals and references are coded with two Huffman codes up to 15 bits long. How DEFLATE works is taken apart in the course chapter on compression.
• JPEG: after the discrete cosine transform and quantisation what remains is mostly zeros and small numbers, and their runs are coded with Huffman codes from tables written in the file.
• HTTP/2 and HTTP/3: the HPACK header compression standard (RFC 7541) contains one static Huffman code for all bytes, built from the statistics of real headers; it compresses addresses and cookies without sending a table.
• MP3, Brotli, zstd: prefix codes for part of the stream as well. In zstd, alongside Huffman, there is asymmetric numeral systems (ANS) coding, which, like arithmetic coding, spends a fractional number of bits per character but is almost as fast.

History

In 1951 David Huffman, then a graduate student, chose a term paper for Robert Fano instead of an exam in information theory: find the most economical binary code. Fano and Shannon had by then devised the top-down splitting method but could not prove it was the best, and indeed it was not. After months of fruitless attempts Huffman decided to give up and, by Huffman’s own account, was already throwing the notes away when the realisation came that the tree must be built from the bottom. The paper “A Method for the Construction of Minimum-Redundancy Codes” came out in September 1952 in the Proceedings of the IRE and ran to four pages. This story is told in more detail in the course chapter.

Huffman went on to teach for many years, and in the last decades of life worked on the mathematics of paper folding, on surfaces with curved creases. The code was never patented.

Problems

In the first problem what is needed is not the code but only its cost, and the formula “the sum of the gluing weights” turns it into a few lines with a heap; the trap is a single character and big numbers. In the second the code is given by lengths alone, as in DEFLATE, and it has to be restored and read.