117 パラメータはＬとＲ（続２）
●117 パラメータはＬとＲ（続２）
夜中に、また目が覚めた。続きをしましょう。今回は Fig.A1 で固定ハフマン符号と動的ハフマン符号との境界がノコギリの歯のようになっている部分についてです。
＊＊＊
Fig.A1 を再掲します。
L=96, R=64 付近や L=192, R=100 付近などで、動的ハフマン符号（DYN-HF）の境域が不自然に凹んでいますね。よく見ると L=48, R=32 付近にもあります。
Fig.A0 でははっきり見えていた気がしますので、Fig.A0 と同様に動的ハフマン符号の発生頻度だけを図にしてみます。
Fig.A1d は、パラメータの範囲を L=0〜512, R=0〜255 に広げたものです。1000 回繰り返して動的ハフマン符号が発生した回数を対数表示しています。ノコギリ状態の部分がよく分かると思います（...よね？）
ノコギリの歯以外に、L=320〜352 の部分で妙に膨らんでいる部分なども見えます。これも気になりますが...。
＊＊＊
L=192, R=100 付近に注目して、どうなっているのか細かく見ましょう。
L=160〜240, R=105〜110 の範囲で、動的ハフマン符号の発生確率を確認してみました。
Fig.C0 は、横軸は L で、縦軸は発生確率です。1000 回繰り返して発生回数を割ったものです。R = 105, 106, 107, 108, 109, 110 の 6 個に対応して 6 本のグラフがあります。青色が R=105 で、茶色が R=110 です。
R が増えると発生確率は下がります。
R が同じで L だけが増える場合、動的ハフマン符号の発生確率は単調に上昇しても良さそうなのに何故に山や谷があるのでしょうか。
まず、ノコギリが発生する原因が、zlib の「特殊な」実装によるものなのか、Deflate の仕様に由来するものなのかを考えるために、固定ハフマン符号と動的ハフマン符号の出力（圧縮データ）を比較しましょう。具体的には、L,R で乱数生成したデータを固定ハフマン符号で圧縮したときと、動的ハフマン符号で圧縮したときとで、圧縮データのビット数を比べます。
固定ハフマン符号の圧縮データは、記号の発生頻度をカウントすれば、符号語のビット数（と補助ビット）との積和から求めることができます。簡単ですね。変数 hQ と dQ を頻度をカウントしたものとします。hc は［記号Ａ］の符号語のビット数を並べたものでしたね。hc[s] で記号からビット数を入手できます。
sF = 3
for s in hQ: sF += (hc[s] + length_codes[s][0]) * hQ[s]
for s in dQ: sF += ( 5 + distance_codes[s][0]) * dQ[s]
固定ハフマン符号は、長さと距離の圧縮がなければ L*8+10 ビットで、R=100 付近では長さと距離の圧縮はあまり発生しませんから、大体 L*8+10 ビットになるはずです。それで、圧縮データのビット数から L*8 を減算した値を求めます。
動的ハフマン符号は、ちょっと面倒です。基本的には記号の発生頻度と符号語のビット数が分かれば固定ハフマン符号と同様に
ss = [0, 0, 0]
for s in lQ: ss[0] += (lc[s] + bit_ext[s] ) * lQ[s]
for s in hQ: ss[1] += (hc[s] + length_codes[s][0] ) * hQ[s]
for s in dQ: ss[2] += (dc[s] + distance_codes[s][0] ) * dQ[s]
sD = 3 + 14 + (hclen+4)*3 + sum(ss)
として求めることができるのですけれども。符号語のビット数を、zlib の実装と一致するように決めるが面倒なのです（...zlib は二分木を作成する際に記号の発生頻度をヒープを構成して求めていて、同じ頻度があった場合にどうなるのか謎でした。詳しくは[113]にて）。記号の発生頻度は固定ハフマン符号と同一で流用できます。
そんな訳で、zlib の謎な動作に悩まされながら、スクリプトを作ってカウントしました。Fig.C1 です。1000 回繰り返した平均値になっています。
下段は Fig.C1 と同じで動的ハフマン符号の発生確率です。上段が圧縮データのビット数です。橙色は固定ハフマン符号です。固定ハフマン符号は R の影響を受けないので 6 本のグラフが重なっています。L*8+10 ビットから L*8 を減算しているので、10 ビットのところで平になっています。動的ハフマン符号は 6 本が別々になっていて、青色が R=105 です。こちらも L*8 を減算した値です。
動的ハフマン符号の圧縮データのサイズが、固定ハフマン符号と交差する付近で、（下段の）動的ハフマン符号の発生確率が変化しています。動的ハフマン符号の発生確率は圧縮データの大小と対応するようです。
ノコギリ状態になるのは、zlib の実装の特徴ではなくて、Deflate の仕様的なものから発生しているのかも知れません。
＊＊＊
動的ハフマン符号の圧縮データが波をうっている原因を追求しましょう。
動的ハフマン符号の圧縮データは [1]〜[5] の 5 つのグループに分けられます（...いつものグループ分けですよ）。[1]〜[3] はほぼ固定で、[4] と [5] が入力データによって変動する部分です。
L=160〜240, R=105〜110 の範囲で、圧縮データから [4] と [5] を抽出して表示してみよう。[4] は ss[0] で、[5] は ss[1]+ss[2] ですからもう準備は出来ています。
Fig.C2 の上段が [4] で、下段が [5] です。繰り返し回数は 1 回のみ、つまり平均していない生の値です。
縦軸は [4] はそのままの値で、[5]は L*8 を減算した値です。Fig.C1 の縦軸は、圧縮データのビット数から L*8 を減算した値、つまり、[1]〜[3] + [4] + [5] - L*8 でした。この値から [1]〜[3] を除いて、[4] と [5] - L*8 に分けたものになっています。
[5] は L に応じてほぼ連続的に変化しています。なお dc はほとんど無くて大部分が hc です。一方、[4] は L=190〜200 前後で 40 ビット位のギャップがあります。符号表のデータの何かが、この付近で不連続に変化するように感じられます。
＊＊＊
[4] の構成を詳しく調べましょう（...符号表のデータは [081] で説明していますよ）。
[4] は、ハフマン符号Ｃで hc と dc を符号化したもので、ハフマン符号Ｃの符号語（と補助のビット）の列です。
［記号Ｃ］は 0〜18 の範囲で定義されていて、記号 1〜15 は hc と dc の符号語のビット数を表します。記号 14 や 15 が使用されることはまれで、hc, dc で使用された記号のみが変数 lc2 に反映されます。記号 0 は対応する記号が使用されない場合に使用されます（...ややこしい）。記号 16, 17, 18 は同じ値が連続した場合の圧縮用です。符号語のあとに補助のビットが続きます。
［記号Ｃ］の頻度は hc, dc の内容で決まります。hc は 286 個で dc は 30 個なので、286+30=316 が頻度の合計の最大です。
［記号Ｃ］の符号語のビット数は 7 が上限です。符号語は変数 lc2 を確認すると分かります。変数 lc2 はハフマン符号Ｃの符号表で、［記号Ｃ］とその符号語の対応表で、ついでに記号の発生頻度もカウントしています（...正確には変数を表示する際に情報を付け足しているのですけど）。
ギャップの前後となる、L=170,R=105 と L=230,R=105 のときの変数 lc2 を出力しました。Sym は［記号Ｃ］、L は符号語のビット数、be は補助のビット数、Fq は記号の発生頻度、BxFq はビット数と頻度の積。SUM はその計で [4] のビット数です。
L=170 のときは [4] は 225 ビットで、L=230 のときは 261 ビットと増加していますね。
Sym:( L,be) # Fq BxFq of L=170,R=105
_0: ( 3, 0) # 16, 48
_1: ( 5, 0) # 2, 10
_5: ( 6, 0) # 2, 12
_6: ( 2, 0) # 28, 56
_7: ( 1, 0) # 43, 43
16: ( 4, 2) # 5, 30
18: ( 6, 7) # 2, 26 (SUM 225)
Sym:( L,be) # Fq BxFq of L=230,R=105
_0: ( 4, 0) # 10, 40
_1: ( 6, 0) # 2, 12
_5: ( 6, 0) # 1, 6
_6: ( 1, 0) # 40, 40
_7: ( 3, 0) # 23, 69
_8: ( 2, 0) # 30, 60
16: ( 6, 2) # 1, 8
18: ( 6, 7) # 2, 26 (SUM 261)
L=170 と L=230 との違いは記号 8 の有無です。記号 8 の符号語で BxFq が 60 ビットあります。
そこで、L=170,R=105 と L=230,R=105 のときの変数 lc2 の BxFq を 1000 回繰り返して平均を求めました。
Sym: L=170 : L=230 : DIFF
_0: 55.296 : 35.018 : -20.278 <-- --- -20
_1: 10.748 : 10.546 : -0.202
_4: 0.030 : 0.012 : -0.018
_5: 14.561 : 15.070 : +0.509
_6: 58.918 : 64.284 : +5.366
_7: 44.069 : 56.723 : +12.654 <-- +12
_8: 0.000 : 50.605 : +50.605 <-- +50
16: 21.837 : 11.304 : -10.535 <-- --- -10
17: 5.841 : 1.178 : -4.663
18: 24.640 : 24.222 : -0.418
記号 8 が一番大きく影響しています。L が増えて（あるところで）符号語のビット数が 7 から 8 へと増えることで、ギャップの発生となっていることが予想されます。L は記号の発生頻度（変数 hQ）に影響し、hQ は符号語のビット数（変数 hc）を決めますので、この辺の仕組みからギャップが発生する理由の説明が付けばよいのですけれども。
他に記号 7 も +12 と増えていること、逆に記号 0 や記号 16 で、-20 や -10 と減っていることはどのような理由なのか気になります。
＊＊＊
色々と検討を始める前に、まずは、状況の整理をします。
R=105 ならリテラルは 0〜105 の 106 個が使用され、106〜255 は使用されないので、hc はリテラル 106 個と終端 1 個の計 107 個が最大です。hc の構成は、
hc = [0〜105の符号語のビット数の並び] + [106〜255はビット数0] + [256の符号語のビット数]
となります。それと、dc は符号語が 0 個のときに用意される 2 個（ビット数 1 の符号語が 2 個）になります。
記号の発生頻度が 1 以上なら何らかの符号語が割付られてビット数は 1 以上です。頻度 0 だと、その記号は使用されない記号で、使用されない記号の符号語はビット数 0 です。
L=170 だと平均して 86 個が頻度 1 以上、L=230 では 95 個が頻度 1 以上です。逆算すると、頻度 0 となるのは 107-86=21 個と 107-95=12 個です（...これは平均なので分散も示さないと困るよ）。
それと L=195 だと頻度 1 以上になるのは平均 90 個です。ちょうど 90 個だったときの hQ と hc の分布を 2 セット示します。
hQQ1 = { 1:28, 2:30, 3:23, 4: 6, 5:3 }; hcQ1 = { 5:3, 6:29, 7:58 }
hQQ2 = { 1:35, 2:24, 3:15, 4:12, 5:4 }; hcQ2 = { 5:4, 6:35, 7:33, 8:18 }
hQQ は記号の発生頻度毎に記号の個数をカウントしたものです。hQQ1 なら頻度 1 の記号が 28 個、頻度 2 が 30 個、...などと読んで下さい。hcQ は符号語のビット数毎に符号語の個数をカウントしたものです。変数 lc2 の Fq と同じ意味ですが記号 0 と 1 の分は含まれていません（...28+30+23+6+3 = 3+29+58 = 90 ですよ）。
さてさて。変数 lc2 の記号に戻ります。
＊＊＊
変数 lc2 に出現した記号が何に使用されているのかを検討して行きましょう。以下では長さと距離の圧縮がない場合で進めます。
記号 0 は、0〜105 の範囲で、頻度 0 でビット数 0 となったものを表すために使用されたのでしょう。L=170 と L=230 の頻度 0 の個数とだいたい合います。
記号 18 は、連続する 0 を表現できます。106〜255 の範囲のビット数 0 が連続する部分のために使用されるのでしょう。1 個で 11〜138 個分となるので 2 個使用されます。
記号 17 は 3〜10 個の連続する 0 を表現できます。0〜105 の範囲で偶然 0 が 3 個以上連続して使用されたのかも知れません。
記号 1 が 2 回出現しているのは、dc で符号語がない場合に使用されたものでしょう。
記号 16 は、同じビット数が 3 個以上連続した場合に圧縮できる記号です。L=170 の時に、記号 16 が 5 回使用されているのは、L=170 では記号 7 で半分近くあるために 7 が連続したからでしょう。L=170 の記号 16 は符号語が 4 ビットで補助が 2 ビットで計 6 ビットです。これで 3〜6 個連続する記号 7 を圧縮できます。記号 7 は 1 ビットですから、3〜6 ビットを 6 ビットに圧縮（...あれ、これ無駄では？かいさーん）。L=230 は記号 6,7,8 が混在していて、連続しなかったのでしょう。むしろよかったかも。BxFq の差分で、記号 7 の +12 と記号 16 の -10 が出ているのはこれの影響かもね。
記号 5〜7 と 8 は、hc で使用される符号語のビット数を示すために使用されるものでしょう。L=230 の記号 5〜8 の頻度を合計すると、1+40+23+30=94 個で、頻度 1 以上の個数と合います。L=170 は記号 16 で圧縮されたせいか、少し個数が少ないです。
変数 lc2 で記号 5 などが現れて、Fq がカウントされているので、hc に該当するデータがあるはずです。実際に hc を調べてみると、hcQ1 や hcQ2 のように見つかります。
hQQ の頻度をもとに二分木を作成すると hcQ でカウントした分だけの符号語ができる、...はずです。これも、実際に二分木を作成してみると、hcQ と同じ数だけ符号語が出てきました。
hQQ1 の頻度 1 と 2 の計 58 個がビット数 7 の符号語になり、頻度 3 と 4 の計 29 個がビット数 6 の符号語、頻度 5 の 3 個はビット数 7 になっているのでしょう。何故か数が合いますね。
＊＊＊
L が増えた場合の影響を分かっている範囲でまとめます（...R=105 の場合で説明します）。
L が増えると、変数 hQ の 0〜105 の範囲の頻度が増えます。sum(hQ)=L+1 ですから。これによって使用される記号（符号語）の数が増えます。L=170 では平均して 86 個で、L=230 では 95 個と増えていますね。
記号の個数が増えることは符号語のビット数を増やすことになります。
記号が 2 個ならビット数は 1 で、記号が 3 個なら 2 です。記号が 4 個なら 2〜3 と増えて行きます。記号の個数を n とすると、最小は log2(n) で、最大は n-1 でしょう。L=130の 86 個なら log2(86)=6.42 で最低 7 ビットです。L=230 の 95 個でも log2(95)=6.56 で 7 ビットですが余裕度（？）みたいなものが違うのでしょうか。
そこで、ビット数 5, 6, 7 の符号語で何個の記号が入るか？を考えます（...教科書でちょっと勉強しました）。クラフトの不等式を使います。各ビット数の符号語を a, b, c 個とすると、次の式を満たす値である必要があります。
a*2^{-5} + b*2^{-6} + c*2^{-7} <= 1
hcQ1 の値を参考に a=3, b=29 とすると、c=58 が最大値です。では hcQ2 の場合はビット数 5, 6, 7 で収まらないのでしょうか。hcQ1 も hcQ2 も記号の個数は 90 個の場合なので、a=3, b=29, c=58 とすれば収まりはします。ですが符号化の効率に影響がでるのです。
hcQ2 のビット数と頻度の積和を求めます（...これと等価な値を教科書では「平均符号長」と定義していたよ）。頻度とビット数を対応させて個数を割り振って、fq は頻度で、b はビット数で、fq と b と個数の積を求めて、合計します。
fq1:18 <---> b8:18 #fq*b*N = 144
fq1:17 <---> b7:17 #fq*b*N = 119
fq2:16 <---> b7:16 #fq*b*N = 224
fq2: 8 <---> b6: 8 #fq*b*N = 96
fq3:15 <---> b6:15 #fq*b*N = 270
fq4:12 <---> b6:12 #fq*b*N = 288
fq5: 4 <---> b5: 4 #fq*b*N = 100 (SUM 1241)
次に hcQ2 を a=3, b=29, c=58 とした場合を求めます。
fq1:35 <---> b7:35 # 245
fq2:23 <---> b7:23 # 322
fq2: 1 <---> b6: 1 # 12
fq3:15 <---> b6:15 # 270
fq4:12 <---> b6:12 # 288
fq5: 1 <---> b6: 1 # 30
fq5: 3 <---> b5: 3 # 75 (SUM 1242)
このように 1 だけですが悪化します。
ハフマン符号としては符号化の効率を優先して、ビット数 8 の符号語を用意するのでしょう。処理の実際では符号化の効率を調べて判定しているのではなくて、ハフマン符号の二分木を作成して、符号語を定めただけで、それで最適な符号語になるのですけれども。記号 8 の追加で 40 ビットのギャップが発生することを勘定にいれて何か調整するすべは無いのでしょうか。
L=195 付近は、ちょうど 7 ビットに収まるか 8 ビットになるかの境界で、乱数生成で決まった記号の頻度（変数 hQ）により、7ビットだったり 8 ビットになったりバラつくのでしょう。あとはもう乱数次第です。
L=230 などでは、記号の個数が増えることで記号の頻度の違いによる影響は塗りつぶされて、符号語のビット数が増えるのでしょうね。
＊＊＊
少しだけ補足します。ハフマン符号では発生頻度が同じ記号がある場合には、ビット数が異なる符号語ができる可能性があります（...[121] の注意点や [111] の記号の発生頻度で言及しています）。
例えば、記号 A, B, C, D の発生頻度が 2, 1, 1, 1 の場合には、A:00, B:01, C:10, D:11 となる可能性も、A:0, B:10, C:110, D:111 となる可能性もあります。どちらも場合も符号語のビット数と発生頻度の積和は 2*2 + 2*1 + 2*1 + 2*1 = 10 と 1*2 + 2*1 + 3*1 + 3*1 = 10 と同じになります（...ベクトルの内積で [2,2,2,2]*[2;1;1;1]=[1,2,3,3]*[2;1;1;1]=10 の方が分かり易い？）。
zlib ではこのような場合には符号語のビット数が少なくなるように節点を組合せます。そのため、ビット数 8 が出現した場合には、それが最小のはずです。...ですが、ちょっと不安なのでスクリプトを書いて、L=160〜240,R=105〜110の範囲で、ビット数 8 が出現した場合に、ビット数 5〜7 の組合せで sum(BxFq) が元と同じ値か小さくなるケースがないかを調べてみました。結果は、そのようなケースは見つかりませんでした。1 ビットだけ悪化するケースは沢山ありました。補足は以上です。
＊＊＊
使用される記号の数が増えるということは、頻度 0 だった記号の数が減るということです。L=170 だと平均 21 個が、L=230 だと 12 個になります。記号 0 よりも記号 7 や 8 の方がビット数が少ないので、記号 0 が減ることは、[4] のビット数が減ることになります。この減少は L の増加に伴って連続的に起きるようです。L=160〜180 まで [4] が徐々に少くなっている理由は、記号 0 の減少が原因なのでしょう。
友「これって、記号 0 の減少の影響を定量的を示さないと駄目。Fig.C2a の L=416〜512 の減少の理由が説明できないのでは。記号 16 の影響を L=170 の 1 例だけで排除するのは早計で、全体的にみて有効な領域は無いのか、有効ではない条件とは何かを検討するべきだよね」
私「それはそうかも」
L=160〜512,R=105 の範囲で [4] の符号表のデータの内訳を調べて見ましょう。Fig.C6a です。横軸は L で、縦軸が[4]のデータです。Fig.C2 の上段のグラフを L=160〜512まで伸ばして、記号 0〜18 までの BxFq を、凡例に示す順番で加算してプロットしました。x16のグラフが[4]のデータと一致します。300回繰り返した平均です。
L=224〜352 の区間に注目すると、[4] の減少に貢献しているのは、記号 0 だけではなくて、記号 5 や 7 もですね。
個々の記号の値をグラフにしたのが Fig.C6b です。横軸は Fig.C6a と同じで、縦軸は各記号の BxFq をそのまま表示しています。凡例の後ろの括弧の中の数値は L=512 の時の値です。色とこの値があればグラフと記号の対応が分かると思います。
L=224 で値が 1 以上の記号について、L=224とL=352の値を書き出しました。小数点以下を切り捨てています。
sym: L224: L352:
s0_: 35: 16: --- -19
s1_: 11: 11:
s5_: 19: _4: --- -15
s6_: 60: 55: --- -5
s7_: 57: 41: --- -16
s8_: 52: 42: --- -10
s16: _9: 31: +22
s17: _1: _0:
s18: 24: 25:
記号 0 の -19 ビットと、記号 5 の -15 ビット、記号 7 の -16 ビットが主な減少の理由ですね。記号 0 以外は、単調には変化していなくて、それぞれ事情があるのでしょうか。
次に記号 16 は役に立っているか？、です。
記号 16 は、L224 では 9 回、L352 では 31 回出現しています。記号 16 が出現した分だけ、記号 5〜8 が減少して全体としてビット数が減っているとよいのですけれども。果たしてどうでしょうか。
Fig.C6c に記号 16 の BxFq と、記号 16 で圧縮されたビット数と、その差分を示します。300回繰り返した時の平均です（...最初に投稿した図にバグがあったので差し替えています。L=192 付近のデータが壊れていました）。
青色（x16+）が記号 16 の BxFq です。記号 16 の符号語のビット数（＋補助のビット数）と発生頻度の積です。橙色（x16-）は圧縮された記号のビット数と個数の積です。緑色（x16）が差分です。どの部分でも青色のグラフが橙色よりも上になっていて、記号 16 で圧縮したらビット数が増加することになっています。記号 16 は（L,Rによる乱数生成データでは）やっぱり要らない子でした。
私「このグラフは 300 回の平均なので、個々のケースではプラスになることもマイナスになることもあり、その累計ではマイナスになるということなので、圧縮してみて、足がでるなら止めればよいと思います」
友「ＬＺ７７とハフマン符号の連携ってどうなっているんでしょうね」
＊＊＊
私「教科書読んだけど、頻度をもとにしたハフマン符号の二分木の作り方は理解できるし、頻度と符号語のビット数の関係も分かってきたのですが、まだ理解が足りないようですね。自信ないです。間違っていないか心配です」
友「...、ということで今回は「調べてみましたが、如何だったでしょうか」の回をお送りしました。ご意見は感想欄でお待ちしてます」
私＆友「おやすみなさい」
＊＊＊
