100 準備いたしましょう
●100 準備いたしましょう
夜中に、また目が覚めた。何だか準備不足で苦戦している夢を見ていた。
＊＊＊
記号 16 に優しくなるように変数 hc を調整することを考えていたのでした、...そもそも可能なのかも含めてね（あー、この話は[119]の続きになります。よろしくお願い致します）。
まず思いつくのは、変数 hc で出来る限り同じ値が連続するように符号語を割当てることでしょうか。変数 hc で頻度が同じ［リテラル］を符号語のビット数でソートする感じか。それと頻度のちょっとした違いで符号語がばらつかないに抑止するとか。
でも色々な条件がありそうで、どこから手を付けたらよいのか。データブロックの [5] と [4] をうまくバランスさせる？ うーん、評価関数は定義できそうですけど。その後の見通しが付きません。
変数 hcQ と変数 lq との差分の処理が気がかりですし。
パラメータ L と R という限定された条件で、ですけれども、変数 hc を（ついでに変数 dc も）観察して、理解を深めましょう。そうです、準備するのです。
＊＊＊
まずは、変数 hc です。Fig.D[R,hcFqlg].sw0.lp1000.L16384.R0-255 です。
パラメータは L=16384 と R=0〜255 です。横軸が R で、縦軸は hc のビット数の頻度（対数表示）です。ビット数 1〜15 までの 15 本のグラフがありますが、対数表示のため頻度 0 の部分は除外しています。凡例の s1 がビット数 1 のグラフです。lp 回の平均です。
ここで変数 hc のビット数の頻度とは、
hcQ = [0]*16
for s in hc:
hcQ[s] += 1
として求めた変数 hcQ のことです。hc = [0, 1, 1, 1, 2, 2, 3] なら hcQ = [1, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] になります。
変数 hc は、L=16K なので［リテラル］の頻度のバラツキは無くなっていて、s8 のグラフが R=255 でピーク値 255 を、s7 のグラフが R=127 で ピーク値 127 になっています（...時々、外れることもありますが）。これらはほぼ理屈通り（R=255 とかは zlib では非圧縮が選択されますけどね）。
ところが、s6 のグラフは、R=63 ではなく R=62 で ピーク値 63 になっています。s5 のグラフも、R=31 ではなく R=30 で ピーク値 28 になります。
これは長さと距離の圧縮によって発生した［長さ］の記号の影響です。R=63 では［長さ］が 3 個発生していて、そのうちの 1 つは［リテラル］とほぼ同じ頻度があります。つまり［リテラル］が 1 個増えたようなものです。そのため、R=63 より 1 つ少ないところでピークになるのでしょう（...R=127 や R=255 では［長さ］は 1〜2 個で［リテラル］より頻度は低い）。
R=63〜127 の区間に注目すると、R が増えるにつれてビット数 6 から 7 に移動していて、（対数軸なので曲線に見えますが）R が 1 増えると、ビット数 6 の符号語が 1 減り、ビット数 7 の符号語が 2 増えています。これも理屈通りの変化です（...、えと、何とかの不等式）。
R=120〜127 付近では、s6 と s7 の他には、s8, s9, s10 の 3 つがあります（s11 もありますが頻度 0.01 程度なので無視）。s8 は［リテラル］で、s9 は［終端］と［長さ］3 でしょう。s10 は［長さ］4 かもですが、得に s10 は上下の変化が激しく、その理由が思いつきません。不思議。
R=31〜63 も R=127〜255 も、概ね同じような変化ですね（...細かい部分では違いがありますけど）。
ですが R=0〜31 は全然違います！ 具体的には s4 がグチャグチャ状態です（...何それ？）。
これを分析するために、変数 hc を［リテラル］と［終端と長さ］に分離して、［リテラル］のみと、［終端と長さ］のみのビット数の頻度を表示してみましょう。パラメータや横軸・縦軸は同じままです。
［リテラル］のみの Fig.D[R,hc0-255Fqlg].sw0.lp1000.L16384.R0-255 です。
［リテラル］の符号語は 2〜3 個で、R>31 なら（10^0未満に目を瞑れば）規則的に変化しています（...これは入力をパラメータ L と R で制御しているからであることに注意を）。
一方、R=0〜31 は s4 の頻度が崩れていて、代わりに s6 が発生していることが分かります。
［終端と長さ］のみの Fig.D[R,hc256-285Fqlg].sw0.lp1000.L16384.R0-255 です。
R=0〜31 では［長さ］が多発していて［リテラル］よりも多い程です。そのため［長さ］の符号語が一番短くなっています。ビット数 1〜3 の符号語は全て［長さ］の符号語です。これで s4 の頻度が崩れたのでしょう。変数 hc の調整を検討する際には［長さ］の影響も考えざるを得ないのかも。
R=255 や R=127 では［終端］1 個と［長さ］が 1〜2 個で、R=63 や R=31 では［長さ］が 3 個程に増えていますね。...、分かります？
［終端］と［長さ］を別の図に分けて見ましょう。［終端］は Fig.D[R,hc256Fqlg].sw0.lp1000.L16384.R0-255 です。
［長さ］は Fig.D[R,hc257-285Fqlg].sw0.lp1000.L16384.R0-255 です。
んー、［長さ］の符号語のビット数ではなくて、［長さ］の頻度を直接確認しましょう。変数 hq でカウントしていますから、これをグラフにするだけです。
Fig.D[R,hqlg].sw0.lp1000.L16384.R0-255 です。パラメータは同じで、横軸は R、縦軸が hq の値です。対数表示です。0〜255 が［リテラル］、256が［終端］、257〜285 が［長さ］に対応する記号です。0〜255 はドット表示、256 と 257〜285 は連続線です。256 と 257〜285 は lp 回の平均ですが、0〜255 はバラツキ具合を把握するために 1 回目の値を表示していて平均していません。
頻度 1（10^0）の記号は［終端］ですね。R<16 などでは長さと距離の圧縮で［リテラル］は 頻度が下がっています。［長さ］は R=8 で 257〜266 くらいが発生していて、符号語のビット数は 1〜10 程です。
R>64 付近からは［長さ］より［リテラル］の頻度が多くなって、符号語が安定するのですね。
R=128 では［長さ］の符号語は 1〜2 個で、2 個になる確率は 0.5 くらいで、R=64 では 2〜3 個で、3 個になる確率は 0.1 くらい、と読み取れますね。
でも、hq のグラフから hc のグラフが何故こうなるのかは全て説明が付く（...理論的には！）のですが、まだまだ紙に二分木を書き出さないと分からないです。習熟不足か。
＊＊＊
参考までに。Fig.D[R,hq0-255].sw0.lp1.L16384.R0-255 です。［リテラル］のみを表示しました。
＊＊＊
私「うーん、hc はこのくらいで良いかー」
友「Zzz」
＊＊＊
次は、変数 dc です。dc のグラフは Fig.D[R,dcFqlg].sw0.lp1000.L16384.R0-255 です。パラメータとかは hc と同じです。
変数 dq のグラフも作りました。Fig.D[R,dqlg].sw0.lp1000.L16384.R0-255 です。
hc と比べると、dc はすっきりしていますね。
dc のグラフでは（s1 を除いて）s2〜s13 まで規則的に並んでいます。
dq のグラフでは R=32 に注目すると（s24〜s27 を除いて）下から順番に s0〜s3, s4〜s5, s6〜s7, s8〜s9, ..., s22〜s23 と並んでいます。
（L を固定して）R が増加すると長さと距離の圧縮が発生する頻度は下がり（dq は減少します）、発生する記号の数も減ります（dq のグラフでは、R=255 で全ての記号が頻度 1 を切っています）。記号の数が減ると符号語のビット数は短くなりますから、dc のグラフで、s13, s12, ..., s3, s2 の順で頻度が下がっていくのでしょう。そして、それと共に s1 は増加するのですね。極めて自然なことですね。
dq のグラフで、下から順に s0〜s23 が並んでいるのは、distance_codes の定義によるものでしょう。
distance_codes = {
0:(0, 1), 8:(3, 17), 16:( 7, 257), 24:(11, 4097),
1:(0, 2), 9:(3, 25), 17:( 7, 385), 25:(11, 6145),
2:(0, 3), 10:(4, 33), 18:( 8, 513), 26:(12, 8193),
3:(0, 4), 11:(4, 49), 19:( 8, 769), 27:(12,12289),
4:(1, 5), 12:(5, 65), 20:( 9,1025), 28:(13,16385),
5:(1, 7), 13:(5, 97), 21:( 9,1537), 29:(13,24577),
6:(2, 9), 14:(6,129), 22:(10,2049),
7:(2,13), 15:(6,193), 23:(10,3073) }
このように、s0〜s3 は［距離］の 1〜4 の各 1 つに対応し、s4 と s5 は 5〜8 の各 2 つ、s6 と s7 は 9〜16 の各 4 つ、s8 と s9 は 17〜32 の各 8 つ、...と順に 2 倍になっています。それで発生頻度も約 2 倍になるのです（...うむ、細かいことは、無視してね）。
R=32 の s0〜s27 の値です。約 2 倍ですね。
0.363 0.382 0.392 0.391 0.790 0.764 1.537 1.535
3.178 3.187 6.300 6.315 12.656 12.423 25.124 24.881
48.970 48.138 95.248 92.735 177.385 168.274 310.132 278.027
18.600 15.258 20.528 6.670
dq のグラフで s24〜s27 が例外になっているのは、zlib の独自仕様で［長さ］3 は［距離］4096 までと制限されているためでしょう。hq のグラフをみれば［長さ］は、3 が圧倒的に多くて、これが s24〜s27 では抑止されるのです。［長さ］4 だと頻度は下がります。hq のグラフによれば L=16384, R=31 では s258/s257 = 106.202/1269.664 = 0.0836 です（...、あー、数値は暫定の値です）。
それと、s28 と s29 が発生しないのは L=16384 だからです。16384+1 以上の［距離］は無いのです。
R=31 に固定して横軸を LENGTH にしてみました。Fig.D[L,dqlg,sw0,lp1000].L=0-16384.R=31 です。パラメータは L=0〜16384（64刻み）と R=31 です。横軸は L で、縦軸は dq です。0〜29 までの 30 本のグラフです。
s24〜s27 は各々 L=4096, L=6144, L=8192, L=12288 から立ち上がっていて、s0〜s23 とは異なる様子が見てとれますね。s24/s23 = 18.984/278.002 = 0.0682 です。
L=16384, R=255 に固定して、dc のビット数のパターンを調べました。次の 10 パターンが見つかりました。「：」の右側は1000 回中の発生頻度です。
[1,1] ___________ : 32 # Only 1,1
[1,1] ___________ : 404 !!!
[1,2,2] _________ : 288 !!
[1,2,3,3] _______ : 19
[1,3,3,3,3] _____ : 8
[1,3,3,3,4,4] ___ : 1
[2,2,2,2] _______ : 152 !
[2,2,2,3,3] _____ : 70
[2,2,3,3,3,3] ___ : 22
[2,3,3,3,3,3,3] _ : 4
最も頻度が高いのは、記号が 1 個か 2 個で [1,1] となるパターンで、404 回です。記号が 0 個で [1,1] となるのは 32 回でした。その次は、記号 3 個で 288 回、記号 4 個で 152 回と続きます。
ビット数 1 の頻度は、2*32 + 2*404 + 1*288 + 1*19 + 1*8 + 1*1 = 1188 回で、dc のグラフの R=255 の s1 の値とほぼ一致します。
ビット数 2 は 2*288 + 2*19 + 4*152 + 3*70 + 2*22 + 1*4 = 1480 回。
ビット数 3 は 2*19 + 3*8 + 3*1 + 2*70 + 4*22 + 6*4 = 317 回。
ビット数 4 は 2*1 = 2 回。だいたい合ってますね。
L=16384, R=192 の場合は次のようになりました。
[1,1] _________________ : 39
[1,2,2] _______________ : 134 !
[1,2,3,3] _____________ : 97
[1,2,3,4,4] ___________ : 19
[1,2,4,4,4, 4] ________ : 3
[1,3,3,3,3] ___________ : 37
[1,3,3,3,4,4] _________ : 15
[1,3,3,4,4,4, 4] ______ : 7
[2,2,2,2] _____________ : 129
[2,2,2,3,3] ___________ : 214 !!!
[2,2,2,3,4,4] _________ : 5
[2,2,2,4,4,4,4] _______ : 1
[2,2,3,3,3,3] _________ : 179 !!
[2,2,3,3,3,4,4] _______ : 21
[2,2,3,3,4,4,4,4] _____ : 8
[2,3,3,3,3,3,3] _______ : 62
[2,3,3,3,3,3,4,4] _____ : 17
[2,3,3,3,3,4,4,4,4] ___ : 3
[2,3,3,3,4,4,4,4,4,4] _ : 1
[3,3,3,3,3,3,3,3] _____ : 9
頻度最多は、記号 5 個の [2,2,2,3,3] で 214 回です。R が減れば、発生する記号が増えて、符号語のビット数も多くなりますね。これで dc のグラフの s1 の頻度は減ります。s2〜 の頻度が減らないのは、記号が 2 個ペアになって、頻度 2 倍の間隔で並んでいるから！
＊＊＊
私「dc は楽勝だよ！」
友「でもね、dc の符号語は hc と一緒になって、lc に反映されるのよ」
私「あー、それはとても面倒っぽい」
＊＊＊
