情報理論的な複雑性指標
情報理論的な複雑性とは
何かしらの文字列に対して、(0,1が想定されている)、その文字列がどれくらい複雑だろうか、ということを指標化しようというもの。
コルモゴロフ複雑性
概念的なもの
出力する文字列に何かしらの規則性があった時、形式的なプログラムに書き下せる。
そのプログラムの長さを複雑性としよう、という考え方。
コルモゴロフ複雑性は計算が困難だと言われる
実用的ではない。
wikipedia:コルモゴロフ複雑性
Lempel-Ziv Complexity
複雑性の指標として実用的に使われるのがLempelZiv複雑性
JPEGの圧縮などに使われる技術だが、複雑性の指標としても使われることがある。
wikipedia:Lempel–Ziv–Welch