最近、私は 1 つの素晴らしい問題に出くわしました。それは、理解するのが簡単であると同時に、解決する方法を見つけるのが難しいというものでした。問題は：
入力からテキストを読み取り、出力に他のプログラムを表示するプログラムを作成します。印刷されたプログラムをコンパイルして実行すると、元のテキストを出力する必要があります。
入力テキストはかなり大きい (10000 文字以上) と想定されています。
唯一の (そして非常に強い) 要件は、アーカイブ (つまり、印刷されたプログラム)のサイズが元のテキストのサイズより厳密に小さくなければならないということです。これにより、次のような明白な解決策が不可能になります
std::string s;
/* read the text into s */
std::cout << "#include<iostream> int main () { std::cout<<\"" << s << "\"; }";
ここでは、いくつかのアーカイブ技術が使用されると思います。
残念ながら、そのようなプログラムは存在しません。
この理由を理解するには、少し計算する必要があります。まず、長さ n のバイナリ文字列がいくつあるか数えてみましょう。各ビットは 0 または 1 のいずれかになり、これらのビットごとに 2 つの選択肢のうちの 1 つが得られます。1 ビットあたり 2 つの選択肢と n ビットがあるため、長さ nの合計 2 n 個のバイナリ文字列が存在します。
ここで、長さ n のビット文字列を常に n 未満の長さのビット文字列に圧縮する圧縮アルゴリズムを構築したいとします。これを機能させるには、長さが n 未満の異なる文字列がいくつあるかを数え上げる必要があります。これは、長さ 0 のビット文字列の数、長さ 1 のビット文字列の数、長さ 2 のビット文字列の数を足して、n - 1 までということで得られます。この合計は次のとおりです。
2 0 + 2 1 + 2 2 + ... + 2 n - 1
数学のビットを使用して、この数が 2 n - 1 に等しいことがわかります。つまり、n 未満の長さのビット文字列の総数は、長さ n のビット文字列の数よりも 1 少なくなります。
しかし、これは問題です。長さ n の文字列を最大 n - 1 の長さの文字列に常にマップするロスレス圧縮アルゴリズムを使用するには、長さ n のすべてのビット文字列を短いビット文字列に関連付ける何らかの方法が必要です。長さ n の 2 つのビットストリングは、同じ短いビットストリームに関連付けられています。このようにして、関連する短い文字列にマッピングするだけで文字列を圧縮でき、マッピングを逆にすることで圧縮解除できます。長さ n の 2 つのビット文字列が同じ短い文字列にマップされないという制限が、これをロスレスにする理由です。長さ n の 2 つのビット文字列が同じ短いビット文字列にマップされた場合、文字列を圧縮解除するときに、圧縮した 2 つの元のビット文字列のどちらかを知る方法です。
ここで問題が発生します。長さ n の2 nの異なるビット文字列と 2 n -1 の短いビット文字列しかないため、少なくとも 2 つの長さ n のビット文字列を同じ短いビット文字列に割り当てずに、長さ n の各ビット文字列を短いビット文字列とペアにする方法はありません。ストリング。これは、私たちがどれほど懸命に努力しても、どれほど賢くても、圧縮アルゴリズムでどれほど創造的であっても、常にテキストを短くすることはできないという厳しい数学的な制限があることを意味します。
では、これは元の問題にどのように対応するのでしょうか? 少なくとも 10000 の長さのテキストの文字列を取得し、それを出力する短いプログラムを出力する必要がある場合、長さ 10000 の 2 10000 文字列のそれぞれを 2 10000 - 1 にマッピングする何らかの方法が必要になります。つまり、常に有効なプログラムを作成する必要がありますが、ここでは関係ありません。単純に、十分な短い文字列がないためです。その結果、解決したい問題は不可能になります。
そうは言っても、長さ 10000 の文字列を 1 つを除いてすべて圧縮して、より短い文字列にするプログラムを取得できる可能性があります。実際、これを行う圧縮アルゴリズムが見つかるかもしれません。つまり、1 ～ 2 10000の確率で、長さ 10000 の任意の文字列を圧縮できるということです。これは非常に高い確率であり、宇宙の生涯にわたって文字列を選び続けた場合、1 つの悪い文字列を推測することはほとんどありません。
さらに読むために、コルモゴロフ複雑度と呼ばれる情報理論の概念があります。これは、特定の文字列を生成するために必要な最小のプログラムの長さです。簡単に圧縮できる文字列 (abababababababab など) とそうでない文字列 (sdkjhdbvljkhwqe0235089 など) があります。非圧縮文字列と呼ばれる文字列が存在します。これは、文字列をこれ以上小さなスペースに圧縮できない可能性があります。これは、任意のその文字列を出力するプログラムは、少なくとも指定された文字列と同じ長さでなければなりません。Kolmogorov Complexity の適切な紹介として、Michael Sipser による「Introduction to the Theory of Computation, Second Edition」の第 6 章を参照してください。この章には、いくつかの優れた結果の優れた概要が記載されています。より厳密で詳細な調査については、「情報理論の要素」の第 14 章を読むことを検討してください。
お役に立てれば！
ASCII テキストについて話している場合は...
これは実際に実行できると思います。また、テキストが 10000 文字を超えるという制限があるのは理由があると思います (コーディングの余地を与えるため)。
ここの人々は、文字列を圧縮できないと言っていますが、それでも圧縮できます。
なんで？
要件: 元のテキストを出力する
テキストはデータではありません。入力テキストを読み取るときは、ASCII 文字 (バイト) を読み取ります。内部に印刷可能な値と印刷できない値の両方があります。
たとえば、次のようにします。
ASCII values characters
0x00 .. 0x08 NUL, (other control codes)
0x09 .. 0x0D (white-space control codes: '\t','\f','\v','\n','\r')
0x0E .. 0x1F (other control codes)
... rest of printable characters
テキストを出力として出力する必要があるため、範囲 (0x00-0x08,0x0E-0x1F) には関心がありません。元のデータではなく元のテキストを返す必要があるため、別の格納および取得メカニズム (バイナリ パターン) を使用して入力バイトを圧縮できます。保存された値の意味を再計算し、それらをバイトに再調整して印刷できます。とにかくテキストデータではないデータのみを効果的に失うため、印刷も入力もできません。WinZip がそれを行う場合、それは大きな失敗になりますが、あなたが述べた要件では、それは問題ではありません。
要件には、テキストが 10000 文字であり、255 文字中 26 文字を節約できると記載されているため、パッキングに損失がなければ、効果的に約 10% のスペースを節約できます。つまり、「解凍」を 1000 (10% 10000 の) 文字を達成できます。10 バイトのグループを 11 文字として扱い、そこから 229 の範囲の外挿法によって te 11 を外挿する必要があります。それができれば、問題は解決可能です。
それにもかかわらず、それには賢い思考と、実際に 1 キロバイトでそれを実行できるコーディング スキルが必要です。
もちろん、これは単なる概念的な回答であり、機能的な回答ではありません。これを達成できるかどうかはわかりません。
しかし、私はこれに 2 セントを与えたいという衝動に駆られました。
あなたの問題の本当の問題は、問題と要件を理解することです。
あなたが説明しているのは、本質的に自己解凍型 zip アーカイブを作成するためのプログラムですが、通常の自己解凍型 zip アーカイブは元のデータを stdout ではなくファイルに書き込むという小さな違いがあります。このようなプログラムを自分で作成したい場合は、圧縮アルゴリズムの実装がたくさんあります。または、DEFLATE (gzip で使用されるアルゴリズム) などを自分で実装することもできます。「外部」プログラムは、入力データを圧縮して解凍用のコードを出力し、圧縮されたデータをそのコードに埋め込む必要があります。
擬似コード:
string originalData;
cin >> originalData;
char * compressedData = compress(originalData);
cout << "#include<...> string decompress(char * compressedData) { ... }" << endl;
cout << "int main() { char compressedData[] = {";
(output the int values of the elements of the compressedData array)
cout << "}; cout << decompress(compressedData) << endl; return 0; }" << endl;
「文字」が「バイト」を意味すると仮定し、入力テキストに少なくともプログラミング言語と同じ数の有効な文字が含まれていると仮定すると、すべての入力に対してこれを行うことは不可能です。より小さな」プログラムは、それ自体がより短い長さの可能な入力であり、これは、可能な出力よりも多くの可能な入力があることを意味します。(「これが 1 の場合、これ以上圧縮できなかったため、以下はエンコードされていない入力です」というビットで始まるエンコード方式を使用して、出力が入力より最大で 1 ビット長くなるように調整することができます。 )
ほとんどの入力 (たとえば、主に ASCII 文字で構成され、可能なバイト値の全範囲ではない入力) に対してこれで十分であると仮定すると、答えはすぐに見つかります: gzip を使用します。それが得意です。これ以上良くなることはありません。自己解凍アーカイブを作成するか、gzip 形式を「言語」出力として扱うことができます。状況によっては、完全なプログラミング言語または実行可能ファイルを出力として使用することで効率が向上する場合がありますが、多くの場合、この問題用に設計された形式を使用することでオーバーヘッドを削減できます。gzip の方が効率的です。
これは、自己解凍アーカイブを生成するファイル アーカイバと呼ばれます。