ファイル圧縮のしくみ

インターネットから多くのプログラムやファイルをダウンロードする場合は、おそらく以前にZIPファイルに遭遇したことがあります。この圧縮システムは、特にWebユーザーにとって非常に便利な発明です。これにより、ファイル内のビットとバイトの総数を減らして、低速のインターネット接続で高速に送信したり、ディスク上の占有スペースを減らしたりできるためです。ファイルをダウンロードすると、コンピュータはWinZipやStuffitなどのプログラムを使用して、ファイルを元のサイズに拡張します。すべてが正しく機能する場合、展開されたファイルは、圧縮される前の元のファイルと同じです。

一見、これは非常に不思議に思えます。どうすればビットとバイトの数を減らして、後でそれらの正確なビットとバイトを追加し直すことができますか？結局のところ、プロセスの背後にある基本的な考え方はかなり単純です。この記事では、圧縮の基本的なプロセスを通じて非常に小さなファイルを取得するため、この単純な方法を検討します。

ほとんどの種類のコンピュータファイルはかなり冗長です-それらは何度も何度も同じ情報をリストしています。ファイル圧縮プログラムは、単に冗長性を取り除きます。ファイル圧縮プログラムは、情報を何度もリストする代わりに、その情報を1回リストし、元のプログラムに表示されるたびにその情報を参照します。

例として、私たちがよく知っている情報の種類、つまり単語を見てみましょう。

ジョンF.ケネディの1961年の就任演説で、彼はこの有名な行を配信しました。

引用には17語が含まれ、61文字、16スペース、1ダッシュ、1ピリオドで構成されます。各文字、スペース、または句読点が1単位のメモリを占める場合、合計ファイルサイズは79単位になります。ファイルサイズを小さくするには、冗長性を探す必要があります。

すぐに、次のことに気付きます。

大文字と小文字の違いを無視すると、フレーズの約半分が冗長になります。9つの言葉-尋ねる、しない、何、あなた、国、できる、する、のために、あなた-は私たちが引用全体に必要なほとんどすべてを私たちに与えます。フレーズの後半を構成するには、前半の単語をポイントし、スペースと句読点を入力します。

次のセクションでは、ファイル圧縮システムが冗長性をどのように処理するかについて詳しく説明します。

コンテンツ

1. 冗長性とアルゴリズム
2. パターンの検索
3. 非可逆および可逆圧縮

ほとんどの圧縮プログラムは、LZ適応辞書ベースのアルゴリズムのバリエーションを使用してファイルを縮小します。「LZ」はアルゴリズムの作成者であるLempelとZivを指し、「辞書」はデータの断片をカタログ化する方法を指します。

辞書を配置するためのシステムはさまざまですが、番号付きリストのように単純な場合もあります。ケネディの有名な単語を調べるとき、繰り返される単語を選び出し、番号付きのインデックスに入れます。次に、単語全体を書き出すのではなく、単に数字を書きます。

したがって、これが私たちの辞書である場合：

私たちの文は今、「1 not 2 3 4 5 6 7 8--1 2 8 5 6 7 34 」と書かれています。 

システムを知っていれば、この辞書と数字のパターンだけを使用して、元のフレーズを簡単に再構築できます。これは、ダウンロードしたファイルを展開するときに、コンピューターの拡張プログラムが実行することです。また、自分自身を開く圧縮ファイルに遭遇した可能性もあります。この種のファイルを作成するために、プログラマーは圧縮ファイルを含む単純な拡張プログラムを組み込みます。ダウンロードされると、元のファイルを自動的に再構築します。

しかし、このシステムで実際にどれだけのスペースを節約できたでしょうか。「1not2 3 4 5 6 7 8--1 2 8 5 6 7 3 4」は、「あなたの国があなたのために何ができるかを尋ねないでください。あなたがあなたの国のために何ができるかを尋ねてください。」より確かに短いです。ただし、辞書自体をファイルと一緒に保存する必要があることに注意してください。

実際の圧縮スキームでは、さまざまなファイル要件を把握するのはかなり複雑です。しかし、私たちの目的のために、すべての文字とすべてのスペースが1単位のメモリを占めるという考えに戻りましょう。フレーズ全体が79単位を占めることはすでに見てきました。圧縮された文（スペースを含む）は37単位を占め、辞書（単語と数字）も37単位を占めます。これにより、ファイルサイズは74になるため、ファイルサイズはそれほど小さくなりません。

しかし、これはたった一文です！圧縮プログラムがケネディのスピーチの残りの部分で機能した場合、これらの単語や他の単語がさらに何度も繰り返されることが想像できます。また、次のセクションで説明するように、可能な限り最も効率的な編成を実現するために辞書を書き直すことにもなります。

前の例では、繰り返される単語をすべて選択して辞書に入れました。私たちにとって、これは辞書を書くための最も明白な方法です。しかし、圧縮プログラムはそれをまったく異なって見ます：それは別々の単語の概念を持っていません-それはパターンを探すだけです。また、ファイルサイズを可能な限り小さくするために、辞書に含めるパターンを慎重に選択します。

この観点からフレーズにアプローチすると、まったく異なる辞書になってしまいます。

圧縮プログラムがケネディのフレーズをスキャンした場合、最初に出くわす冗長性はほんの数文字の長さです。 「何を聞いてはいけない」では、「t」の後にスペースが続くパターンが繰り返されています。「not」と「what」にはスペースがあります。圧縮プログラムがこれを辞書に書き込んだ場合、「t」の後にスペースが続くたびに「1」を書き込むことができます。しかし、この短いフレーズでは、このパターンは価値のあるエントリにするのに十分ではないため、プログラムは最終的にそれを上書きします。

プログラムが次に気付くのは「ou」で、これは「your」と「country」の両方に表示されます。これがより長いドキュメントである場合、このパターンを辞書に書き込むと、多くのスペースを節約できます。「ou」は、英語ではかなり一般的な組み合わせです。しかし、圧縮プログラムがこの文を処理すると、辞書エントリのより良い選択がすぐに見つかります。「ou」が繰り返されるだけでなく、「your」と「country」という単語全体が繰り返され、実際に繰り返されます。一緒に、「あなたの国」というフレーズとして。この場合、プログラムは「ou」の辞書エントリを「yourcountry」のエントリで上書きします。

「できる」というフレーズも繰り返され、1回は「あなた」が続き、もう1回は「あなた」が続き、「あなたのためにできる」という繰り返しのパターンが得られます。これにより、1つの数値で15文字（スペースを含む）を書き込むことができますが、「yourcountry」では1つの数値で13文字（スペースを含む）しか書き込むことができないため、プログラムは「yourcountry」エントリを「r」として上書きします。国」をクリックしてから、「あなたのためにできる」という別のエントリを作成します。プログラムはこのように進行し、繰り返されるすべての情報を取得して、辞書に書き込むパターンを計算します。辞書を書き直すこの機能は、LZ適応辞書ベースのアルゴリズムの「適応」部分です。プログラムが実際にこれを行う方法は、に関する議論からわかるように、かなり複雑です。Data-Compression.com。

どの特定の方法を使用する場合でも、この詳細な検索システムを使用すると、単語を選択するだけの場合よりもはるかに効率的にファイルを圧縮できます。上で選択したパターンを使用し、スペースに「__」を追加すると、次のより大きな辞書が作成されます。

そして、この小さな文："1not__2345 __--__ 12354"

文は18単位のメモリを使用し、辞書は41単位を使用します。そのため、ファイルの合計サイズを79ユニットから59ユニットに圧縮しました。これはフレーズを圧縮する1つの方法にすぎず、必ずしも最も効率的な方法ではありません。（より良い方法を見つけることができるかどうかを確認してください！）

では、このシステムはどれほど優れているのでしょうか。ファイル・縮小率は、ファイルタイプ、ファイルサイズ、圧縮方式を含む多くの因子に依存します。

世界のほとんどの言語では、特定の文字や単語が同じパターンで一緒に表示されることがよくあります。この高い冗長性のために、テキストファイルは非常によく圧縮されます。適切なサイズのテキストファイルの場合、50％以上の削減が一般的です。ほとんどのプログラミング言語は、比較的少数のコマンドのコレクションを使用するため、非常に冗長です。これらのコマンドは、設定されたパターンで一緒に実行されることがよくあります。グラフィックやMP3ファイルなど、多くの固有の情報を含むファイルは、多くのパターンを繰り返さないため、このシステムではあまり圧縮できません（これについては次のセクションで詳しく説明します）。

ファイルに繰り返しパターンがたくさんある場合、通常、ファイルサイズとともに縮小率が高くなります。これは、例を見るだけでわかります。ケネディのスピーチが多ければ、辞書のパターンをより頻繁に参照できるため、各エントリのファイルスペースをさらに活用できます。また、より広範なパターンがより長い作業で出現する可能性があり、より効率的な辞書を作成できるようになります。

この効率は、圧縮プログラムで使用される特定のアルゴリズムにも依存します。一部のプログラムは、特定の種類のファイルのパターンを取得するのに特に適しているため、より簡潔に圧縮する場合があります。他の辞書は辞書内にあり、大きなファイルでは効率的に圧縮されますが、小さなファイルでは圧縮されない場合があります。この種のすべての圧縮プログラムは同じ基本的な考え方で動作しますが、実際には実行方法にかなりのばらつきがあります。プログラマーは常により良いシステムを構築しようとしています。

ここで説明した種類の圧縮は、元のファイルを正確に再作成できるため、可逆圧縮と呼ばれます。すべての可逆圧縮は、送信または保存のためにファイルを「より小さな」形式に分割し、それをもう一方の端に戻して再び使用できるようにするという考えに基づいています。

非可逆圧縮の動作は大きく異なります。これらのプログラムは、単に「不要な」情報を排除し、ファイルが小さくなるように調整します。このタイプの圧縮は、かなりかさばる傾向があるビットマップ画像のファイルサイズを縮小するためによく使用されます。これがどのように機能するかを確認するために、コンピューターがスキャンした写真をどのように圧縮するかを考えてみましょう。

可逆圧縮プログラムは、このタイプのファイルでは多くのことを実行できません。画像の大部分は同じように見えるかもしれませんが（たとえば、空全体が青い）、個々のピクセルのほとんどは少し異なります。解像度を損なうことなくこの画像を小さくするには、特定のピクセルのカラー値を変更する必要があります。写真に青い空がたくさんある場合、プログラムはすべてのピクセルに使用できる1色の青を選択します。次に、プログラムはファイルを書き換えて、すべての空のピクセルの値がこの情報を参照するようにします。圧縮方式がうまく機能している場合、変更に気付くことはありませんが、ファイルサイズは大幅に削減されます。

もちろん、非可逆圧縮では、圧縮後に元のファイルを元に戻すことはできません。あなたは、圧縮プログラムによるオリジナルの再解釈に固執しています。このため、ソフトウェアアプリケーション、データベース、大統領就任式のスピーチなど、正確に再現する必要のあるものには、この種の圧縮を使用することはできません。

ファイル圧縮と関連トピックの詳細については、次のページのリンクを確認してください。

初版：2001年1月18日

ファイルの圧縮は何をしますか？

ファイル圧縮スキームの基本的なタイプは何ですか？

zipファイルはどのような圧縮を使用しますか？

ファイル圧縮は品質を低下させますか？

関連記事

その他のすばらしいリンク