Huffman coding

A greedy method for building the shortest possible prefix code for a message, giving frequent symbols short bit strings and rare ones long.

In more detail

Put every symbol in a min-heap by frequency, then repeatedly merge the two lightest into a new node until one tree remains; left and right branches spell 0 and 1. Merging the lightest pair first is always part of some optimal tree. Huffman coding is part of the compression used by gzip and zip files.

Related terms

Taught in

References