> [!theoremb] Algorithm > > ![[huffman.png]] > > Given the [[Probability Distribution|probability distribution]] of the [[Code|source alphabet]] in decreasing order, $p_n \lt p_{n - 1} \le \cdots \le p_2 \le p_1$. Merge the symbols $S_n$ and $S_{n - 1}$ into a new symbol with [[Probability|probability]] $p_n + p_{n - 1}$ to arrive at a source alphabet with $n - 1$ symbols. Repeat this procedure inductively until the source alphabet has only two symbols. Code these with $0$ and $1$, and work backwards. > > This is the most efficient noiseless code, as it is prefix-less, and gives the most probable symbols the shortest code, aligning them most closely to the optimal result given by the [[Noiseless Coding Theorem|noiseless coding theorem]].