Koji Arai
JCA02****@nifty*****
2003年 1月 13日 (月) 08:13:08 JST
Fork新井です。
更新。これで一通りの解読が完了。全体を見直して体裁を整えた後は huf.c
に移るか、slide.c のソース書き換えを行うか？
Index: Hackinf_of_LHa
===================================================================
RCS file: /cvsroot/lha/lha/Hackinf_of_LHa,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -u -r1.4 -r1.5
--- Hackinf_of_LHa 12 Jan 2003 18:46:22 -0000 1.4
+++ Hackinf_of_LHa 12 Jan 2003 23:07:31 -0000 1.5
@@ -1,4 +1,4 @@
-$Id: Hackinf_of_LHa,v 1.4 2003/01/12 18:46:22 arai Exp $
+$Id: Hackinf_of_LHa,v 1.5 2003/01/12 23:07:31 arai Exp $
The Hacking of LHa for UNIX (1st draft)
-------------------------------------------
@@ -1850,6 +1850,142 @@
細部は未だ目をつぶっているのだがこれで match_insert() の解読は終りだ。
+match_insert() の処理とは以下の通りだ。
+
+----------------------------------------------------------------------------
+ match_insert() は、text[pos] から始まる文字列に一致する文字列を辞書
+ から検索し、見つかった位置と一致長を matchpos, matchlen に設定する。
+
+ もし、最長一致文字列が見つからなければ matchpos は、off に設定され、
+ matchlen は更新されない。
+
+ 見つかった場合、matchlen は呼び出し前の matchlen よりも大きくなる。
+ (呼び出し前では matchlen の意味は最低限一致しなくてはならない文字列
+ 長で、照合条件の一つになっている)
+
+ この関数の入力は
+
+ matchlen
+ pos
+
+ 出力は
+
+ matchlen
+ matchpos
+
+ といったところ。
+
+ さらに、insert() と同様の処理で、pos の位置をハッシュ配列に記録し、
+ 次回の検索に備える。これはついでの処理。
+----------------------------------------------------------------------------
+
+これを踏まえた上で処理内容を再読しよう。(E) 〜 (H) だ。
+
+ /* (E) */
+ lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
+ --matchlen;
+
+ /* (F) */ /* (G) */
+ get_next(); match_insert();
+ if (matchlen > remainder) matchlen = remainder;
+
+ /* (H) */
+ if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
+ /* (H.1) */
+ encode_set.output(text[pos - 1], 0);
+ count++;
+ } else {
+
+(H) の条件とは何なのかを見る。この条件が真なら、文字列をそのまま出力す
+るのだが、素直に slide 辞書法の処理を考えればこの条件は「辞書から見つ
+からなかった場合」となる。が、実際にはもう少し複雑だ。
+
+ /* (H) */
+ if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
+
+matchlen は、pos の位置の文字列が見つかった辞書上の長さ
+lastmatchlen は、pos-1 の位置の文字列が見つかった辞書上の長さ
+
+であるとすると、この条件は、「pos の位置で見つかった長さが、pos-1 の位
+置で見つかった長さよりも長ければ」っとなる。
+
+これはつまり、pos-1 と pos のニ箇所に関して辞書を検索して、より長くマッ
+チする方を選ぼうとしているわけだ。matchlen の方が長いなら 1 つ前
+(pos-1)の文字はそのまま出力し、次のループに移る(もし、次の文字が
+さらに長くマッチするなら。またそのまま出力される)
+
+この条件で「見つからなかった場合」というのはどう表されているかを考える。
+もし、pos の文字列が辞書になければ pos - 1 の文字列は、どうすべきかと
+いうと「pos-1 の文字列が見つかってなければ。そのまま出力。辞書にあった
+なら <lastmatchlen, lastmatchoffset> のペアを出力」っとならなければな
+らない。
+
+lastmatchlen は、初期状態では THRESHOLD - 1 であったので、見つからなかっ
+たという条件は (H) の右側の条件 lastmatchlen < THRESHOLD でまず表され
+ている。
+
+では、例えば lastmatchlen が 5 であったとしよう。このとき (E) の処理で
+matchlen は lastmatchlen - 1 つまり、4 に設定される。そして、match_insert()
+で次の文字列がもし辞書から見つからなければ matchlen は更新されないので
+ matchlen < lastmatchlen
+となる。このような条件(前回見つかり、今回見つからない)場合に限り、(H.2)
+の処理が実行されるようになっている。では、(H.2) の処理を追いかけよう。
+
+まず、この状態を図示する。
+
+----------------------------------------------------------------------------
+
+ lastmatchlen lastmatchlen
+ |-- --| |-- --|
+ +---------------+--------------+--------------+--------------+--+
+text | | | | | | | | | | | | | |
+ +---------------+--------------+--------------+--------------+--+
+ ^ | \ \
+ matchpos pos-1 pos pos2
+
+ |--------------------------|
+ lastmatchoffset
+
+----------------------------------------------------------------------------
+
+
+ /* (H.2) */
+ encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
+ (lastmatchoffset) & (dicsiz-1) );
+ --lastmatchlen;
+
+ while (--lastmatchlen > 0) {
+ get_next(); insert();
+ count++;
+ }
+ get_next();
+ matchlen = THRESHOLD - 1;
+ match_insert();
+ if (matchlen > remainder) matchlen = remainder;
+ }
+
+まず、<長さ, 位置> のペアを出力する。これはいいだろう。出力する「位置」
+は0 なら 1 文字前を表すので、実際のオフセット pos - 1 - matchpos より
+も 1 小さい値になっていることに注意しておこう。
+
+そして、lastmatchlen は 1 引かれる。この場合例えば 4 になる。したがっ
+て、次のループでは 3 文字 pos が先送りされる(4 ではない)。pos は既に 1
+文字先に進んでいるので、最初に 1 引くのはこのことを考慮している。while
+ループが終った後はpos の位置は実際に出力した文字列の最後の文字 pos2-1
+を指していることになる。
+
+そして、get_next() でまた 1 文字先に送る。pos は図の pos2 の位置になる。
+そして、match_insert() で、この位置の文字列を照合する。matchlen は、
+THRESHOLD - 1 に初期化されるので pos2 の位置の文字列が辞書から見つから
+なければ matchlen は、THRESHOLD-1 だ。これは初期状態と同じ状態を示すの
+で、次のループの処理も想像がつく((H) の条件の右側 lastmatchlen < THRESHOLD
+が有効になる)。では、見つかった場合はというと、次のループでさらに先
+pos2+1 の照合結果と比較されるのでこの処理も想像がつく。
+
+最初、どうにもこの処理内容が理解できなかったのだが「現在の文字列と、次
+の文字列のそれぞれで辞書を検索し、より長く見つかった方を使う」という最
+適化を行っている事がわかってしまった後は解読は簡単だった。(実はこの事
+実も教えてもらった事だ。全然ダメじゃん)
# Local Variables:
# mode : indented-text