Koji Arai
JCA02****@nifty*****
2003年 2月 3日 (月) 00:00:47 JST
新井です。 In message "Re: [Lha-users] The Hacking of LHa for UNIX (2nd draft)" on Sun, 02 Feb 2003 08:32:17 +0900 (JST), Koji Arai <JCA02****@nifty*****> wrote: > 新井です。 > > 更新しました。 さらに頑張ってみました。 Index: Hackinf_of_LHa =================================================================== RCS file: /cvsroot/lha/lha/Hackinf_of_LHa,v retrieving revision 1.8 diff -u -u -r1.8 Hackinf_of_LHa --- Hackinf_of_LHa 1 Feb 2003 23:32:37 -0000 1.8 +++ Hackinf_of_LHa 2 Feb 2003 14:49:49 -0000 @@ -2917,6 +2917,467 @@ 視した if 文にも関連する。そしてこれは「アルゴリズム辞典」には載ってい ない部分だ。どうやら LHa なりの工夫があるようだ。 +まず、maketree.c:make_len(root) から見てみようと思うが、その前にこの関 +数は maketree.c:count_len(root) という関数を呼び出している。こちらから +先に見ることにした。 + +static void +count_len(i) /* call with i = root */ + int i; +{ + static unsigned char depth = 0; + + if (i < n) + len_cnt[depth < 16 ? depth : 16]++; + else { + depth++; + count_len(left[i]); + count_len(right[i]); + depth--; + } +} + +この関数に渡される i は、最初ハフマン木の根を指す値だ。この関数の全体 +を見れば、i が節や葉を示すことはすぐわかる。最初の if 文に出てくる n +は何かというとなんとこのファイル内の static 変数で、make_tree() の冒頭 +で nparm で初期化していた。先程は気にもとめなかったのだが、変数名の選 +び方がどうにもよろしくない。とにかく n は、nparm で、freqparm の最初の +要素数で、文字の種類の数を表していたものだ。ここではハフマン木の節や葉 +となる i と比較していることから、i がハフマン木の節を示すか葉を示すか +の判断に使用しているらしい。if 文の条件が真の場合(i < n)、i は葉である。 +偽の場合 i は節である。偽の場合は、depth を足して二つの子に対して再帰 +的にこの関数を呼び出している。で、結局この関数が何をしているかというと、 +先ほど構築したハフマン木に関して、ある深さの葉の数を数えているようだ。 + +len_cnt[1] は、深さ 1 (根の子)の葉の数で 0 〜 2 の値になる。len_cnt[2] +は、深さ 2 (根の孫)の葉の数で 0 〜 4 の値を持つだろう。そして、深さ 16 +以上の層に関しては len_cnt[16] にすべて計上されるようだ。とにかくその +ような処理だということでこの関数を終え、make_len() を見よう。 + +static void +make_len(root) + int root; +{ + int i, k; + unsigned int cum; + + /* (A) */ + for (i = 0; i <= 16; i++) + len_cnt[i] = 0; + count_len(root); + /* (B) */ + cum = 0; + for (i = 16; i > 0; i--) { + cum += len_cnt[i] << (16 - i); + } +#if (UINT_MAX != 0xffff) + cum &= 0xffff; +#endif + /* (C) */ + /* adjust len */ + if (cum) { + fprintf(stderr, "17"); + len_cnt[16] -= cum; /* always len_cnt[16] > cum */ + do { + for (i = 15; i > 0; i--) { + if (len_cnt[i]) { + len_cnt[i]--; + len_cnt[i + 1] += 2; + break; + } + } + } while (--cum); + } + /* (D) */ + /* make len */ + for (i = 16; i > 0; i--) { + k = len_cnt[i]; + while (k > 0) { + len[*sort++] = i; + k--; + } + } +} + +ちょっと複雑だがゆっくり見ていこう。まず (A) の初期化部分は先ほどの +count_len() を呼び出すだけのものなのでもうよいだろう。 + + /* (A) */ + for (i = 0; i <= 16; i++) + len_cnt[i] = 0; + count_len(root); + +これで、len_cnt[0:16] にはハフマン木の各層の葉の数が計上される。続いて (B) + + /* (B) */ + cum = 0; + for (i = 16; i > 0; i--) { + cum += len_cnt[i] << (16 - i); + } +#if (UINT_MAX != 0xffff) + cum &= 0xffff; +#endif + +これは、どういうことだろう？len_cnt[] は short の配列だが、とにかく以 +下のような計算(len_cnt[] の要素を 1 ビットずらしながら足す)をしている。 +最後に int 型のサイズが 2 でない場合 0xffff で論理積をしているので 2バ +イトの符号なし整数を結果として欲しいらしい。 + +---------------------------------------------------------------------------- + f e d c b a 9 8 7 6 5 4 3 2 1 0 bit + len_cnt[16] |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x| (下位 16ビット) ++ len_cnt[15] |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|0| (下位 15ビット) ++ len_cnt[14] |x|x|x|x|x|x|x|x|x|x|x|x|x|x|0|0| (下位 14ビット) ++ : : ++ len_cnt[ 2] |x|x|0|0|0|0|0|0|0|0|0|0|0|0|0|0| (下位 2 ビット) ++ len_cnt[ 1] |x|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0| (下位 1 ビット) +& 0xffff |1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1| +------------------------------------------------ += cum x x x x x x x x x x x x x x x x +---------------------------------------------------------------------------- + +ここで、len_cnt[] の各要素の値が各層の葉の数であることを考えると、各要 +素で使用するビット数との関連が見える。 + + 取り得る + 値の範囲 使用ビット数 + ----------------------------------------- + len_cnt[16] 0.. 2^16以上 17ビット以上 + len_cnt[15] 0.. 2^15 16ビット + len_cnt[14] 0.. 2^14 15ビット + : + len_cnt[ 3] 0.. 2^3 4 ビット + len_cnt[ 2] 0.. 2^2 3 ビット + len_cnt[ 1] 0.. 2^1 2 ビット + +先の計算式では len_cnt[] の各要素で使用し得るビット数から 1 引いたビッ +ト数が計算に使用されている。例えば根の子がすべて葉なら len_cnt[1] は、 +2 になり、2進で、00000000 00000010 だが、cum の計算にはこの下位 1 ビッ +トしか使用されない。 + + /\ + a b .. len_cnt[1] = 00000000 00000010 + | + v + cum = x0000000 00000000 + +根の孫がすべて葉なら len_cnt[2] は、4 になり、2進で、00000000 00000100 +だが、cum の計算にはこの下位 2 ビットしか使用されない。 + + / \ .. len_cnt[1] = 00000000 00000000 + /\ /\ + a b c d .. len_cnt[2] = 00000000 00000100 + || + vv + cum = xx000000 00000000 + +このようにある層のすべてが葉であるようなバランスのよいハフマン木に +対しては先の計算結果 cum は 0 になるらしい。 + +また、 + /\ + a /\ .. len_cnt[1] = 00000000 00000001 + b c .. len_cnt[2] = 00000000 00000010 + || + vv + cum = xx000000 00000000 + +のような木に対しても計算結果はオーバーフローされ cum は 0 になる。 + + /\ + a /\ .. len_cnt[1] = 00000000 00000001 + b /\ .. len_cnt[2] = 00000000 00000001 + c d .. len_cnt[3] = 00000000 00000010 + ||| + vvv + cum = xxx00000 00000000 + +も同様に cum は 0 だ。結局 cum が 0 にならない木とはある節が 1 つの葉 +しかもたないような場合であるらしい。 + + /\ + a /\ .. len_cnt[1] = 00000000 00000001 + b \ .. len_cnt[2] = 00000000 00000001 + d .. len_cnt[3] = 00000000 00000001 + ||| + vvv + cum = 11100000 00000000 + +そして、ハフマン木の作り方からこのようなことは起こりえないのではないか +と思える。 + +(C) では、if (cum) で、この起こりえないハフマン木の場合になにか処理を +行っている。まったく謎であるが、まず、この (C) を特殊条件とみなして先 +に (D) の方を見ることにしよう。 + + /* (D) */ + /* make len */ + for (i = 16; i > 0; i--) { + k = len_cnt[i]; + while (k > 0) { + len[*sort++] = i; + k--; + } + } + +sort は何かというと、make_tree() の引数に渡された codeparm を指してい +る。この配列の中には(ハフマン木を構築する際に設定されていたのだが)、出 +現頻度の低い順で平文の文字コードが入っている。make_tree() で、sort に +値を設定する際、 + + if (j < n) + *sort++ = j; + +のように条件判断があったので、sort[] にはハフマン木の節は入っていない。 +そしてハフマン木はその構築の仕方から出現頻度の低い文字は木のより深い場 +所に位置づけられている。これらのことから make_len()で求めようとしてい +るものが何なのかがわかる。make_len() は、 + len[文字] = ハフマン木の深さ +といった対応表を作成する処理だ。さらに言うとハフマン木の深さは文字を符 +号化した結果のビット数を表すことから + lenparm[文字] = 符号語のビット数 +といった対応表を作成する処理であると言った方が正解だろう。 +len[] は、make_tree() の冒頭で、lenparm を指すように設定された変数なの +で、そのように置き換えておいた。 + +では、謎の (C) を見よう。その前に cum != 0 は起こりえないと書いたがよ +く考えたら len_cnt[16] だけは深さ16以上の葉すべての数を計上しているた +め、どのような値もあり得る。つまり、この (C) の処理はハフマン木が深さ +17 以上になったときに処理されるものだと言えそうだ。思い切って図示しよ +う例えばこんな木は、(C)の処理対象となる。 + + /\ + a /\ .. len_cnt[ 1] = 0000000000000001 + b /\ .. len_cnt[ 2] = 0000000000000001 + c /\ .. len_cnt[ 3] = 0000000000000001 + d /\ .. len_cnt[ 4] = 0000000000000001 + e /\ .. len_cnt[ 5] = 0000000000000001 + f /\ .. len_cnt[ 6] = 0000000000000001 + g /\ .. len_cnt[ 7] = 0000000000000001 + h /\ .. len_cnt[ 8] = 0000000000000001 + i /\ .. len_cnt[ 9] = 0000000000000001 + j /\ .. len_cnt[10] = 0000000000000001 + k /\ .. len_cnt[11] = 0000000000000001 + l /\ .. len_cnt[12] = 0000000000000001 + m /\ .. len_cnt[13] = 0000000000000001 + n /\ .. len_cnt[14] = 0000000000000001 + o /\ .. len_cnt[15] = 0000000000000001 + p /\ .. len_cnt[16] = 0000000000000011 + q r |||||||||||||||| + vvvvvvvvvvvvvvvv + cum = 0000000000000001 + +このような木は例えば各文字が以下の出現頻度となるファイルを作成すると起 +こる(実際には、LHA の場合、スライド辞書法の処理もあるのでこれほど単純 +ではない)。 + + 文字 頻度 文字 頻度 + ------------ ------------ + r 1 i 256 + q 1 h 512 + p 2 g 1024 + o 4 f 2048 + n 8 e 4096 + m 16 d 8129 + l 32 c 16384 + k 64 b 32768 + j 128 a 65535 + +ところで、cum の値は何なのかというと、 + + : + .. len_cnt[15] = 0000000000000001 + p /\ .. len_cnt[16] = 0000000000000100 + q /\ |||||||||||||||| + r s vvvvvvvvvvvvvvvv + cum = 0000000000000010 + +この場合は cum = 2 だ。 + : + .. len_cnt[15] = 0000000000000001 + p /\ .. len_cnt[16] = 0000000000000101 + q /\ |||||||||||||||| + r /\ vvvvvvvvvvvvvvvv + s t cum = 0000000000000011 + +この場合は cum = 3 だ。少なくともこの例では深さ 16 以上の葉の数 - 2に +なるらしい(そうか、11111111 11111110 = -2 を足しているのだから当然だ)。 + +では、今度こそ (C) を見る。 + + /* (C) */ + /* adjust len */ + if (cum) { + fprintf(stderr, "17"); + len_cnt[16] -= cum; /* always len_cnt[16] > cum */ + do { + for (i = 15; i > 0; i--) { + if (len_cnt[i]) { + len_cnt[i]--; + len_cnt[i + 1] += 2; + break; + } + } + } while (--cum); + } + +である。いきなり fprintf() しているところがすごい。デバッグ用の出力が +残っているのだろう。LHa for UNIX で 17 という出力を見たことがある人は +教えて欲しい。 + +で・・・、結局この (C) の部分は見てもよくわからなかった。ここまで書い +ておいてなんだが、気持ちよく無視することにした。 + +では、make_tree() から呼び出される最後の関数、maketree.c:make_code() +を見よう。make_code() は、make_tree() の(F) の部分で以下のように呼ばれ +ていた。 + + make_code(nparm, lenparm, codeparm); + +この引数のうち、lenparm[] は先ほどの make_len[] で値が作られたものだが、 + lenparm[文字] = 符号語のビット数 +という対応表だった。codeparm[] は、先ほども出たが make_tree() の中で設 +定されているものだった。出現頻度の低い順で平文の文字コードが入った配列 +だ。 + +void +make_code(n, len, code) + int n; + unsigned char len[]; + unsigned short code[]; +{ + unsigned short weight[17]; /* 0x10000ul >> bitlen */ + unsigned short start[17]; /* start code */ + unsigned short j, k; + int i; + + j = 0; + k = 1 << (16 - 1); + for (i = 1; i <= 16; i++) { + start[i] = j; + j += (weight[i] = k) * len_cnt[i]; + k >>= 1; + } + for (i = 0; i < n; i++) { + j = len[i]; + code[i] = start[j]; + start[j] += weight[j]; + } +} + +最初の for 文では、変数 i に対して、weight[i] が以下のように設定される。 + + weight[i=1..16] = 2^(16-i) + +そして、start[i] は、 + + start[1] = 0 + start[n] = start[n-1] + weight[n-1] * len_cnt[n-1] (n > 1) + +という漸化式だ。starr[] の添字 i は、len_cnt[i](深さ i の葉の数)の添字 +でもあることから、ハフマン木の深さを表している。start が実際にどのよう +な値を取るかと言うと、例えば len_cnt[i] の各要素が Li であった場合、 + + i len_cnt[i] weight[i] start[i] + -------------------------------------------- + 1 L1 2^15 0 + 2 L2 2^14 2^15 * L1 + 3 L3 2^13 2^15 * L1 + 2^14 * L2 + 4 L4 2^12 2^15 * L1 + 2^14 * L2 + 2^13 * L3 + +こんな感じだ。これはいったい何だろうか？続く for 文を見てみよう。 + + for (i = 0; i < n; i++) { + j = len[i]; + code[i] = start[j]; + start[j] += weight[j]; + } + +ここでの i は、0...n の範囲であることから平文の文字を示す。紛らわしい +ので、i は、c に書き換え、j を i にしよう。(これで、i は前の for 文の +i と同じ意味になる) + + int c; + + for (c = 0; c < n; c++) { + i = len[c]; + code[c] = start[i]; + start[i] += weight[i]; + } + +i = len[c] は文字 c のビット長で、ハフマン木の深さを示す。 +code[c] には、start[i] が設定されるが、一度 start[i] が参照されると +start[i] は、weight[i] を足した値が次回使われる。例えば、ある文字 +a, b, c がそれぞれ以下のハフマン木で表現されたとする。 + + /\ a: 0 + a /\ b: 10 + b c c: 11 + + + i len_cnt[i] weight[i] start[i] + -------------------------------------------- + 1 1 2^15 0 + 2 2 2^14 2^15 + + c len[c] i len_cnt[i] weight[i] code[c] + --------------------------------------------------- + a 1 1 1 2^15 0 + b 2 2 2 2^14 2^15 + c 2 2 2 2^14 2^15 + 2^14 + +こんな感じになる。別のハフマン木の場合も見てみよう。 + + /\ a: 00 + /\ /\ b: 01 + a b c d c: 10 + d: 11 + + i len_cnt[i] weight[i] start[i] + -------------------------------------------- + 1 0 2^15 0 + 2 4 2^14 0 + 3 0 2^13 2^14 * 4 + + c len[c] i len_cnt[i] weight[i] code[c] + --------------------------------------------------- + a 2 2 4 2^14 0 + b 2 2 4 2^14 2^14 + c 2 2 4 2^14 2^14 * 2 + d 2 2 4 2^14 2^14 * 3 + +これで、ピント来ると凄いのだが code[c] には文字 c に対応する符号化した +ビット列が設定されるようになっていることに気づくだろうか？つまりは、 + + c len[c] i len_cnt[i] weight[i] code[c] + ----------------------------------------------------------- + a 2 2 4 2^14 00000000 00000000 + b 2 2 4 2^14 01000000 00000000 + c 2 2 4 2^14 10000000 00000000 + d 2 2 4 2^14 11000000 00000000 + +だ。とにかく code[] (実際には codeparm) を利用することで表引きで文字に +対応するハフマン符号を得ることができるようになっている(code[c]のうち上 +位len[c]ビットだけを見る)。符号化の際に木を辿る必要はなく、高速な符号 +化が可能になる(と期待される。どの程度効果があるかはいずれ検証してみた +い。そういえば、葉から根に向かって木を辿るための情報が必要なかったこと +もこれでわかった)。 + +結局 make_tree(nparm, freqparm, lenparm, codeparm) は、lenparm[c] と +codeparm[c] を作成する関数だったわけだ(ハフマン表とでも言うのだろう +か？)。実は、このことは make_tree() を呼び出し、 codeparm を使用してい +る箇所(huf.c)を見るまでまるでわからなかった。しかも、まだちゃんと理解 +したわけではない。 + +ふと思ったのだが、上記の表作成は文字コード順に依存している(コードの若 +い方が左の子になる)が、木を作成する場合はそのようなことはなかったはず +だ。ハフマン木を辿った場合と表を参照した場合とでは得られる符号語は異な +るのではないだろうか？ということは圧縮文に埋め込まれるのは木ではなくこ +の表の方だということも想像がつく。木の構造を表す left[]、right[] はグ +ローバル変数だが、実際には make_tree() 内でしか使われないのかも知れな +い(少なくとも符号化に関してはそのようだ。huf.c を眺めるとどうやら復号 +時は left[]、right[]は使われるらしい)。 + # Local Variables: # mode : indented-text # indent-tabs-mode: nil
Fork