こんにちは！くるです！
今回は情報源符号化の方法の1つ「ハフマン符号」について説明していきます！
ハフマン符号とは？
まずは、簡単にハフマン符号について説明しておきます。
ハフマン符号は簡単に言えば「情報を最適な形で符号化した符号」です。ハフマン符号は必ずコンパクト符号（平均符号長が最短な符号）になります。
同じ符号化としてシャノンファノ符号がありますが、あちらはコンパクト符号になるとは限りません。
その意味でシャノンファノ符号より性能の良い符号と言えるでしょう。
シャノンファノ符号と同様に、符号化には各記号の発生確率を使います。
では、ハフマン符号化のやり方について説明していきます。
ハフマン符号化のやり方
では、実際にどうやって符号化をするのかを説明していきます。
今回は次のような条件のもと符号化を行います。
符号化のやり方をステップごとに見ていきましょう！
ステップ１ 発生確率の大きい順に並び替える
まずは、それぞれの発生確率を大きい順に並び替えます。
今回の例では次のようになります。
ここで、$s_1=d,s_2=b,s_3=a,s_4=c$と置きます。すると、次のようになります。
ステップ２ 発生確率の小さい２つの記号を選び、大きい順に符号の末尾を「1」,「0」にする
今回の例では「$s_3$」,「$s_4$」がそれに該当します。なので、「$s_3$」の末尾が$1$、「$s_4$」の末尾が$0$となります。
ステップ３ ステップ２で選んだ２つの記号の発生確率を足し合わせ、新たな記号を生成する
$s_3$と$s_4$の発生確率はそれぞれ「0.2」,「0.1」なので、足し合わせて、「0.3」になります。
そして、新しい記号$s_5$を定義し、この記号の発生確率が「0.3」であるとします。
$s_3$と$s_4$から$s_5$を作ったと考えましょう。
すると、各記号とそれぞれの発生確率は次のようになります。
ステップ４ 記号が１個になるまで、ステップ１～３を繰り返す
２回目
【ステップ１】 発生確率の大きい順に並び替える
【ステップ２】 発生確率の小さい２つの記号を選び、大きい順に符号の末尾を「1」,「0」にする
$s_5$は$s_3,s_4$から生成されており、$s_5$が「1」なので、$s_3,s_4$の末尾に「1」を繋ぎます。
赤文字が今回のループで追加された符号部分です。
【ステップ３】 ステップ２で選んだ２つの記号の発生確率を足し合わせ、新たな記号を生成する
$s_5,s_2$から新たに$s_6$という記号を生成します。
３回目
【ステップ１】 発生確率の大きい順に並び替える
発生確率が同じなので、入れ替えずに次のステップへ向かいます。
入れ替えても大丈夫ですよ。
入れ替えた場合、最終的な符号の形が変わりますが、ちゃんとコンパクト符号になります。
【ステップ２】 発生確率の小さい２つの記号を選び、大きい順に符号の末尾を「1」,「0」にする
$s_6$は$s_2,s_3,s_4$から生成されており、$s_6$が「0」なので、$s_2,s_3,s_4$の末尾に「0」を繋ぎます。
【ステップ３】 ステップ２で選んだ２つの記号の発生確率を足し合わせ、新たな記号を生成する
$s_5,s_2$から新たに$s_7$という記号を生成します。
記号が１つになったので、ループ終了です。
ステップ５ 符号の完成
ステップ４の３回目より、符号は次のようになりました。
この符号の符号木は次のようになります。
ちゃんと瞬時符号になってるっすね！
また、平均符号長$L$は「各記号の発生確率と符号長の積の和」から求めることができ、
$$L=0.5×1+0.2×2+0.2×3+0.1×3=1.8$$
となります。
ハフマン符号はコンパクト符号であったので、平均符号長$1.8$が最短というわけです。
今回はここまで！
発生確率とは、記号列の中でその記号が出てくる確率です。
今回の例で言えば、$aabbcddddd$という記号列を考えると、それぞれの発生確率は上表と同じですよね？
なお、確率なので、全てを足したら「$1$」になることにも注意してください。