5

ロスレス圧縮できない文字列が1つ以上あるのではないかと思っていました。より正式には:

String文字列、f(var)の圧縮バージョンを返す圧縮関数、varg(var)のような解凍関数、g(f(var)) = varおよびstrlen(var)の長さを返す関数とするとvar、または
の有効な値はありStringますstrlen(String) < strlen(f(String))strlen(String) = strlen(f(String))

理論的な答えだけでなく、さまざまな言語やさまざまな圧縮アルゴリズムを使用した例も歓迎します。

4

3 に答える 3

12

の巣原理は、任意の圧縮関数*に対して、展開される入力文字列が常に少なくとも1つ存在する必要があることを示しています。


*つまり、少なくとも1つの入力文字列を真に圧縮する関数。

于 2013-01-01T14:48:57.740 に答える
2

私はこの文字列が法案に合うと期待します: ""

于 2013-01-01T14:52:33.273 に答える
0

はい、そして単純な理由で:たとえば、入力文字列に対して少なくとも1ビット少ない無損失の圧縮文字列を返すことを保証する関数を考えてみましょう。そのような関数が存在する場合、この同じ関数を前の結果に何度も再適用することにより、パスごとに少なくとも1ビット連続して任意の文字列を圧縮することが保証されます。したがって、損失のない圧縮を行うことができます。毎回1ビットまでの任意の長さの文字列。

明らかに、これは誤りです(一部の初期文字列はそのような最終結果をもたらす可能性があり、1ビット長の圧縮文字列に解凍アルゴリズムを適用していることを簡単に見つけることができますが、この結果をすべての非圧縮文字列に拡張することはできません)。そのような関数は存在できません。つまり、どの圧縮アルゴリズムでも、少なくとも1つの非圧縮文字列が存在します。

于 2013-01-01T18:48:25.140 に答える