情報理論と符号の基礎
ZIPやgzipなどで使われるLZ77方式の考え方として、正しいものはどれか。
- A出現する確率の高い記号に短い符号語を、低い記号に長い符号語を割り当てる
- B人の目や耳で気づきにくい成分を捨てて、データを小さくする
- C前に現れた文字列と同じ文字列を、前の位置までの距離と長さの組で置き換える
答えと解説を見る
正解：C. 前に現れた文字列と同じ文字列を、前の位置までの距離と長さの組で置き換える
LZ77方式は、すでに処理したデータを辞書のように使い、同じ文字列がもう一度現れたら、「何文字前から、何文字分」という距離と長さの組に置き換えます。記号の確率をあらかじめ知らなくても、繰り返しの多いデータを小さくでき、元のデータを完全に復元できる可逆圧縮です。ZIPやgzipのDeflate方式は、LZ77で置き換えた結果を、さらにハフマン符号で符号化しています。
- A. これはハフマン符号などの、記号の確率を使う符号化の考え方です。
- B. これはJPEGやMP3などの非可逆圧縮の考え方で、LZ77は可逆圧縮です。
- C. 正しい。繰り返し現れる文字列を、前の出現への参照で表します。