情報理論と符号の基礎
可逆圧縮と、情報源のエントロピーの関係の説明として、正しいものはどれか。
- A優れた可逆圧縮のアルゴリズムを使えば、どのような内容のファイルでも、必ず元より小さくできる
- B記号を独立に出す情報源でも、工夫した可逆な符号なら、平均符号長をエントロピーより小さくできる
- C可逆な符号の平均符号長はエントロピーより小さくできないが、記号をまとめて符号化すると近づけられる
答えと解説を見る
正解：C. 可逆な符号の平均符号長はエントロピーより小さくできないが、記号をまとめて符号化すると近づけられる
記号を独立に出す情報源では、可逆な符号の1記号あたりの平均符号長はエントロピー以上になり、記号をまとめて符号化すると、エントロピーにいくらでも近づけられます(情報源符号化定理)。また、nビットのファイルは2ⁿ通りあるのに、それより短いビット列は全部で 2ⁿ − 1 通りしかないので、すべてのファイルを短くできる可逆圧縮はありません。可逆圧縮は、偏りや繰り返しのあるデータを短くする代わりに、そうでないデータを少し長くしています。
- A. 鳩の巣原理から、すべてのファイルを短くすることはできません。ランダムなデータや、すでに圧縮したデータは、ほとんど小さくなりません。
- B. 平均符号長の下限がエントロピーです。それより短くしようとすると、1通りに復号できない符号になります。
- C. 正しい。エントロピーが、可逆な符号化の限界を与えます。