ロスレス データ圧縮の仕組み | クアンタマガジン

毎日 9 億ギガバイトを超える情報がインターネット上を行き来するため、研究者はデータをより小さなパッケージに圧縮する新しい方法を常に探しています。 最先端の技術は、伝送から意図的に情報を「失う」ことで圧縮を実現する非可逆アプローチに焦点を当てています。 たとえば、Google は最近、送信側コンピューターが画像から詳細を削除し、受信側コンピューターが人工知能を使用して欠落部分を推測するという非可逆戦略を発表しました。 Netflix でさえ、損失の多いアプローチを採用しており、ユーザーが低解像度のデバイスで視聴していることを同社が検出すると、ビデオの品質を低下させます。

対照的に、送信量は小さくなるが実質は犠牲にされないロスレス戦略については、現在ほとんど研究が進められていない。 理由？ ロスレスアプローチはすでに著しく効率的です。 これらは、JPEG 画像標準からユビキタス ソフトウェア ユーティリティ PKZip に至るまで、あらゆるものを強化します。 それもすべて、ただ単に厳しい最終試験から抜け出す方法を探していた大学院生のせいだ。

XNUMX 年前、ロバート・ファノというマサチューセッツ工科大学の教授は、情報理論のクラスの学生に、従来の期末試験を受けるか、データ圧縮のための最先端のアルゴリズムを改良するかの選択肢を与えました。 ファノは、自分がその既存のアルゴリズムの作者であること、または何年も改良を探していたことを生徒たちに伝えたかもしれないし、伝えていないかもしれません。 私たちが知っていることは、ファノが生徒たちに次のような課題を与えたということです。

文字、数字、句読点で構成されるメッセージを考えてみましょう。 このようなメッセージをエンコードする簡単な方法は、各文字に一意の 01000001 進数を割り当てることです。 たとえば、コンピュータは文字 A を 00100001 と表現し、感嘆符を XNUMX と表現する場合があります。これにより、XNUMX 桁またはビットごとに XNUMX つの固有の文字に対応する、解析が容易なコードが生成されますが、同じ数字を使用するため、非常に非効率的になります。 XNUMX 進数の値が共通エントリと非共通エントリの両方に使用されます。 より良いアプローチは、モールス信号のようなものです。頻繁に使用される文字 E は XNUMX つのドットで表されますが、あまり一般的ではない Q は、より長くて手間のかかるダッシュ-ダッシュ-ドット-ダッシュを必要とします。

しかし、モールス信号も非効率的です。 確かに、短いコードもあれば、長いコードもあります。 しかし、コードの長さはさまざまであるため、モールス信号のメッセージは、各文字の送信の間に短い沈黙期間が含まれていない限り理解できません。 実際、こうしたコストのかかる一時停止がなければ、受信者はモールス信号のダッシュ ドット-ダッシュ-ドット ドット-ドット ダッシュ ドット (「トリテ」) とダッシュ ドット-ダッシュ-ドット ドット-ドット-ダッシュ ドット (「本当」) を区別する方法がありません。 ）。

ファノは問題のこの部分を解決しました。 彼は、完全なコードと別のコードの開始の両方に同じ桁パターンを使用しない限り、コストのかかるスペースを必要とせずに、さまざまな長さのコードを使用できることに気づきました。 たとえば、文字 S が特定のメッセージで非常に一般的であるため、Fano がそのメッセージに非常に短いコード 01 を割り当てた場合、そのメッセージ内の他の文字は 01 で始まるものでエンコードされることはありません。 010、011、0101 などのコードはすべて禁止されます。 その結果、コード化されたメッセージを曖昧さなく左から右に読むことができました。 たとえば、文字 S に 01、文字 A に 000、文字 M に 001、文字 L に 1 を割り当てると、メッセージ 0100100011 は、L が XNUMX で表されているにもかかわらず、即座に「小さい」という単語に変換できます。数字、S は XNUMX 桁、その他の文字は XNUMX 桁ずつです。

コードを実際に決定するために、Fano はバイナリ ツリーを構築し、必要な各文字を視覚的な分岐の末尾に配置しました。 各文字のコードは上から下へのパスによって定義されました。 パスが左に分岐した場合、Fano は 0 を追加しました。 右側の分岐には 1 が付けられました。ツリー構造により、Fano はこれらの望ましくない重複を簡単に回避できました。Fano がツリーに文字を配置すると、その分岐は終了します。つまり、今後のコードは同じように開始できなくなります。

どの文字をどこに配置するかを決定するために、ファノは最大限の効率を得るために考えられるすべてのパターンを徹底的にテストすることもできましたが、それは非現実的でした。 そこで、代わりに彼は近似値を作成しました。すべてのメッセージについて、関連する文字を頻度ごとに整理し、その後、特定の分岐ペアの左側の文字が、メッセージ内で使用される回数とほぼ同じ回数になるように文字を分岐に割り当てます。右側の文字。 このようにして、頻繁に使用される文字は、より短く密度の低い枝に配置されることになります。 少数の高頻度文字は、多数の低頻度文字と常にバランスをとります。

その結果、驚くほど効果的な圧縮が実現しました。 しかし、それは単なる近似値にすぎませんでした。 より良い圧縮戦略が存在する必要がありました。 そこでファノは生徒たちにそれを見つけるように挑戦しました。

ファノは、対になった枝の間で可能な限りの対称性を維持しながら、上から下に木を構築しました。 彼の弟子であるデビッド・ハフマンは、プロセスをひっくり返し、同じ種類の木をボトムアップから構築しました。 ハフマンの洞察は、他に何が起こっても、効率的なコードでは最も一般的でない XNUMX つの文字が最も長い XNUMX つのコードを持つべきであるということでした。 そこで、ハフマンは最も一般的でない XNUMX つの文字を特定し、それらを分岐ペアとしてグループ化し、次にこのプロセスを繰り返し、今度は残りの文字と作成したばかりのペアの中から最も一般的ではない XNUMX つのエントリを探しました。

ファノのアプローチが行き詰まるメッセージを考えてみましょう。 「schoolroom」ではOが27回、S/C/H/L/R/Mが各XNUMX回登場する。 Fano のバランスをとるアプローチは、O と他の XNUMX つの文字を左の枝に割り当てることから始まり、これらの文字を合計 XNUMX 回使用することで、残りの文字の XNUMX つの出現のバランスがとれます。 結果のメッセージには XNUMX ビットが必要です。

対照的に、ハフマンは、珍しい XNUMX つの文字、たとえば R と M から始めて、それらをグループ化し、そのペアを XNUMX つの文字のように扱います。

次に、彼の更新された頻度チャートは、XNUMX つの選択肢を提示します。XNUMX 回出現する O、機能的に XNUMX 回使用される新しい結合 RM ノード、および XNUMX つの文字 S、C、H、L です。ハフマンは再び、最も一般的ではない XNUMX つの選択肢を選択し、一致します。 （言う）HとL。

チャートが再度更新されます。O の重みは依然として 4 ですが、RM と HL の重みはそれぞれ 2 になり、文字 S と C は独立しています。 ハフマンはそこから続行し、各ステップで最も頻度の低い XNUMX つのオプションをグループ化し、ツリーと頻度グラフの両方を更新します。

最終的に、「schoolroom」は 11101111110000110110000101 となり、Fano のトップダウン アプローチから少し外れます。

XNUMX ビットでは大したことではないように聞こえるかもしれませんが、たとえ少額の節約であっても、数十億ギガバイト単位で拡張すると、大幅に増加します。

実際、ハフマンのアプローチは非常に強力であることが判明し、現在、ほぼすべての可逆圧縮戦略でハフマンの洞察が全体または部分的に使用されています。 Word 文書を圧縮するには PKZip が必要ですか? 最初のステップには、繰り返しを特定してメッセージ サイズを圧縮するためのさらに別の賢い戦略が含まれますが、XNUMX 番目のステップでは、結果として得られる圧縮メッセージを取得し、ハフマン プロセスを通して実行します。 画像をJPEGとして保存しますか? コンピュータはまず画像をテキストベースの表現に変換し、次に再びハフマン エンコーディングを使用してそのテキストを圧縮します。

もともと最終試験をスキップしたいという大学院生の願望によって動機付けられたプロジェクトとしては悪くありません。