2012年03月10日

Kolmogorov complexity はそのデータ構造を吐き出す外部からの入力のない最小プログラムのサイズで定義される．んで，シャノンの情報理論ではデータ構造はそのエントロピーのサイズまで圧縮できるとされていて，その圧縮したデータと解凍プログラムとそのデータをそのプログラムに食わせるブートストラップとを組み合わせたプログラムは元ののデータ構造を生成する一つのプログラムなので，その組み合わせたプログラムのサイズは Kolomogorov complexity より大きい．とはいえ，解凍プログラムとブートストラップは固定長であってそのサイズは元のデータが大きくなるとエントロピーに比べて十分小さい．なので，シャノンのエントロピーは Kolomogorov complexity 以上．逆に，エントロピーより小さい表現からは元データを一意に復元できないので，Kolomogorov complexity はエントロピー以上．合わせるとエントロピーと Kolomogorov complexity は同じ？

ということを悩んだ．

閑話休題．

圧縮したままのデータ上で計算ができるのは良いとして，その時間がどの位なのかが気になるところ．succinct data structure みたいにオペレーションを限ってでも一瞬で結果が返るとかの性質が実用上は欲しいかも？