#-*- indent-tabs-mode: nil -*- まず、グローバル変数の洗い出し text childcount pos matchpos avail position parent prev next remainder matchlen level これらをすべて理解すれば、ソース解析は完了と思ってよい。 この段階では、変数名とソースの概観から木を使ってるっぽい程度に認識する。 アルゴリズムの予想がある程度立っている場合は、変数名からその用途を予想しても 良い。私はわからなかったのでとっとと次に進むことにする。 次に、処理をトップダウンで解析する。 encode(void) { int lastmatchlen; node lastmatchpos; (A) allocate_memory(); (B) init_slide(); (C) huf_encode_start(opts.method); (D) remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile); (E) if (outfile != stdout && opts.quiet < 1) { putc('.', stdout); } (F) matchlen = 0; pos = DICSIZ; insert_node(); (G) if (matchlen > remainder) matchlen = remainder; (H) while (remainder > 0 && !unpackable) { lastmatchlen = matchlen; lastmatchpos = matchpos; get_next_match(); if (matchlen > remainder) matchlen = remainder; if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) output(text[pos - 1], 0); else { output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD), (pos - lastmatchpos - 2) & (DICSIZ - 1)); while (--lastmatchlen > 0) get_next_match(); if (matchlen > remainder) matchlen = remainder; } } (I) huf_encode_end(); } 注目すべきところに適当に記号を割り振る。 (A) allocate_memory() を見ると以下のようなメモリ割り当てを行っている。 (B) の初期化に該当する部分もある程度（適当に）図示した。 dicsiz dicsiz*2 / / +---------------------+---------------------+----+ text | | | | +---------------------+---------------------+----+ |----| maxmatch dicsiz(8192) / +---------------------+---+ level| |111| +---------------------+---+ |--| UCHAR_MAX(255) + 1 dicsiz ' position | +---------------------+---+ | |NIL| +---------------------+---+ |---| UCHAR_MAX(8) + 1 parent +---------------------+---------------------+ | | NIL | +---------------------+---------------------+ +---------------------+---------------------+ prev | | | +---------------------+---------------------+ DICSIZ DICSIZ*2 max_hash_val + 1 / / / +---------------------+---------------------+---------------------+----+ next | 234... NIL| | NIL | | +---------------------+---------------------+---------------------+----+ なお、サイズは適当だ。ざっと上記のようにまとめて次に移る (C) huf_encode_start() は、Huffman coding の初期化であることを 既にLHa for UNIXの解析で知っているので、次に進む。 (D) 圧縮対象のファイルを読み込んで text の右半分に書き込んでいる。 (E) 単に圧縮の進行状況を画面に出力する（ために、最初の "."を出力している） だけ、無視する。 (F) matchlen, pos を初期化して insert_node() を呼んでいる。 insert_node() をざっと見ても内容はすぐにわからなさそうなので、 いったん無視して次に進む。 (G) if (matchlen > remainder) という判定を行っている。(F)の段階で、 matchlen = 0 の設定を行っているので、insert_node() にて、matchlen が変更される場合があるのだろう程度に考える。おそらくは、insert_node() 実行後の例外条件に対応しているのではないかと予想しつつ次に進む。 (H) ちょっと長いが、LHa for UNIX の解析により以下の通り要約できるのでは ないかと予想する。 /* ファイルの残りがある間ループ */ while (remainder > 0 && !unpackable) { /* 前回のマッチを記録 */ lastmatchlen = matchlen; lastmatchpos = matchpos; /* 次のマッチを行う */ get_next_match(); /* 例外条件 */ if (matchlen > remainder) matchlen = remainder; /* 次のマッチした長さが前回よりも大きいか、前回のマッチが THRESHOLDよりも小さい場合は、前回のマッチを出力する */ if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) output(text[pos - 1], 0); else { /* 前回のマッチの方が最適であるなら、マッチ長と位置を出力する */ output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD), (pos - lastmatchpos - 2) & (DICSIZ - 1)); /* 前回のマッチ長分のマッチを繰り返す。 */ while (--lastmatchlen > 0) get_next_match(); /* 例外条件 */ if (matchlen > remainder) matchlen = remainder; } } おおよそ、LHa for UNIX のスライド辞書のアルゴリズムと同様の処理が 見える。 (I) huf_encode_end() にて、Huffman coding の後処理を行う。 以上から、スライド法の出力ループは(H)が、単語のマッチをinsert_node() と get_next_match() が実行していることがわかる。 また、insert_node() が最初のループの直前だけしか呼ばれていないことから insert_node() と get_next_match() の処理は似ているのではないかと 勘で予想する。 とにかく、insert_node() および get_next_match() の解析を進める べきであることがわかる。 前の予想があっているかどうか、insert_node() および get_next_match() を並べて比べてみる。 ・・・見たところ、insert_node() の処理は大きい、また get_next_match() は予想以上に小さく、どうやら勘ははずれてこの二つの処理は違うことを行っ ているらしい。 予想に反して get_next_match() の処理内容は短いので、こちらを先に 解析することにした。 static void get_next_match(void) { int n; (A) remainder--; (B) if (++pos == DICSIZ * 2) { memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH); n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile); remainder += n; pos = DICSIZ; if (outfile != stdout && opts.quiet < 1) { putc('.', stdout); } } (C) delete_node(); (D) insert_node(); } (A) 残りサイズを縮めている。一文字読み進んでいるということだろう。 (B) pos を一つ進めている。remainder と対応しているのだろう。 なお、if 分の中身は例外条件(pos が端に到達した場合)であるので、 無視することにする。（ざっと見ればファイルを読み込んで各変数を 再度初期化しているだけであることはわかる） (C), (D) ここがこの処理のメインである。delete_node() して insert_node() している。 結局、マッチ処理は処理の冒頭にて最初に insert_node() していることから このinsert_node()の部分ではないか？また、delete_node() は「次」を 行うのに必要な処理なのではないかとなんとなく考える。 ここで、insert_node() と delete_node() のいずれを読むべきか？ insert_node() は処理が複雑なので、delete_node() の方を読み進めることと した。 static void delete_node(void) { #if PERCOLATE node q, r, s, t, u; #else node r, s, t, u; #endif if (parent[pos] == NIL) return; r = prev[pos]; s = next[pos]; next[r] = s; prev[s] = r; r = parent[pos]; parent[pos] = NIL; if (r >= DICSIZ || --childcount[r] > 1) return; #if PERCOLATE t = position[r] & ~PERC_FLAG; #else t = position[r]; #endif if (t >= pos) t -= DICSIZ; #if PERCOLATE s = t; q = parent[r]; while ((u = position[q]) & PERC_FLAG) { u &= ~PERC_FLAG; if (u >= pos) u -= DICSIZ; if (u > s) s = u; position[q] = (s | DICSIZ); q = parent[q]; } if (q < DICSIZ) { if (u >= pos) u -= DICSIZ; if (u > s) s = u; position[q] = s | DICSIZ | PERC_FLAG; } #endif s = child(r, text[t + level[r]]); t = prev[s]; u = next[s]; next[t] = u; prev[u] = t; t = prev[r]; next[t] = s; prev[s] = t; t = next[r]; prev[t] = s; next[s] = t; parent[s] = parent[r]; parent[r] = NIL; next[r] = avail; avail = r; } なかなか複雑である。が、このまま読み進める(insert_node()よりはマシだか ら) ここまで、PERCOLATEの部分は無視してきたが、PERCOLATEは未定義である として読み進めることにする。PERCOLATE の部分はアルゴリズムの改善を行っ ている部分のように思えるので、より複雑である可能性が高いからまずは基本 部分の理解を優先するためである。 PERCOLATE を未定義であるとして、処理を再掲する。 static void delete_node(void) { node r, s, t, u; (A) if (parent[pos] == NIL) return; (B) r = prev[pos]; s = next[pos]; next[r] = s; prev[s] = r; (C) r = parent[pos]; parent[pos] = NIL; (D) if (r >= DICSIZ || --childcount[r] > 1) return; (E) t = position[r]; (F) if (t >= pos) t -= DICSIZ; (G) s = child(r, text[t + level[r]]); (H) t = prev[s]; u = next[s]; next[t] = u; prev[u] = t; (I) t = prev[r]; next[t] = s; prev[s] = t; (J) t = next[r]; prev[t] = s; next[s] = t; (K) parent[s] = parent[r]; parent[r] = NIL; next[r] = avail; avail = r; } これだけ削るだけでも、なんとか解析できそうな気がしてくる。モチベーショ ンを上げることは重要である。 まずは、(A) if (parent[pos] == NIL) return; 例外条件なので、無視する。ただし、変数pos（これは現在読んでいる位置であ るようだ)を使用している。これはこの関数の入力であるらしいことは意識する。 （入力と出力が何であるかは常に意識すべき) (B) r = prev[pos]; s = next[pos]; next[r] = s; prev[s] = r; これはつまり next[r] = next[pos]; prev[s] = prev[pos]; である。ただし、r と s はそれぞれ右辺値であることから next[prev[pos]] = next[pos]; prev[next[pos]] = prev[pos]; である。なんとなくわかりそうな気がする。日本語に訳すと pos の prev の next は、pos の next である。 pos の next の prev は、pos の prev である。 ということを書いている。図示してみる。 prev<--+ ^ next | | pos | | | | | v prev next<---+ つまりは、双方向リンクリストで pos を中心に環状にリンクを作っている。 なんとなくわかったので、次に進む (C) r = parent[pos]; parent[pos] = NIL; pos の親を取得し、pos の親を NIL で上書きしている。 pos の親を「取り出している」と読めばよいのか？ (D) if (r >= DICSIZ || --childcount[r] > 1) return; 例外条件であろう。無視する。 (E) t = position[r]; r つまり、pos の親の position を取得している。変数名から pos の親のマッ チ位置ではなかろうか？ (F) if (t >= pos) t -= DICSIZ; 例外条件であろうか？t つまり、posの親の position が pos より大きい 場合これは text バッファにおいて、posより右側の位置を t が指している ことを示しているのだろう。このような場合があるのかどうかはわからないが やはり例外条件である。無視する。 (G) s = child(r, text[t + level[r]]); r つまり、pos の親と text[t + level[r]] つまり、pos の親の位置 t +　level[r] を引数に child() 関数を呼んでいる。わかりそうなわからなさそうな・・・ 次に進む (H) t = prev[s]; u = next[s]; next[t] = u; prev[u] = t; これは前に出てきたのと同じである。つまり、 next[prev[s]] = next[s]; prev[next[s]] = prev[s]; で、child()の戻り値についてリンクトリストを構築している。 (I) t = prev[r]; next[t] = s; prev[s] = t; r つまり、pos の親の prev について next[prev[parent[pos]]] = child() prev[child()] = prev[parent[pos]] としている。親の前の次と子を、子の前を親の前と繋げている。 (J) (I) と同様である。 t = next[r]; prev[t] = s; next[s] = t; (K) parent[s] = parent[r]; parent[r] = NIL; next[r] = avail; avail = r; parent[r] つまり、posの親の親とparent[child()] を繋げている。 なんだかわかりそうなわからなさそうな・・・まだ情報が足りない。 キモとしては、next[], prev[], parent[] を理解すれば、データ構造が見えて くるであろうことから、この辺りの操作をしている小さめの関数を探してみる ことにする。 ざっと見て、child(), makechild(), split() が見つかる。これらは ほとんど、insert_node() で呼ばれている。 get_next_match() delete_node() child() insert_node() child() split() makechild() makechild() といったコールグラフとなっている。insert_node()が複雑であることから やはり、これらの小さな関数群をまず調べるべきであろう。 ボトムアップ的にまずは、makechild() から static void makechild(node q, uchar c, node r) /* Let r be q's child for character c. */ { node h, t; h = HASH(q, c); t = next[h]; next[h] = r; next[r] = t; prev[t] = r; prev[r] = h; parent[r] = q; childcount[q]++; } コメントから q の子を r につなげる処理らしい。 まず、q と文字 c からハッシュ値を求める。 h = HASH(q, c); そのハッシュ値の next を取得する t = next[h]; そして以下でリストに挿入している next[h] = r; next[r] = t; つまり、 h.next --> t だったところに h.next --> r r.next --> t と r を挿入している。 prev も同様である。 prev[t] = r; prev[r] = h; 以下のようなイメージとなる。 h <--- r.prev r <----- t.prev r がちゃんと挿入されていることがわかる。 さらに、 parent[r] = q; r の parent として、q を設定している。 next[], prev[] が q と c のHASH値をさしているのに対し、 parent[] は、q そのものを指しているらしい。 childcount[q]++; q の子を繋げたので、q の子の数を足しているらしい。 次に child() を見てみる static node child(node q, uchar c) /* q's child for character c (NIL if not found) */ { node r; r = next[HASH(q, c)]; parent[NIL] = q; /* sentinel */ while (parent[r] != q) r = next[r]; return r; } q の子を返すらしい。 親は、直接 parent[] で取得できるが、子を取得するには、 リンクをたどる必要があることを示すようだ。 q の next を取得し、parent[] が q である r を探している。見つからなけれ ば sentinel として設定してある NIL を返すようだ。 ここまでで言えることは、 ・q と c のHASH値により、next[], prev[] が指す先は q の子の候補である。 というところか。 では、split()を見てみる void split(node old) { node new, t; new = avail; avail = next[new]; childcount[new] = 0; t = prev[old]; prev[new] = t; next[t] = new; t = next[old]; next[new] = t; prev[t] = new; parent[new] = parent[old]; level[new] = matchlen; position[new] = pos; makechild(new, text[matchpos + matchlen], old); makechild(new, text[pos + matchlen], pos); } ここで、ようやく元々の処理目的であるマッチ位置、マッチ長を指す変数が 現れている。 ・new に avail を退避し ・avail を新たに next[new] に設定 ・new の childcount は 0 どうやら avail は空きの位置を示しているらしく、新たな node の割り当て は、 new = avail; で行い、 avail = next[new] で次の空きをavailにセットしているようだ。avail, next[avail], next[next[avail]] は 空き領域のリストとなるらしい。そういえば、初期化の処理で avail = 1; for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1; next[DICSIZ - 1] = NIL; というのがあったが、next の領域(下図)のうち、左、1/3 は、この空きリス トをさすらしい（そして、そのリンクは、next[DICSIZ-1]でNILとなる。 なお、next[0] は使われておらず、next[1] -> 2 から始まるらしい。 ------------------------------------------------------------------------------------------- DICSIZ DICSIZ*2 max_hash_val + 1 / / / +---------------------+---------------------+---------------------+----+ next | 234... NIL| | NIL | | +---------------------+---------------------+---------------------+----+ ------------------------------------------------------------------------------------------- ・old の prev は、new の prev に設定(あわせて next も再設定) ・new の parent を old の parent に これで、old は切り離された、 ・newの level に matchlen を設定 ・newの position に pos を設定 ・new の子として old および pos を設定 注目すべきは、最後の makechild() 2連発である。 最初の makechild() により、matchpos + matchlen の文字を old として、 子に連結し、次の makechild() により、新たな pos + matchlen を pos として、子に連結している。 ここで、matchpos, matchlen は前回のマッチを、pos, matchlen は 今回のマッチを指し、new の子の浅い方がより最近のマッチを指すことを 示すようだ。 ここまでで、どうやらおおよその構造の使い方はつかめて来たが、まだまだよ くわからない。結局、 insert_node() を読み解くまでは全貌はつかめないよう だ。 insert_node() を読み進めることにする。例によって、PERCOLATE は未定義として 見ることにする。 static void insert_node(void) { node q, r, j, t; uchar c, *t1, *t2; (A) if (matchlen >= 4) { matchlen--; r = (matchpos + 1) | DICSIZ; while ((q = parent[r]) == NIL) r = next[r]; while (level[q] >= matchlen) { r = q; q = parent[q]; } t = q; while (t < DICSIZ) { position[t] = pos; t = parent[t]; } } (B) else { q = text[pos] + DICSIZ; c = text[pos + 1]; if ((r = child(q, c)) == NIL) { makechild(q, c, pos); matchlen = 1; return; } matchlen = 2; } for (;;) { (C) if (r >= DICSIZ) { j = MAXMATCH; matchpos = r; } (D) else { j = level[r]; matchpos = position[r] & ~PERC_FLAG; } (E) if (matchpos >= pos) matchpos -= DICSIZ; (F) t1 = &text[pos + matchlen]; t2 = &text[matchpos + matchlen]; (G) while (matchlen < j) { if (*t1 != *t2) { split(r); return; } matchlen++; t1++; t2++; } (H) if (matchlen >= MAXMATCH) break; (I) position[r] = pos; (J) q = r; if ((r = child(q, *t1)) == NIL) { makechild(q, *t1, pos); return; } (K) matchlen++; } (L) t = prev[r]; prev[pos] = t; next[t] = pos; (M) t = next[r]; next[pos] = t; prev[t] = pos; (N) parent[pos] = q; parent[r] = NIL; next[r] = pos; /* special use of next[] */ } 最初に(A) matchlen >= 4 の場合を扱っている一旦無視することにする。 (B) matchlen < 4 の場合である。 q = text[pos] + DICSIZ; c = text[pos + 1]; ここで、pos の位置の文字と pos + 1 の位置の文字を取得している。 pos には DICSIZ を足しているがそのことは一旦無視する。 if ((r = child(q, c)) == NIL) { makechild(q, c, pos); matchlen = 1; return; } 1文字目の q と 2文字目の c を使って child() を呼び出している。つまり、 q の次に c が続く文字を木から探しているようだ。見つからない場合(NIL)は、 makechild() により、この2文字を木に登録し、matchlen = 1 としてこの関数 を抜けている。matchlen は実際のマッチ長が 1 の場合は、見つからなかった 場合を指しているらしい。 matchlen = 2; 見つかった場合は、最低 2 文字はマッチしているということから matchlen を 2 に設定して次の処理に進む。 for (;;) { (C) if (r >= DICSIZ) { j = MAXMATCH; matchpos = r; } r つまり、q の子が DICSIZ以上であれば、j を MAXMATCHに matchpos を r に 設定している。child() の戻り値 r は pos を示すようだ。 (D) else { j = level[r]; matchpos = position[r] & ~PERC_FLAG; } DICSIZ より小さい場合は、j を level[r] に設定し、 matchpos を position[r] の位置にしている。position[r] も位置を示すらしい。 (E) if (matchpos >= pos) matchpos -= DICSIZ; matchpos が pos 以上を指す場合は、matchpos から DICSIZ を引いている。 スライド前の位置を差す場合を想定しているのか？ (F) t1 = &text[pos + matchlen]; t2 = &text[matchpos + matchlen]; t1 が現在の文字（の末尾）、t2がマッチ文字（の末尾）を指す。 (G) while (matchlen < j) { if (*t1 != *t2) { split(r); return; } matchlen++; t1++; t2++; } matchlen が j （最大マッチ長）となるまで、*t1 と *t2 を比較し、 一致する間先に進めている(matchlen++)そして、一致しない部分を 見つけたときに、split(r) により、木を分割している。 以前、split(r) を見たときに詳細は不明だが、新しいマッチを 木に登録する処理のように見えた。なんとなく理解できる。 (H) if (matchlen >= MAXMATCH) break; matchlen == j となったとき、matchlen が MAXMATCH より大きければ break して for() ループを抜ける。 (I) position[r] = pos; matchlen が MAXMATCH に達しない間は、新しい pos を position[r] に 登録する。 (J) q = r; if ((r = child(q, *t1)) == NIL) { makechild(q, *t1, pos); return; } q を r にし、q と t1 について木を探索する 見つからなければ、新たな q, t1, pos について makechild() して 木に登録して、終了。 (K) matchlen++; } みつかるようなら matchlen を伸ばして、より長いマッチがあるか探索する。 (L) t = prev[r]; prev[pos] = t; next[t] = pos; (M) t = next[r]; next[pos] = t; prev[t] = pos; (L) 以降は for() を抜けた後の処理である。つまり、matchlen が MAXMATCH 以上となった場合。このとき、木を更新している。 r を取り除き、pos とすり替えている。 (N) parent[pos] = q; parent[r] = NIL; next[r] = pos; /* special use of next[] */ pos の親を q とし、r の親をNILに、r の next は pos としているが、 先ほど木から切り離していることおよび、コメントから木とは関係ない 用途に利用しているらしい。 nextやprev、parentに対して似たような処理が何度か現れていた これを関数に切り出せるか考えてみる 。。。。 ここまで読み進めてもはっきり言ってよくわからない なぜかというとデータ構造がまだよくわからないからである そこで今度は各変数を中心に処理を追うことにする なお現時点でわかった情報を変数の一覧に書き込んでおく (1) 以下は本処理の入出力となる text・・・読み込んだテキストのバッファ兼辞書　 remainder・・・読み込んでいるデータのバッファ上の残りサイズ pos・・・現在読み込んでいる位置 matchpos・・・pos位置の文字とマッチした辞書上の位置 matchlen・・・pos位置の文字とマッチした辞書上のマッチ長 (2) 以下により木を現している。ざっと処理をみてトライ木なのではないかと予想 parent prev next (3) 以下は上の木に格納されている補足情報らしい level・・・マッチ長 position・・・文字に対する位置 (4) 以下は木に関するその他の情報 childcount・・・子の個数 avail・・・nextの空きを指すリストのトップ ここで、不明確なのは(2)なので、この構造について追求してみる。 まず、型 next, prev, parent (ついでに、position) はいずれも node 型（の配列）である。 その添え字はというと、next を中心に利用している箇所を上から順に探してみると child(node q, uchar c) /* q's child for character c (NIL if not found) */ { node r; r = next[HASH(q, c)]; parent[NIL] = q; /* sentinel */ while (parent[r] != q) r = next[r]; return r; } next の添え字は、HASH(q, c) である。その後の parent[r], next[r] の記述を見るとどうやら添え字も node である。 node とは何を表すのかが重要である。 insert_node() の冒頭 q = text[pos] + DICSIZ; c = text[pos + 1]; if ((r = child(q, c)) == NIL) { makechild(q, c, pos); match->len = 1; return; } match->len = 2; child() の第一引数は、pos 位置の文字 text[pos] に DICSIZ を足している。 第二引数は、pos の次の位置の文字である。 child() は、next[HASH(第一引数, 第二引数)] を実行するのであった。 ここで、HASH関数がどうなっているか見てみると #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2) つまり、 p + ((c) << (DICBIT - 9)) + DICSIZ * 2 である。HASH()の値はnext[]の添え字であり、常に DICSIZ * 2 以上である(c はunsigned charなので、<< により、負になることはない)。 したがって、下図 *1 の部分の範囲がHASH()の値である。 さらに言うと、HASH(p, c) の p は、text[pos] + DICSIZ なので、 （この部分に関して言えば）、*2 の部分を返すことになる。 ------------------------------------------------------------------------------------------- DICSIZ DICSIZ*2 max_hash_val + 1 / / / +---------------------+---------------------+---------------------+----+ next | 234... NIL| | NIL | | +---------------------+---------------------+---------------------+----+ |----------- *1 -----------| |-*2-| ------------------------------------------------------------------------------------------- ざっと、HASH() を使用している箇所を探してみると、他に makechild() がある これも、makechild()の第一、第二引数がそのままHASH()の引数となる。 では、child(), makechild() を使用している箇所を探すと split() で、使用する new (avail で空きリストが割り当てられる箇所)がmakechild() の第一引数となる場合がある、*1 の範囲がHASH()の戻りのようだ。 HASH() の ((c) << (DICBIT - 9)) の部分を考えてみる c は、text[] の値 （つまり、文字）を示すので、c の値は、0 〜 255 である。そうすると DICBIT は、とりあえず13(-lh5)であるからビット列であらわすと 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| 0| 0| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |-----------| (DICBIT-9) と11ビット目から4ビット目までを使用した値の範囲となる。 ここでは、node 型(実体はunsigned short)の範囲を想定している。 なお、short が16bitであることも前提となっているように思う。 なお、2 * DICSIZ は、(DICSIZ は、1 << DICBITであるので) 以下である。 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ p はというと、今のところ 1 から 255 + DICSIZ の範囲なので、 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 0| 1| 0| 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ これらを足すということは、 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ p | 0| 0| 1| 0| 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| c<<4 | 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| 0| 0| 0| 0| 2*DICSIZ | 0| 1| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ max 0 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 最大でも、max の値にしかならない、これは、next の領域サイズに使われている #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX) と照らし合わせると MAX_HASH_VAL 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 1| 1| 0| 0| 0| 0| 1| 1| 1| 0| 1| 1| 1| 1| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ `-----' `-----------------------------------' / \ 3 * DICSIZ (DICSIZ / 512 + 1) * UCHAR_MAX{255} DICSIZ は、2^13、512 は、2^9 であるから、DICSIZ / 512 は、2^4 である) 見事一致している。なにか納得いかない同じ値を示すのに、どうして違う計算式を 使うのだろう？もう一度、HASH()とMAX_HASH_VALを列挙してみよう。 #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2) #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX) HASH() の式の最大値を考えると p = DICSIZ + UCHAR_MAX c = UCHAR_MAX であるから #define HASH(p, c) ((DICSIZ+UCHAR_MAX) + ((UCHAR_MAX) << (DICBIT - 9)) + DICSIZ * 2) DICSIZを切り出すと #define HASH(p, c) (3 * DICSIZ + UCHAR_MAX + ((UCHAR_MAX) << (DICBIT - 9))) << をべき乗(^ はここでは、べき乗)であらわすと(x << n)は、x * 2^(n)であるから #define HASH(p, c) (3 * DICSIZ + UCHAR_MAX + ((UCHAR_MAX)* 2^(DICBIT - 9))) UCHAR_MAX を切り出すと #define HASH(p, c) (3 * DICSIZ + UCHAR_MAX * (1 + 2^(DICBIT - 9))) x^(a-b) は、x^a / x^b であるから #define HASH(p, c) (3 * DICSIZ + UCHAR_MAX * (1 + 2^DICBIT / 2^9)) これで、MAX_HASH_VALと同じになった。やはり、MAX_HASH_VALは基のHASH()関数の計算式を保存して、 #define MAX_HASH_VAL ((DICSIZ+UCHAR_MAX) + ((UCHAR_MAX) << (DICBIT - 9)) + DICSIZ * 2) とするか、むしろ #define MAX_HASH_VAL HASH(DICSIZ + UCHAR_MAX, UCHAR_MAX) とした方がわかりやすい。どうせ定数の計算式だからコンパイラが計算してくれるのである。 横道にそれた、HASH()関数についてもう一度再考する。 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ p | 0| 0| 1| 0| 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| c<<4 | 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| 0| 0| 0| 0| 2*DICSIZ | 0| 1| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 2*DICSIZ は、値の範囲をnext[]の領域下図（再掲）の*1の部分に押し上げるためのものである。 ------------------------------------------------------------------------------------------- DICSIZ DICSIZ*2 max_hash_val + 1 / / / +---------------------+---------------------+---------------------+----+ next | 234... NIL| | NIL | | +---------------------+---------------------+---------------------+----+ |----------- *1 -----------| |-*2-| ------------------------------------------------------------------------------------------- では、2*DICSIZ を除いて、13ビット目をx その他をyであらわすと 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ p | 0| 0| x| 0| 0| 0| 0| 0| y| y| y| y| y| y| y| y| c<<4 | 0| 0| 0| 0| y| y| y| y| y| y| y| y| 0| 0| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ x y y y y y y y y y y y y y 13ビット目が立っている場合は、*2 の範囲を表しており、*2 の範囲はほぼDICSIZと同じであることが わかる。(正確にはMAX_HASH_VAL+1であるから、yyyyyyyyyyyyy は、1000011110000 半分よりちょっと 多いサイズである。 そして、13ビット目が立っていない場合は、*1 の領域は、やはりyyyyyyyyyyyyyであるつまり、 DICSIZの領域をすべて使っているわけではないのである図を少し訂正しよう。 ------------------------------------------------------------------------------------------- DICSIZ DICSIZ*2 DICSIZ*3 / / / max_hash_val + 1 +---------------------+---------------------+---------------------+----------+ next | 234... NIL| | NIL | NIL | +---------------------+---------------------+---------------------+----------+ |--- *1 ---| |--- *2 ---| ------------------------------------------------------------------------------------------- *1 と *2 は同じである。max_hash_val + 1 - DICSIZ*3 は、*2 + 1 なので、 + 1 の分だけ、図の通りではない。 *1 と *2 は、DICSIZ/2 より少し大きい もう少し、HASH()について考える。13 bit目をとりあえず無視して p ・・・text[]の１文字目 c ・・・text[]の２文字目 であるが、c<<4 としている理由は、 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ p | 0| 0| x| 0| 0| 0| 0| 0| y| y| y| y| y| y| y| y| c<<4 | 0| 0| 0| 0| y| y| y| y| y| y| y| y| 0| 0| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ x y y y y y y y y y y y y y p, c の2文字(2*8bit)の情報を、12bitに写像(桁上がりも考慮)しており、p の 上位4bitとcの下位4bit を使っている。これを行う理由ははっきりとはまだわ からないが、HASH()が指す node は、引数の組み合わせにより同じ値を持つ場 合があることがわかる。 c<<4 はc<<(DICBIT-9)であるが、DICBITが大きくなるとbitをずらす範囲が広がる。 c<<(DICBIT-9) は、2<