070 ファイルを復活させよう（６日目）
●070 ファイルを復活させよう（６日目）
ときは平成Ｙ＋１年、チャレンジの６日目、今日も研究室には誰もいない。さみしい気がちょっとする。最近コンビニのレジの人としか話していない、「お箸は？」「いらないです」
昨夜は「情報理論」や「算法序論」などの教科書でハフマン符号を勉強した。「算法辞典」も少し読んだ。
教科書では、ハフマン符号の構成法を丁寧に図解していて、そこは理解できた。でも、実際の応用である Deflate は色々と処理が追加されていて、どうしてそうなるのか分からず悩んだ。七転八倒した。
Deflate はＬＺ７７とハフマン符号の 2 つの処理があるので、大雑把に言えば、「圧縮前データ（バイト列） → ＬＺ７７で圧縮 → 中間データ → ハフマン符号で符号化 → 圧縮後データ（ビット列）」という流れになるはずだ。だけれども、中間データには色々なモノがあって相互の関係付けを理解する必要があり、圧縮後データもハフマン符号の符号語の並びではなくて符号語以外のデータが混在していて、その構成を理解する必要があった。
ひと晩悩んで、Deflate を、つまりＬＺ７７とハフマン符号による圧縮を私なりにまとめてみたので読んで欲しい（...「変換」は、圧縮、展開（展張、解凍）、符号化、復号（復元）、エンコード、デコードなどと、好みに合わせて適宜読み替えて下さい）。ＬＺ７７アルゴリズムやハフマン符号そのものについてはここでは説明を省きます。時間があったらあとで後述するかも知れません。
＊＊＊
まず、全体像を次に示す。［Ａ｜Ｂ］という表記は［Ａ］または［Ｂ］という感じで読んで下さい。
・［バイト列］←ＬＺ７７変換→［リテラル｜終端｜長さと距離］
・［リテラル｜終端｜長さと距離］←補助的な変換→［記号Ａ｜記号Ａと補助１と記号Ｂと補助２］
・［記号Ａ］←ハフマン変換Ａ→［ＬＩＴ｜ＥＯＢ｜ＬＥＮ］
・［記号Ｂ］←ハフマン変換Ｂ→［ＤＩＳ］
・［補助１と補助２］←二進数変換→［ＥＸ１とＥＸ２］
・［ＬＩＴ｜ＥＯＢ｜ＬＥＮとＥＸ１とＤＩＳとＥＸ２］←→［ビット列］
説明しよう。まず［バイト列］は圧縮前のデータで、［ビット列］は圧縮後のデータになる。
ＬＺ７７変換は、ＬＺ７７アルゴリズムにより［バイト列］と［リテラル｜終端｜長さと距離］との変換を行う。［リテラル］は 0〜255、［長さ］は 3〜258、［距離］は 1〜32768 の範囲である。［終端］は 256 で終端を示す。
そして、Deflate が独自に定義する、補助的な変換で［リテラル｜終端｜長さと距離］と［記号Ａ｜記号Ａと補助１と記号Ｂと補助２］との変換を行う。［リテラル］［終端］［長さ（の一部）］と［記号Ａ］が対応し、［距離（の一部）］と「記号Ｂ」が対応する。この補助的な変換については後述します。
ハフマン変換Ａは、ハフマン符号Ａにより［記号Ａ］と［ＬＩＴ｜ＥＯＢ｜ＬＥＮ］との変換を行う。［記号Ａ］は 0〜287 まで定義されているが実際に使用するのは 0〜285 までだ。［ＬＩＴ］［ＥＯＢ］［ＬＥＮ］は［記号Ａ］と対応するハフマン符号Ａの符号語となる。［ＬＩＴ］は［記号Ａ］の 0〜255 に対応する符号語で、［ＥＯＢ］は 256、［ＬＥＮ］は 257〜285 に対応する。
ハフマン変換Ｂは、ハフマン符号Ｂにより［記号Ｂ］と［ＤＩＳ］との変換を行う。［記号Ｂ］は 0〜31 まで定義されていて、実際に使用するのは 0〜29 までだ。［ＤＩＳ］は［記号Ｂ］と対応するハフマン符号Ｂの符号語となる。
符号語とは「00110101」のような 0 と 1 からなる数ビット〜十数ビットのデータだ。ハフマン符号ＡとＢの符号語のビット数は最大 15 と制限されている等、教科書的なハフマン符号と違う点が幾つかある（...詳しくは後述しますね）。
二進数変換は、数値と二進数との変換です。その際、ビットの順番を反転させます。
［記号Ｂ］や［補助１］［補助２］が存在するために、［ビット列］はハフマン符号Ａの符号語の連続ではなくて、［ＬＩＴ｜ＥＯＢ｜ＬＥＮとＥＸ１とＤＩＳとＥＸ２］という繰り返しになる。
＊＊＊
補助的な変換は、次の処理を行う。
・［リテラル］と［記号Ａ］の 0〜255 とを対応させる。
・［終端］と［記号Ａ］の 256 とを対応させる。
・［長さ］を［長さの一部］と［補助１］に分割する。［長さの一部］と［記号Ａ］の 257〜285 とを対応させる。
・［距離］を［距離の一部］と［補助２］に分割する。［距離の一部］と［記号Ｂ］の 0〜29 とを対応させる。
［長さの一部］と［補助１］の分割と、［長さの一部］と［記号Ａ］の対応は、RFC1951 で定義されている。［距離］についても同様。
＊＊＊
補助的な変換は、何故こうなったのか。［長さ］は 3〜258 の 256 個あり、［記号Ａ］の 257〜285 の 29 個では足りない。［距離］も 1〜32768 あって［記号Ｂ］の 0〜29 の 30 個では全然足りない。それで［長さ］と［距離］はその一部のみを符号化して、足りない分を補うのが［補助１］と［補助２］の役割である。
だけれども、全部をハフマン符号にしては駄目なのか。ハフマン符号Ｂの各符号語に［補助２］を連結して 1 つにすることは可能と思える。ハフマン符号だけでは効率が悪かったのか。符号語が長すぎると駄目なのか。教科書を少し読んだ程度では分からなった。誰かコメントが欲しい。研究室に誰か同期とか後輩とか居たら捕まえて、ホワイトボードの前に連行して、色々を図解した上で、議論を開始したい気分だ。今日はいないけれど、研究室ではお茶とお菓子を用意すれば割と喜んで議論に付き合ってくれる。面白い内容ならお菓子無しでも可だ。私も呼ばれたら余程のことがない限り参加する。連行するときは「お菓子を買ってきたので一緒に食べましょう」と言えばスムーズだ。先輩に参加して欲しいときは事前の動向把握が大切です。研究室に在席していても、何か採点していたりして近寄り難いときもあります（...知らずに近づくと「この回答だとバツだよね？」とか相談されて、「そうですね」とか返事する。そのテスト自分も受けているのですけど、とは言えない）。
＊＊＊
RFC1951 では、［リテラル］と［長さ］は共通のハフマン符号を使い、［距離］はそれとは別のハフマン符号を使う、と書いている。別のハフマン符号とは上述のハフマン符号Ｂのことなのだが。最初に読んだときには理解できなくて悩みました。ちょっとだけ、余談を述べさせて下さい。
固定ハフマン符号の場合、［記号Ｂ］の 0〜31 について、0 を「00000」に、1 を「00001」に、2 を「00010」、...、31 を「11111」と、割り当てているように読めた。どう見ても十進数を二進数に変換しているだけで、ここがハフマン符号なのだとの説明も見つからず、RFC1951 ではハフマン符号は 2 個あると書いてあるけど、2 個目はどこだろうと考えてしまいました。愚かでした（...APPNOTE ではハフマン符号ＡとＢの両方を並べて記述されていたよ）。
実際に ZIP ファイルの中をみてビット列を確認したり、動的ハフマン符号のデータを展開したら、そういうことかと分かったのですが！、だったら［補助１］と［補助２］はハフマン符号である可能性はないのか（...ないけど）、ハフマン符号だと言い張れば、数値化する際にビット順を反転させる処理が不要になって有益ではないか、と悔しくてそんなことを思ってしまいます。
ビットの順番を反転していないからハフマン符号なのは当然！とか、［記号Ｂ］の発生確率を吟味したらどれも同じでしたので符号語のビット数が全部同じになりました！とか言われたら、泣けてしまいます。
それとあと 1 つ、［長さの一部］と［記号Ａ］の対応表の説明の前後で［記号Ａ］の 257 などのことを「length alphabet」としたり、「length code」と書いてたりしていて紛らわしかったのです。「length code」は APPNOTE の記述を引き継いだのでしょうが整理して欲しかったです。思い返せば TN1150 は神の世界。カタログノードもゼロクリアされていました。
余談は以上です。
＊＊＊
さて、Deflate の仕様がだいたい確認できたところで元の懸案に戻ろう。デコードだけで圧縮は全く未着手だけど Deflate やハフマン符号の勉強が本旨ではないから。私はいつか復習すると決意した。
ZIP ファイルの PK34 と PK12 の間にある 1,464,501 ブロックのギャップを見分けて、ZIP ファイルのデータを特定したいのである。
任意の 4KB がハフマン符号による圧縮データであるかを判別することは、固定ハフマン符号ならできなくはないが不確定的で、動的ハフマン符号は難しそうだ。非圧縮のデータブロックだと判定は不可能、という結論になった。
ならば、データブロックの先頭から順番にデコードして調べるしかない。
データブロックの先頭は PK34 で特定できる。ここからスタートしてデコードを進めて、エラーを検出したらそのブロックはギャップと見做して排除して、次のブロックを試す。これを繰り返す。
エラーの検出は、［記号Ａ］の未使用な 286 や 287 の出現、データブロックの途中で［終端］の出現、［記号Ｂ］の 30 や 31 の出現、動的ハフマン符号で符号表のデコードエラー、非圧縮の場合でデータブロック長のチェックコードが不一致、データブロックの先頭 3 ビットが未定義値、...等々で可能だろう。
＊＊＊
私「ハフマン符号のデコードはどうしよう、エディタ上で手動での解釈は出来るけれど。zlib にデータブロックを放り込んだら出来るところまで展開してくれないかな？」
zlib とは Deflate を実装したライブラリのことだ。圧縮や展張を行うメソッドが用意されている。RFC1951 の参考文献リストにも、Deflate を実装した例として zlib の名前が出ている。
最初の 4KB ブロックを zlib で正常にデコードできるか確認して正常だったら、さらに 4KB ブロックを追加して、デコードデータが増えたらヒットで、なかったらアウトと判定できるはず。
考えるより試してみようと、zlib を呼び出したら、そんなに都合よくエラーリターンしなかった。
私「うーん、面倒だが、この際、自力でデコードするスクリプトを作るしかないなー、ZIP のデコードか、手強そうだなー」（...ちょっと嬉しそう）
でも、zlib のマニュアルを読むと大きなファイルを分割してデコードするためのメソッド decommpressobj() を使えば判定できそうなことに気が付く。decommpressobj() は出力データサイズを指定すると、残ったブロックが壊れていてもエラーリターンしない。出力データサイズを制御して残余データとエラーの有無を確認すれば、正常にデコードされたブロックの範囲をチェックできる。
私「残念だが仕方ない。zlib を使ってスクリプトを作ろう」
1 ブロックだけの判定だとブロックの境界で判定を間違えそうで、10 ブロック分を管理して判定を進めることにする。不格好な気がするけれど。ハフマン符号のデコードをスクリプトで処理する方が細かく監視できるけれど。でもそれよりも ZIP ファイルを復活させねば。
＊＊＊
違うブロックを排除できる確率は、［記号Ａ］の 286 と 287 のチェックだけでも、「1 - (127/128) の 4096 乗」でほぼ 100% か。いや、そうでもないか。これはアロケーションブロックが全部データブロックの中に入っていた場合の話で、そうでなければ違う。データブロックは 32KB 程なので、4KB のブロックがデータブロックの境界をまたぐことは割とありそう。
他の ZIP ファイルのブロックが混じっていた場合は誤判定する可能性は高いかも。固定ハフマン符号のブロック同士だと、ブロックの境界で１個の符号語がうまく合わさるだけで誤判定になるはず。動的ハフマン符号ならまだエラー検出できる余地はあるかな。データブロックのサイズも表示して危なそうなケースはワーニングを出したいな。他の ZIP ファイルは今回は混じっていないと思うけれど。ないといいな。
非圧縮の場合は先頭のブロック以外はノーチェックで 8 ブロックを読み込むことになるな。うーん、排除に一度でも失敗するとその後のブロックの追跡が終了しないで延々と探し続けることになりそう。排除に失敗しつつ終了する可能性も、これも運が悪いとどうなるか分からない。現実はどのくらい厳しいか。ZIP ファイルが特定できた場合でも UNZIP して中身の確認は必須だ。結果確認を忘れないようにしよう。
エスクテントがアドレス順に並んでいなかったら、どうなるんだろう。まずいよね。これは考えないことにしよう。
＊＊＊
色々な不安要素を考え出しながらも、スクリプトは組み上がっていく。小規模なデータで動作確認してデバック。
スクリプトをＲＵＮする。不安要素は一杯あるけれど、どうかうまく行きますように。
今日も帰って寝よう。ご飯もちゃんと食べよう。ちゃんと食べて寝た方が作業が進む気もしないではない。
不安要素がやっぱり ZIP デコードのスクリプトを作ったらとささやいている、...気がする。
明日が運命の日になるか。祈っておこう、...!orz
＊＊＊
