データ圧縮の不確定性

Question

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％の圧縮率が達成されます。これは です。（これ以上のビット数を書き込むことによって、比率を任意に低くすることができます。 ）そのようなファイルを圧縮するには、それを生成したプログラム を発見することです。

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

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

1. 著者はこの線より上に挙げた例から、「あなたは、ファイルを作成したプログラムについてのいくつかのことを発見している」とはどういう意味ですか？

2. "プログラムは計算の理論の深い問題につながる"とは何を意味しますか？

3. 「指定された文字列を生成するための最短のプログラムを見つける」とは、何を意味しますか？

ありがとう！

Answer 1

1）ビットストリームを圧縮するには、このビットストリームを生成したアルゴリズムの実装を検索することを意味します。次に、実装のソーステキストをそのビットストリームの圧縮形式として格納します。プログラムをコンパイルして実行するだけの元のビットストリームを再作成します。

2）私にはこの本がありませんので、私はあなたに言いません。

3）1）と同じですが、文字通り：与えられたビットストリームを生成する最短のプログラムを検索します。このプログラムのソースコードは、ビットストリームの圧縮形式になります。