112 余談になります（３）
●112 余談になります（３）
Calgary corpus の謎について、調べてみました！
＊＊＊
Deflate で使用するハフマン符号の符号語のビット数は最大で 15 と制限されている。
乱数生成したデータではビット数が最大となる符号語は発生しなかったので、止むを得ず、記号の発生頻度を意図的に操作して、15 ビットの符号語の作成を試みた。中途半端な頻度の記号が二分木の成長を阻害するのを排除して、そして遂にオーバーフローさせることに成功した。
符号語のオーバーフローを目にした主人公は、オーバーフローの秘密を解くため、迷宮 zlib の奥深くに進んだ。トラップを避け、無限ループの出口を探す。探索を続ける最中、最下層の壁に「これは Calgary corpus の ....、で発生する」と記されていることを発見した。
これは何のメッセージか。Calgary corpus とは何か？、コメントに誘われるように調べ始めると、謎が謎を呼ぶ混沌とした状態に陥っていく、...。
＊＊＊
友「何書いてんの？」
私「えへ、ちょっと雰囲気を変えようと思って」
友「ビット数がオーバーフローした時って、寝てたでしょ？」
私「そうなんだけど（泣）、...そう言えば、なんで起こしてくれないの」
友「寝てたから。夜はしっかり眠りましょう」
＊＊＊
zlib は Calgary corpus の obj2 と pic でオーバーフローが発生するとコメントしている。
丁度、符号語（二分木）を生成して、そのビット数をカウントした後、ビット数が制限値を越えていることを判定した場所でのコメントだ。「This happens ...」と。obj2 や pic とは何か、何を意図したコメントなのでしょうか。
調べてみると「Calgary corpus」とは 90 年代にデータ圧縮法の比較に使用されたファイルセットのことでした。1987 年に開発され、1989 年に論文発表されている。データ圧縮業界では知られている存在らしい。
Calgary corpus の「Calgary」はカルガリー大学のことで、「corpus」は「言語資料」という意味らしい。コーパスって聞いたことがある気が微かにする（...言語辞典？）。
Calgary corpus は 14 個のファイルからなり、ファイルの合計は 3,141,622 バイト。そして obj2 と pic とは、その 14 ファイルのうちの 2 ファイルのこと。obj2 は 246,814 バイト、pic は 513,216バイトのファイル。
Wiki によれば Deflate（...実際には Info-ZIP とか gzip）で Calgary corpus を圧縮すると 1MB 程になるらしい。実際、Calgary corpus の ZIP ファイルをダウンロードしたら 1,066,978 バイトでした。
あと、Calgary corpus を使った圧縮アルゴリズムの競技について解説があって、589,863 バイトという記録が出ているそうだ。Deflate の半分近くだ。これはこれで凄いことだけれども、zlib とは前提条件が違うよね。圧縮に要する時間とかメモリとか。
それはさておき。コメントの意味は分かった、...気がしますね。
＊＊＊
早速、calgary.zip をダウンロードして調べてみた。
まず、calgary.zip を UNZIP すると 18 個のファイルが出てくる。あれ？、と Wiki を再度、確認すると、途中で 4 ファイルが追加されたようだ。了解です。
ダウンロードしたファイルは破損していないことが分かったので、次は calgary.zip をスクリプトでデコードしてみる。
calgary.zip で PK34 を探すと 18 個見つかる。PK34 のレコード（...正式には Local file header といいます）が見つかった場所に PK34 のレコードのバイト数を加算するとデータストリーム（圧縮データ）の開始場所となる。それと PK34 レコードの +12h にはデータストリームのサイズがある。これで Deflate のデータストリームを特定できるので、切り出してデコードする。
calgary.zip に含まれるファイルには大きなファイルもあって、データストリームは複数個のデータブロックに分かれている。一番大きいのは book1 で（圧縮データで）313,351 バイトだった。6 個のブロックに分かれている。1〜5 個目のブロックは 57〜59KB で、最後のブロックが 17KB 程。
データブロックが複数個ある場合の処理もスクリプトは対処済みなので特に修正はない。アロケーションブロックの直読みから、ファイルシステム上のファイルを読むように変更（...ファイル名でアロケーションブロックにアクセスできるのって何か新鮮な感じがする。ファイルシステムって便利だった）。
データブロック毎に hc と dc とかをログに出力していく。
念の為にスクリプトのデコード結果を UNZIP で展開されたファイルと比較する。もちろんバイナリコンペアで一致する。
色々と事前確認して上で、obj2 と pic の符号語、具体的には変数 hc2 と dc2 を表示すると、...オーバーフローしていない。obj2 の hc の符号語は 14 ビットまで。dc は 10 ビットまで。pic は 12 と 10。全くオーバーフローしていない。
どういうことなのでしょうか？
発生頻度から二分木を生成してみても符号語のビット数は 14 ビット。zlib のコメントには、...歴史的な経緯とかがあるのでしょうか。
＊＊＊
calgary.zip を UNZIP したファイルを zlib で圧縮してみると更に混乱しました。
obj2 は ZIP ファイルでは 8 ブロックだったのが zlib では 4 ブロックになってしまいました。圧縮後のデータサイズも微妙に違います。
どういうことなのか分かっていないのですが、ZIP コマンドと zlib の実装は完全に同じモノというわけではなさそうです。
歴史的には、PKZIP の UNIX版 Info-ZIP（ZIP コマンドと UNZIP コマンド）があって、PKZIP2 で Deflate が公開された後、Info-ZIP も Deflate を実装して、その後、Deflate の実装をライブラリとして切り出したものが zlib なのだから、ZIP コマンドは zlib をコールしている位の勢いで全く同一の実装なんだろうと思い込んでいました。
更にですね、UNZIP したファイルを ZIP コマンドで再度圧縮すると、圧縮後のデータサイズが微妙に違っています。ブロック数も、元の calgary.zip と 17 ファイルは同じですが、1 ファイル（news というファイル）が違っていました。
ZIP コマンド同士でも差異があるようです。何が違うのでしょうか？
＊＊＊
私「えーと、推理小説ではないので、謎は要らないのですけど（困惑）」
友「謎ですって。ワクワクしますね」
＊＊＊
＊＊＊
＊＊＊
状況を整理しましょう。18 ファイルのうちの obj2 を中心に追求します（...他は必要に応じて参照しましょう）。
まず、圧縮後のデータサイズと、データブロック数。
（１）オリジナル状態： 81,572 バイト、データブロック 8 個
（２）ZIPで再度圧縮 ： 81,608 バイト、データブロック 8 個
（３）zlibで圧縮 ： 81,499 バイト、データブロック 4 個
データブロックの［リテラル｜終端｜長さと距離］の数（...以下これを要素の数と表現します）を数えると、
（１）[ 4097, 4097, 16385, 4097, 8193, 4097, 12289, 298 ] 計 53,553
（２）[ 4097, 4097, 16385, 4097, 8193, 4097, 12289, 288 ] 計 53,543
（３）[ 16384, 16384, 16384, 4387 ] 計 53,539
でした。データブロックごとのビット数も載せておきますね。
（１）[ 43120, 40549, 190296, 54388, 109448, 53016, 158599, 3155 ] 計 652571 bit (81571.375 byte)
（２）[ 43148, 40620, 190344, 54380, 109517, 53134, 158670, 3049 ] 計 652862 bit (81607.750 byte)
（３）[ 168588, 215749, 214763, 52888 ] 計 651988 bit (81498.500 byte)
（１）と（２）はブロック数は同じですが、最後のデータブロックの要素の数が 10 違います。圧縮後のデータサイズも一致しません。ZIP コマンドのバージョン違いのせいでしょうか。（３）はデータブロックの数が違います。
要素の数の合計は、データブロックの最後にはＥＯＢが付いていて、それを除くと（１）は 53,545、（２）は 53,535、（３）は 53,535 ですから、（２）と（３）は同じで、（１）だけ 10 多いのです。
[116] の説明によれば、zlib はバッファがフルになるとデータブロックを切断して次のブロックにするそうです。そして、16384 は zlib のデフォルトのバッファサイズと一致します。それと（１）と（２）の ZIP は、（３）の zlib とは違い、バッファ・フル以外の条件でもデータブロックを切断するそうです。
ダウンロードした calgary.zip と、それを ZIP コマンドで再圧縮したもの、そして zlib による圧縮の 3 つについて、同異とその原因を明らかにしたいですね。
以下、（１）と（２）を区別したいときは、ダウンロードした calgary.zip を ZIP、ZIP コマンドで再圧縮したものを reZIP とします（...zlib は zlib ですよ）。
データブロックの切断から確認して行きましょう。
＊＊＊
＊＊＊
＊＊＊
ZIP のソースを見てみたところ、データブロックを切断する条件は次のような感じです。
要素の数が 4095 以下では切断しません。32768（32K）になるとバッファ・フルで切断します。このときは 32768-1 でフルと判定して、フラッシュ時に終端を追加して 32K ピッタリとなります（...32K は ZIP のバッファサイズです）。
要素の数が 4096〜32768-2 の範囲では「距離／リテラルの比」と「出力／入力の比」の 2 つを調べて、両方共に 50% 未満であるときに切断と判定するようです（...何故、こんな条件で判定するのかは全然理解できていませんけれどもそのようなコードになっています）。
判定は 4096 毎に行います。その為、切断するときは 4096 単位となり、これに終端が追加されて、データブロックの要素の個数は 4096*n+1 になります。1 余分なのは、...別にいいですけどね。ZIP のデータブロックの要素の数は（最後のブロックは除いて）、4097 = 4096*1+1, 8193 = 4096*2+1, 12289 = 4096*3+1, 16385 = 4096*4+1, ...となっています。データブロックの要素の個数（12289 とか）を直に書く代わりに、n の値（3 とか）を示すことで圧縮表記できますね（...後で使うので覚えておいてね）。
なお、ZIP のソースをみたら deflate.c の冒頭に「#ifndef USE_ZLIB」という記述があり、対となる #endif は最終行でした。つまり USE_ZLIB が定義されると deflate.c は空になります。zlib を使用するかはコンパイル時に選択できるみたいですね。利用した ZIP コマンドは、ZIP ファイルの状況から zlib は使用していないのでしょう。
＊＊＊
距離／リテラルの比とは？
距離／リテラルの比は、［リテラル｜長さと距離］をバッファに格納する際にリテラルと距離の個数をカウントしていて、これらを比較します。
（圧縮時の）ＬＺ７７の出力は［リテラル］か［長さと距離］です。ZIP の ct_tally() では［リテラル］と［長さ］をリテラルのバッファに格納して、リテラルの個数とします。［リテラル］のときも［長さと距離］のときもリテラルの個数は +1 されます。距離の個数は［長さと距離］のときだけ +1 です。
例えば、
dec = [ LIT, LIT, (LEN,DIS), LIT, (LEN,DIS), (LEN,DIS) ]
だと、リテラルの個数は 6 個、距離の個数は 3 個です。比率は 50% になります。
リテラルの割合が多い（長さと距離の圧縮が少ない）と切断するのはどうしてなのでしょうか？
切断しても入力データは変わらないのでリテラルの割合は同じですよね。dc の符号表をリセットしたいのでしょうか。
＊＊＊
出力／入力の比とは？
入力は圧縮前の生のデータのことです。現在のデータブロックの先頭から処理中のデータまでのサイズです。これはまさに処理中なのでポインタから直ぐに計算できます。データブロックの先頭を指すポインタと、現在処理中のデータを指すポインタがあり、この 2 つの差が入力データのサイズになります。
出力については、この時点では確定していないため、簡易的な式で、バッファに蓄積されたデータを固定ハフマン符号っぽく符号化したときのバイト数を計算します。
具体的には「リテラルの個数 ＋ 距離の頻度とビット数の積和／８」です。出力には符号表のデータは含まないようです。リテラルと長さ、つまり［記号Ａ］は固定ハフマン符号でも 7〜9 ビットと記号により異なりますが、全部 8 ビットとしてカウントします。［補助１］は無視します。距離は、固定ハフマン符号の［記号Ｂ］が 5 ビット固定だからでしょうか、全部 5 ビットとして、これに［補助２］のビット数を加算して、頻度との積和を求めています。記号の発生頻度はバッファに格納するときにカウントしています。
出力／入力の比は圧縮率に相当する値だと思います。圧縮率が良ければ続行して、符号表と入力データがミスマッチして圧縮率が悪化したら切断して符号表をリセットする、...のではなくて、圧縮率が良くなる（50% 未満になる）と切断するのはどうしてなのでしょうか。符号表は同じままで長く使用した方が効率が良さそうですけれども。
現在の符号表を使った圧縮率を計算していないことからして、符号表と入力データのミスマッチは考慮してないのかもしれません。とすると、何を目的に切断するのか。考察が足りないですね。理解が及びません。
＊＊＊
calgary.zip の 18 個のファイルについて、データブロック毎に 2 つの比を求めると、32K のブロックは少くとも片方は 50% 以上、32K 未満のブロックは両方が 50% 未満になっていました（...もちろん、最後の BFIN=1 となるデータブロックは別です）。
＊＊＊
obj2 について、もう少し細かく 4K 単位で調べてみました。obj2 は 8 個のデータブロックに分かれていて、
1: 0 EOB{4097}
2: 0 EOB{4097}
3: 1 1 1 0 EOB{16385}
4: 0 EOB{4097}
5: 1 0 EOB{8193}
6: 0 EOB{4097}
7: 1 1 0 EOB{12289}
8: EOB{298}
となりました。0 は切断（両方が 50% 未満）で、1 は継続（0 以外）です。EOB の後ろの値はデータブロックのリテラルの個数です。32768 未満は切断か、BFIN=1 となる最後のブロックです。
ZIP と reZIP とでデータブロックの個数が違っていた news についても確認してみます。切断と、バッファ・フル（32768）、最後のブロック（BFIN=1）の 3 パターンがありますね。
ZIP の場合（データブロック 4 個）：
1: 1 1 0 EOB{12289}
2: 1 1 1 1 1 1 1 EOB{32768}
3: 1 1 1 0 EOB{16385}
4: 1 1 1 1 1 1 1 EOB{29003}
reZIP の場合（データブロック 7 個）：
1: 1 1 0 EOB{12289}
2: 1 1 1 1 1 1 1 EOB{32768}
3: 1 1 1 1 1 1 1 EOB{32768}
4: 0 EOB{4097}
5: 0 EOB{4097}
6: 0 EOB{4097}
7: EOB{323}
ZIP と reZIP を比べてみると、3 個目のデータブロックの 4 回目の判定で ZIP は切断（0）と、reZIP は継続（1）としています。3 個目のデータブロックの距離の個数と、リテラルの個数は、
__ZIP：[2127, 4096] 1 [4204, 8192] 1 [6267, 12288] 1 [8189, 16384] 0 （...略）
reZIP：[2132, 4096] 1 [4213, 8192] 1 [6286, 12288] 1 [8215, 16384] 1 （...略）
です。4 回目の判定で、リテラルは 16384 なので、50% となる距離の個数は 8192 個です。ZIP は 8189 個で 3 個足りず（reZIP は 8215 個）、ここで判定が分かれました。
この後にＬＺ７７の出力の差異を比べてみますが、reZIP だと長さ＆距離を 2 個出力するところを、ZIP はリテラル 1 個と、長さ＆距離 1 個を出力します。そのため、ZIP は（reZIPより）距離／リテラルの比が小さくなる傾向があります。これが差異の原因でしょう。
あと、zlib で圧縮したデータは 2 つの比には関係なく（BFIN=1 となる最後のデータブロックは除いて）全て 16KB でした。
データブロックの個数が違う原因は、把握できて来ましたね。切断条件が何故これなのかは不明ですけれども、...。
＊＊＊
＊＊＊
＊＊＊
ZIP と reZIP と zlib との違いを整理しましょう！（...あ、分かった範囲での差異ですよ、真に正しいかは不明ですよ）
比較する観点は、ＬＺ７７、データブロックの切断、ハフマン符号の３つです。
・ＬＺ７７ ： reZIP と zlib は同じ。ZIP だけ違う。
・ブロック切断： ZIP と reZIP は切断あり。zlib は切断なし。
・ハフマン符号： みな同じ。
確認したことは次のことです。
ＬＺ７７の出力（変数 dec）を最後のＥＯＢを除去して連結すると、reZIP と zlib では 18 ファイルの全部で一致しました。ZIP は 18 ファイル中、16 ファイルで不一致でした（一致したのは paper4 と paper5 の 2 つ）。
reZIP のＬＺ７７の出力をスクリプトでハフマン符号で符号化してみましたら、reZIP から抽出した圧縮データと一致しました。18 ファイルの全部です。同様に、ZIP と zlib のＬＺ７７の出力をスクリプトで変換すると各々の圧縮データと一致しました。
このことから、ハフマン符号の処理はどれもスクリプトで記述した処理と同じだと考えられます（...ハフマン符号の符号化の処理は後述しましょう）。
＊＊＊
ＬＺ７７には、deflate_fast() や deflate_slow() などをパラメータで選択できる他に、コンパイル時の調整でバッファサイズなどが違う可能性があり得ます。calgary.zip が作成されたのは多分 90 年代で（...遅くとも 2001年）、現在とは何か違うのでしょう、きっとね。
圧縮データが違っていてもデコード結果（元データ）は一致します。Deflate というフォーマットに準拠していればデコード結果が保証されるのですね。有り難いことです。
＊＊＊
＊＊＊
＊＊＊
ＬＺ７７の出力が違うとは、どのように違うのか確認したいですね。ZIP のデータブロックをダンプして zlib と比較してみましょう。
ＬＺ７７の出力が異なる例を示します。obj2 のデータです。左端の数値は、変数 deca の添字です（...リテラルのバッファの番号？）。その右側がＬＺ７７の出力（変数 deca のデータです）で、ZIP と zlib の場合の値を並べてあります。丸カッコの中の 4 個は、順に、記号Ａ、記号Ｂ、リテラル（または長さ）、距離です。リテラルの場合は記号Ｂと距離は 0 にしています。
NUM : ZIP________________: zlib_______________
1720: (_41, _0, 41, __0) : (_41, _0, 41, __0)
1721: (_35, _0, 35, __0) : (_35, _0, 35, __0)
1722: (269, 16, 20, 305) : (269, 16, 20, 305)
1723: (259, 21, _5, 1922): (259, 21, _5, 1922)
1724: (257, 16, _3, 292) : (257, 16, _3, 292)
1725: (_52, _0, 52, __0) : (_52, _0, 52, __0)
1726: (260, 15, _6, 228) : (260, 15, _6, 228)
1727: (_40, _0, 40, __0) : (269, 16, 21, 341) <-False
1728: (273, 10, 35, _36) : (267, 10, 15, _36) <-False
1729: (258, 16, _4, 262) : (258, 16, _4, 262)
ＬＺ７７の出力は、右端に False と表示している 2 箇所、1727 番と 1728 番で不一致しています。
ZIP の場合は LIT:40 と (LEN:35, DIS:36) で、zlib は (LEN:21, DIS:341) と (LEN:15,DIS:36) です。コピー先をどこに求めるか、という方向性の違いでしょうか。
デコード結果は、どちらも 36 バイトの出力で、次のように一致します。
NUM : ZIP
1727: 40
1728: 35 60 51 35 49 35 61 58 32 35 50 37 32 62 35 51 32 32 35 60
51 35 37 49 35 35 55 35 52 35 61 58 32 35 53
NUM : zlib
1727: 40 35 60 51 35 49 35 61 58 32 35 50 37 32 62 35 51 32 32 35 60
1728: 51 35 37 49 35 35 55 35 52 35 61 58 32 35 53
符号語のビット数を確認しましょう。関係するのは、記号Ａ（hc）の 40, 267, 269, 273 と、記号Ｂ（dc）の 10 と 16 ですね。
まず、ZIP
hc 40: (9, '110101110', 0) #Fq 10 BxFq 90
hc 267: (8, '11001110', 1) #Fq 21 BxFq 189
hc 269: (9, '111010101', 2) #Fq 10 BxFq 110
hc 273: (11, '11111101101', 3) #Fq 3 BxFq 42
dc 10: (4, '0011', 4) #Fq 123 BxFq 984
dc 16: (4, '0110', 7) #Fq 109 BxFq 1199
次は、zlib
hc 40: (8, '10011100', 0) #Fq 60 BxFq 480
hc 267: (7, '1001000', 1) #Fq 91 BxFq 728
hc 269: (8, '11000100', 2) #Fq 48 BxFq 480
hc 273: (10, '1111101011', 3) #Fq 12 BxFq 156
dc 10: (4, '0010', 4) #Fq 319 BxFq 2552
dc 16: (4, '0101', 7) #Fq 283 BxFq 3113
ZIP は、hc:40 と hc:273 & dc:10 だと 9+14+8=31、hc:269 & dc:16 と hc:267 & dc10 だと 11+11+9+8=39 です。
zlib は 8+13+8=29 と 10+11+8+8=37 です。
ZIP と zlib のどちらにとっても ZIP の出力の仕方の方がビット数が 8 少ないです。ZIP は記号 3 つなのに対して、zlib は記号 4 つなので、ZIP の方が少ないビット数になるのは自然ですね。
こういうチリツモで圧縮データのサイズの違いが出てくるのでしょうけれど、1727 番で ZIP も 40 に続く 21 バイトが距離 341 にあるのを見ているはずですが、長さと距離の圧縮を行わずに次の 1728 番で 35 回コピーすることを選択しています。
何がどうしてこうなるのでしょうか。
試しに zlib の圧縮時のパラメータを変えて試してみたところ、デフォルトの値では上述のとおりですが、lvl=9 をセットしたところ挙動が変わりました（...デフォルトは lvl=6 です）。
lvl=9 では 2026 番まで False 無しとなります。つまり、zlib でも lvl をアップすれば、1727番で ZIP と同じく、少ないビット数となる出力を選択できるようです。
ただし、lvl=9 にすると、1727番の False はなくなりますが、False の発生箇所は lvl=6 のときよりも増えています（...False が多いのは、圧縮処理が強化されて、沢山圧縮できたからでしょうから良いことですけれども）。
0〜4096 番の範囲で lvl=6 では 4 箇所で False が発生します。1727 番, 3961 番, 4079 番, 4096 番です。4079 番は、1727 番と同じパターンです。3961 番は少し変形していますがほぼ同じパターンです。4096 番はデータブロックが切断してＥＯＢが付いたからですね。
対して、lvl=9 では正確には数えていませんが 10 倍位は発生します（...多すぎて数えられないって小学生か）。
ZIP の出力との比較では、zlib のデフォルト（lvl=6）が一番近い動作をするようです。
zlib では lvl 毎にＬＺ７７を制御する数値が定義されていて（これは ZIP も同じです）、lvl が違えば挙動が違って、差異が発生するのだろうと思いますが、lvl が同じでも差異がでるとは、その理由が気になりますね（...ZIPは 90 年代で、reZIP と zlib は現在のものとすると、90 年代〜現在の間のどこかでデグレードしたようにも見えます）。
＊＊＊
ちょっと気になっていることがあって、lvl=9 の zlib のデータをもう少し見てみます。
zlib で lvl=9 をセットしたときのＬＺ７７の出力が異なる例です。同じく obj2 のデータで、ZIP と zlib の比較です。符号語のビット数も追加しました。
____: (ZIP, __, ___, ___) (zlib, _, ___, ____) :(ZIP_bits____) (zlib bits___):
2020: (_10, _0, _10, __0) (_10, _0, _10, ___0) :( 8, 0) (_, _) ( 7, 0) (_, _):
2021: (264, 18, _10, 685) (264, 18, _10, _685) :( 7, 0) (4, 8) ( 7, 0) (4, 8):
2022: (257, _7, __3, _16) (257, _7, __3, __16) :( 3, 0) (4, 2) ( 4, 0) (5, 2):
2023: (178, _0, 178, __0) (178, _0, 178, ___0) :(11, 0) (_, _) ( 9, 0) (_, _):
2024: (__0, _0, __0, __0) (__0, _0, __0, ___0) :( 5, 0) (_, _) ( 5, 0) (_, _):
2025: (_11, _0, _11, __0) (_11, _0, _11, ___0) :( 9, 0) (_, _) ( 9, 0) (_, _):
2026: (262, 14, __8, 160) (263, 24, __9, 5812) :( 5, 0) (5, 6) ( 6, 0) (5,11):<-False
2027: (__0, _0, __0, __0) (200, _0, 200, ___0) :( 5, 0) (_, _) (10, 0) (_, _):<-False
2028: (200, _0, 200, __0) (__1, _0, __1, ___0) :( 9, 0) (_, _) ( 6, 0) (_, _):<-False
2029: (__1, _0, __1, __0) (_58, _0, _58, ___0) :( 6, 0) (_, _) ( 9, 0) (_, _):<-False
2026 番で False になっています。ZIP は (LEN:8, DIS:160) を見つけ、zlib は (LEN:9, DIS:5812) を見つけています。zlib の方が長さが 1 多いです。そのため、2028 番以降は 1 つずれています。以降は ZIP 側の番号に合わせて zlib 側の表示をします（...zlibの番号に幾らかのオフセットを加えます）。
符号語は、えーと、ZIP の出力だと記号Ａの 0, 262 と記号Ｂの 14 で、zlib の出力は記号Ａの 263 と記号Ｂの 24 ですね。ZIP の符号表では 5+5+11=21 と 6+16=22 となり、zlib では 5+6+10=21 と 6+16=22 です。
意外なことに記号の数が少ない zlib の出力の仕方の方が、ビット数が 1 多いのですね。
その後も次々と不一致は発生しますが、大きなのが出てきました。
____: (ZIP, __, ___, ___) (zlib, _, ___, ____) :(ZIP_bits____) (zlib bits___):
3649: (258, _0, __4, __1) (259, 27, __5,12892) :( 5, 0) (6, 0) ( 5, 0) (6,12):<-False
3650: (__2, _0, __2, __0) (257, _1, __3, ___2) :( 8, 0) (_, _) ( 4, 0) (7, 0):<-False
3651: (257, _1, __3, __2) (_22, _0, _22, ___0) :( 3, 0) (7, 0) ( 9, 0) (_, _):<-False
（lvl=9 をセットされた）zlib は、ZIP より 1 バイト長い文字列を［距離］12892 から探し出した結果、［補助２］の 12 ビット分だけ赤字になっています。1 バイト長いだけでは差し引きしても赤字になる可能性が高いでしょう。
ZIP は 5+6+8=19 ビットで、zlibは 5+6+12=23 ビットです。zlib が ZIP と同じく［長さ］4［距離］1 と［リテラル］2 を出力していたら 4+7+6=17 ビットでした。6 ビットも違います。
赤字になるか否かは、厳密には符号表を生成しないと判断できないと思います。でも［補助２］のビット数はＬＺ７７でも把握できるので、1 バイト長い文字列を探しに行くべきか、ＬＺ７７は考慮してよいと思います（...随時に頻度をカウントしているのですから、レアなリテラルかどうか分からないのかな）。
これもＬＺ７７とハフマン符号との間にある課題ですね。このようなケースがあるのではないかと思っていたらやっぱりあって、予想通りで安心しました。
＊＊＊
Calgary corpus の謎とは、元々は符号語のビット数のオーバーフローだったのですが、これについては次回！
＊＊＊
