ハフマンが最適符号を構築する方法
ハミングはハフマン符号化をグリーディアルゴリズムとして提示し、最小平均長のプレフィックスフリー符号を構築します。重要なアイデア：ツリーをボトムアップで構築し、常に最も確率の低い2つのシンボルをマージします。
フォワードパス（構築）
1. すべてのシンボルを確率でソートします。最高から最低へ。
2. 最も確率の低い2つのシンボルを取ります。確率が2つの合計に等しい新しいメタシンボルに組み合わせます。
3. メタシンボルをソートされた位置に挿入します。
4. 2つのシンボルだけが残るまで繰り返します。
5. 残りの2つのシンボルに0と1を割り当てます。
バックワードパス（符号を割り当てる）
マージをさかのぼって取り消します：各スプリットで、マージされた2つのシンボルは、統合された親と同じプレフィックスビットに加えて、追加の0（1つの子）または1（もう1つの子）を受け取ります。0/1割り当ては任意です—どちらでも有効です。
これが最適な理由：他のコードがより小さい平均長L'を持っていた場合、同じフォワード削減を適用すると、最終的には平均長が1ビット未満の2つのシンボルが生成されます—2シンボル符号では不可能です。矛盾。
アルゴリズムの追跡
ハミングの例：4つのシンボルA、B、C、Dで、p(A)=0.5、p(B)=0.25、p(C)=0.125、p(D)=0.125。
フォワードパス：
ステップ1：ソート済み：A(0.5)、B(0.25)、C(0.125)、D(0.125)。最も低い2つ：C、D。
ステップ2：CDをp=0.25でマージします。新しいリスト：A(0.5)、B(0.25)、CD(0.25)。
ステップ3：最も低い2つ：B(0.25)、CD(0.25)。BCDをp=0.5でマージします。
ステップ4：2つのシンボルが残ります：A(0.5)、BCD(0.5)。A=0、BCD=1を割り当てます。
バックワードパス：
BCD → Bは10を取得、CDは11を取得します。CD → Cは110を取得、Dは111を取得します。
最終符号：A=0（l=1）、B=10（l=2）、C=110（l=3）、D=111（l=3）。
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75ビット。
複数の有効なハフマン符号
ハミングは非一意性の2つの原因を指摘します：
1. 任意の0/1割り当て。 各スプリットで、どちらの子に0を付与するかを選択できます。0と1を全体で交換すると、同じLの異なる符号が生成されます。
2. タイブレーク。 2つのノードが等しい確率を持つ場合、どちらも「高い」（最初に統合）に配置できます。異なるタイブレーク選択により、異なる構造のツリーが生成される可能性があります—「細長い」対「茂密な」—同じLですが異なる符号長分布。
細長いツリー対茂密なツリー
細長いツリー（スキュー）： 各深さレベルに1つのシンボル（フィボナッチのような構造）。符号長は大きく変動します：1つのシンボルは短い符号を取得し、他は長い符号にカスケードします。
茂密なツリー（バランス）： シンボルは深さレベル全体に均等に分散します。符号長は平均の近くでクラスタリングされます。分散が低い。
ハミングの推奨：選択肢がある場合は、茂密なツリーを優先します。Lは同じですが、符号長の分散が小さい→デコード時間がより均一→リアルタイムアプリケーションでのバッファ要件が小さい。
符号長の分散の計算
符号長の分散：Var = E[l²] − (E[l])²
コード{A=0 l=1、B=10 l=2、C=110 l=3、D=111 l=3}でp=[0.5、0.25、0.125、0.125]の場合：
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
同じ確率のシンボルに対する別の茂密なコードは、すべての長さ2のコードを使用します：L=2、Var=0。
圧縮ゲイン対シンボル分布
ハミングのルール：ハフマン符号化はシンボル確率が大きく異なる場合にのみ利益が生じます。
等確率。 すべての2^kシンボルが等確率1/2^kを持つ場合、ハフマンはブロック符号を生成します：すべてのシンボルは長さkを取得します。L = H = k。単純なブロック符号よりゲインはありません。
スキュー確率。 1つのシンボルが支配的な場合（p >> 1/2^kその他の場合）、ハフマンはそれに非常に短い符号（長さ1または2）を割り当て、Lを劇的に減らします。
コンマコード（ハミングの用語）。各確率が残りの合計の2/3を超える場合、ハフマンは自然に生成します：p(s1)→0、p(s2)→10、p(s3)→110、...、末尾の2つの等長符号までカスケード。これはコンマコードです：1の実行後の後続の0はコンマのように機能します。
ハミングは指摘します：実世界のデータ圧縮（バックアップ、ファイルアーカイブ）は、ソースがスキュー確率を持つ場合、ストレージを半分以上削減できます—英語テキストが典型的な例です。
ハフマン対ブロック符号：数値比較
ハミングの2番目の例：p(s1)=1/3、p(s2)=1/5、p(s3)=1/6、p(s4)=1/10、p(s5)=1/12、p(s6)=1/20、p(s7)=1/30、p(s8)=1/30。
ブロック符号：8シンボル → 各3ビット → L_block = 3。
ハミングはハフマン符号を計算し、L_Huffman ≈ 2.58ビットを報告します。
節約：(3 − 2.58)/3 ≈ ブロック符号化に対して14%圧縮。
シンボル確率が大きく異なる場合（ここで1/3対1/30、10:1比率）、可変長符号化は大幅に報われます。
自己コンパイルプログラム
ハミングは第11章を印象的なアイデアで終わらせます：ハフマンエンコーダーは自分自身をエンコードできます。デコーディングツリー（デコーダーが圧縮されたメッセージの読み方を伝える）は、圧縮されたデータと一緒に送信されます。受信者は符号の事前の知識を必要としません。
エンコーダー：データをサンプリングし、確率を推定し、ハフマン符号を構築し、デコーディングツリーをヘッダーとしてエンコードし、データをエンコードします。
デコーダー：ヘッダーを読んでツリーを再構築し、それを使用してデータをデコードします。
ハミングのポイント：このパイプライン全体は、人間の関与なしでライブラリ関数として実行できます。呼び出すと、自動的に圧縮および解凍されます。最新のアーカイブ形式（ZIP、gzip、bzip2）はまさにこのパターンを実装しています。
より深い原則：インテリジェンスは固定されたコードテーブルではなく、アルゴリズムにあります。アルゴリズムは受け取るデータに適応します。これはハミングが素晴らしいエンジニアリングシステム全体で見る、パターンです：適応性は組み込まれており、ボルトで留められていません。