情報源を効率的に符号化しよう
このページはマス旅の一部です。
今回は、「情報源の効率的な符号化」を探ってみよう。
情報アルファベットを最も効率的に送る符号化、codingの実現を考えよう。
情報の通信では、情報をつくる記号を別の記号に置き換えることが普通です。置き換えることを符号化(Encoding)といいます。
そうなると、符号化によって、情報の量が少なくなるとか、雑音に強いとか
何かしらのメリットが重要になってきますね。
１.符号化と効率
＜符号化の効率計算方法＞
情報源A＝{A1,A2,A3,A4}に対して、
順に符号語={0,01,011,0111}
に置き換えたとしよう。
符号を構成する記号は元の数rで
r元符号というので、
r=2のX=|0,1}は2元符号。
これでできた符号語の起きる確率が順に
Ps={1/2,1/4,1/8,1/8}
だとしましょう。
そして、符号語の長さは順に
Ls={1,2,3,4}
だ。
そうすると、平均語長Lは語長の期待値により、
L=1*1/2 + 2*1/4 + 3*1/8 + 4*1/8
= 4/8+4/8+3/8+4/8=15/8
となるね。
また、エントロピーHは平均ビットなので、ビットの期待値により
H=1*1/2 +2*1/4+3*1/8+3*1/8
=4/8+4/8+3*2/8=14/8
となる。
すると、エントロピーHを平均語長Lでわった商は
1記号あたりのエントロピーとなり、(14/8)/(15/8)=14/15
一方で、1記号あたりの最大エントロピーは無記憶情報源のエントロピーと
同じだから、等確率でlog_2(r)=1/2=0.1(2)=1ビット
だから、
最大値との比較から符号化効率eは
e=(H/L)/log_2(r)
=14/15/1≒0.98
だから、効率がよい。
e=1が理想だ。
（しかし、残念ならが、効率が高いと誤りの訂正に弱いこともわかっている。
誤り訂正についたは、今回はスルーします。）
さて、今の例で、効率がよかった原因を考えてみましょう。
LもHも両方とも期待値計算をしています。
その対象が
Lでは語長で、
Hでは情報量ビットでした。
「確率の高いHは、情報量ビットは小さい」ですね。
期待値計算への寄与が大きいのは、確率の高い部分です。
ということは、確率の高いところで、HにあわせてLも小さくなればよいわけです。
まあ、ここまで調べなくても、よく使う語が短い方が、通信時間が短くて
すむわけだから、タイパがいいです。
そこからも短い語をよく使う符号化がよいことがわかるね。
１．シャノンの符号化
＜シャノンの符号化法＞
シャノンとファノの符号化法があります。
情報源Aの記号Anの起きる確率をpnとしましょう。
Aiをpiの大きい順のソートします。これが木のルートです。
ソート済のj番記号をAjとします。
ソート済番号で{A1,...Am}の確率の和と{A{m+1},..,An}の確率の和の差が最小になるところで、記号列を2群に分割します。
この作業を2分と呼びます。
それぞれの群について再帰的に2分を繰り返し、分割できないところでやめます。最後は1語になります。これがリーフです。
分割を木表現にしましょう。
たとえば、左を０右を１に割り当てると、
木のルートからリーフに至るまでの履歴を表す01記号列が求める符号語です。
たとえば、
A={{A1,A2,A3,A4,A5,A6},{0.09, 0.14, 0.40, 0.15, 0.12, 0.10}
#降順ソート
As={{A3,A4,A2,A5,A6,A1},{0.40,0.15, 0.14, 0.12, 0.10, 0.09}}
#全体2分
A0={{A3,A4},{0.40,0.15}},
A1={{A2,A5,A6,A1},{0.14, 0.12, 0.10, 0.09}}
#子の2分
A00={A3}, A01={A4} A10={A2,A5},A11={A6,A1}
#孫の2分
A100={A2},A101={A5},A110={A6},A111={A1}
だから、符号化法のあとは、
Aen={{A3,A4,A2,A5,A6,A1},{00,01,100,101,110,111}}となり、
確率数列は{0.40, 0.15, 0.14, 0.12, 0.10, 0.09}
語長数列は{2,2,3,3,3,3}
となりますね。
＜効率チェック＞
今の例で効率を確認しましょう。
e=(H/L)/log_2(r)
Hはソートも2分も関係ありません。
{pi}={0.09, 0.14, 0.40, 0.15, 0.12, 0.10}として、
H（A)=-Σpi log_2(pi)=...=2.35ビット
L(Aen)=2*0.40 +2*0.15 +3*0.14 +3*0.12 +3*0.10 +3*0.09
=2.45
2元符号r=2では、log_2(r)=1だから、
e=2.35/2.45=0.96
で効率的な符号化と言えるでしょう。
３．ハフマンの符号化
＜ハフマンの符号化法＞
別の符号化もあります。それはハフマンの考えたものです。
確率の降順にソートするのは同じですが。
そのあとが少しちがいます。
確率の小さいところから始めます。
小さい２つを１つの合体して、確率の合計を求めます。
確率の降順ソートと合体という２つのステップを再帰的に繰り返します。
たとえば、
#降順ソート
As={{A3,A4,A2,A5,A6,A1},{0.40,0.15, 0.14, 0.12, 0.10, 0.09}}
A1A6の確率和は0.09+0.10=0.19はA3の次。
#降順ソート
Ass={{A3,A16,A4,A2,A5},{0.40,0.19,0.15, 0.14, 0.12}}
A52の確率和は0.12+0.14=0.26はA3の次。
#降順ソート
Asss={{A3,A52,A16,A4},{0.40,0.26,0.19,0.15}}
A4A16の確率和は0.15+0.19=0.34はA3の次。
Assss={{A3,A416,A52},{0.40,0.34,0.26}}
A52A416の確率和は0.26+0.34=0.6はA3の前。
Assss2={{A52416,A3},{0.60, 0.40}}
A3A52416の確率和は１でこれがルートになる。
これを逆にたどる。左０、右１として、記号の固まりをリーフに分解する。
[0]={A52416},[1]=A3
[00]={A416},[01]={A52}
[000]=[A16],[001]=A4,[010]=A2,[011]=A5
[0000]=A6,[0001]=A1
＜ハフマン符号化の効率チェック＞
A={{A1,A2,A3,A4,A5,A6},{0.09, 0.14, 0.40, 0.15, 0.12, 0.10}
に対し対するハフマン符号化の効率はどうでしょうか。
効率はどうでしょうか。H=2.35はシャノンもハフマンも同じですね。
符号化は、
Aen={{A1,A2,A3,A4,A5,A6},{0001, 010, 1, 001, 011, 0000}
語長数列は{4,3,1,3,3,4}
log_2(r)=1です。
L=0.09*4+0.14*3+0.40*1+0.15*3+0.12*3+0.10*4
=2.39ビットです。
e=(H/L)/1=2.35/2.39=0.98
ですね。
シャノンさんより、ハフマンさんの方が効率的ですね。
４．振り返り
＜シャノンの第一定理＞
シャノンさんは符号化自体の手法では、ハフマンさんより少し下でしたが、理論化の元祖なだけあって、そっち方面では負けていません。
さっきのeの式を思い出してください。
ｒ元符号化の効率の式です。
e=(H/L)/log_2(r)
今までは0,1で符号化していたかから、
r=2でlog_2(r)=1でした。
だから、e=(H/L)でしたね。
H=Lになったときがe=1となり一番効率がよいということは、
今までの例でわかるでしょう。
eが１に近づくということは、LビットがHビッチに近づくということです。
式を変形すると、L e ＝H/log_2(r)です。
一般に、Lの下限はH/log_2(r)であり、
それに近づけることができるというのがシャノンの第一定理（情報源符号化定理）です。
＜振り返り＞
「情報源の符号化は平均符号語長LをH以上とH+1未満まで圧縮できる」
という言い換えもできます。
そして、「ハフマン符号」はさっきの例でたまたまよかったのではなく、
つねに「平均符号語長が最小になる」ことが定理になっています。
また、「LZ符号」という情報源の確率分布が不明でも平均符号語長がエントロピーが収束する符号もあるようです。Lempel,Zivというイスラエルの科学者が1978した画期的な方法もあるようです。
課題：シャノンの符号化の効率チェックするgeogebraで作りましょう。
情報源Anのn=5のとき、降順ソート済であるとする。
最初の2分で左3個、右2個に分かれるとしたらソート失敗だから、これはない。
だから最初の2分で左２個、右3個に分かれるAパターンか、
左1個、右4個に分分かれるBパターン。
どの5語も1回目の2分に参加する。
Aパタン
２回目に左2個は1個ずつになるので、語長は{2,2}となる。
２回目に右3個群は、左2個、右1個で2分することはないから、左1個、右2個となり、3回ですべてリーフになる。だから、語長は{2,2,2,3,3}
Bパタン
２回目に、左1個と右３個のB1パタン、左２個と右２個になるB2パタン
３回目でB1パタンは右３個が右１と左２個に分かれるので、B1語長は{1,2,3,4,4}。３回目でB2パタンはすべてリーフでB2語長は{1,3,3,3,3}
結局、ソート後の確率の大小関係から、
語長はA={2,2,2,3,3},B1={1,2,3,4,4},B2={1,3,3,3,3}となる。
語長の最大が4から、2分回数の最大は2^4=16回。
タイトルは「シャノンの符号化の効率をチェックする」
#パタン候補
ptnA={2,2,2,3,3}
ptnB1={1,2,3,4,4}
ptnB2={1,3,3,3,3}
ptns={ptnA, ptnB1, ptnB2}
#確率の選択(p1からp5が降順になる）
p1=Slider(1/5+0.01, 1/2+0.01, 0.01)
rest1=1-p1
p2=Slider(rest1/4+0.01, p1-0.01, 0.01)
rest2=rest1-p2
p3=Slider(rest2/3+0.01, p2-0.01, 0.01)
rest3=rest2-p3
p4=Slider(rest3/2+0.01, p3-0.01, 0.01)
p5=rest3-p4
Pros={p1,p2,p3,p4,p5}
#パタン決定
con1 = (p1 > rest1)
con2 = (p2 > rest2)
JudgedPtn = if(con1,if(con2,Element(ptns,2),Element(ptns,3)),Element(ptns,1))
#期待値計算
f(x)= -x log(2,x)
H = Sum(Zip(f(t),t,Pros))
L = Sum(Sequence(Element(Pros, i)*Element(JudgedPtn,i) ,i, 1,5))
e=H/L
テキストボックスで入力する。
確率リスト（降順）=Pros\\シャノン符号の語長=JudgedPtn\\だから、効率e = H/L = H/L=e
スライダーで確率を変えることで、効率が変わるのがわかるでしょう。
５つの語の語長のビットと確率のビットのずれが少ないときに、効率がよくなります。
確率p1を0.5近くにして、他を小さくすると効率がよいですが、
p1が0.5でも、p2を上げていくと１，３，３，３，３の語長パタンとのずれが拡大するので、効率は
下がります。語長パタンが1,2,3,4,4まで変わったとたんに効率があがります。
このように、符号化は1種の最適化なので、変化のはざまの部分では逆効果になる部分も
出てくるところが面白いですね。