基礎理論

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

ア.BA

イ.AB正解

ウ.AA

エ.BB

解説

LZW圧縮は「会話中に略語を自動で作る辞書係」。最初に「AB」という略語が生まれる——なぜなら最初の未知パターンがABだから。

なぜイが正解か

イが正解。LZWのエンコード手順：①w=A（辞書にあり）②次文字B→「AB」を辞書で探す→ない→「AB」を辞書に登録（エントリ2）→Aを出力→w=B。③次文字A→「BA」を探す→ない→「BA」を登録（エントリ3）→Bを出力。最初に登録される2文字以上のエントリはステップ②の「AB」。

なぜアは間違いか

BAは辞書への登録順では2番目（AB登録後）。最初ではない。

なぜウは間違いか

AAは入力「ABABABAB」には連続するAAパターンが存在しないため登録されない。

なぜエは間違いか

BBも同様に入力に存在しないパターン。

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

← 前の問題

文字列「AAAABBBAABBBBBB」（15文字）をランレングス符号化で圧縮した。符号化結果として正しいものはどれか。（「文字,回数」ペアで表現）

次の問題 →

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