6. 情報源符号化定理とハフマン符号

情報源符号化定理は、通信時のデータ圧縮と誤り訂正のうち、/
データ圧縮に関するもので、/
任意の符号（データ）の圧縮率の下限は エントロピーの値になる、というものです。/
この定理によって、統計熱力学のエントロピーと 通信理論が結合されました。/
具体的には、各々の文字に生成確率が割り振られた符号後の、平均語長を計算すると、/
その値は、エントロピーの値を下回ることは決してない、というものです。/
シャノンの通信モデルに即して考えてみます。/
主に、データ圧縮に関する事項を指しています。/
情報源符号化定理は、エントロピーの木構造と加法性によるところが大きく、/
その意味では、決定木を基調とするアンサンブル学習の源流と言えるかも知れません。/
圧縮は、ハミング符号などの通信路符号化の前に行います。/
鉄板の手法としては、ハフマン符号があります。/
これは符号後の生起確率に応じて符号長を変えるというもので、/
これにより、それぞれの符号語の大小によって木が生成されます。/
後とはエントロピーの議論と同じく、符号語を決定するための平均質問回数が、下界としてのエントロピーの値になります。/
一般化すると二分木（ハフマン符号木 ）における平均経路長の話になります。/
こちらは、符号の平均符号長を計算した例です。/
５つの符号後があり、それぞれに確率が割り当てられています。/
ここでは、ハフマン符号ではなく、シャノン・ファノ符号を使っているため、/
符号語長はそれぞれ２，３，３になります。/
これにより平均符号長は約2.6です。/
一方、確率変数としての符号xのエントロピーは、2.23なので、/
確かに情報源符号化定理の公式の通りになっています。/
平均符号語長と、エントロピーの値の計算によって、/
符号の効率性を計算することが出来ます。/
情報源符号化定理により、エントロピーの値の値を分母にすると、/
N(ブロック長）を長くする事によって、/
符号化の効率を限りなく１に近づけることが 出来ます。/
こちらの動画では載せていませんが、 Ｎ次の拡大情報源を構成することで可能になります。/
ハフマン符号は、データ圧縮の手法です。/
手法としては、可逆圧縮になります。/
データの各要素に対して、出現頻度を計算し、/
これをもとに、ハフマン符号木とよばれる２分木を計算します。/
プログラム的には、出現頻度でソートされた各要素に対して、縮約を繰り返すアルゴリズムです。/
AからEの文字列を圧縮する方法を考えます。/
まず、各文字の生起確率を計算します。/
各文字の生起確率の和は１になります。/
生起確率がソートできれば、あとは確率の低い ノード（文字）から縮約を繰り返します。/
縮約後の確率の和は、ノードとして扱われ、前の２つのノードは参照されなくなります。/
縮約を繰り返す際には、常に最小と、次に最小のノードを選択します。/
ポイントは、幅優先探索になっていることです。/
つまり、縮約の後は、新しくできたノードも含め、必ずすべてのノードの生起確率をスキャンします。/
ここからは、ハフマン符号木が作成された後の 手順です。/
枝の方向に沿って０と１を割り当てます。/
割り当ての方向は、常に同じでなくても、/
左右で１と０が割り当てられれば 問題ありません。/
このことで、各文字に別々のビット列が割り当てられます。/
確率の小さいものから縮約したので、/
生起確率が、大きいものは小さい符号が割り当てられることになります。/
これで、各辺に生起確率が割り当てられた符号木が完成しました。/
５つのアルファベットに符号が割り当てられた結果がこちらになります。/
生起確率が一番大きいAに、一番短い符号が割り当てられています。/
ハフマン符号は可逆圧縮なので、圧縮後の文字列から元の文字列を完全に（一意に）復元できます。/
今までで作成した圧縮文字列の圧縮率を計算すると、１２パーセントになります。/
文字列が増え、生起確率の偏りが大きくなるほど、圧縮率は上がります。/