= Ternary Huffman coding
= Ternary Huffman code
{synonym}
The three-symbol output version of <Huffman coding>. For an <odd number> $m\geq3$ 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.
Back to article page
