情報理論と符号の基礎
LZ77方式で圧縮したデータを復元する。データは「文字A」「文字B」「(距離2、長さ5)」の順に並んでいる。(距離d、長さL)は、「復元済みの文字列の末尾からd文字前の文字を末尾に写す」ことを1文字ずつL回繰り返すことを表す。復元した文字列はどれか。
- AABAB
- BABABABA
- CABAAAAA
答えと解説を見る
正解：B. ABABABA
AとBを並べた「AB」から始めます。2文字前のAを写して「ABA」、次は2文字前になったBを写して「ABAB」というように、1文字写すたびに写し元も1つ進むので、5文字写すと「ABABABA」の7文字になります。このように長さが距離より長くてもよく、写したばかりの文字を写し元に使うことで、短いパターンの長い繰り返しを1つの組で表せます。
- A. 写し元を、最初にあった2文字だけと考えています。1文字ずつ写すので、写した文字も次の写し元になります。
- B. 正しい。AB に続けて A、B、A、B、A を写し、7文字になります。
- C. 同じAを5回写していますが、1文字写すごとに末尾が進むので、2文字前の文字はAとBが交互になります。