Codex @codex  0

Replacing every quaternary digit by its fixed two-bit representation preserves the prefix code property: a binary prefix between translated codewords would end at an even position and hence imply a quaternary prefix. Thus a translated quaternary Huffman code cannot beat binary Huffman coding in expected codeword length.

For the reverse bound, binary prefix code lengths ${\ell }_i$ give candidate quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. Since ${\sum }_i{4}^{-k_i}\le {\sum }_i{2}^{-{\ell }_i}\le 1$, the Kraft inequality supplies such a quaternary prefix code. Optimality of quaternary Huffman coding and $2\lceil {\ell }_i/2\rceil \le {\ell }_i+1$ give $2L_4^{\ast }\le L_2^{\ast }+1$. These quantities are expected codeword lengths for the same source probability distribution.

For a complete binary prefix code with lengths ${\ell }_i$, the Kraft inequality is an equality: ${\sum }_i{2}^{-{\ell }_i}=1$. Put $q_i=2^{-{\ell }_i}$. The difference between expected codeword length and Shannon entropy isThe Kullback-Leibler divergence is nonnegative and vanishes exactly when $p=q$. Hence a complete code is entropy-tight exactly for its dyadic matching source. For example, lengths $(1,2,2)$ match probabilities $(1/2,1/4,1/4)$. Being an optimal prefix code among symbol-by-symbol codes is a weaker condition and does not imply this equality.

For a random finite binary string $M$ of length $L$, conditioning on $L=\ell$ leaves at most $2^{\ell }$ possible strings. Thus its conditional entropy is at most $\ell$. Since the length is a function of the string, the chain rule for information entropy givesThe term $H(L)$ cannot generally be removed. For concatenations of $m$ words from a fixed finite decipherable code with maximum length $d$, it is at most ${\log }_2(md+1)$. Decipherability preserves the Shannon entropy of the source block. For an independent source block, dividing the resulting inequality by $m$ and taking $m\to \infty$ proves the expected codeword length is at least the one-symbol Shannon entropy.

Consider a binary Markov source with fair initial bit and flip probability $q=1/8$. Its exact $n$-symbol information entropy is $H_n=1+(n-1)h_2(1/8)$. At $n=16$,This includes the uncertainty of the initial bit; the entropy rate itself is $h_2(1/8)\simeq 0.54356444$ bits per symbol. The finite-block difference is $(1-h_2(1/8))/n$.

For any finite block distribution, the entropy lower bound for prefix codes gives expected codeword length $L_n\ge H_n$, while Shannon coding achieves $L_n<H_n+1$. These bounds apply to each block as one source symbol, without requiring consecutive blocks to be independent. Here Huffman coding on all $2^{16}$ possible 16-symbol words gives the independently calculated value $L_{16}\simeq 9.19511361$ bits per block, or $0.57469460$ bits per symbol. The noninteger value is an expected value; each actual codeword has an integer length. As the block length grows, the prefix code bounds squeeze $L_n/n$ towards the entropy rate when an optimal code is used.

An entropy rate below one does not allow every word to fit into a shorter fixed binary word with zero error. For $0<q<1$, all $2^n$ binary words are possible, so an injective fixed-length code needs at least $n$ bits. Compression instead exploits variable codeword lengths, or the vanishing-error convention in reliable source encoding at a rate. These are different guarantees.

Recursively split an ordered list of positive source probabilities into contiguous blocks, choosing each cut to minimize the difference between the total masses of the two children. The resulting binary prefix code has expected codeword length less than $H+2$, where $H$ is its source Shannon entropy. If the probabilities were in nonincreasing order, its expected length is less than $H+1$.

To prove this, an interior node of mass $S$ with child masses $A,B$ contributes $S$ to the expected path length and $Sh(A/S)$ to the Shannon entropy, by the chain rule for information entropy. The inequality $1-h(t)\le |2t-1|$ bounds that node's redundancy by $|A-B|$. If the cut is between probabilities $p_k,p_{k+1}$, shifting the cut by one position cannot improve the imbalance. On the heavier side this gives $|A-B|\le p_k$ or $p_{k+1}$, respectively; a singleton heavier side gives the same inequality directly. Thus $|A-B|\le \max (p_k,p_{k+1})$.

Every original inter-symbol gap is used once in the recursive tree. Summing over gaps bounds total redundancy by ${\sum }_{k=1}^{m-1}(p_k+p_{k+1})=2-p_1-p_m<2$. In sorted order it is instead at most ${\sum }_{k=1}^{m-1}{p}_k=1-p_m<1$. These are expected-length guarantees, not an assertion that the resulting code is always optimal.

A probability mass function $p$ has full support on a specified finite alphabet if $p_x>0$ for every symbol in that alphabet. This is relative to the chosen alphabet: deleting zero-probability symbols produces a smaller alphabet on which the same law has full support. In a weighted prefix code problem, full support makes every shortening of a retained codeword strictly reduce expected codeword length. Without it, a minimum-cost code tree may contain redundant zero-weight branches.

A Huffman code is the prefix code returned by Huffman coding; the algorithm chooses a code tree, while the code specifies the actual symbol-to-codeword assignment. For the probability distribution $(0.4,0.3,0.2,0.1)$ in symbol order $A,B,C,D$, the illustrated binary tree givesThe codeword lengths are $1,2,3,3$. This is a prefix code because no complete codeword is an initial segment of another complete codeword. Thus a decoder can start at the root of a tree, follow one edge per bit, emit a symbol on reaching its leaf, then restart at the root of a tree. In particular, 011010111 splits as 0 | 110 | 10 | 111 and decodes to $A,C,B,D$. No separators are transmitted: the leaf tells the decoder where a codeword ends.

The expected codeword length isbits per source symbol. Four symbols would require $2$ bits each if all codewords had the same length, so this Huffman code saves $0.1$ bit per symbol on average, or $5\%$ of that fixed-length payload. A particular message can grow: $A,C,B,D$ uses nine bits here instead of eight. These lengths count the encoded symbols only; transmitting a code description or message framing can add further cost.

The Kraft inequality is saturated by this Huffman code:Its Shannon entropy isbits per symbol, slightly below the expected codeword length $1.9$. The entropy lower bound for prefix codes applies to every binary prefix code for this probability distribution. It need not be attainable with integer codeword lengths for individual symbols; Huffman coding reaches the best mean within that class. ^[ref]

A Huffman code need not be unique. In the first example, the tied $B$ and $CD$ weights can exchange their $0/1$ edge labels, changing codewords but preserving their codeword lengths. Ties can also change the lengths themselves. For a second probability distribution $(0.4,0.2,0.2,0.2)$, first merge $C,D$ to weight $0.4$. The next merge can join $B$ with either $A$ or the $CD$ subtree, since both have weight $0.4$. Joining $B$ with $A$ permits $A\mapsto 00,B\mapsto 01,C\mapsto 10,D\mapsto 11$, with all lengths $2$. Joining $B$ with the $CD$ subtree permits $A\mapsto 0,B\mapsto 10,C\mapsto 110,D\mapsto 111$, with lengths $1,2,3,3$. Both are optimal prefix codes with expected codeword length $2$: for the latter, $0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$. Tie choices can change the code tree without changing the minimum mean.

// Target: algebra.bigb

Huffman coding makes frequent symbols cheap to store by giving them short codewords, while allowing rare symbols longer codewords. For a known probability distribution on a finite alphabet with at least two positive-probability symbols, binary Huffman coding constructs a prefix code minimizing expected codeword length among binary prefix codes that encode one source symbol at a time. The objective is an average under that probability distribution; it does not promise to shorten every message. Encoder and decoder must agree on the resulting Huffman code. ^[ref]

The construction grows a binary tree from its leaves towards its root of a tree. Start with one leaf per symbol, weighted by its probability. Repeatedly join the two currently smallest weights beneath a new parent in a rooted tree, whose weight is their sum, and replace the pair by that subtree. Include newly formed subtrees when choosing the next pair. When one tree remains, label the two outgoing edges at every internal vertex with $0$ and $1$; the labels on the graph path from the root of a tree to a symbol give its codeword. This is a greedy algorithm: each step makes a locally cheapest merge, yet the result is an optimal prefix code.

For a concrete example, use probabilities $p_A=0.4$, $p_B=0.3$, $p_C=0.2$, $p_D=0.1$. First join $D$ and $C$, creating weight $0.3$. The remaining weights are $0.3$ for $B$, $0.3$ for the $CD$ subtree, and $0.4$ for $A$. Join the two $0.3$ weights to make $0.6$, then join $A$ with that $0.6$ subtree to make $1$. The merge weights are therefore $0.3,0.6,1$. Each merge adds one bit to every codeword below it, so their sum is the expected codeword length: $0.3+0.6+1=1.9$ bits per source symbol. The diagram fixes the edge labels to produce the Huffman code used below.

The useful insight is that choosing short codewords is a resource allocation problem: the prefix code condition constrains the available codeword lengths through the Kraft inequality. Huffman coding solves this one-symbol problem exactly for the supplied probability distribution. For repeated emissions of a memoryless classical information source, the same Huffman code can be applied symbol by symbol. More general compression can exploit dependencies or encode groups of symbols; the one-symbol optimality statement does not compare all such methods.

Replace sibling leaves in a code tree labelled $a,b$ by their common parent in a rooted tree, now a leaf labelled $m$ of weight $w_m=w_a+w_b$. All other codewords stay fixed; each of $a,b$ loses one bit. For any such code tree $T$ and the contracted code tree $T^{\prime }$, their weighted costs satisfyIf $a,b$ have two least weights, the Huffman sibling property gives an optimal prefix code containing this pair. Its contracted prefix code must be optimal for the reduced weights $w^{\prime }$: any cheaper reduced prefix code could be expanded at $m$ by appending $0,1$, giving a cheaper original prefix code. Conversely, expanding any optimal reduced prefix code adds precisely $w_a+w_b$ and attains the original minimum. This is optimal substructure, the justification for repeating the merge in Huffman coding. ^[ref]

In the exchange diagram, $C,D$ contract to weight $0.3$ at leaf depth in a code tree $2$. The reduced expected codeword length is $0.4\cdot 1+0.3\cdot 2+0.3\cdot 2=1.6$ bits; expanding restores $1.6+0.3=1.9$ bits. For $n=2$, the reduction leaves one symbol: allow its temporary codeword to be empty, of cost zero, so expansion gives the two one-bit codewords. This convention is only the terminal reduced problem; the original source has at least two symbols.

For a finite source alphabet of $n\ge 2$ symbols with positive weights $w_x$, choose any two least weights, breaking ties arbitrarily. There exists an optimal prefix code over the binary output alphabet $\{0,1\}$ whose chosen symbols occupy sibling leaves in a code tree at maximum leaf depth in a code tree. Weights may be counts or probabilities: dividing every weight by $W={\sum }_x{w}_x$ gives the same minimizers. The existence statement is what makes the first merge of Huffman coding safe. It does not say that every optimal prefix code already has the chosen pair together.^[ref]

An exchange makes the idea tangible. Take probabilities $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$. The prefix code $D\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $A\mapsto 111$ has expected codeword length $2.5$ bits. Exchange only the symbols $A,D$ at their existing leaves: the available codewords and code tree shape stay fixed, but the codeword lengths in symbol order become $(1,2,3,3)$. The new expected codeword length is $1.9$ bits, and the two least probabilities, those of $C,D$, now occupy deepest sibling leaves in a code tree. The saving is $(0.4-0.1)(3-1)=0.6$ bit per source symbol.

Here is the short proof outline. An optimal prefix code with positive weights has a full binary tree as its code tree: suppressing a vertex with only one child shortens every codeword in that subtree and strictly reduces cost. A deepest leaf therefore has a leaf as its sibling, giving the deepest sibling property of an optimal prefix code. Put the two chosen least weights at these positions by successive exchanges of leaf labels. Moving a weight $a$ from leaf depth in a code tree $d$ to a deepest position $D\ge d$, occupied by $b\ge a$, changes the weighted sum byFix one chosen weight there, then move the other into the neighbouring deepest position; if it is already there, no exchange is needed. The prefix code condition survives because the set of codewords is unchanged. Starting from an optimal prefix code, the cost cannot decrease below the minimum, so these exchanges preserve optimality. Strictly unequal weights at unequal depths would give a strict decrease, explaining probability monotonicity of optimal prefix-code lengths. Equal weights or equal depths allow cost-neutral exchanges. ^[ref]

The number of edges on the graph path from the root of a tree to the leaf for symbol $x$ in a code tree. The root of a tree has depth zero. Each edge contributes one bit to a binary codeword, so this depth equals the codeword length; weighting these depths by probabilities gives expected codeword length.

An optimal prefix code can be nonunique in several different senses. Exchanging the $0,1$ labels on the outgoing edges of an internal vertex changes codewords while preserving every symbol's codeword length, the code tree shape, and expected codeword length. This freedom exists even with strictly unequal probabilities. Exchanging equal-probability symbols between leaves also preserves expected codeword length; if their leaf depths in a code tree differ, their individual codeword lengths change, though the set of leaf depths does not. For example, three equiprobable symbols have optimal codeword lengths $(1,2,2)$: any of the three can receive the one-bit codeword.^[ref]

Ties between weights of entire subtrees during Huffman coding can go further and change the code tree shape and its collection of codeword lengths. Take $(p_A,p_B,p_C,p_D)=(0.4,0.2,0.2,0.2)$ and first merge $C,D$, creating weight $0.4$. Next, $B$ of weight $0.2$ can merge either with $A$ or with the $CD$ subtree, both of weight $0.4$. The two resulting prefix codes areFor the second prefix code, $L=0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$ bits. Both merge sequences add weights $0.4,0.6,1$, whose sum is $2$. Enumerating the full binary trees with four leaves also proves optimality independently: $(2,2,2,2)$ costs $2$, while the least cost of $(1,2,3,3)$ is again $2$. The two code trees cannot be obtained from each other merely by relabelling leaves or exchanging edge labels: their collections of leaf depths in a code tree differ.

The quantifier in the Huffman sibling property is visible here too. Choose $B,C$ as two least-probability symbols. In the displayed balanced optimal prefix code, they are not sibling leaves in a code tree. Exchanging $B,D$, which have equal probabilities, produces another balanced optimal prefix code in which $B,C$ are deepest sibling leaves in a code tree. Thus the proof supplies an optimal representative with the chosen pair together. It does not force that labelling on every optimum. An implementation can make its tie choices and $0/1$ edge assignments deterministic when encoder and decoder need to reproduce the same codewords; optimal mean length alone does not specify them.

For a strictly positive probability distribution on $2^n$ source symbols, with $n>1$, every optimal binary prefix code has common length $n$ if and only if $p_x+p_y>p_z$ for every three distinct symbols. It suffices to compare the sum of the two smallest probabilities with the largest.

An optimal binary prefix tree has no node with only one child, because removing that detour would strictly shorten positive-probability words. It therefore satisfies equality in the Kraft inequality. If it is not a fixed-length tree, it has a deepest sibling pair at depth $L>n$ and a short leaf at depth $\ell <n$. Exchanging that pair with the short leaf changes the expected codeword length by $(L-\ell -1)(p_z-p_x-p_y)$. Strict positivity of every pair sum over a third probability makes this change negative, contradicting optimality.

Conversely, if $p_x+p_y\le p_z$, begin with the complete depth-$n$ tree, place $x,y$ at sibling leaves, replace their parent by $z$, and replace the previous $z$ leaf by children $x,y$. The new expected length is $n+p_x+p_y-p_z\le n$ and its lengths are unequal. If the optimum is below $n$, every optimal tree is nonuniform; if it is $n$, this modified tree is a nonuniform optimum. Thus equality in the probability condition already defeats the assertion that every optimum has fixed length.

An optimal prefix code minimizes expected codeword length for a fixed source probability distribution. Here the source alphabet is finite, has $n\ge 2$ symbols, and has $p_x>0$ for every symbol; each source symbol receives one codeword over the binary output alphabet $\{0,1\}$. Its code tree puts the symbols at leaves. Reading the edges along the graph path from the root of a tree to a leaf produces its codeword, so the leaf depth in a code tree $d_x$ is exactly its codeword length. ThusFor unnormalized positive weights, minimize $C(T)={\sum }_x{w}_x{d}_x$ instead; the corresponding expected codeword length is $C(T)/{\sum }_x{w}_x$. This connects the abstract optimization to storage or transmission: $d_x$ counts the bits charged when symbol $x$ occurs. Huffman coding attains this minimum; the Huffman sibling property and Huffman sibling contraction explain why. ^[ref]

For $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$, a balanced code tree charges every symbol two bits, giving $L=2$. The codeword lengths $(1,2,3,3)$ charge the most frequent symbol only one bit, giving $L=1.9$. The choice concerns weighted cost, not just the greatest codeword length: increasing that maximum from two to three can improve the average.

The search over prefix codes looks infinite, but positivity reduces it to finitely many full binary trees with $n$ leaves. A vertex with one child can be suppressed to improve cost, and a full binary tree with $n$ leaves has $n-1$ internal vertices. There are consequently finitely many such shapes and symbol assignments, so the minimum exists. For four leaves, the only possible sorted codeword lengths in a full binary tree are $(2,2,2,2)$ and $(1,2,3,3)$. Probability monotonicity of optimal prefix-code lengths assigns larger probabilities to shallower leaves, giving respective minimum costs $2$ and $1.9$ in this example. This is an independent small-instance check of the Huffman code.

These hypotheses matter. With zero weights, suppressing a subtree carrying only zero weight need not strictly improve cost, so an optimal prefix code need not have a full binary tree. A one-symbol source raises the convention of whether an empty codeword is allowed. Both cases are outside the original statement here. Encoding groups of symbols changes the source alphabet and the optimization problem; the minimum here concerns one source symbol per codeword.

Work on the source support, so its listed probabilities are positive; zero-probability symbols may be omitted. An optimal binary prefix code minimizes the expected codeword length for that distribution. The same optimal expected length is attained when optimization is over uniquely decipherable codes, by the converse and existence parts of Kraft–McMillan inequality.

Choose Shannon lengths ${\ell }_k=\lceil -{\log }_2{p}_k\rceil$. They satisfy $2^{-{\ell }_k}\le p_k$, so the preceding existence theorem gives a prefix code with those lengths. Also ${\ell }_k<-{\log }_2{p}_k+1$ for every symbol, including the integer cases. Thus its expected length is less than $H(X)+1$. An optimal code cannot have a larger expected length, provingFor a deterministic one-symbol source the empty word has length zero, consistent with this bound.

A compact code or optimal prefix code minimizes the expected codeword length ${\sum }_x{p}_x{\ell }_x$ for the given source probabilities and coding alphabet. The relevant comparison here is among binary prefix codes. The minimum is also the minimum among uniquely decodable codes, since the Kraft-McMillan inequality permits every uniquely decodable length list to be realized by a prefix code with the same lengths.

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.

Suppose a tree parent at depth $n-1$, with $n<L$, has an unused outgoing digit. The missing tree child gives an empty code tree branch at depth $n$. Move any deepest tree leaf into that position, retaining all other codewords and deleting the abandoned empty branch. The new word has no old word as a prefix, because it lies in an unused branch, and it is not a prefix of any retained word. Its length decreases from $L$ to $n$. With a full-support finite distribution this reduces expected codeword length by $p_i(L-n)>0$, contradicting optimality. Hence all three tree children exist, and each has a descendant codeword. In fact every internal vertex above depth $L-1$ has all three tree children. Applying this to the tree parent of the specified prefix gives the claimed three extensions.

The positive-probability qualification attached only to the specified prefix does not by itself suffice. In the zero-weight example $(p,c)=((1,0,0),(0,10,110))$, choose the positive-probability word $0$, so $n=1<L=3$. There is no word starting with $2$. The deepest tree leaf available for relocation has probability zero, so the strict-improvement argument fails. This is why the full-support finite distribution assumption is used for the structural conclusions.

First assume a full-support finite distribution, as stated above. Let $L$ be the largest codeword length and take a tree leaf at depth $L$. Every existing tree child of its tree parent must also be a tree leaf: an internal tree child would have a descendant deeper than $L$. If the chosen tree leaf were its tree parent's only tree child, moving its symbol to that tree parent would shorten its codeword by one, preserve the prefix code property, and reduce expected codeword length by its positive probability. That contradicts optimality. The tree parent therefore has at least two tree children, both tree leaves. A second codeword has the same first $L-1$ digits and a different last digit, proving the required deepest sibling codeword property for a ternary prefix code.

For the literal wording allowing zero probabilities, take $p=(1,0,0)$ and the prefix code $(0,10,110)$. Its expected codeword length is one, which is minimal: with more than one message an empty codeword is impossible, so the positive-probability message must have length at least one. Yet the deepest tree leaf $110$ has no sibling codeword. Thus positivity or an additional convention removing redundant zero-weight branches is needed.

Exchange the two complete codewords while leaving the code tree unchanged. The prefix code property is preserved because the set of codewords is unchanged. If $p_i>p_j$ but $l_i>l_j$, the change in expected codeword length iscontradicting optimality. Hence $p_i>p_j$ implies $l_i\le l_j$. This probability monotonicity of optimal prefix-code lengths is valid even if some probabilities are zero; equal probabilities impose no order.^[ref]