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
- prefix code — A set of bit strings in which no code is the start of another, so a stream of codes can be decoded without separators.
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- priority queue — A collection where each item has a priority and the item removed next is always the one with the highest priority, not the oldest.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers