データ圧縮の不確定性

Robert Sedgewickの書籍アルゴリズムのデータ圧縮で不確定性について読んでいます。データ圧縮の不確定性

不確定性。

百万ビットの文字列を考えてみましょう。この文字列はランダムなように見えるので、あなたはを圧縮するロスレス圧縮アルゴリズムを見つける可能性は低いです。しかし、それは以下のプログラムによって生成されたので、ちょうど数千ビットでその文字列を表現する方法があります。

public class RandomBits 
{ 
public static void main(String[] args) 
{ 
int x = 11111; 
for (int i = 0; i < 1000000; i++) 
{ 
x = x * 314159 + 218281; 
BinaryStdOut.write(x > 0); 
} 
BinaryStdOut.close(); 
} 
}

（このプログラムは JavaのMath.random（）メソッドのようなexampleof擬似乱数発生器である。）ASCIIにプログラムを書き込むことによってを圧縮し、膨張する圧縮アルゴリズムプログラムを読んでを実行すると0.3％の圧縮率が達成されます。これはです。（これ以上のビット数を書き込むことによって、比率を任意に低くすることができます。）そのようなファイルを圧縮するには、それを生成したプログラムを発見することです。

この例では、それが最初に表示されるようにこじつけではありません。あなたがビデオやスキャナやウェブからのファイルの無数の他のタイプのいずれかでデジタル化した古い本を圧縮とき、あなたは発見をしていますファイルを作成したプログラムに関するもの。処理するデータの大部分がプログラムによって生成されていることを認識すると、計算理論で深刻な問題が発生し、はデータ圧縮の課題に洞察を与えます。だけでなく、私たちははすべてのビットストリームを圧縮アルゴリズムを持つことはできませんが、また、例えば：

、最適なデータ圧縮は（与えられた文字列を生成する最短のプログラムを見つける。）決定不可能な問題であることを証明することが可能です最適なアルゴリズムを開発するための戦略をに作成することはできません。