エントロピー符号化

情報理論において、エントロピー符号化（またはエントロピーエンコーディング）とは、シャノンの情報源符号化定理によって宣言された下限に近づこうとする可逆データ圧縮方法である。シャノンの情報源符号化定理では、あらゆる可逆データ圧縮方法では、予想される符号長が情報源のエントロピー以上でなければならないとされている。^[1]

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

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

2014 年以降、データコンプレッサーは、算術符号化の圧縮率とハフマン符号化と同様の処理コストを組み合わせることができる、エントロピー符号化技術の非対称数値システムファミリを使用し始めました。

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

エントロピーコーディングをデジタルデータの圧縮方法として使用するほかに、エントロピーエンコーダーを使用して、データストリームと既存のデータクラス間の類似性の量を測定することもできます。これは、各データクラスに対してエントロピーコーダー/コンプレッサーを生成することによって行われます。次に、圧縮されていないデータを各コンプレッサーに送り、どのコンプレッサーが最も高い圧縮率を実現するかを調べることによって、未知のデータを分類します。最も高い圧縮率を実現するコーダーは、おそらく未知のデータに最も類似したデータでトレーニングされたコーダーです。

参照

参考文献

^ 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 。
^ Huffman, David (1952). 「最小冗長コードの構築方法」. Proceedings of the IRE . 40 (9). Institute of Electrical and Electronics Engineers (IEEE): 1098– 1101. doi :10.1109/jrproc.1952.273898. ISSN 0096-8390.

外部リンク

David MacKay (2003)著の「情報理論、推論、学習アルゴリズム」では、ハフマン符号化や算術符号化を含むシャノン理論とデータ圧縮について紹介しています。
Source Coding、T. Wiegandと H. Schwarz (2011)著。

[1] 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 。

[Huffman_1952_pp._1098–1101-2] Huffman, David (1952). 「最小冗長コードの構築方法」. Proceedings of the IRE . 40 (9). Institute of Electrical and Electronics Engineers (IEEE): 1098– 1101. doi :10.1109/jrproc.1952.273898. ISSN 0096-8390.