61

圧縮について考えていましたが、適用できる圧縮には何らかの制限が必要なようです。そうしないと、1バイトになります。

だから私の質問は、ファイルを何回圧縮できるかということです:

  • 小さくならない？
  • ファイルが壊れる？

この 2 点は同じですか、それとも異なりますか。

収穫逓減のポイントはどこに現れますか?

これらの点はどのように見つけることができますか？

一般的に、特定のアルゴリズムや特定のファイルについて話しているのではありません。

4

15 に答える 15

74

可逆圧縮の場合、ファイルを再圧縮することで何回圧縮できるかを知る唯一の方法は、試してみることです。圧縮アルゴリズムと圧縮するファイルによって異なります。

2 つのファイルを同じ出力に圧縮することはできないため、1 バイトに減らすことはできません。解凍できるすべてのファイルを 1 バイトで表現するにはどうすればよいでしょうか?

2 番目の圧縮が機能する場合があるのは、圧縮アルゴリズムが全知の完全な圧縮を実行できないためです。実行しなければならない作業と実行にかかる時間の間にはトレードオフがあります。ファイルは、すべてのデータから、データに関するデータとデータ自体の組み合わせに変更されています。

例

例として、ランレングス エンコーディング (おそらく最も単純で有用な圧縮) を取り上げます。

04 04 04 04 43 43 43 43 51 52 11 バイト

その一連のバイトは次のように圧縮できます。

[4] 04 [4] 43 [-2] 51 52 7 バイト (括弧内はメタデータを入れています)

括弧内の正の数は繰り返し回数であり、括弧内の負の数は次の -n 文字が見つかったときに出力するコマンドです。

この場合、もう 1 つの圧縮を試すことができます。

[3] 04 [-4] 43 fe 51 52 7 バイト (fe は 2 の補数データと見なされる -2 です)

何も得られませんでした。次の反復で成長を開始します。

[-7] 03 04 fc 43 fe 51 52 8 バイト

しばらくの間、反復ごとに 1 バイト増加しますが、実際には悪化します。1 バイトは -128 までの負の数しか保持できません。ファイルの長さが 128 バイトを超えると、2 バイト増加し始めます。ファイルが大きくなるにつれて、成長はさらに悪化します。

圧縮プログラム、つまりメタデータには逆風が吹いています。また、実際のコンプレッサーの場合、ヘッダーはファイルの先頭に付けられました。つまり、最終的には、圧縮が追加されるたびにファイルが大きくなり始めるということです。

RLE は出発点です。詳細については、LZ77 (ファイルを調べてパターンを見つける) とLZ78 (辞書を作成する) を参照してください。zip のようなコンプレッサーは、多くの場合、複数のアルゴリズムを試して、最適なものを使用します。

複数の圧縮が機能したと考えられるいくつかのケースを次に示します。

  1. 私は、ディスクが付属する Amiga マガジンで働いていました。当然、ディスクをえらまで詰め込みました。私たちが使用したツールの 1 つは、実行可能ファイルをパックして、実行時に解凍して実行できるようにするものでした。解凍アルゴリズムはすべての実行可能ファイルに含まれている必要があったため、小さくて単純でなければなりませんでした。2 回圧縮することで、多くの場合、追加のゲインが得られます。解凍はRAMで行われました。フロッピーの読み取りが遅かったので、速度も向上することがよくありました。
  2. Microsoft は、bmp ファイルの RLE 圧縮をサポートしています。また、多くのワード プロセッサは RLE エンコーディングを行いました。RLE ファイルは、ほとんどの場合、より優れたコンプレッサーによって大幅に圧縮できます。
  3. 私が取り組んだゲームの多くは、小さくて高速な LZ77 デコンプレッサを使用していました。ピクセルの大きな四角形を圧縮する場合 (特に背景色が多い場合、またはアニメーションの場合)、多くの場合、2 回圧縮して良好な結果を得ることができます。(理由は? ルックバック距離と長さを指定するためのビット数が非常に多いため、単一の大きな繰り返しパターンがいくつかの部分にエンコードされ、それらの部分は高度に圧縮可能です。)
于 2009-07-22T16:11:31.230 に答える
16

一般に、ほとんどのアルゴリズムでは、複数回の圧縮は役に立ちません。ただし、特殊なケースがあります。

多数の重複ファイルがある場合、zip 形式はそれぞれ個別に圧縮するため、最初の zip ファイルを圧縮して、重複する zip 情報を削除できます。具体的には、サイズが 108kb の 7 つの同一の Excel ファイルを 7-zip で圧縮すると、120kb のアーカイブになります。再度圧縮すると、18kb のアーカイブが作成されます。それを過ぎると、リターンが減少します。

于 2009-07-22T16:50:25.003 に答える
9

Nビット長のファイルがあり、元のファイルを復元できるように、ロスレスで圧縮したいとします。Nビット長の2^Nの可能なファイルがあるため、圧縮アルゴリズムはこれらのファイルの1つを2^Nの可能な他のファイルの1つに変更する必要があります。ただし、2^N個の異なるファイルをNビット未満で表現することはできません。

したがって、いくつかのファイルを取得して圧縮できる場合は、短縮するファイルのバランスをとるために、圧縮時にその長さのファイルをいくつか用意する必要があります。

つまり、圧縮アルゴリズムは特定のファイルしか圧縮できず、実際には一部のファイルを長くする必要があります。これは、平均して、ランダムファイルを圧縮してもファイルを短くすることはできませんが、長くする可能性があることを意味します。

通常、ランダムファイルを使用しないため、実用的な圧縮アルゴリズムが機能します。私たちが使用するファイルのほとんどは、テキストやプログラムの実行可能ファイル、意味のある画像など、何らかの構造やその他のプロパティを持っています。優れた圧縮アルゴリズムを使用することで、通常使用するタイプのファイルを大幅に短縮できます。

ただし、圧縮ファイルはそれらのタイプの1つではありません。圧縮アルゴリズムが優れている場合、構造と冗長性のほとんどが絞り出されており、残っているものはランダム性のように見えます。

これまで見てきたように、ランダムファイルを効果的に圧縮できる圧縮アルゴリズムはありません。これはランダムに見えるファイルにも当てはまります。したがって、圧縮ファイルを再圧縮しようとしても、大幅に短縮されることはなく、ある程度長くなる可能性があります。

したがって、圧縮アルゴリズムを有益に実行できる通常の回数は1回です。

破損は、非可逆圧縮について話しているときにのみ発生します。たとえば、JPEGファイルから画像を正確に復元できるとは限りません。これは、JPEGコンプレッサーがイメージファイルを確実に短縮できることを意味しますが、正確に回復できないという犠牲を払うだけです。多くの場合、これは画像に対しては実行できますが、テキストに対しては実行できません。特に実行可能ファイルに対しては実行できません。

この場合、破損が始まる段階はありません。圧縮を開始すると開始し、さらに圧縮すると悪化します。そのため、優れた画像処理プログラムでは、JPEGを作成するときに必要な圧縮率を指定できるため、画像の品質とファイルサイズのバランスをとることができます。ファイルサイズのコスト（一般に、ストレージよりもネット接続にとって重要です）と品質の低下のコストを比較することで、停止点を見つけます。明確な正解はありません。

于 2009-07-22T17:07:43.863 に答える
5

アルゴリズムが適切であれば、通常は 1 回の圧縮で十分です。
実際、複数回圧縮するとサイズが大きくなる可能性があります

あなたの2つのポイントは異なります。

  • 圧縮を繰り返してもサイズの改善が見られないの
    が理論上の想定条件
  • 破損を引き起こす圧縮の繰り返し
    は、実装 (またはアルゴリズム自体) のエラーである可能性があります。

次に、いくつかの例外またはバリエーションを見てみましょう。

  • 暗号化は、セキュリティを強化する目的で、サイズを縮小せずに繰り返し適用できます
    (実際には、サイズが大きくなる場合もあります) 。
  • 画像、ビデオ、またはオーディオ ファイルの圧縮が進むと、
    データが失われます(事実上、ある意味で「破損」します)。
于 2009-07-22T16:11:23.540 に答える
3

圧縮 (私はロスレスだと思っています) とは、基本的に何かをより簡潔に表現することを意味します。例えば

111111111111111

より簡潔に次のように表現できます。

15 X '1'

これはランレングス符号化と呼ばれます。コンピューターが使用できるもう 1 つの方法は、ファイル内で定期的に繰り返されるパターンを見つけることです。

これらの手法を使用できる量には明らかに限界があります。たとえば、ランレングス エンコーディングは、

15 X '1'

繰り返しパターンがないからです。同様に、パターン置換メソッドが長いパターンを 3 文字のパターンに変換する場合、残りの繰り返しパターンのみが 3 文字以下になるため、再適用してもほとんど効果がありません。一般に、すでに圧縮されているファイルに圧縮を適用すると、さまざまなオーバーヘッドが原因でファイルがわずかに大きくなります。通常、圧縮率の低いファイルに適切な圧縮を適用することは、適切な圧縮のみを適用することよりも効果が低くなります。

于 2009-07-22T16:39:23.687 に答える
1

これは究極の圧縮アルゴリズム (Python による) であり、繰り返し使用することで数字の文字列をサイズ 0 に圧縮します (これをバイトの文字列に適用する方法は読者の演習として残します)。


def compress(digitString):
    if digitString=="":
        raise "already as small as possible"
    currentLen=len(digitString)
    if digitString=="0"*currentLen:
        return "9"*(currentLen-1)
    n=str(long(digitString)-1); #convert to number and decrement
    newLen=len(n);
    return ("0"*(currentLen-newLen))+n; # add zeros to keep same length

#test it
x="12";
while not x=="":
    print x;
    x=compress(x)

プログラムは 12 11 10 09 08 07 06 05 04 03 02 01 00 9 8 7 6 5 4 3 2 1 0 を出力し、次に空の文字列を出力します。各パスで文字列を圧縮するわけではありませんが、十分な数のパスを使用すると、任意の数字文字列を長さ 0 の文字列に圧縮します。コンプレッサーを介して送信した回数を書き留めておいてください。そうしないと、元に戻すことができなくなります。

于 2009-12-18T00:07:44.023 に答える
0

それはすべてアルゴリズムに依存します。言い換えれば、問題は、最初にこのアルゴリズムを使用してファイルを何回圧縮でき、次にこれを使用して圧縮できるかということです...

于 2010-08-16T19:42:44.750 に答える
0

理論的には、私たちは決して知ることはありません。それは終わりのないものです。

コンピュータ サイエンスと数学では、完全雇用定理という用語は、あるクラスの専門家が行う特定のタスクを最適に実行できるアルゴリズムはないことを示す定理を指すために使用されてきました。このような定理により、少なくとも特定のタスクの実行方法を改善するための新しい手法を発見し続ける無限の可能性が保証されるため、この名前が付けられました。たとえば、コンパイラ作成者の完全雇用定理は、証明可能な完全なサイズ最適化コンパイラなどは存在しないと述べています。コンパイラがそのような証明を行うには、終了しない計算を検出し、それらを 1 命令の無限に削減する必要があるためです。ループ。したがって、完全であることが証明されているサイズ最適化コンパイラの存在は、存在し得ない停止問題の解決策を意味します。、証明自体が決定不能な問題になります。

（ソース）

于 2014-01-30T05:01:00.880 に答える
0

「ダブル テーブルまたはクロス マトリックス」を使用した、より高度な圧縮手法の例 また、アルゴリズムで余計な不必要な記号を排除します

[前の例] 例として、ランレングス エンコーディング (おそらく最も単純で有用な圧縮) を取り上げます。

04 04 04 04 43 43 43 43 51 52 11 バイト

その一連のバイトは次のように圧縮できます。

[4] 04 [4] 43 [-2] 51 52 7 バイト (括弧内はメタデータを入れています)

[変換] 04.43.51.52 値 4.4.**-2 圧縮

追加のシンボルを代替値として使用したさらなる圧縮

04.ABC 値 4.4.**-2 圧縮

于 2013-05-14T19:44:03.963 に答える