ハフマン符号化と確率が同じ場合での平均符号長の違い[情報理論]

こんにちは、ぽたです。今回は、ハフマン符号化した場合に何パターンか作れる場合ありますよね。平均符号長の長さは同じなのかと気になったので考えてみました。

ハフマン符号化とは

ハフマン符号化とは、確率が大きいもの、出てきやすいものの符号長を短く、出てきにくいものの符号長を長くすることによって全体の符号長を小さくするという符号化です。

ハフマン符号化された符号はハフマン符号と呼ばれますが、これは現代でも画像の圧縮などにも使われるので、有用性のある符号です。現在、圧縮するといわれるとファイルとか写真とかを思い浮かべるとおもいますが、大体利用されていたりします。簡単かつ効果絶大な符号になっています。

ハフマン符号化のやり方は簡単です。確率が求まっていた場合、小さい確率のものを二つ取り出し、足し算しながら符号を作っていくやり方です。実際にやってみます。例えば、

このように４つ符号があった場合を考えてみましょう。英字は符号で横の分数は確率になっています。これをハフマン符号化すると、

と、４つ符号が出てきました。小さい確率のものから足し算していくと、このような形で符号化できます。

上から平均符号長を出してみましょう。平均符号長の定義として、

ただし、ｐは確率、ｌはその符号の長さです。

確かに、符号の長さに、その確率を掛算してすべて足してあげると、全体の符号長出そうですよね。それでは上の符号を例にして平均符号長を計算してみましょう。

より、平均符号長は２とわかります。今回はすべて符号長が２だったので簡単にイメージでもわかります。

上の符号化をしているとき、少し疑問に感じませんでしたか？

同じ確率が３つある場合、どれか２つを選んで確率を足し算することになります。その場合って個々の符号の長さは変わってきます。その場合、どうなるんだ？と思っていました。一緒に考えてみましょう。例えば、

このように計算した場合、別の符号が出てきます。先ほどはすべての符号長が２だったのに対して、今回は符号長の長さが３のものが二つ、符号長の長さが２，１のものが一つずつあります。

この場合の平均符号長を計算してみると、

となるため、平均符号長は２で変わりません。

それはそうですよね。1/3のときの足し算のパターンが違うだけですが、その時にどれに符号長１を追加しても答えは変わるわけないです。

今回考えてわかったこととして、

です。実は少し友達に聞かれたのでまとめてみました。参考になれば幸いです。院試に関係することをたくさんまとめているのでぜひ見ていってください。

それではまた、ぽたでした。