このページはマス旅の一部です。[br][br]今回は、「情報源の効率的な符号化」を探ってみよう。[br][br]情報アルファベットを最も効率的に送る符号化、codingの実現を考えよう。[br]情報の通信では、情報をつくる記号を別の記号に置き換えることが普通です。置き換えることを符号化(Encoding)といいます。[br]そうなると、符号化によって、情報の量が少なくなるとか、雑音に強いとか[br]何かしらのメリットが重要になってきますね。[br][br]

[b][size=150]＜符号化の効率計算方法＞[br][/size][/b][br]情報源[b]A＝{A1,A2,A3,A4}[/b]に対して、[br]順に符号語=[b]{0,01,011,0111}[br][/b]に置き換えたとしよう。[br][br]符号を構成する記号は元の数rで[br]r元符号というので、[br]r=2のX=|0,1}は2元符号。[br]これでできた符号語の起きる確率が順に[br][b]Ps={1/2,1/4,1/8,1/8}[/b][br]だとしましょう。[br]そして、符号語の長さは順に[br][b]Ls={1,2,3,4}[/b][br]だ。[br]そうすると、平均語長Lは語長の期待値により、[br][br][b][color=#0000ff][size=150]L=1*1/2 + 2*1/4 + 3*1/8 + 4*1/8 [br][/size][/color][/b] = 4/8+4/8+3/8+4/8=[b]15/8[/b][br]となるね。[br][br]また、エントロピーHは平均ビットなので、ビットの期待値により[br][br][b][color=#0000ff][size=150]H=1*1/2 +2*1/4+3*1/8+3*1/8[br][/size][/color][/b]=4/8+4/8+3*2/8=[b]14/8[/b][br]となる。[br][br]すると、[b][size=150]エントロピーHを平均語長Lでわった商[/size][/b]は[br]1記号あたりのエントロピーとなり、(14/8)/(15/8)=14/15[br]一方で、1記号あたりの最大エントロピーは無記憶情報源のエントロピーと[br]同じだから、等確率で[b]log_2(r)=1/2=0.1(2)=1[/b]ビット[br]だから、[br]最大値との比較から符号化効率eは[br][b][color=#0000ff][size=200]e=(H/L)/log_2(r)[br][/size][/color]=14/15/1≒0.98[br][/b][br]だから、効率がよい。[br]e=1が理想だ。[br]（しかし、残念ならが、効率が高いと誤りの訂正に弱いこともわかっている。[br]誤り訂正についたは、今回はスルーします。）[br][br]さて、今の例で、効率がよかった原因を考えてみましょう。[br][b]LもHも両方とも期待値計算[/b]をしています。[br][br]その対象が[br][b]Lでは語長で、[br]Hでは情報量ビットでした。[br][/b]「[b][size=150][color=#0000ff]確率の高いHは、情報量ビットは小さい[/color][/size][/b]」ですね。[br][br][b]期待値計算への寄与が大きいのは、確率の高い部分[/b]です。[br]ということは、[b][color=#0000ff]確率の高いところで、HにあわせてLも小さくなればよい[/color][/b]わけです。[br][br]まあ、ここまで調べなくても、よく使う語が短い方が、通信時間が短くて[br]すむわけだから、タイパがいいです。[br][b]そこからも短い語をよく使う符号化がよい[/b]ことがわかるね。

[b][size=150]＜シャノンの符号化法＞[br][/size][/b][br]シャノンとファノの符号化法があります。[br][br]情報源Aの記号Anの起きる確率をpnとしましょう。[br]Aiをpiの大きい順のソートします。これが木のルートです。[br]ソート済のj番記号をAjとします。[br]ソート済番号で{A1,...Am}の確率の和と{A{m+1},..,An}の確率の和の差が最小になるところで、記号列を2群に分割します。[br]この作業を2分と呼びます。[br][br]それぞれの群について再帰的に2分を繰り返し、分割できないところでやめます。最後は1語になります。これがリーフです。[br][br]分割を木表現にしましょう。[br]たとえば、左を０右を１に割り当てると、[br]木のルートからリーフに至るまでの履歴を表す01記号列が求める符号語です。[br][br][b]たとえば、[br]A={{A1,A2,A3,A4,A5,A6},{0.09, 0.14, 0.40, 0.15, 0.12, 0.10}[br]#降順ソート[br]As={{A3,A4,A2,A5,A6,A1},{0.40,0.15, 0.14, 0.12, 0.10, 0.09}}[br]#全体2分　[br] A0={{A3,A4},{0.40,0.15}},[br] A1={{A2,A5,A6,A1},{0.14, 0.12, 0.10, 0.09}}　[br]#子の2分[br]A00={A3}, A01={A4} A10={A2,A5},A11={A6,A1}[br]#孫の2分[br]A100={A2},A101={A5},A110={A6},A111={A1}[br][/b][br]だから、符号化法のあとは、[br][br][b][color=#0000ff]Aen={{A3,A4,A2,A5,A6,A1},{00,01,100,101,110,111}}となり、[br]確率数列は{0.40, 0.15, 0.14, 0.12, 0.10, 0.09}[br]語長数列は{2,2,3,3,3,3}[br][/color][/b]となりますね。[br][br][b][size=150]＜効率チェック＞[br][/size][/b][br]今の例で効率を確認しましょう。[br][b][size=150]e=(H/L)/log_2(r)[br][/size][/b][br]Hはソートも2分も関係ありません。[br]{pi}={0.09, 0.14, 0.40, 0.15, 0.12, 0.10}として、[br]H（A)=-Σpi log_2(pi)=...=[b]2.35[/b]ビット[br][br]L(Aen)=2*0.40 +2*0.15 +3*0.14 +3*0.12 +3*0.10 +3*0.09[br][b]=2.45[/b][br]2元符号r=2では、log_2(r)=1だから、[br][br][b]e=2.35/2.45=0.96[br][br][/b]で効率的な符号化と言えるでしょう。

[br][b][size=150]＜ハフマンの符号化法＞[br][/size][/b][br]別の符号化もあります。それはハフマンの考えたものです。[br]確率の降順にソートするのは同じですが。[br]そのあとが少しちがいます。[br]確率の小さいところから始めます。[br]小さい２つを１つの合体して、確率の合計を求めます。[br]確率の降順ソートと合体という２つのステップを再帰的に繰り返します。[br][br][b]たとえば、[br]#降順ソート[br]As={{A3,A4,A2,A5,A6,A1},{0.40,0.15, 0.14, 0.12, 0.10, 0.09}}[br]A1A6の確率和は0.09+0.10=0.19はA3の次。[br]#降順ソート[br]Ass={{A3,A16,A4,A2,A5},{0.40,0.19,0.15, 0.14, 0.12}}[br]A52の確率和は0.12+0.14=0.26はA3の次。[br]#降順ソート[br]Asss={{A3,A52,A16,A4},{0.40,0.26,0.19,0.15}}[br]A4A16の確率和は0.15+0.19=0.34はA3の次。[br]Assss={{A3,A416,A52},{0.40,0.34,0.26}}[br]A52A416の確率和は0.26+0.34=0.6はA3の前。[br]Assss2={{A52416,A3},{0.60, 0.40}}[br]A3A52416の確率和は１でこれがルートになる。[br]これを逆にたどる。左０、右１として、記号の固まりをリーフに分解する。[br][0]={A52416},[1]=A3[br][00]={A416},[01]={A52}[br][000]=[A16],[001]=A4,[010]=A2,[011]=A5[br][0000]=A6,[0001]=A1[br][/b][br][b][color=#0000ff]＜ハフマン符号化の効率チェック＞[br]A={{A1,A2,A3,A4,A5,A6},{0.09, 0.14, 0.40, 0.15, 0.12, 0.10}[br]に対し対するハフマン符号化の効率はどうでしょうか。[br]効率はどうでしょうか。H=2.35はシャノンもハフマンも同じですね。[br]符号化は、[br]Aen={{A1,A2,A3,A4,A5,A6},{0001, 010, 1, 001, 011, 0000}[br]語長数列は{4,3,1,3,3,4}[br][/color][/b]log_2(r)=1です。[br][br][b]L=[/b]0.09*4+0.14*3+0.40*1+0.15*3+0.12*3+0.10*4[br][b]=2.39[/b]ビットです。[br][b]e=(H/L)/1=2.35/2.39=0.98[br][/b]ですね。[br][br]シャノンさんより、ハフマンさんの方が効率的ですね。[br]

[b][size=150]＜シャノンの第一定理＞[br][/size][/b][br]シャノンさんは符号化自体の手法では、ハフマンさんより少し下でしたが、理論化の元祖なだけあって、そっち方面では負けていません。[br][br]さっきのeの式を思い出してください。[br]ｒ元符号化の効率の式です。[br]e=(H/L)/log_2(r)[br]今までは0,1で符号化していたかから、[br]r=2でlog_2(r)=1でした。[br]だから、e=(H/L)でしたね。[br]H=Lになったときがe=1となり一番効率がよいということは、[br]今までの例でわかるでしょう。[br]eが１に近づくということは、LビットがHビッチに近づくということです。[br]式を変形すると、L e ＝H/log_2(r)です。[br][br]一般に、[color=#0000ff][b][size=150]Lの下限はH/log_2(r)[/size][/b][/color]であり、[br]それに近づけることができるというのが[b]シャノンの第一定理（情報源符号化定理）[/b]です。[br][br][b][size=150]＜振り返り＞[br][/size][/b]「情報源の符号化は平均符号語長LをH以上とH+1未満まで圧縮できる」[br]という言い換えもできます。[br]そして、「[b]ハフマン符号」[/b]はさっきの例でたまたまよかったのではなく、[br]つねに「[b]平均符号語長が最小になる[/b]」ことが定理になっています。[br][br]また、「[b]LZ符号」[/b]という情報源の確率分布が不明でも平均符号語長がエントロピーが収束する符号もあるようです。Lempel,Zivというイスラエルの科学者が1978した画期的な方法もあるようです。[br][br][color=#9900ff][u][b][size=150]課題：シャノンの符号化の効率チェックするgeogebraで作りましょう。[br][/size][/b][/u][/color][br]情報源Anのn=5のとき、降順ソート済であるとする。[br]最初の2分で左3個、右2個に分かれるとしたらソート失敗だから、これはない。[br]だから最初の2分で左２個、右3個に分かれるAパターンか、[br]左1個、右4個に分分かれるBパターン。[br]どの5語も1回目の2分に参加する。[br]Aパタン[br]２回目に左2個は1個ずつになるので、語長は{2,2}となる。[br]２回目に右3個群は、左2個、右1個で2分することはないから、左1個、右2個となり、3回ですべてリーフになる。だから、語長は{2,2,2,3,3}[br]Bパタン[br]２回目に、左1個と右３個のB1パタン、左２個と右２個になるB2パタン[br]３回目でB1パタンは右３個が右１と左２個に分かれるので、B1語長は{1,2,3,4,4}。３回目でB2パタンはすべてリーフでB2語長は{1,3,3,3,3}[br]結局、ソート後の確率の大小関係から、[br]語長はA={2,2,2,3,3},B1={1,2,3,4,4},B2={1,3,3,3,3}となる。[br]語長の最大が4から、2分回数の最大は2^4=16回。[br][br]タイトルは「シャノンの符号化の効率をチェックする」[br][br]#パタン候補[br]ptnA={2,2,2,3,3}[br]ptnB1={1,2,3,4,4}[br]ptnB2={1,3,3,3,3}[br]ptns={ptnA, ptnB1, ptnB2}[br][br]#確率の選択(p1からp5が降順になる）[br]p1=Slider(1/5+0.01, 1/2+0.01, 0.01)[br]rest1=1-p1[br]p2=Slider(rest1/4+0.01, p1-0.01, 0.01)[br]rest2=rest1-p2[br]p3=Slider(rest2/3+0.01, p2-0.01, 0.01)[br]rest3=rest2-p3[br]p4=Slider(rest3/2+0.01, p3-0.01, 0.01)[br]p5=rest3-p4[br]Pros={p1,p2,p3,p4,p5}[br][br]#パタン決定[br]con1 = (p1 > rest1)[br]con2 = (p2 > rest2)[br]JudgedPtn = if(con1,if(con2,Element(ptns,2),Element(ptns,3)),Element(ptns,1))[br][br]#期待値計算[br]f(x)= -x log(2,x)[br]H = Sum(Zip(f(t),t,Pros))[br]L = Sum(Sequence(Element(Pros, i)*Element(JudgedPtn,i) ,i, 1,5))[br]e=H/L[br][br]テキストボックスで入力する。[br]確率リスト（降順）=Pros\\シャノン符号の語長=JudgedPtn\\だから、効率e = H/L = H/L=e[br][br]スライダーで確率を変えることで、効率が変わるのがわかるでしょう。[br]５つの語の語長のビットと確率のビットのずれが少ないときに、効率がよくなります。[br][br]確率p1を0.5近くにして、他を小さくすると効率がよいですが、[br]p1が0.5でも、p2を上げていくと１，３，３，３，３の語長パタンとのずれが拡大するので、効率は[br]下がります。語長パタンが1,2,3,4,4まで変わったとたんに効率があがります。[br]このように、符号化は1種の最適化なので、変化のはざまの部分では逆効果になる部分も[br]出てくるところが面白いですね。