データ圧縮の限界
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/19 04:09 UTC 版)
「コルモゴロフ複雑性」の記事における「データ圧縮の限界」の解説
(可逆な) 圧縮プログラムは与えられた文字列 x に関して、文字列 y を返す関数とみることができる。 ただし y は対応する展開プログラムで x に復元できなければならない。 よって、コルモゴロフ複雑性の定義から、展開プログラムの長さと y の長さの和は x のコルモゴロフ複雑性以上でなければならない。 この意味でコルモゴロフ複雑性はその文字列データに対する究極的な圧縮を限界づけている。 通常、圧縮プログラムでは y の長さは x よりも小さくなることが期待されるが、上述の圧縮不能な文字列の議論は圧縮プログラムに関しても成立するので、実際には圧縮できない x が少なくとも半数存在し、ほとんどは大きな圧縮ができない。 圧縮プログラムが我々が扱う多くの文字列を圧縮できるようにみえるのは、我々が実際に扱う文字列が、可能なすべての文字列と比べて極めて偏ったものにすぎないからである。 また、コルモゴロフ複雑性が計算不能であるという事実は、すべての文字列 x に対してコルモゴロフ複雑性がしめす究極の圧縮を実現するプログラムを作ることが原理的に不可能であるということを意味している。もしすべての文字列をコルモゴロフ複雑性まで圧縮するプログラムが存在すれば、その出力結果の長さを数えることでコルモゴロフ複雑性が計算できてしまい、上述の事実と矛盾するからである。
※この「データ圧縮の限界」の解説は、「コルモゴロフ複雑性」の解説の一部です。
「データ圧縮の限界」を含む「コルモゴロフ複雑性」の記事については、「コルモゴロフ複雑性」の概要を参照ください。
- データ圧縮の限界のページへのリンク
