圧縮アルゴリズムについての簡単な説明

1. 冒頭発言

お久しぶりです。白部長です。

研究であれ実践であれ、既存の問題、解決策、ボトルネック、突破口となる方向性などを深く理解するには、長期にわたる蓄積が必要です。

今日は、圧縮アルゴリズムに関するいくつかの知識ポイントについてお話します。早速、読み始めましょう!

2. 圧縮アルゴリズムの理論的基礎

エンジニアリングに適用可能なアルゴリズムはすべて、数学と情報科学に理論的根拠を持っています。

論文を書く前にシミュレーションを行う必要があるのと同じように、理論は実践のための特定の方向性と基礎を提供します。

圧縮アルゴリズムについては、「これが圧縮の限界か？改善の余地はあるか？」と自問する必要があります。

2.1 情報学の父

ここで、情報科学の父、クロード・エルウッド・シャノンについて触れなければなりません。彼の経歴を簡単に見てみましょう。

[[421668]]

クロード・エルウッド・シャノン（1916年4月30日 - 2001年2月24日）はアメリカの数学者であり、情報理論の創始者であった。

彼は1936年にミシガン大学で学士号を取得し、1940年にマサチューセッツ工科大学で修士号と博士号を取得し、1941年にベル研究所に加わった。1956年にMITの客員教授となり、1958年に終身教授となり、1978年に名誉教授となった。

シャノンは情報エントロピーの概念を提唱し、情報理論とデジタル通信の基礎を築きました。また、有名な暗号解読者でもありました。ベル研究所の彼の暗号解読チームはドイツの飛行機とロケットの追跡に重点を置いていた。

関連論文: 修士論文「リレーおよびスイッチング回路の記号解析」(1938 年)、「通信の数学的原理」(1948 年)、「ノイズに直面した通信」(1949 年)、および別の重要な論文「秘密システムの通信理論」(1949 年)。

この紹介文を読んで、一瞬にして粉々にされたような気分になりました。インターネット鬱音楽アプリを静かに開くことしかできませんでした。人間として生まれたことを後悔しています。

2.3 エントロピー

エントロピー自体は熱力学の分野における概念であり、混沌と無秩序の程度を表します。

自然の本質は無秩序と混沌であるため、これは特に有用な概念です。

不適切な例を挙げると、よく芸能ゴシップニュースを読むと、情報量が非常に多い、話題になっている、などと言われますが、その情報量とはどうやって測るのでしょうか？

前述の情報科学の父シャノンは、情報の測定の問題を解決し、無秩序で不確実な状態を数学的な言語で記述できるようにしました。

1948 年の論文「通信の数学的理論」では、著者はエントロピーと不確実性を同義で使用しました。

この記事は、情報エントロピーは情報の不確実性の尺度であると提案しています。不確実性が大きいほど、情報エントロピーも大きくなります。

論文アドレス: http://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

論文の第 6 章では、情報エントロピーのいくつかの特性と、情報エントロピーと不確実性の関係が示されています。

簡単な翻訳：

情報エントロピーは確率とともに連続的に変化します。
イベントを構成するさまざまな要因の確率が等しい場合、構成要因の総数 n が増加すると情報エントロピーが増加します。つまり、選択肢が増えるほど、不確実性が大きくなります。
選択肢を 2 つの連続する選択肢に分解できる場合、分解前と分解後のエントロピー値は等しく、不確実性も同じになります。

イベントには複数の選択肢があり、各選択肢の確率は p1、p2...pn として記録されると仮定します。この記事ではさらに、確率と情報エントロピーの式を示します。

ここで、k は正の定数です。

これまでの分析をいくつか行った後、私たちは基本的に混乱しています。難しすぎるのです。

したがって、今のところ 1 つの結論を覚えておきましょう。情報は測定可能であり、確率分布に直接関係しています。

3. データ圧縮の性質

理論的な裏付けが得られたので、データを圧縮する方法について考えてみましょう。

データ圧縮は、可逆圧縮と非可逆圧縮に分けられます。

ロスレス圧縮は、テキスト、実行可能ファイル、ソースコードなど、元の情報を完全に復元する必要がある状況に適しています。

非可逆圧縮は圧縮率が高いですが、元の情報を完全に復元することはできません。主にビデオ、オーディオ、その他のデータの圧縮に使用されます。

3.1 データ圧縮の定義

圧縮の前提は冗長性の存在です。冗長性を排除することが圧縮であり、より少ない情報で情報を完全に表現します。百科事典の定義を見てみましょう。

データ圧縮とは、有用な情報を失うことなく、データ量を減らしてストレージスペースを削減し、データの転送、保存、処理の効率を向上させることを指します。

データの冗長性とストレージスペースを削減するために、特定のアルゴリズムに従ってデータを再編成する必要がある技術的な方法。

以下に簡単な例をいくつか示します。

「北京交通大学の交通情報工学と制御専攻は良い」と「北京交通大学の交通制御専攻は良い」

上記のテキストでは、「北京交通大学」は「北交通大学」に、「交通情報工学および制御専攻」は「交通制御専攻」に置き換えることができます。

「aaaaaaaaxxxxxxkkkkkkzzzzzzzzzz」と「8a6x6k10z」

上記のテキストには明らかな局所的な繰り返しがあります。たとえば、a は 8 回、z は 10 回出現します。入力文字の分布を分析し、「繰り返し回数 + 文字数」のルールを決定すれば、置換を行うことができます。

3.2 確率分布とデータコーディング

本質的には、データ圧縮とは、圧縮するコンテンツの確率分布を見つけ、特定のエンコードアルゴリズムに従って、発生確率の高い部分をより短い形式で置き換えることです。

したがって、入力コンテンツの繰り返し部分が多いほど、圧縮できるサイズが小さくなり、圧縮率が高くなります。コンテンツに繰り返しがほとんどなく、完全にランダムな場合は、圧縮が難しくなります。

これは、コードパフォーマンスを最適化するための通常のアプローチと非常によく似ています。ホットコードを最適化すると、より大きなメリットが得られます。

3.3 データ圧縮の制限

前述のように、圧縮は長い文字列を短い文字列に置き換えることによって実現されるため、各置き換えに最短の文字列が使用される場合、最適な圧縮と見なされます。

したがって、圧縮限界に近づくためには、理論上の最短の置換文字列の長さ、つまりバイナリ単位でのバイナリ長を見つける必要があります。

分析してみましょう:

コインを投げた場合、表と裏の 2 つの結果しかあり得ないので、1 ビットのバイナリ 0 と 1 を使用すれば十分です。
バスケットボールの試合には勝ち/負け/引き分けの3つの状況があるため、2ビットのバイナリを使用する必要があります。00勝ち、01負け、10引き分け
誕生月は 1 月から 12 月まで 12 か月あるため、各月を表すには 4 ビットのバイナリが必要です。
確率がn個の異なる値を持つ場合、置換文字列はlog2(n)のバイナリビットで表現する必要がある。

コンテンツが n 個の部分で構成され、各部分が出現する確率が p1、p2、... pn であると仮定すると、置換シンボルが占める最小のバイナリ空間は次のようになります。

 log2(1/p1) + log2(1/p2) + ... + log2(1/pn) = ∑ log2(1/pn)

考えられるケースが増えるほど、必要なバイナリの長さが長くなる可能性があります。n が等しい 2 つのファイルの場合、確率 p によってこの式のサイズが決まります。

p が大きいほど、ファイルの内容は規則的になり、圧縮後のサイズは小さくなります。
p が小さいほど、ファイルの内容はランダムになり、圧縮されたファイルのサイズが大きくなります。

たとえば、A、B、C という 3 つの異なる文字を含むファイルがあるとします。50% が A、30% が B、20% が C です。ファイルには合計 1024 文字が含まれています。各文字が占めるバイナリビットの数学的期待値は次のとおりです。

 0.5*log2(1/0.5) + 0.3*log2(1/0.3) + 0.2*log2(1/0.2)=1.49

圧縮後、各文字は平均 1.49 バイナリビットを占めることがわかります。理論的には、少なくとも 1.49*1024=1526 バイナリビットが必要であり、これは約 0.1863KB です。最終的な圧縮率は 18.63% に近くなります。

4. ハフマン符号化の概要

ハフマン符号化は、ハフマンコーディングとも呼ばれるコーディング方式です。ハフマン符号化は、可変ワード長符号化 (VLC) の一種です。ハフマンは 1952 年にコーディング方法を提案しました。この方法では、文字の出現確率のみに基づいて、さまざまなレターヘッドの平均長さが最短のコードワードを構築します。この方法は最適コーディングと呼ばれることもあり、一般にハフマンコーディング (ハフマンコーディングと呼ばれることもあります) と呼ばれます。

ハフマン符号化では、可変長符号化テーブルを使用してソースシンボルを符号化します。可変長符号化テーブルは、ソースシンボルの発生確率を評価することによって取得されます。

出現確率の高い文字には短いコードが使用され、出現確率の低い文字には長いコードが使用されるため、エンコード後の文字列の合計長が短縮されます。

4.1 プレフィックスエンコーディング

可変長コードの使用に加えて、ハフマン符号化では、デコード中に一意性を保証するためにプレフィックス符号化も使用します。例:

A-0 C-1 B-00 D-01の場合、エンコードは次のようになります: 000011010

これをデコードすると、0000 は AAAA、AAB、ABA、BB などの複数のデコード方法に対応する可能性があることがわかります。

ハフマンツリーのリーフノード間には親子関係がないため、各リーフノードのコードは他のリーフノードのコードのプレフィックスになることはできません。これは非常に重要です。

4.2 ハフマン木の簡単な構築

ハフマンツリーは、ハフマンコーディングの重要な部分です。具体的な例を挙げて、ハフマンツリーの特徴をいくつか見てみましょう。

入力データ: 「おっぱいはビーボーイ」
文字列の収集と頻度の統計
- 集合 {b,o,s,i,e,y}
- 頻度 {b:4,o:3,e:2,i:1,y:1,s:1}
全部で6文字あるので3ビット必要
頻度の高い、短い文字、プレフィックスのエンコードルールに従って処理する
- 午前0時
- 午前01時
- 100倍
- 私:101
- y:110
- s:111
- 注: eは001ではありません。これはプレフィックスエンコーディングに準拠していないためです。bはeの親ノードです。

ハフマン符号化の原理と実装は比較的複雑です。スペースが限られているため、後ほど別の記事で詳しく紹介する予定です。