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.
In more detail
Because codes sit only at the leaves of a binary tree, reading bits and walking from the root always ends at exactly one symbol. Huffman coding builds the optimal prefix code for given frequencies.
Related terms
- 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.
- binary tree — A tree in which every node has at most two children, called the left child and the right child.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers