← デモ一覧へ戻る

ハフマン符号化法（Huffman Coding）可視化

出現頻度の高い記号に短いビット列、低い記号に長いビット列を割り当て、全体の平均符号長を最小化する可変長接頭語コード（prefix-free code）。

ハフマン符号化法とは（概要を開く）

出現頻度（確率）の高い記号ほど短いビット列、低い記号ほど長いビット列を機械的に割り当て、平均符号長を最小化する可変長の接頭語（prefix-free）符号です。

  1. Step1: 記号と出現頻度（確率）を集計し、多い順に並べる
  2. Step2: 最小2つを親に結合（左=0, 右=1）し、1つになるまで反復
  3. Step3: 根→葉の0/1列が各記号の符号（接頭語条件を満たす）
符号木の可視化（左枝=0, 右枝=1）
ノードは頻度（重み）を表示。葉は記号:頻度。

符号表

記号頻度確率符号長さp×長さ
学習モード（構築手順の可視化）

構築ステップ

    現在のグループ（多い順/進捗反映）

    順位記号頻度確率
    解説 — 手順・計算・よくある出題

    1. 手順の要点（最短ルート）

    • 並べ替え: 出現頻度（確率）の小さい順に注目（このツールの学習モードは多い順表も併記）。
    • 結合: 最小2つを取り出して親に結合。親の重み=子の合計。
    • 符号割当: 左枝=0、右枝=1（左右は自由だが一貫性を保つ）。
    • 平均符号長: L = Σ p(i) × length(code(i))。本ツールの表「p×長さ」の総和が L。

    2. 例題の見方

    • プリセットを読み込んだら「進む」で1手ずつ結合して確認します（完成時に符号表と L を表示）。
    • 左右（0/1）を入れ替えても平均符号長 L は同じ（最適性は変わらない）。符号の形が多少違ってもOK。
    • 平均符号長 L とエントロピー H の関係は H ≤ L < H+1（非負の確率）。表示を目安に妥当性を確認。

    2.5 平均ビット長の求め方（例つき）

    各文字の「ビット長 × 出現確率」を足し合わせれば、平均ビット長（平均符号長）が求まります。

    例（符号長と確率）
    • A: 1ビット（符号 1）、確率 0.5
    • B: 2ビット（符号 10）、確率 0.3
    • C: 3ビット（符号 110）、確率 0.1
    • D: 3ビット（符号 111）、確率 0.1
    計算
    L = 1×0.5 + 2×0.3 + 3×0.1 + 3×0.1
= 0.5 + 0.6 + 0.3 + 0.3 = 1.7 ビット

    3. よくある出題とコツ

    • 符号表の空欄穴埋め: 既存の符号が互いに接頭語でないかを確認して候補を消去。二分木に置いて「すべて葉ノード」になれば瞬時復号可能。
    • 平均符号長の計算: 表の p と 長さ を掛けて足すだけ。小数第2位四捨五入などの規則に注意。
    • 結合順の同点: 同じ重みが複数あるときの選び方は自由。最終 L は同じなので焦らない。

    4. チェックリスト

    • 確率の合計が 1（または 100%）付近か。
    • 符号語が接頭語を持たない（どれも他の先頭に一致しない）。
    • L が H と H+1 の間に入っているか。

    2.6 エントロピーの求め方（式）

    • 確率の定義: p(i) = f(i) / T（f: 記号 i の頻度, T = Σ f）。
    • 平均符号長: L = Σ p(i) × ℓ(i)（ℓ: 符号語の長さ）。
    • エントロピー: H = − Σ p(i) × log₂ p(i)（p(i) > 0 のみ）。
    性質: H ≤ L < H + 1。単一記号の場合は H=0、実装では接頭語制約の便宜上 ℓ=1 を割り当て L=1。

    2.7 接頭語条件とは

    接頭語条件（prefix-free）とは、任意の2つの符号語について「一方が他方の先頭（接頭語）になっていない」ことを指します。簡単に言うと、どの符号語も他の符号語で始まらない、という条件です。