データ構造におけるハフマンコードとエントロピー

ハフマンコード

ハフマンコードは、ロスレスデータ圧縮に一般的に使用される特定のタイプの最適なプレフィックスコードとして定義されます。

このようなコードを見つけたり実装したりするプロセスは、ハフマンコーディングによって進行します。ハフマンコーディングは、デビッドA.ハフマンが理学博士号を取得しているときに開発したアルゴリズムです。 MITの学生であり、1952年の論文「最小冗長コードの構築方法」に掲載されました。

ハフマンのアルゴリズムからの出力は、ソースシンボル（ファイル内の文字など）をエンコードするための可変長コードテーブルとして表示できます。アルゴリズムは、ソースシンボルの可能な値ごとに、推定される確率または発生頻度（重み）からこのテーブルを作成します。他のエントロピー符号化方法と同様に、より一般的なシンボルは、一般的に、あまり一般的でないシンボルよりも少ないビットを実装して表されます。ハフマンの方法は効率的に実装でき、これらの重みがソートされている場合、入力重みの数に線形な時間でコードを見つけることができます。

エントロピー

情報理論では、シャノンの情報源コーディング定理（またはノイズレスコーディング定理）は、可能なデータ圧縮の限界と、シャノンエントロピーの操作上の意味を確立することができます。

ソースコーディングの定理は、（限界では、独立して同じように分布する確率変数（i.i.d.）データのストリームの長さが無限大になる傾向があるため）、コードレート（の平均数シンボルあたりのビット数）は、情報が失われることは事実上確実ではありませんが、ソースのシャノンエントロピーよりも小さくなります。ただし、シャノンエントロピーに任意に近いコードレートを取得することは可能であり、損失の可能性はごくわずかです。

情報エントロピーは、確率的なデータソースによって情報が生成される平均レートとして定義されます。

確率変数のエントロピーを計算する

確率変数に含まれる情報の量を計算することもできます。

たとえば、確率分布pを持つ確率変数Xの情報を計算する場合、これは関数H（）として記述できます。例：H（X）

事実上、確率変数の情報を計算することは、確率変数のイベントの確率分布の情報を計算することと似ています。

確率変数の情報を計算することは、「情報エントロピー」、「シャノンエントロピー」、または単に「エントロピー」と呼ばれます。

これは、両方が用語の不確実性に関係しているという点で、類推による物理学からのエントロピーの概念に関連しています。

エントロピーの直感は、確率変数の確率分布から引き出されたイベントを表現または送信するために必要な平均ビット数として定義されるということです。

分布のシャノンエントロピーは、その分布から引き出されたイベントで予想される情報量として定義されます。

分布Pから引き出されたシンボルをエンコードするために平均して必要なビット数の下限を提供します。

エントロピーは、次のようにK個の離散状態にあるkを持つ確率変数Xに対して計算できます

H(X) = -sum(each k in K p(k) * log(p(k)))

これは、各イベントの確率の合計に各イベントの確率の対数を掛けたものの負の数を意味します。

情報と同様に、log（）関数は基数2を実装し、単位はビットです。代わりに自然対数を実装できます。

最も低いエントロピーは、確実性が1.0の確率で単一のイベントを持つ確率変数に対して計算されます。すべてのイベントが同じように実行される場合、確率変数の最大のエントロピーが可能になります。