こんにちは！krです！
今回は情報源符号化の方法の1つ「シャノン・ファノ符号」について説明していきます！
シャノンファノ符号とは？
まずは、簡単にシャノン・ファノ符号について説明しておきます。
シャノン・ファノ符号は簡単に言えば「情報を符号化する方法」です。
どうやって符号化するんすか？
確率を使うのです！
例えば、「$a$」という記号が「$\frac{1}{3}$」、「$b$」という記号が「$\frac{2}{3}$」の確率で発生するとしたら、それぞれの確率を使って、$a, b$の符号を決めるのです。
符号化の方法はこの後説明しますが、とりあえず、シャノン・ファノ符号は「確率を使って符号を求める方法」ということを頭に入れておいてください。
あと、シャノン・ファノ符号で作られる符号は瞬時符号です。ただ、ハフマン符号とは違いコンパクト符号になるとは限りません。
シャノン・ファノ符号化のやり方
では、実際にどうやって符号化をするのかを説明していきます。
今回は次のような条件のもと符号化を行います。
符号化のやり方をステップごとに見ていきましょう！
ステップ１ 発生確率の大きい順に並び替える
まずは、それぞれの発生確率を大きい順に並び替えます。
今回の例では次のようになります。
ここで、$s_1=d, s_2=b, s_3=a, s_4=c$と置きます。
ステップ２ 符号長を決定する
次のような式を使って各符号語の符号長$l_k$を求めていきます。
$$-logP(s_k) \leq l_k \lt -logP(s_k)+1$$
例えば、$s_1=d$のとき
$$-log0.5 \leq l_1 \lt -log0.5+1$$
$$1 \leq l_1 \lt 2$$
となり、この式より、$l_1=1$と求まります。
他の$s_2=b, s_3=a, s_4=c$についても同様の計算をすると、
$$2.32… \leq l_2 \lt 3.32…$$
$$2.32… \leq l_3 \lt 3.32…$$
$$3.32… \leq l_4 \lt 4.32…$$
となり、$l_2=3, l_3=3, l_4=4$と求まります。
これで、$d$は1桁、$b$は3桁、$a$は3桁、$c$は4桁の符号で表されることが分かりました。
瞬時符号が存在するための必要十分条件であるクラフトの不等式を思い出しましょう。
$$\displaystyle \sum_{k=1}^n r^{-l_k} \leq 1$$
発生確率を全て足すと$1$になるので、
$$\displaystyle \sum_{k=1}^n P^{(s_k)} = 1$$
したがって、1つ目の式を次のように変形することが出来ます
$$\displaystyle \sum_{k=1}^n r^{-l_k} \leq \displaystyle \sum_{k=1}^n P^{(s_k)}$$
両辺総和記号を外すと、
$$r^{-l_k} \leq P^{(s_k)}$$
両辺対数をとると、
$$logr^{-l_k} \leq logP^{(s_k)}$$
$$-l_k logr \leq logP^{(s_k)} \ $$
$$-logP^{(s_k)} \leq l_k logr \quad \quad $$
$$\frac{-logP^{(s_k)}}{logr} \leq l_k \qquad \qquad \ $$
となります。よって、
$$\frac{-logP^{(s_k)}}{logr} \leq l_k \lt \frac{-logP^{(s_k)}}{logr}+1$$
となり、今回の例では$r=2$なので、
$$-logP{(s_k)} \leq l_k \lt -logP{(s_k)}+1$$
となるのです。
つまり、この式で計算した符号長$l_k$はクラフトの不等式を満たすのです。
ステップ３ 符号のもととなる確率を求める
符号長が決まったので、次は具体的に符号を決めていきます。
まず、$P_1=0$として、次のように計算します。
$$P_2=P_1+P(s_1)=0+0.5=0.5$$
$$P_3=P_2+P(s_2)=0.5+0.2=0.7$$
$$P_4=P_3+P(s_3)=0.7+0.2=0.9$$
$P_1=0, P_2=0.5, P_3=0.7, P_4=0.9$という値を使って符号を作っていきます。
ステップ４ ステップ３で求めた確率を２進数にする
ステップ３より、「$P_1=0, P_2=0.5, P_3=0.7, P_4=0.9$」と求まりました。
これを２進数に変換します。
$$P=0_{(10)}=0.0000…_{(2)}$$
$$P=0.5_{(10)}=0.1000…_{(2)}$$
$$P=0.7_{(10)}=0.1011…_{(2)}$$
$$P=0.9_{(10)}=0.1110…_{(2)}$$
ステップ５ 符号長に合わせて符号を決定する
ステップ４で求めた２進数の小数点以下だけに注目し、符号長の長さに合わせます。
「$d$は1桁、$b$は3桁、$a$は3桁、$c$は4桁」だったので、
$$d=0, b=100, a=101, c=1110$$
となります。
ちゃんと瞬時符号になってるっすね！
発生確率と符号長の関係
発生確率を思い出すと、「$d=0.5, b=0.2, a=0,2, c=0.1$」でした。
そして、各記号は「$d=0, b=100, a=101, c=1110$」というように符号化されます。
これを見て何か気づかないでしょうか？
「発生確率が大きいほど、符号長が短い」とかですか？
その通り！
発生確率が大きい記号に符号長が長い符号を対応させると、無駄にデータが大きくなってしまいますよね？
だから、発生確率が大きい記号ほど、符号長が短い符号を対応させることで、通信を効率的に行えるのです。
今回はここまで！
お疲れ様でした！
発生確率とは、記号列の中でその記号が出てくる確率です。
今回の例で言えば、$aabbcddddd$という記号列を考えると、それぞれの発生確率は上表と同じですよね？
なお、確率なので、全てを足したら「$1$」になることにも注意してください。