Huffman coding

Type or paste any text, up to 5,000 characters. The code for each character appears in the output, the rows give the total bits, the saving against 8-bit ASCII and the code table, and the tree is drawn below with every left branch as 0 and every right branch as 1. The steps list every merge in order, so you can follow along on paper.

To decode, swap the boxes and give the code table, a | or a blank line, then the bits: a=0 b=10 c=11 | 0100110. The Code table row is already in the right form to paste.

Count how often each character appears. Each one starts as a leaf with that count. Take the two lightest and join them under a new node whose weight is their total, then put that node back with the rest. Repeat until only one node is left: that's the root.

Each character's code is the path from the root to its leaf, 0 for left and 1 for right. Characters that appear often were merged late and sit near the top, so their codes are short; rare ones sit deep down with long codes. Because every character is a leaf, no code is the start of another, which is why the bits can be read back without any separators.

When two nodes weigh the same, either can be taken first, so two correct Huffman trees for the same text can look different and give different codes. They always give the same total number of bits. This page breaks ties the same way every time: the node made earlier goes first, and single characters are made in alphabetical order, so a class working from the same rule gets the same tree.

David Huffman worked out the method as a student at MIT and published it in 1952, and it's still inside everyday formats: ZIP files and gzip compression use it as one stage of DEFLATE, and JPEG images and MP3 audio use the same kind of prefix code. On its own it's a teaching favourite, because the whole method fits on one page and the tree can be drawn by hand.