基礎理論

文字A(出現頻度5)、B(3)、C(2)、D(1)を用いてハフマン符号を構築するとき、最初に結合する2つのノードはどれか。

ア.AとB

イ.BとC

ウ.CとD正解

エ.AとD

解説

ハフマン木は「貧乏な人から先に仲間を作る」合体ゲーム。出現頻度が最も低い2つを先に結合することで、よく使う文字ほど短い符号をもらえる仕組み。

なぜウが正解か

ウが正解。ハフマン符号の構築手順：①全ノードを頻度の昇順に並べる：D(1)、C(2)、B(3)、A(5)。②最小頻度の2ノードを取り出して結合：DとC→親ノード(1+2=3)。③新ノード(3)をB(3)、A(5)と共にキューに戻す。最初の結合は必ず頻度最小の2つ=CとD。

なぜアは間違いか

AとBは頻度が大きい組み合わせ。大きい者同士を先に結合すると符号効率が下がる（頻度大=短い符号、が崩れる）。

なぜイは間違いか

BとCは3+2=5の結合。CとD(1+2=3)より大きく、最小2つではない。

なぜエは間違いか

AとD(5+1=6)は最小と最大の組み合わせ。これもハフマン手順に反する。

出典: AI生成問題（学習用）

← 前の問題

LZW圧縮において、入力文字列「ABABABAB」を圧縮するとき、辞書に最初に登録される2文字以上のエントリとして正しいものはどれか。（初期辞書：A=0、B=1とする）

次の問題 →

1000バイトのデータを圧縮した結果650バイトになった場合の圧縮率として正しいものはどれか。