木としてのコード
接頭辞フリーコードは二進木にマップされます。根はデコーディングの開始を表し、左の枝は0ビット、右の枝は1ビットを表し、葉は完全なコードワードを表します。
幾何学的制約：すべての葉は根から葉へのパスを終了させます。葉は子孫を持つことができません（そうすると、そのコードワードは子孫のコードワードの接頭辞になり、接頭辞フリー性に違反します）。
これはクラフト不等式に幾何学的解釈を与えます：
深さdの各葉は、全木容量の2^(−d)の割合を「占有」します。 深さDの完全二進木の全容量は1です。接頭辞フリーコードはさまざまな深さの葉を使用します。クラフト和は全占有率を測定します。
クラフト和 = 1：完全コード（すべてのパスが葉で終わる — 完全なパッキング）。
クラフト和 < 1：不完全コード（一部の木容量は未使用 — より多くの記号を追加できます）。
クラフト和 > 1：接頭辞フリーコードでは不可能（一部のパスが葉を共有する必要があります）。
より深い葉 = より長いコード = より少ない容量
深さ1の葉は、木容量の半分を使用します（2^(−1) = 0.5）。
深さ3の葉は8分の1を使用します（2^(−3) = 0.125）。
短いコードワードを木の高い位置に配置すると、そのすべての子孫が使用されるのをブロックします。1つの短いコードを多くの潜在的な長いコードと交換します。
接頭辞フリー木の構築
長さl = {1, 2, 3, 3, 3}の5つの記号を考えます。クラフト和 = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1。
これは1を超えています：これらの長さは接頭辞フリーコードと互換性がありません。少なくとも1つの長さは増加する必要があります。
修正：l_1を1から2に変更します。新しい長さ {2, 2, 3, 3, 3}：クラフト = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1。有効ですが、不完全です。
修正：l_1を2から2に変更し、l_2 = 3を追加して残りの容量を使用します。クラフト = 0.875；残り = 0.125 = 2^(−3)：もう1つの深さ3の葉のための余地があります。
エントロピーがコード長に界を設定する理由
クラフト不等式はコード構造を制約します（長さは木に収まる必要があります）。シャノンのエントロピーはコード効率を制約します（平均長は理論的下界に勝つことができません）。
最適なコード長。 確率p_iを持つ記号の場合、理想的なコード長はlog₂(1/p_i)です。珍しい記号は長いコードに値し、頻繁な記号は短いコードに値します。これはクラフト等式を反映しています：l_i = log₂(1/p_i)の場合、2^(−l_i) = p_iです。
しかし、log₂(1/p_i)はめったに整数ではありません。⌈log₂(1/p_i)⌉に切り上げるとハフマン長が得られ、H ≤ L < H + 1を満たします。
幾何学的読取。 各記号を二進木上の深さl_iの点としてプロットします。クラフト和は全葉カバレッジを測定します。エントロピーは、確率によって加重された加重平均深さを測定します。シャノンの定理：確率加重平均深さ ≥ 確率加重情報含有量。
エントロピー界の検証
実例：記号{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。
これらはすべて整数です — 完全一致。ハフマンコード：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%を節約します。大きなメッセージの場合、これは実質的です。
英語のエントロピーレート。 シャノンは、5ビットのASCIIコードを使用しているにもかかわらず、書き言葉の英語のエントロピーを1文字あたり約1.0〜1.3ビットと推定しました。その4：1の比率は、自然言語の膨大な冗長性を反映しています — 一般的な文字が集まり、単語が繰り返され、文法はシーケンスを制約します。
圧縮はエントロピーに勝つことができません
圧縮率：H / （ブロックコード長）。この例：1.75/2.0 = 0.875 — 87.5%の効率。
さらに圧縮できますか？コンテキストを使用することでのみ：記号のペアまたは3つ組を一緒にエンコードする場合、統計的依存により結合エントロピーH(X、Y)は2·H(X)未満である場合があります。これは無音声符号化定理をn-gramに拡張したものです。