ハフマン符号

情報源の記号の確率から 2 元ハフマン符号を構成し、1 記号あたりの平均符号長 $L ˉ = \sum_{i} p_{i} l_{i}$ の最小値を求め、エントロピー $H (X)$ と比べられる

前提

語頭符号とクラフトの不等式（大学数学情報理論・符号理論）
エントロピー（大学数学情報理論・符号理論）

この技能までの道筋（22 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
語頭符号とクラフトの不等式（大学数学情報理論・符号理論）
対数の定義と性質（数学II 指数関数と対数関数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
エントロピー（大学数学情報理論・符号理論）

説明

ハフマン符号は、情報源の各記号の出現確率から、1 記号あたりの平均符号長 $L ˉ = \sum_{i} p_{i} l_{i}$ が最も小さくなる語頭符号を組み立てる方法です。データ圧縮のように、よく出る記号には短い符号語を、まれな記号には長い符号語を割り当てたい場面で使います。得られた $L ˉ$ はどの語頭符号の平均符号長よりも小さいか等しく、エントロピー $H (X)$ との間に $H (X) \leq L ˉ < H (X) + 1$ が成り立ちます。

なぜそうしてよいのか

2 元語頭符号は、根から 0・1 の枝で分かれる二分木の葉に記号を置いたものと見なせます。符号長 $l_{i}$ は葉の深さです。平均符号長が最小の語頭符号（最適符号）には、次の性質をもつものがあります。(1) $p_{i} > p_{j}$ なら $l_{i} \leq l_{j}$ です。逆なら 2 つの符号語を入れ替えると $L ˉ$ が $(p_{i} - p_{j}) (l_{i} - l_{j}) > 0$ だけ減り、最適であることに反します。(2) 最も深い葉には必ず兄弟の葉があります。兄弟がなければ親の位置まで縮めても語頭符号のままで、 $L ˉ$ が減るからです。(1)(2) から、確率の最も小さい 2 記号を、最も深い位置で兄弟の葉にしておいても最適性は失われません。

そこで、確率最小の 2 記号（確率 $p_{m - 1}, p_{m}$ ）を、確率 $p_{m - 1} + p_{m}$ の 1 つの記号にまとめた $m - 1$ 記号の問題を考えます。まとめた記号の符号語に 0 と 1 を付け足すと元の 2 記号の符号語になり、そのとき $L ˉ_{元} = L ˉ_{縮小} + (p_{m - 1} + p_{m})$ が成り立ちます。足される $p_{m - 1} + p_{m}$ は符号の選び方によらない定数なので、縮小した問題で最適な符号を作れば、元の問題でも最適になります。これを記号が 1 つになるまで繰り返すのがハフマンの方法です。この式から、 $L ˉ$ は各回にまとめた確率の和の合計にも等しいことがわかります。

エントロピーとの比較も確かめておきます。 $lo g x \leq x - 1$ （自然対数）を使うと、 $H - L ˉ = \sum_{i} p_{i} lo g_{2} \frac{2 ^{- l_{i}}}{p _{i}} \leq \frac{1}{l o g 2} \sum_{i} p_{i} (\frac{2 ^{- l_{i}}}{p _{i}} - 1) = \frac{1}{l o g 2} (\sum_{i} 2^{- l_{i}} - 1) \leq 0$ です（和は $p_{i} > 0$ の記号についてとり、最後の不等号はクラフトの不等式から従います）。よって $L ˉ \geq H$ であり、等号は全ての $p_{i}$ が $2^{- l_{i}}$ の形のときに限ります。一方、 $l_{i} = ⌈ - lo g_{2} p_{i} ⌉$ と選ぶと $\sum_{i} 2^{- l_{i}} \leq \sum_{i} p_{i} = 1$ となるので、クラフトの不等式によりこの長さの語頭符号が存在します。その平均符号長は $H + 1$ 未満です。ハフマン符号はこれ以下なので、 $L ˉ < H + 1$ が成り立ちます。

手順

記号を確率の小さい順に並べ、各記号を 1 つの節点とみなす（記号数 $m \geq 2$ とする）
確率が最も小さい 2 つの節点を選んで 1 つの新しい節点にまとめ、その確率を 2 つの和とする。2 本の枝には 0 と 1 を割り当てる
新しい節点をリストに戻して確率を並べ直し、節点が 1 つになるまで手順 2 を繰り返す（合計 $m - 1$ 回）
根から各記号の葉までの枝のラベルを順に読んで符号語とする。符号長 $l_{i}$ は葉の深さに等しい
平均符号長 $L ˉ = \sum_{i} p_{i} l_{i}$ を計算する（各回にまとめた確率の合計とも一致するので、検算に使える）
エントロピー $H (X) = - \sum_{i} p_{i} lo g_{2} p_{i}$ を求め、 $H (X) \leq L ˉ < H (X) + 1$ を確かめる

例題

情報源の記号 $A, B, C, D, E$ の出現確率がそれぞれ $0.4, 0.3, 0.15, 0.1, 0.05$ である。2 元ハフマン符号を構成し、1 記号あたりの平均符号長 $L ˉ$ （語頭符号の平均符号長の最小値）を求めよ。

例題の解答

手順 1: 確率の小さい順に並べると $E (0.05), D (0.1), C (0.15), B (0.3), A (0.4)$ となる。

手順 2・3: 最小の 2 つをまとめる操作を繰り返す。
1 回目は $E$ と $D$ をまとめて $X = 0.15$ を作る。残りは $0.15 (C), 0.15 (X), 0.3 (B), 0.4 (A)$ である。
2 回目は $C$ と $X$ をまとめて $Y = 0.3$ を作る。残りは $0.3 (B), 0.3 (Y), 0.4 (A)$ である。
3 回目は $B$ と $Y$ をまとめて $Z = 0.6$ を作る。残りは $0.4 (A), 0.6 (Z)$ である。
4 回目は $A$ と $Z$ をまとめて根（確率 $1$ ）になる。

手順 4: 根から $A$ 側の枝を 0、 $Z$ 側の枝を 1 とし、以下同様にラベルを付ける。すると $A = 0$ 、 $B = 10$ 、 $C = 110$ 、 $D = 1110$ 、 $E = 1111$ となり、符号長は $1, 2, 3, 4, 4$ である。検算すると $2^{- 1} + 2^{- 2} + 2^{- 3} + 2^{- 4} + 2^{- 4} = 1 \leq 1$ となり、クラフトの不等式を満たす。

手順 5: $L ˉ = 0.4 \cdot 1 + 0.3 \cdot 2 + 0.15 \cdot 3 + 0.1 \cdot 4 + 0.05 \cdot 4 = 0.4 + 0.6 + 0.45 + 0.4 + 0.2 = 2.05$ となる。まとめた確率の合計 $0.15 + 0.3 + 0.6 + 1 = 2.05$ とも一致する。

手順 6: $H (X) = - (0.4 lo g_{2} 0.4 + 0.3 lo g_{2} 0.3 + 0.15 lo g_{2} 0.15 + 0.1 lo g_{2} 0.1 + 0.05 lo g_{2} 0.05) \approx 2.009$ である。したがって $H (X) \leq L ˉ = 2.05 < H (X) + 1$ が成り立つ。

答えは $L ˉ = 2.05 = \frac{41}{20}$ である。

答え: $\frac{41}{20}$

よくある誤り

まとめてできた節点をリストに戻さず、直前の節点に次の記号を一つずつつなげてしまう誤り。確率 $0.3, 0.3, 0.2, 0.2$ の場合、 $0.2 + 0.2 = 0.4$ の次に $0.4$ と $0.3$ をまとめると、符号長は $1, 2, 3, 3$ となり $L ˉ = 2.1$ になってしまう。正しくは、新しい節点も含めて最小の 2 つを選ぶ。次は $0.3 + 0.3$ をまとめるので、符号長はすべて 2、 $L ˉ = 2$ となる。
平均符号長を符号長の単純な平均 $\frac{1}{m} \sum_{i} l_{i}$ としてしまう誤り。例題では $\frac{1 + 2 + 3 + 4 + 4}{5} = 2.8$ となってしまう。正しくは確率で重みを付けた期待値 $\sum_{i} p_{i} l_{i} = 2.05$ である。
確率が同じ節点があるとき、ハフマン符号はただ一つに決まると考える誤り。確率 $0.4, 0.2, 0.2, 0.1, 0.1$ では、まとめ方によって符号長が $(1, 2, 3, 4, 4)$ にも $(2, 2, 2, 3, 3)$ にもなる。正しくは、符号語や符号長の組は一意でないが、 $L ˉ$ はどちらも $2.2$ で、最小値は変わらない。
平均符号長はエントロピーに等しくなる、あるいはエントロピーより小さくできると考える誤り。正しくは常に $H (X) \leq L ˉ < H (X) + 1$ である。 $L ˉ = H (X)$ となるのは、全ての $p_{i}$ が $2^{- l_{i}}$ の形のとき（例: $\frac{1}{2}, \frac{1}{4}, \frac{1}{4}$ で $L ˉ = H = 1.5$ ）に限る。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

D 元ハフマン符号（大学数学情報理論・符号理論）