碼作為樹
前綴碼映射到一棵二叉樹：根表示解碼的開始，左分支表示位元0，右分支表示位元1，葉表示完整的碼字。
幾何約束：每個葉終止一條從根到葉的路徑。沒有葉可以有後代（如果有，其碼字就是後代碼字的前綴，違反前綴碼性質）。
這給出了Kraft不等式的幾何解釋：
深度為d的每個葉'佔據'樹總容量的分數2^(−d)。完整二叉樹在深度D的總容量為1。前綴碼在各種深度使用葉；Kraft和測量總佔據。
Kraft和 = 1：完整碼（每條路徑終止於葉——完美填充）。
Kraft和 < 1：不完整碼（某些樹容量未使用——可以添加更多符號）。
Kraft和 > 1：前綴碼不可能（某些路徑必須共享葉）。
更深的葉 = 更長的碼 = 更小的容量
深度為1的葉使用樹容量的一半（2^(−1) = 0.5）。
深度為3的葉使用八分之一（2^(−3) = 0.125）。
在樹中的高處放置短碼字會阻止其所有後代被使用——你用一個短碼交換許多潛在的更長的碼。
構建前綴碼樹
考慮5個符號，碼長l = {1, 2, 3, 3, 3}。Kraft和 = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1。
這超過1：這些長度與前綴碼不相容。至少一個長度必須增加。
修復：將l_1從1改為2。新長度{2, 2, 3, 3, 3}：Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1。有效，但不完整。
修復：將l_1從2改為2，添加l_2 = 3以使用剩餘容量。Kraft = 0.875；剩餘 = 0.125 = 2^(−3)：還有一個深度3葉的空間。
為什麼熵約束碼長度
Kraft不等式約束碼的結構（長度必須適應樹）。Shannon熵約束碼的效率（平均長度無法超越理論下限）。
最優碼長。對於概率為p_i的符號，理想碼長是log₂(1/p_i)。罕見符號值得長碼；常見符號值得短碼。這反映了Kraft等式：當l_i = log₂(1/p_i)時，2^(−l_i) = p_i。
但log₂(1/p_i)很少是整數。四捨五入到⌈log₂(1/p_i)⌉得到Huffman長度，滿足H ≤ L < H + 1。
幾何解釋。在二叉樹的深度l_i處繪製每個符號作為一點。Kraft和測量總葉覆蓋。熵測量加權平均深度，按概率加權。Shannon定理：按概率加權的平均深度 ≥ 按概率加權的信息含量。
熵界驗證
所述例子：對於符號{A, B, C, D}，p = [1/2, 1/4, 1/8, 1/8]。
最優長度：l_A = log₂(2) = 1，l_B = log₂(4) = 2，l_C = log₂(8) = 3，l_D = log₂(8) = 3。
這些都是整數——完美匹配。Huffman碼：A=0，B=10，C=110，D=111。
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75。
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75。L = H恰好：最優碼。
完整的工作例子
完整管道：給定概率，計算熵，驗證碼滿足界限。
信源：p(A)=0.5，p(B)=0.25，p(C)=0.125，p(D)=0.125。
H = 1.75位（如上計算）。
一個簡單的塊碼：4個符號→每個2位→L = 2.0。超過熵的開銷：2.0 − 1.75 = 0.25位/符號 = 12.5%浪費。
變長碼相對於固定長度碼節省12.5%。對於大消息，這是可觀的。
英文的熵率。Shannon估計書面英文的熵約為每個字符1.0到1.3位，儘管使用5位ASCII碼。該4:1比率反映了自然語言中的大量冗餘——常見字母聚集，單詞重複，語法約束序列。
壓縮無法超越熵
壓縮比：H /（塊碼長度）。對於我們的例子：1.75/2.0 = 0.875——87.5%效率。
你能進一步壓縮嗎？只能通過使用上下文：如果你將符號對或三元組編碼在一起，聯合熵H(X,Y)可能少於2·H(X)，因為統計依賴性。這是無噪聲編碼定理對n-元組的擴展。