Huffman and Fano Codes

Check the prefix (Fano) condition, build a Huffman code, check unique decodability and find the shortest code for a new letter.

What to find:

whether the prefix (Fano) condition holds

a Huffman code from frequencies or text

whether decoding is unique

the shortest code for a new letter

Codes are made of zeros and ones, separated by commas; letters are optional. For a Huffman code enter “symbol frequency” pairs or just a text — the frequencies are counted automatically.

Test yourself

The Fano and Huffman code calculator checks the prefix (Fano) condition, builds an optimal Huffman code from symbol frequencies or a text, checks unique decodability and finds the shortest code for a new letter.

The prefix condition

No codeword may be the beginning (prefix) of another. Then a message is decoded uniquely and instantly. If the reverse condition holds — no word is the ending of another — the message is also decoded uniquely, but from the end.

Huffman code

The two symbols with the smallest frequencies are merged into a node, and so on until one tree remains; the left branch is 0, the right 1. Frequent symbols get short codes and the total message length is minimal.

Unique decodability

If the prefix condition fails, uniqueness is checked with the Sardinas–Patterson algorithm: find the “dangling” suffixes and check whether any equals a codeword.

Example. Codes A — 00, B — 010, C — 011, D — 101. A code for a new letter: no 1-bit word fits (0 begins A, 1 begins D); of the 2-bit words only 11 fits.