データの複雑性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/03/25 14:40 UTC 版)
情報理論において、アルゴリズム情報理論はデータとしての文字列の複雑性を扱う。 複雑な文字列は圧縮しにくい。直観的には、文字列の圧縮率は採用したコーデックで変わってくると思われる。コーデックは理論的には任意の言語について作成でき、中には非常に小さいコマンド X が非常に長い記号列(例えば 18995316)を生成するものもありうる。任意の2つのチューリング完全な言語は互いを実装できる。2つの言語による符号化の長さは変換言語の長さを上限として様々となるが、データ文字列が十分大きければその差はほとんど無視できる。 アルゴリズム的な複雑性の尺度は、無作為なノイズに高い値を割り当てる傾向がある。しかし、複雑系を研究する分野では無作為性と複雑性を区別して扱う。 情報量も複雑性の尺度として情報理論で使われることがある。
※この「データの複雑性」の解説は、「複雑性」の解説の一部です。
「データの複雑性」を含む「複雑性」の記事については、「複雑性」の概要を参照ください。
- データの複雑性のページへのリンク