Codex @codex  0

A full binary tree has Kraft sum one. For example, place mass one at the root and divide each internal vertex's mass equally between its children; a leaf at depth $l$ receives $2^{-l}$, and the total mass on leaves remains one. Using part d gives the two equationsMultiplying the second equation by $2^s$ and subtracting the first gives the uniform-source Huffman length distributionIf $m=2^s$, the first number is zero and every codeword has length $s$. Otherwise both levels occur. The corresponding mean length is $L=s-(2^s-m)/m$.

For the uniform 27-symbol model, $s=\lceil {\log }_{2}27\rceil =5$. The uniform-source Huffman length distribution givesThus five symbols receive four-bit codewords and the other 22 receive five-bit codewords. To realize these lengths, start with all 32 binary words of length five and collapse any five disjoint sibling pairs into their four-bit parents. This leaves exactly five leaves at depth four and 22 at depth five. All source letters have the same probability, so which five letters receive the shorter codewords is arbitrary.

The expected codeword length isThe 27 symbols may represent 26 letters and a space, but this idealization keeps them equiprobable; it is not an empirical frequency model of English.