圧縮不能な文字列

ウィキペディア小見出し辞書

圧縮不能な文字列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/19 04:09 UTC 版)

「コルモゴロフ複雑性」の記事における「圧縮不能な文字列」の解説

文字列 x が Ku(x) ≧ |x| となるなら x は「圧縮不能」であるという。 このような圧縮不能な文字列が存在するならどの程度存在するかを考えたい。 まず、簡単な基数 (濃度) についての考察から、ある長さの文字列 x すべての中には「圧縮不能」な文字列が少なくとも 1 つは存在していることがわかる。 なぜなら、長さ n のバイナリ列 (2 種類のアルファベットからなる文字列) は 2n 個存在するが、 それより短いバイナリ列は長さ 0 も含めて 2n - 1 しか存在しないからである。さらに同じ理由で、長さ n 以下の 2n+1 - 1 個のバイナリ列のうち、その半数より多い 2n が長さ n をもつのであるから、ある長さ以下のバイナリ列のうち圧縮不能な文字列は半数より多い。 一般に、圧縮不能の定義に自然数 c だけの余裕を入れ、Ku(x) ≧ |x| - c を満たすとした x を「c 圧縮不能」 という。 長さ n - c より短いバイナリ列の個数は、長さ n のバイナリ列と比べ、 (2n-c - 1) / 2n しかないので、 c 圧縮不能な文字列は全体の 1 - 1/2c より多い。 例えば、 c = 100 ビットだけ圧縮できるような文字列は、たかだか全体の 2-100 ∼ 10-30 しかない。 よって、ほとんどの文字列は文字列の長さと大きく違わないコルモゴロフ複雑性しかもたないだろうと結論できる。