エントロピー符号化

情報理論において、エントロピー符号化（またはエントロピー符号化）とは、シャノンのソース符号化定理によって宣言された下限に近づこうとする、あらゆるロスレスデータ圧縮方法のことである。シャノンのソース符号化定理は、あらゆるロスレスデータ圧縮方法の期待コード長はソースのエントロピー以上でなければならないと述べている。 ^[¹^]^[²^]

より正確には、ソース符号化定理は、任意のソース分布に対して、期待されるコード長が以下を満たすことを述べている。 $\operatorname {E} _{x\sim P}[\ell (d(x))]\geq \operatorname {E} _{x\sim P}[-\log _{b}(P(x))]$ 、どこ $\ell$ は、コードワード内のシンボル数を指定する関数です。 $d$ はコーディング関数です。 $b$ は出力コードを作成するために使用されるシンボルの数であり、 $P$ はソースシンボルの確率です。エントロピー符号化はこの下限に近づこうとします。^{[ 2 ]}^{[ 3 ]}

最も一般的なエントロピー符号化技術の 2 つは、ハフマン符号化と算術符号化です。^{[ 4 ]}^{[ 5 ]}データストリームのおおよそのエントロピー特性が事前にわかっている場合 (特に信号圧縮の場合)、より単純な静的コードが役立つ場合があります。これらの静的コードには、ユニバーサルコード(エリアスガンマコーディングやフィボナッチコーディングなど) やゴロムコード(単項符号化やライスコーディングなど) が含まれます。^{[ 5 ]}

2014 年以降、データ圧縮機は、算術符号化の圧縮率とハフマン符号化と同様の処理コストを組み合わせることができる非対称数値システム(ANS) ファミリーのエントロピー符号化技術を使用し始めています。^[⁶^]^[¹^] ANS は、 Facebook ( Zstandard )、Apple ( LZFSE )、Google (Draco)などが開発した圧縮機に採用されています。^[⁶^]

直感的な説明

エントロピー符号化は、一部のシンボルが他のシンボルよりも頻繁に出現するという事実を利用します。シンボルの確率が不均等な場合、一部の結果はより予測可能になり、この予測可能性を使用してデータをより少ないビットで表現できます。逆に、すべてのシンボルが等しい確率で出現する場合、各シンボルは可能な限り最大の情報量を持ち、圧縮は不可能です。^{[ 3 ]}^{[ 2 ]}

圧縮が不可能な場合：表と裏がそれぞれ確率 0.5 で発生する独立した公平なコイン投げのストリームは、シンボルあたり 1 ビットのエントロピーを持ち、これは 1 つのバイナリ数字を保存するコストとまったく同じです。すべてのシンボルがすでに可能な限り最小のスペースを占めているため、利用できる冗長性はなく、エントロピー符号化方式を使用しても平均的にデータを小さくすることはできません。同じ原理はより大きなアルファベットにも適用されます。確率 1/3 でそれぞれ発生する独立した 3 進シンボル (0、1、2) は、シンボルあたり約 1.585 ビットのエントロピーを持ち、これは 3 つのシンボルのアルファベットの最大値であり、同様に圧縮できません。^{[ 3 ]}^{[ 2 ]}

圧縮が可能な場合：同じバイナリソースが代わりに確率 0.9 で 1 を、確率 0.1 で 0 を生成する場合、エントロピーはシンボルあたり約 0.469 ビットに低下します。これは 1 ビットのストレージコストをはるかに下回ります。これは、1 が優勢であるため、各シンボルが部分的に予測可能になるためです。算術符号化などのエントロピー符号化器は、この予測可能性を利用して、より一般的なシンボルに短いコードを割り当てることで、約 2.1:1 の圧縮率を達成できます。^{[ 3 ]}^{[ 5 ]}

実例:英語のテキストには、およそ 27 文字 (26 文字とスペース) のアルファベットがあります。すべての文字が均等に出現すると仮定すると、各文字は約 4.75 ビット必要になります。しかし、文字の出現頻度は非常に不均等であり (「e」は「z」よりもはるかに多く出現する)、文字は独立していない (「u」はほぼ常に「q」の後に続く) ため、英語の真のエントロピーは、文字あたりおよそ 1.0 ～ 1.5 ビットと推定されています。この大きな差が、英語のテキストを非常に圧縮可能にしているのです。^{[ 7 ]}^{[ 3 ]}

類似性の尺度としてのエントロピー

デジタルデータを圧縮する方法としてエントロピー符号化を使用する以外にも、エントロピーエンコーダは、データストリームと既存のデータクラスとの類似度を測定するためにも使用できます。これは、データクラスごとにエントロピーコーダー/コンプレッサーを生成することによって行われます。次に、未知のデータは、非圧縮データを各コンプレッサーに入力し、どのコンプレッサーが最も高い圧縮率をもたらすかを確認することによって分類されます。最も圧縮率の高いコーダーは、おそらく未知のデータに最も類似したデータでトレーニングされたコーダーです。^[⁸^]このアプローチは、正規化圧縮距離の概念に基づいています。これは、計算不可能な正規化情報距離を近似する、圧縮に基づくパラメータフリーの普遍的な類似度メトリックです。^[⁸^]^[⁹^]

参考文献

1 2 Duda, Jarek; Tahboub, Khalid; Gadgil, Neeraj J.; Delp, Edward J. (2015年5月). 「ハフマン符号化の正確な代替としての非対称数値システムの使用」 . 2015 Picture Coding Symposium (PCS) . pp. 65–69 . doi : 10.1109/PCS.2015.7170048 . ISBN 978-1-4799-7783-3. S2CID 20260346 .
1 2 3 4シャノン、クロード E. (1948). "通信の数学的理論".ベルシステム技術ジャーナル. 27 (3): 379–423 . Bibcode : 1948BSTJ...27..379S . doi : 10.1002/j.1538-7305.1948.tb01338.x .
1 2 3 4 5カバー、トーマス M.、トーマス、ジョイ A. (2006).情報理論の基礎(第 2版). ジョンワイリー & サンズ. ISBN 978-0-471-24195-9。
↑ Huffman, David (1952). "最小冗長符号の構築方法". Proceedings of the IRE . 40 (9). Institute of Electrical and Electronics Engineers (IEEE): 1098–1101 . Bibcode : 1952PIRE...40.1098H . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .
1 2 3 Sayood, Khalid (2017).データ圧縮入門（第5版）. Morgan Kaufmann. ISBN 978-0-12-809474-7。
1 2 Duda, Jarek (2013). "非対称数体系: ハフマン符号化の速度と算術符号化の圧縮率を組み合わせたエントロピー符号化". arXiv : 1311.2540 [ cs.IT ].
↑シャノン、クロード E. ( 1951). 「印刷された英語の予測とエントロピー」。ベルシステムテクニカルジャーナル。30 (1): 50–64。Bibcode : 1951BSTJ...30... 50S。doi : 10.1002 / j.1538-7305.1951.tb01366.x。
1 2 Cilibrasi, Rudi; Vitányi, Paul MB (2005). "Clustering by Compression". IEEE Transactions on Information Theory . 51 (4): 1523– 1545. Bibcode : 2005ITIT...51.1523C . doi : 10.1109/TIT.2005.844059 . S2CID 911 .
↑ヴィタニー、ポールMB;バルバック、フランク J.チリブラシ、ルディ L.李明（2009）。「正規化された情報距離」。情報理論と統計学習。スプリンガー。土井: 10.1007/978-0-387-84816-7_3。ISBN 978-0-387-84816-7。

外部リンク

デビッド・マッケイ著『情報理論、推論、学習アルゴリズム』（2003年）は、シャノン理論とデータ圧縮（ハフマン符号化や算術符号化を含む）の入門書である。
ソースコーディング、T. Wiegandおよび H. Schwarz著(2011)。

[Duda2015-1] 1 2 Duda, Jarek; Tahboub, Khalid; Gadgil, Neeraj J.; Delp, Edward J. (2015年5月). 「ハフマン符号化の正確な代替としての非対称数値システムの使用」 . 2015 Picture Coding Symposium (PCS) . pp. 65–69 . doi : 10.1109/PCS.2015.7170048 . ISBN 978-1-4799-7783-3. S2CID 20260346 .

[Shannon1948-2] 1 2 3 4シャノン、クロード E. (1948). "通信の数学的理論".ベルシステム技術ジャーナル. 27 (3): 379–423 . Bibcode : 1948BSTJ...27..379S . doi : 10.1002/j.1538-7305.1948.tb01338.x .

[CoverThomas-3] 1 2 3 4 5カバー、トーマス M.、トーマス、ジョイ A. (2006).情報理論の基礎(第 2版). ジョンワイリー & サンズ. ISBN 978-0-471-24195-9。

[Huffman1952-4] Huffman, David (1952). "最小冗長符号の構築方法". Proceedings of the IRE . 40 (9). Institute of Electrical and Electronics Engineers (IEEE): 1098–1101 . Bibcode : 1952PIRE...40.1098H . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .

[Sayood2017-5] 1 2 3 Sayood, Khalid (2017).データ圧縮入門（第5版）. Morgan Kaufmann. ISBN 978-0-12-809474-7。

[Duda2013-6] 1 2 Duda, Jarek (2013). "非対称数体系: ハフマン符号化の速度と算術符号化の圧縮率を組み合わせたエントロピー符号化". arXiv : 1311.2540 [ cs.IT ].

[Shannon1951-7] シャノン、クロード E. ( 1951). 「印刷された英語の予測とエントロピー」。ベルシステムテクニカルジャーナル。30 (1): 50–64。Bibcode : 1951BSTJ...30... 50S。doi : 10.1002 / j.1538-7305.1951.tb01366.x。

[Cilibrasi2005-8] 1 2 Cilibrasi, Rudi; Vitányi, Paul MB (2005). "Clustering by Compression". IEEE Transactions on Information Theory . 51 (4): 1523– 1545. Bibcode : 2005ITIT...51.1523C . doi : 10.1109/TIT.2005.844059 . S2CID 911 .

[Vitanyi2009-9] ヴィタニー、ポールMB;バルバック、フランク J.チリブラシ、ルディ L.李明（2009）。「正規化された情報距離」。情報理論と統計学習。スプリンガー。土井: 10.1007/978-0-387-84816-7_3。ISBN 978-0-387-84816-7。

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[

[

エントロピー符号化

直感的な説明

類似性の尺度としてのエントロピー

関連項目

参考文献

外部リンク

関連するトピック

情報理論

シャノンの

ソース符号化定理

ロスレスデータ圧縮