応用情報技術者 2010年秋期午前2 問02

問題文

a, b, c, dの4文字からなるメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表は a, b, c, dの各1文字を符号化するときのビット列を表している。メッセージ中での a, b, c, dの出現頻度は、それぞれ 50%、30%、10%、10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。

🖊️ 解答を隠して解いてみる

選択肢

ア：

イ：

ウ：（正解）

エ：

🔒 解説は解答すると表示されます

平均符号長の最小化【午前2解説】

正解の理由

与えられた4通りの符号のうち、ウは「各符号語が他の符号語の先頭になっていない（プレフィックス性が成り立つ）」ため、符号列から瞬時に一意に復号可能です。さらに各文字の出現確率に基づく平均符号長を計算すると、ウが最も短くなり、

L = 0.5 \times 1 + 0.3 \times 2 + 0.1 \times 3 + 0.1 \times 3 = 1.7

（ビット）となります。他の選択肢は一意復号可能でないもの（ア・イ）や平均長が長いもの（エ）となるため、最短かつ一意復号可能なものはウです。

解法ステップ

各選択肢について「一意に復号可能（UD）」か調べる。簡易チェックとしてプレフィックス性（瞬時復号可能性）やクラフト・マクミランの条件（必要条件）を用いる。
UDであるものについて平均符号長 $L = \sum p_{i} l_{i}$ を計算する（ $p_{i}$ は確率、 $l_{i}$ は符号長）。
UDでないものは除外し、UDの中で $L$ が最小のものを選ぶ。
必要ならハフマン符号で最適性を確認する。

具体的な計算と判定（確率：a=0.5, b=0.3, c=0.1, d=0.1）：

ア: 符号長は (1,1,2,2)。クラフト和は $2^{- 1} + 2^{- 1} + 2^{- 2} + 2^{- 2} = 1.5 > 1$ → マクミラン条件違反で UD にならない。例："00" は c または a+a と解釈できる（曖昧）。
イ: 符号長は (1,2,2,2)。クラフト和は $0.5 + 3 \times 0.25 = 1.25 > 1$ → UD にならない。例：符号列 "010" は b(01)+a(0) と a(0)+c(10) で両立する。
ウ: 符号長は (1,2,3,3)。クラフト和は $0.5 + 0.25 + 0.125 + 0.125 = 1$ → プレフィックスコードが可能。実際に各語は互いに先頭になっておらずプレフィックス成立 → 一意復号可能。平均長 $L = 1.7$ 。
エ: 符号長は (2,2,2,2)。クラフト和 $= 1$ 、プレフィックス成立で UD。平均長 $L = 2.0$ 。

ハフマン符号で構築すると、最小平均長の符号割当はウと同じ（c,d をまず結合 → b と結合 → a と結合）になり、最適性が確認できる。

選択肢別の誤答解説

ア：表面上は a,b が短く見えて平均長も小さく計算できるが、a=0 と c=00 のため "00" が c と a+a のどちらとも解釈でき、復号が一意でない。したがって問題の要件（元のメッセージが一意に復号可能）を満たさない。
イ：a=0 と b=01 でプレフィックス関係があり、さらにクラフト和が $> 1$ であるため UD にできない。実例で "010" のように曖昧になる。
ウ：各符号語が互いに先頭になっておらず、プレフィックス性が成り立つ（プレフィックス成立）。平均符号長 $1.7$ は与えられた確率分布下では最小であり、ハフマン符号と一致するため最適。
エ：全語長が2でプレフィックス成立・UDだが、平均長が $2.0$ とウの $1.7$ より長い。

よくある誤解

「短い単体の符号語があると平均は常に小さくなる」：短い語があっても、それが他の語の先頭になると一意復号可能性を失い使えないため、単純に短さだけで評価できません。
「プレフィックスでないがデコード可能な場合はあり得ない」：非プレフィックスでも一意復号可能（UD）な符号は存在しますが、与えられた長さがクラフト・マクミランの必要条件を満たさない場合はそもそも UD にできません。問題では明示的に「一意に復号可能」が条件なので、まず UD の判定が必須です。
「クラフト和が1でないと最適にならない」：クラフト和 $\leq 1$ は UD の必要条件（マクミラン）で、等号はプレフィックス符号の構成が可能であることを意味しますが、最適かどうかは別に平均長の比較が必要です。

補足コラム

クラフト（Kraft）不等式：可変長の瞬時符号（プレフィックス符号）について、各符号長 $l_{i}$ が与えられるとき $\sum_{i} 2^{- l_{i}} \leq 1$ が成り立ち、等号成立なら完全に木を埋めた構成が可能です。マクミランの定理は、任意の一意復号可能符号にも同様の不等式が必要であることを示します。
ハフマン符号は与えられた確率分布に対して平均符号長を最小にする可変長プレフィックス符号を構成します。本問ではハフマンの手順（最小の2つを逐次結合）によりウの割当が得られ、平均長 1.7 が最適値となることが確認できます。
理論的下限としてシャノンエントロピー $H$ があり、本例では $H = - \sum p_{i} lo g_{2} p_{i} \approx 1.685 (bits)$ 実際の最良平均長 1.7 はエントロピーに近い良好な符号です。

FAQ

Q. クラフト和が1を超えると必ずデコード不能ですか？
A. マクミランの必要条件より、任意の一意復号可能符号についてはクラフト和

\leq 1

が成り立ちます。したがって与えられた長さでクラフト和が1を超える場合、その長さ割当で一意に復号可能な符号は存在しません。

Q. プレフィックス性と一意復号可能性の違いは？
A. プレフィックス性（瞬時復号可能）は「どの符号語も他の符号語の先頭にならない」こと。これは一意復号可能性の十分条件であり、実用的に分かりやすく安全です。ある符号が一意復号可能でもプレフィックス性を満たさないことはあり得ます（ただしマクミラン条件は満たす必要あり）。

Q. ハフマン符号で必ず整数ビット長が出る理由は？
A. ハフマン法は2分木で符号語を割り当てるため、符号長は整数（枝の深さ）になり、与えられた離散確率に対して局所最適・全体最適を達成します。

関連キーワード: 可変長符号、ハフマン符号、クラフト不等式、平均符号長、プレフィックス符号、エントロピー