ファイル圧縮の仕組み

先ほどの例では、繰り返される単語をすべてピックアップして、それを辞書に入れました。 これは、私たちにとって、辞書を作成する最も明白な方法です。 しかし、圧縮プログラムは全く異なる方法で辞書を作成します。 圧縮プログラムは、別々の単語という概念を持たず、パターンを探すだけです。

この観点からフレーズにアプローチすると、まったく異なる辞書ができあがります。

圧縮プログラムがケネディ氏のフレーズをスキャンした場合、最初に遭遇する冗長性は、わずか数文字の長さです。 ask not what your」では、「not」と「what」の間に、「t」の文字の後にスペースを置くパターンが繰り返されています。 圧縮プログラムがこれを辞書に書き込んだ場合、「t」の後にスペースが続くたびに「1」が書き込まれることになります。

次にプログラムが気づくのは、”your “と “country “の両方に出てくる “ou “です。 この文書がもっと長いものであれば、このパターンを辞書に書き込むことで、かなりのスペースを節約することができます。 しかし、圧縮プログラムがこの文章を読んでいるうちに、すぐに辞書登録に適した選択肢が見つかるはずです。 ou “が繰り返されているだけでなく、”your “と “country “という単語全体が繰り返されており、実際に “your country “というフレーズとして一緒に繰り返されているのです。

“can do for “というフレーズも、”your “と “you “が繰り返され、”can do for you “という繰り返しパターンになっています。 この場合、1つの数値で15文字（スペースを含む）を書くことができますが、「your country」では1つの数値で13文字（スペースを含む）しか書くことができないので、プログラムは「your country」の項目を「r country」と上書きし、「can do for you」の項目を別に作成します。 このように、プログラムは繰り返される情報をすべて拾い上げ、どのパターンを辞書に書き込むべきかを計算しながら進めていく。 このように辞書を書き換える機能が、LZ適応型辞書ベースアルゴリズムの「適応性」の部分です。

具体的にどのような方法を使用しても、この詳細な検索システムにより、単に単語を抽出するよりもはるかに効率的にファイルを圧縮することができます。

そして、次のような小さな文章があります。 “1not__2345__–__12354」

現在、文は18ユニットのメモリを使用しており、私たちの辞書は41ユニットを使用しています。 つまり、ファイルサイズの合計が79ユニットから59ユニットに圧縮されたことになります。 これは、フレーズを圧縮する一つの方法に過ぎず、必ずしも最も効率的な方法ではありません。 (より良い方法を見つけてください!)

では、このシステムはどのくらい優れているのでしょうか?

世界のほとんどの言語では、特定の文字や単語が同じパターンで現れることがよくあります。

世界のほとんどの言語では、特定の文字や単語が同じパターンで出てくることが多く、このような冗長性が高いため、テキストファイルは非常によく圧縮されます。 ほどよい大きさのテキストファイルであれば、50%以上の圧縮が可能です。 ほとんどのプログラミング言語は、比較的少ない数のコマンドを使用し、それらが同じパターンで頻繁に使用されるため、非常に冗長です。

繰り返しパターンの多いファイルでは、ファイルサイズが大きくなるにつれて、圧縮率も高くなります。 このことは、先ほどの例を見ればわかります。ケネディのスピーチがもっとあれば、辞書のパターンをより頻繁に参照することができ、各エントリのファイル容量をより多く利用できるようになります。

この効率性は、圧縮プログラムが使用する特定のアルゴリズムにも依存します。 プログラムによっては、特定の種類のファイルのパターンを拾うのに特に適しているため、より簡潔に圧縮することができます。 また、辞書の中に辞書が入っていて、大きなファイルは効率的に圧縮できても、小さなファイルは効率的に圧縮できないものもあります。 この種の圧縮プログラムはどれも基本的な考え方は同じですが、その実行方法にはかなりのバリエーションがあります。 プログラマーは常により良いシステムを構築しようとしています。