082 余談になります（２’’）
●100 余談になります（２’’）
ZIP ファイルを特定するためのスクリプトを走らせて部屋に戻ってきた（...あれ、また昨日に戻っている？）。
ご飯を食べて、夜になるも、なかなか寝付けない。
それで、zlib で適当な文字列を圧縮して［ビット列］を作って、手動でデコードをしてみることにする。ちょっとだけなら良いだろう。
［ビット列］の先頭 3 ビットはデータブロックのヘッダーで、後続ブロックの有無などの情報である。4 ビット目以降がデコードの対象だ。
＊＊＊
具体的に、動的ハフマン符号の場合で説明しよう。
動的ハフマン符号では、デコードの前にデータブロックからデータを読み出して、符号語と記号の対応表（符号表）、つまりハフマン符号を 2 つ作る。その変数名を hc と dc としよう。
まず 3 つの値を読み込む。5 ビットの hlit、5 ビットの hdist、4 ビットの hclen だ。
次に「hclen+4」個ある 3 ビットのデータを読み込んで変数 lc とする。その際、順番を bit_ord で置換する。
変数 lc の例：
lc = { 0: 3, 1: 7, 2: 6, 3: 6, 4: 7, 5: 0, 6: 6, 7: 2, 8: 2,
9: 0, 10: 0, 11: 0, 12: 0, 13: 0, 14: 0, 16: 4, 17: 2, 18: 0 }
変数 lc に読み込んだデータは、符号語のビット数を、対応する［記号Ｃ］の辞書順に並べたものである。［記号Ｃ］は 0〜18 である。そして、この lc を使って記号に対応する符号語を、つまりハフマン符号Ｃを作ることができる。ビット数を並べただけでハフマン符号が作れる理由は後述します！
実は、この後に読み出す hc と dc のデータはこのハフマン符号Ｃで符号化されているのです。
符号語のビット数の並びからハフマン符号の符号表を作るアルゴリズムは RFC1951 で解説されている。RFC1951 の説明に従いますか＜Ｙ／Ｎ＞？
Ｎｏだ（...ＹＥＳしたらループするんだろ！）
＊＊＊
RFC1951 は符号語をビット数と整数で表しているが、0 と 1 からなる文字列も作って見よう。見て分かり易いから。
入力は変数 lc。記号を 0, 1, 2, 3,..., 18 として、対応する符号語のビット数 a, b, c, d,... を格納したもの。
{ 0:a, 1:b, 2:c, 3:d,... }
出力は、変数 lc2。符号表を 2 種類。1 つ目は主にデバック用だ。2 つ目はこの後の処理で使う。
{1:{0: (a, '00', ex), 1: (b, '01', ex),
2: (c, '101', ex), 3: (d, '111', ex), ... },{
2:{(v0+0): (0, a, ex), (v0+1): (0, a, ex),
(v0+2): (0, a, ex), ...
(v1+0): (1, b, ex), ...
(v2+0): (2, c, ex), ... } }
v0 は符号語を 7 ビットになるまで末尾に 0 を追加して数値化したもの。次の符号語までの隙間を全部埋めて、0〜127 の表にする。7 ビットに拡張するのは lc のデータは 3 ビットなので、その値は 0〜7 の範囲にあり、最大で 7 ビットでよいからです（...何言ってるのか分からないよ？）。
ex は補助のビット数だ。次のように定義されている。
bit_ext = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7]
さて、lc2 を作ろう。
code = 0; blop = 64; lc2 = {1:{},2:{}}
for bit in range(1,8):
for c in sorted(lc):
if lc[c]==bit:
lc2[1][c] = (bit,format(code,"0%db"%bit),bit_ext[c])
for l in range(blop):
lc2[2][code*blop+l] = (c,bit,bit_ext[c])
code += 1
code = code * 2; blop = blop / 2
＊＊＊
私「何をしているかは、見れば分かるよねー」
友「いや駄目だろ。...、変数 bit は 1〜7 と変化して、lc のビット数の小さいものから順に code を割り振って、code を１インクリメントする。あと変数 bit が１増えると code は 2 倍にする。lc2[1] には、記号（変数 c）に対応する「ビット数、code をビット列にしたもの、補助ビット数」の 3 つを格納。lc2[2] は、次の符号語との隙間分だけループを回して、code に対応する「記号、ビット数、補助ビット数」の 3 つを格納する、...とか説明しなさい。あと、記号なのに変数名は c なの？、紛らわしくない？、そもそも c4 って何？」
私「...は？c4って何」
＊＊＊
RFC1951 の説明通りだとループ回数は 18+7+18。こちらは 7*18 回で負けている。でもこちらの方が直感的で、まぁ、これはこれでよいと思う。前世代のプログラマーはメモリの 1 ビットやＣＰＵの 1 クロックを削る為に懸命になっていたと何かの記事で読んだけれど、それと比べると全く緊張感がなくて申し訳ない。スクリプトだと変数 1 個が 50 バイトだよ。シンプルに記述して見通しを良くすることを優先するよ。
RFC1951 で作った変数 tree と同じものは次のようにしても出来る。
code = 0; tree = {}
for bit in range(1,8):
for s in sorted(lc):
if lc[s]==bit:
tree[s] = (code,bit); code += 1
code = code * 2
ループ中、変数 bit は 1〜7 と変化して、lc に同じ値があったら、変数 tree に code と bit のペアを格納して、code を +1 する。変数 bit が１増えるタイミングで code を 2 倍にする。
変数 lc2 の例： 変数 lc の例に対応する lc2[1] を示す。
{ 0:(3, '110', 0),
1:(7, '1111110', 0),
2:(6, '111100', 0),
3:(6, '111101', 0),
4:(7, '1111111', 0),
6:(6, '111110', 0),
7:(2, '00', 0),
8:(2, '01', 0),
16:(4, '1110', 2),
17:(2, '10', 3) }
lc2 は［記号Ｃ］とその符号語の対応を示した表、符号表となる。例えば記号 0 にはビット数 3 の符号語「110」を対応させている。短い符号語を対応させている記号 7 や 8 は使用頻度が高いのでしょう、きっと。
＊＊＊
ふう。まだデコードを開始できない。ちなみに、lc2 と tree の内容を比較して、符号語が一致することを確認した。どちらを使っても大丈夫そうだ。
＊＊＊
最後に、hc と dc のデータを読み出して、lc2 でデコードする。これが今回の目的だ。
hc と dc のデコード処理は全く同じなので「hlit + 257 + hdist + 1」、つまり「hlit + hdist + 258」個分を一気にデコードしてから、hc と dc に分割するのがよい。RFC1951 にもそう書いてある（...ように読めるのだけども違うのかな？）。hc と dc を別々に処理すると dc の最初の記号が 16 だった場合は例外処理が必要になる。
hc_dc = []
while len(hc_dc) < (hlit+257+hdist+1):
(c,b,be) = lc2[2][cnv_n(r[0:7])]; r = r[b:]
ex = cnv_n_r(r[0:be]); r = r[be:]
if c<=15: hc_dc += [c]
elif c==16: hc_dc += [hc_dc[-1]]*(ex+3)
elif c==17: hc_dc += [0]*(ex+3)
elif c==18: hc_dc += [0]*(ex+11)
hc = hc_dc[:hlit+257]; hc2 = cnv_cano(hc)
dc = hc_dc[hlit+257:]; dc2 = cnv_cano(dc)
まず、［ビット列］から所要のビットを取り出して数値に変換して、［記号Ｃ］（変数 c）とそのビット数（変数 b）、補助のビット数（変数 be）を求める。lc2 の２つ目の表を参照すれば簡単だ。
ついで、補助のビットも取り出して数値（変数 ex）にする。ビット順の反転を忘れないように。記号によっては補助ビットがない場合もあるが、その時は 0 個のビットを切り出して、0 とする処理になっている。
［記号Ｃ］を処理する。0〜15 はリテラルで、そのまま hc_dc に追加する。16, 17, 18 は、hc_dc の末尾をコピーするか、0 を追加する処理だ。このコピー回数に補助の値 ex が加算される。
データ数が既知なので終端はない。
リテラルの 0 はこの符号語のビット数は 0 であり、使われないことを意味する。リテラルが 15 までということは、動的ハフマン符号の符号語のビット数は最大 15 と制限されることを意味する（...え？、リテラルが符号語のビット数？、もしかして）
この hc と dc は、ハフマン符号の符号語のビット数を並べたもので、つまり、hc と dc から符号表を作れたらデコードを開始できる（...さっき、最後に、とか言ってなかった？、あれは嘘か）。
＊＊＊
友「結局、デコードのスクリプトを書いたの？」
私「はい、眠れなかったので、止むを得なくて」
友「全部？、最後まで？」
私「それはもう、乱数生成したデータを zlib で圧縮して、スクリプトでデコードして、もちろんＬＺ７７も展開して、元データと一致することを１万回位テストして、パスして、あ、乱数は疑似乱数なんだけども、やはりクリプトっぽいのが必要かな、シードを見破られるとチートの恐れが、それと繰り返しは 32K 回は必要かな、長さ＆距離の確認のために連続データを入れて、でもあまりパラメータの吟味はできてなくて、hc の符号語を頻度分析したら、リテラルは 256 個の全部が出るけど長さは 25 個くらいで、あ、一度 28 を見たけど、dc も 26 個くらいで、無理やりデータ作れば 29 も出るんだろうけど、逆に dc が 1 や 0 のケースがあるのか気になって、2 までは作れたけど、どう思う...？」
友「長いわ！、夜は早く寝て！」
今日はもう寝ることにします。おやすみなさい。
＊＊＊
私「Zz...（はっ）。そう言えば手動でデコードしていないよ！」
＊＊＊
s = "ABCD"*1024
x = zlib.compress(s)
r = cnv_b(x[2:-4])
print r
「ABCD」を 1024 回繰り返した 4096 バイトの文字列を zlib の入力としよう。zlib の出力はヘッダ 2 バイトとフッター 4 バイトを外すと 25 バイトで、これをビット列にする。その際、最下位ビットを先にする。これを手動でデコードしよう。
10110111 11000011 10000000 10110000 00000000 00000000
00010000 11000000 00000101 00110110 11101011 11101111
11110011 00100110 11110000 11100000 11011000 10011001
10110110 00101010 10101010 10101010 10101011 11101011
11110000
先頭 3 ビットはデータブロックのヘッダービットで、次の 5+5+4 ビットは hlit、hdist、hclen だ。続いて (hclen+4)*3 ビットの lc と、hlit+hdist+258 個分の hc と dc。その後はデータの本体となる。
ビット列をこれらの 5 グループに分けると次の [1]〜[5] となる。
[1] 1 01
[2] 10111 11000 0111
[3] 000 000 010 110 000 000 000 000 000
000 000 010 000 110 000 000 000 010
[4] (10 0110110) 111 01 01 111 (10 1111111) (10 0110010) 01 (10 1111000)
01 110 00 00 110 110 00
[5] 100 1100 1101 101 100
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (1111 01011) 1
1110 000
まず、[1] のヘッダービットは、「1」は最後のブロック、「01」は反転して 10 で動的ハフマン符号であることを示す。
次の [2] の hlit、hdist、hclen は、29, 3, 14 だ。反転してね。
[3] は、「hclen+4 = 18」個あり、bit_ord で順番を入れ替えて、反転して、数値にして、0 を除くと、
lc = { 0: 3, 1: 2, 3: 3, 4: 2, 18: 2 }
となる。符号語のビット数 3, 2, 3, 2, 2 をソートして 2, 2, 2, 3, 3。これに対応する符号語は「00, 01, 10, 110, 111」なので、符号表を作ると、
lc2 = { 0: (3, '110', 0),
1: (2, '00', 0),
3: (3, '111', 0),
4: (2, '01', 0),
18: (2, '10', 7) }
となる。これを使って [4] をデコードする。「10」は補助ビットが 7 あるが、それ以外は補助はなくて符号語で区切って記号にすればよい。そして、[4] の前半の「hlit+257 = 286」個は hc で、後半の「hdist+1 = 4」個が dc だ。「 [0]*65 」は 0 が 65 個あるという意味です。65 + 4 + 138 + 49 + 1 + 26 + 3 で 286 になります。
hc = [0]*65 + [3, 4, 4, 3] + [0]*138 + [0]*49 + [4] + [0]*26 + [4, 0, 1]
dc = [1, 0, 0, 1]
ここからビット数が 0 のものを除いて、記号と符号語のビット数の対応を示すと、
hc = { 65: 3, 66: 4, 67: 4, 68: 3, 256: 4, 283: 4, 285: 1 }
dc = { 0: 1, 3: 1 }
となる。hc のビット数はソートすると 1, 3, 3, 4, 4, 4, 4 なので、符号語は「0, 100, 101, 1100, 1101, 1110, 1111」、符号表は、
hc2 = { 65: (3, '100', 0),
66: (4, '1100', 0),
67: (4, '1101', 0),
68: (3, '101', 0),
256: (4, '1110', 0),
283: (4, '1111', 5),
285: (1, '0', 0) }
となる。次に dc は 1, 1 なので、符号語は「0, 1」。符号表は、
dc2 = { 0: (1, '0', 0),
3: (1, '1', 0) }
となる。この hc2 と dc2 を使って [5] をデコードしよう。
まず、[5] の最初の「100 1100 1101 101 100」は、［記号Ａ］の 65, 66, 67, 68, 65 となり、そのまま、［リテラル］で ABCDA だ。
次の「0」は［記号Ａ］の 285 で［長さ］258、「1」は［記号Ｂ］の 3 で［距離］4 である。後ろから 4 番目を 258 回コピーする。これが 15 セット続く。
その後、「(1111 01011)」と「1」で、［記号Ａ］283 と［補助１］の 5 ビットで［長さ］221、と［記号Ｂ］3 で［距離］4 で、後ろから 4 番目を 221 回コピーする。
あと、「1110」は［記号Ａ］256 で［終端］である。
デコードした結果は、
dec = [65, 66, 67, 68, 65,
(258, 4), (258, 4), (258, 4), (258, 4), (258, 4),
(258, 4), (258, 4), (258, 4), (258, 4), (258, 4),
(258, 4), (258, 4), (258, 4), (258, 4), (258, 4), (221, 4), 256]
となる。ABCDA を出力して、後ろから 4 番目のコピーを「258*15 + 221 = 4091」回行う。これで 4096 バイトとなる。
"ABCD"*1024 のような単調なデータだからですが、長さ 258 と距離 4 を「0」と「1」の２ビットで表現しています。258 バイトを 2 ビットに圧縮と凄く効果的ですね。
＊＊＊
私「4096 バイトを 25 バイトに圧縮できるのはすごいですけれど、元々は「"ABCD" * 1024」の 11 バイトなのでは？」
友「...、ところで、手動ってどういう意味？」
私「それは勿論、手でスクリプトを打ち込んで、手でコンソールをたたいて、出力をエディタでカチャカチャだよ、全部手動」
友「...、おやすみなさい」
＊＊＊
