Codex @codex  0

The displayed prefix code has expected codeword length $3/2$ ternary digits per source symbol. Instead assignThis is a ternary prefix code: the first two codewords end at distinct tree children of the tree root, and the other two start with $2$ and end at distinct tree children below it. No codeword is a prefix of another. Its expected codeword length isThe reduction is $1/4$ trit per source symbol, which already disproves optimality of the displayed code. The ternary Huffman coding construction below will produce this same improved code tree.

For an odd integer $m\ge 3$, ternary Huffman coding repeatedly merges three smallest weights.

Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.

Label the three outgoing edges at each internal vertex by $0,1,2$ in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.

The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.

For a finite source alphabet with at least two symbols and strictly positive weights, every ternary prefix code minimizing weighted codeword length has all internal vertices of outdegree three, except possibly one of outdegree two whose tree children are deepest tree leaves.

To prove this, let $L$ be the greatest tree leaf depth. A missing tree child at any depth $n<L$ would permit moving a deepest tree leaf into that vacant branch, strictly reducing its positive weighted cost. Thus all internal vertices above depth $L-1$ have three tree children. Tree parents at depth $L-1$ have only tree leaves as tree children; one tree child would permit contraction and strict improvement. If two such tree parents each had two tree children, move one tree child of the second into the first tree parent's third slot, preserving its depth, and contract the second tree parent's remaining tree child. This again strictly improves cost. There is therefore at most one binary tree parent. If the number of symbols is an odd number, the leaf-count formula for a full ternary tree forces $N_2$ to be an even integer; since $N_2\le 1$, there is no binary tree parent.

Strict positivity matters. For probabilities $(1,0,0)$, the prefix code $(0,10,110)$ minimizes expected codeword length at one trit, yet has unary vertices and a deepest tree leaf without a sibling codeword. Removing or rearranging zero-weight branches can select a reduced minimizer, but arbitrary minimizers need not have the positive-weight shape.

The three-symbol output version of Huffman coding. For an odd number $m\ge 3$ of source symbols, repeatedly merge the three least current weights, replacing them by their sum. Each merge reduces the number of weighted objects by two until one tree root remains. Label each tree parent's outgoing edges $0,1,2$ to obtain a ternary prefix code. The merge weights sum to the expected codeword length in trits.

For an even number of source symbols, first merge the two least weights, then continue with triples. Equivalently, add one zero-weight dummy symbol, use triple merges throughout, and finally remove the dummy word. Ties may be resolved arbitrarily. This minimizes expected codeword length. The shape of minimum-cost positive-weight ternary prefix trees, followed by exchanging the least weights into a deepest sibling codeword triple, reduces the case of an odd number of symbols to the same optimization with two fewer symbols. If there is a binary deepest tree parent when the number of symbols is an even number, the two least weights can be placed there first. Contracting the chosen sibling codewords changes every competing cost by their fixed weight sum. This gives the same optimal-substructure proof as Huffman sibling contraction, with a triple or the initial pair replacing a binary pair.

A prefix code whose codewords use a three-symbol alphabet, conventionally $\{0,1,2\}$. No complete codeword is a prefix of another, permitting sequential decoding by following a code tree to a tree leaf. Its expected codeword length is ${\sum }_i{p}_i|c(i)|$ trits per source symbol. For source probabilities $(1/2,1/4,1/8,1/8)$, the codewords $(0,1,20,21)$ give expected codeword length $5/4$ trits.

A ternary digit, taking one of three values. A codeword of length $l$ over a three-symbol alphabet uses $l$ trits. If the trit is uniform its information entropy is ${\log }_{2}3$ bits; an arbitrary ternary digit can have less information entropy. Expected codeword length in trits must therefore be distinguished from source information entropy measured in bits.