前回は固定ハフマンコードで圧縮されたデータを伸長するアルゴリズムを見てきた。圧縮に使うハフマンコードが仕様書で事前に決められているので、コードの情報を圧縮ファイルに記述する必要のないのが利点だが、出現頻度の高い文字に短いコードを割り付けるという本来のハフマン圧縮の考え方からすれば、圧縮効率は最適化されていない状態だといえる。例えば、英文などの1バイト文字と日本語などの２バイト文字では8ビット単位で見たときの出現頻度がまったく異なるので1-143を8ビット、144-255を9ビットで表現する固定ハフマンコードは日本語の方が効率が悪い。
ZIP仕様書で書かれているようにハフマンコードはコード長を指定するだけで一意に決定することができる。文字・長さコードは287個、距離コードは32個あるので、単純に羅列すると319バイト必要になり、各圧縮ブロック毎に指定することを考えると無駄が大きい。そこで、ダイナミックハフマンコードでは、0から18までのコード長記録用のハフマンコードを使って文字・長さコードと距離コードを記録している。今年の夏のように汗をたっぷり吸い込んだTシャツがまだ汗の残った肌にまとわりつくような、実に粘着質のアルゴリズムだ。
夏の暑さに負けずにVIを書いてみると以下のようになった。3ビットの固定長で指定個数のコード長を読み取って、ツリーを作ればいいのだが、記録されている順番が「16, 17, 18, 0, 8, 、、、」と指定されているので、ちょっとやっかいだ。また、指定個数が4個の場合は、先頭から4個の「16, 17, 18, 0」以外のコードのコード長は０であると認識しなければならない。指定された順番のcodeという配列定数とコード長配列をクラスター配列にしてソートをかけて、順番通りのコード長配列を作る。あとは前回作ったツリーを作るサブVI "BuildTree.vi" を使えばコードが生成される。
コード長コードを使って文字・長さコードと距離コードのコード長を読み取っていくのは、固定ハフマンコードでアルファベットを読み取っていくのと同じ要領だ。前回作ったVIの一部を独立したサブVIとし、さらにハフマンコードの最小ビット長からデーコードを開始するように変更しした。また、今回はデバッグに手間取ったこともあり、最大ビット長よりも大きくなったときにエラーで停止するようにした。
上のVIの中で使われているtree_decorder.viにはバグがあることが分かったので、下のように変更した。Trueのケースが従来のものだが、#lit codeを数値にしたときに値が0になる場合、コード長が0で値が0になっているものとコード長が1で値が0になっているものとの区別がつかない。このような場合にはビット長が該当する要素を検索してコードが一致するか調べることにした。
このほかにも考えが足りなかったVIがあるが、次回に回すことにしよう。