結論から言うと,ハフマン符号化は最適な接頭辞付き可変長符号化方法であり,その核心は「高頻度文字には短い符号,低頻度文字には長い符号」という考え方です.ハフマン木を構築して符号表を生成し,全体の符号長を最も短にします."ABRACADABRA"という11文字の例では,固定長符号化では33ビット必要なところ,ハフマン符号化ではわずか23ビットで済み,30%の削減を実現します.ハフマン符号化はDEFLATE(ZIP/GZIP/PNG)など主にな圧縮形式の中核コンポーネントであり,ほぼすべての可逆圧縮アルゴリズムがこの段階を含んでいます.本記事では頻度統計から始め,ハフマン木の構築と符号生成のプロセスを段階的に解説します.
可逆圧縮と非可逆圧縮の違いにまだ馴染みがない場合は、まず可逆圧縮 vs 非可逆圧縮：核心のな違いをご覧ください。
1. なぜ可変長符号化が必要なのか
コンピュータが文字を保存する際には,通常,固定長符号化が使われます.例えばASCIIは各文字に8ビット,Unicodeは各文字に16〜32ビットを割り当てます.固定長符号化の利点はランダムアクセスが容易なことですが,非効率でもあります.英文テキストで文字'e'の出現頻度は約12.7%であるのに対し,'z'はわずか0.07%です.両方に同じ長さの符号を割り当てるのは明らかに不合理です.可変長符号化は,文字の出現頻度に応じて異なる長さの符号語を割り当て,頻度が高いほど符号語を短くすることで,全体のサイズを圧縮ます.
| 符号化方法 | 原理 | 符号語長 | 復号の曖昧さ | 代表のな用途 |
|---|---|---|---|---|
| 固定長符号化 | 各文字に固定Nビット | 固定 | 曖昧さなし | ASCII, Unicode |
| 可変長符号化(非接頭辞) | 頻度に応じて異なる長さ | 可変 | 曖昧さが生じうる | 実用的でない |
| ハフマン接頭辞符号化 | 頻度に応じて+接頭辞制約 | 可変 | 曖昧さなし | DEFLATE, JPEG |
| 算術符号化 | メッセージ全体を1つの数に | 小数レベル | 曖昧さなし | ZSTD, brotli |
ハフマン符号化の重要な制約は「接頭辞符号」です.どの文字の符号も,他の文字の符号の接頭辞になってはいけません.例えば文字Aの符号が"0"なら,他の文字の符号は"0"で始まってはならず,"1"で始まる必要があります.こうすることで,復号時に1ビットずつ読み取り,完全な符号語に達した時点で即座に復号でき,曖昧さが生じません.
2. ハフマン符号化の原理を詳しく解説
ハフマン符号化の生成は3つのステップで行われます.頻度統計,ハフマン木の構築,符号表の生成です.プロセス全体は貪欲アルゴリズムであり,毎回最も頻度の低い2つのノードをマージして,最も終のに最適な二分木を形成します.
2.1 頻度統計
最初のステップは、入力データ内の各文字の出現頻度を統計することです。"ABRACADABRA"を例におり、各文字の出現回数を統計します。
| 文字 | 出現回数 | 頻度(%) | 固定長符号(3ビット) |
|---|---|---|---|
| A | 5 | 45.5% | 000 |
| B | 2 | 18.2% | 001 |
| R | 2 | 18.2% | 010 |
| C | 1 | 9.1% | 011 |
| D | 1 | 9.1% | 100 |
5種類の文字の場合,固定長符号化にはceil(log2(5))=3ビット/文字が必要で,11文字で合計33ビットになります.ASCII符号化では11×8=88ビットが必要なので,固定長3ビットでもすでに70%削減できていますが,ハフマン符号化でさらに圧縮できます.
2.2 ハフマン木の構築
ハフマン木の構築は貪欲なプロセスです。毎回、すべてのノードの中から最も頻度の低い2つを選び出し、それらをマージして新しいノードとします。新しいノードの頻度は2つの合計値です。これを1つのルートノードだけになるまで繰り返します。
| ステップ | 操作 | マージ前の最も低2ノード | マージ後の新ノード | 残りのノード |
|---|---|---|---|---|
| 1 | C(1)とD(1)をマージ | C:1, D:1 | CD:2 | A:5, B:2, R:2, CD:2 |
| 2 | B(2)とR(2)をマージ | B:2, R:2 | BR:4 | A:5, CD:2, BR:4 |
| 3 | CD(2)とBR(4)をマージ | CD:2, BR:4 | CDBR:6 | A:5, CDBR:6 |
| 4 | A(5)とCDBR(6)をマージ | A:5, CDBR:6 | Root:11 | 完 |
構築が完したら,ルートノードから出発し,左の分岐を0,右の分岐を1とマークします.各葉ノードに至るまでの経路が,その文字のハフマン符号になります.最も頻度の高いA(5回)は木の第2層にあり,符号はわずか1ビットです.最も頻度の低いCとDは最も深い層にあり,符号は3ビットです.
2.3 符号表の生成
ハフマン木のルートノードから各葉ノードまでを走査し,経路上の0/1の並びを記録すると,符号表が得られます.
| 文字 | 頻度 | ハフマン符号 | 符号長 | 符号への貢献(ビット) |
|---|---|---|---|---|
| A | 5回 | 0 | 1 | 5×1=5 |
| B | 2回 | 100 | 3 | 2×3=6 |
| R | 2回 | 101 | 3 | 2×3=6 |
| C | 1回 | 110 | 3 | 1×3=3 |
| D | 1回 | 111 | 3 | 1×3=3 |
接頭辞符号特性を検証します.Aの符号"0"は他のどの符号の接頭辞にもなっていません.B"100",R"101",C"110",D"111"は互いに接頭辞の関係にありません.復号時には1ビットずつ読み取り,"0"が来ればA,"1"が来ればさらに2ビット読んでB/R/C/Dを区別できるため,曖昧さは生じません.
3. 実践例:"ABRACADABRA"の符号化比較
生成した符号表を使って"ABRACADABRA"を完全に符号化し,固定長符号化とハフマン符号化のサイズの違いを比較します.
原文： A B R A C A D A B R A（11文字）
符号化プロセス:
| 位置 | 文字 | ハフマン符号 | 累計ビット |
|---|---|---|---|
| 1 | A | 0 | 1 |
| 2 | B | 100 | 4 |
| 3 | R | 101 | 7 |
| 4 | A | 0 | 8 |
| 5 | C | 110 | 11 |
| 6 | A | 0 | 12 |
| 7 | D | 111 | 15 |
| 8 | A | 0 | 16 |
| 9 | B | 100 | 19 |
| 10 | R | 101 | 22 |
| 11 | A | 0 | 23 |
符号化効率の比較:
| 符号化方法 | 1文字あたりのビット | 総ビット数 | 総バイト | ASCII比圧縮率 |
|---|---|---|---|---|
| ASCII符号化 | 8 | 88 | 11 | —（基準） |
| 固定長3ビット符号化 | 3 | 33 | 5 | 62.5% |
| ハフマン符号化 | 2.09（平均） | 23 | 3 | 73.9% |
| 理論エントロピー下限 | 2.04 | 22.5 | 3 | 74.4% |
結果： ハフマン符号化により,11文字がASCIIの88ビットから23ビットに圧縮され,73.9%削減されました.固定長3ビット符号化と比較しても30%削減されています.理論エントロピー下限は22.5ビットで,ハフマン符号化は理論最適値よりわずか0.5ビット多いだけであり,効率は97.8%に達します.これこそがハフマン符号化が「最適接頭辞符号」と呼ばれる理由です.
4. ハフマン符号化の主にな圧縮アルゴリズムへの応用
ハフマン符号化が単独で使われることはほとんどなく,通常は圧縮パイプラインの最後の段階であるエントロピー符号化として使用されます.まずLZ77などの辞書アルゴリズムで重複パターンを除去し,その後ハフマン符号化で残差データに対して頻度圧縮を行います.以下の表に,主にな圧縮形式におけるハフマン符号の適用方法を示します.
| 圧縮形式 | 辞書段階 | エントロピー符号化段階 | ハフマンの変種 | 典型的な圧縮率 |
|---|---|---|---|---|
| DEFLATE (ZIP/GZIP) | LZ77 | ハフマン | 静的+動的ハフマン | 50%–70% |
| PNG | LZ77 | ハフマン | DEFLATE内蔵ハフマン | 50%–75% |
| JPEG | DCT変換 | ハフマン | DC/AC係数を別々に符号化 | 10:1（視覚のに可逆） |
| ZSTD | LZ77変種 | FSE/ハフマン | ある限状態エントロピー+ハフマン混合 | 60%–80% |
| brotli | LZ77+文脈 | ハフマン+算術 | 文脈ハフマン | 65%–85% |
| BZIP2 | BWT変換 | ハフマン | 複数テーブルハフマン | 70%–85% |
LZ77辞書圧縮の詳細な原理については、LZ77アルゴリズム詳解：辞書圧縮の仕組みを参照してください。PNG形式におけるDEFLATEの具体的な応用については、PNG圧縮原理の詳解をご覧ください。
5. よくある質問（FAQ）
Q1:ハフマン符号化とは何ですか?
ハフマン符号化は,最適な接頭辞付き可変長符号化方法で,1952年にDavid Huffmanによって提案されました.核心となる考え方は,出現頻度の高い文字には短い符号を,頻度の低い文字には長い符号を割り当てることで,全体の符号長を最も短にすることです.ハフマン木を構築して符号表を生成し,どの文字の符号も他の文字の符号の接頭辞にならない(接頭辞符号特性)ことを保証するため,復号時に曖昧さが生じません.
Q2:ハフマン符号化が最適な接頭辞符号である理由は?
ハフマン符号化の最適性は貪欲戦略に基づいています.毎回,頻度が最も低い2つのノードをマージし,頻度の低いノードは木の深い層(符号長が長い)に,頻度の高いノードは浅い層(符号長が短い)に配置されます.数学的に証明されているように,とえられた文字頻度分布に対して,ハフマン符号化の期待符号長は他のどの接頭辞符号の期待符号長よりも短くなく,エントロピー符号化の理論的下限(情報源エントロピーH)に達します.ABRACADABRAの例では,ハフマン符号化が23ビット,理論エントロピー下限が22.5ビットで,効率は97.8%です.
Q3:ハフマン符号化と算術符号化の違いは?
ハフマン符号化は文字レベルで符号化し,各文字に独立した可変長の符号語を割り当てます.一方,算術符号化はメッセージ全体を1つの[0,1)区間の小数にマッピングするため,より細かい粒度で符号化できます.ハフマン符号化は実装が簡単で高速ですが,文字レベルの符号化に制約されるため,情報源エントロピーに完全に迫ることはできません.算術符号化は圧縮率が高い(エントロピー値に迫れる)反面,計算複雑度が高くなります.DEFLATEはハフマン符号を,現代のZSTD/brotliは両者を組み合わせて使用しています.
Q4:ハフマン符号化はどのような圧縮形式で使われていますか?
ハフマン符号化はDEFLATE(ZIP/GZIP/PNG)の中核コンポーネントであり,LZ77と組み合わせて使用されます.ZSTDはFSE(ある限状態エントロピー符号化)をハフマン符号の代替として使用していますが,原理は共通しています.brotliやJPEG(DC/AC係数)もハフマン符号化を使用しています.ほぼすべての主にな可逆圧縮形式が,エントロピー符号化の段階でハフマン符号またはその変種を含んでいます.
まとめ
ハフマン符号化は圧縮アルゴリズムの基礎であり,その核心原理は「高頻度短符号,低頻度長符号」です.ハフマン木を構築して最適な接頭辞符号を生成します."ABRACADABRA"の例では,11文字がASCIIの88ビットから23ビットに圧縮され,効率は理論エントロピー下限の97.8%に達しました.ハフマン符号化はほぼすべての主にな可逆圧縮形式に存においてし,LZ77辞書アルゴリズムと組み合わせてDEFLATE/ZSTDなどの古典のな圧縮パイプラインを構成しています.
ハフマン符号化を理解するための3つのポイントは,1つ目は頻度統計が符号長の配分を決定すること,2つ目はハフマン木の貪欲な構築が最適性を保証すること,3つ目は接頭辞符号の制約が復号の曖昧さを防ぐことです.ハフマン符号化を理解すれば,現代のすべての圧縮アルゴリズムを理解する鍵を手に入れたことになります.
ファイルを圧縮てみませんか？SmartSlimを試す
独自開発のRust圧縮エンジンに基づき、PDF/画像/動画/Office/OFDなど10分野40以上の形式に対応。ローカル圧縮でデータは外部に送信されません。