Tsugio Okamoto
tsugi****@muc*****
2003年 1月 9日 (木) 00:59:13 JST
岡本です. On Wed, 08 Jan 2003 07:17:58 +0900 (JST) Koji Arai <JCA02****@nifty*****> wrote: > 新井です。 > > > offは検索を早くするための名残です.lhaを誕生させる試行錯誤した結果です． > > もとは，こんなに汚いソースではなかったのです． > > off は難解です。まだわかりません。 うる覚えなのですが，もともとはこんなアイディアからです． 現在の圧縮しようとしている文字列の位置: pos として， text[pos],text[pos+1],text[pos+2]をハッシュ値として，ハッシュリスト から辞書内の位置を示す値を取得します．まだ本当に一致するのか， 一致してもどのくらいの長さで一致するのかは不明です． 次に，同じハッシュ値のハッシュリストをだどっていくと，辞書内に 3文字以上一致する可能性のある文字列の位置の候補がいくつか検索 できるわけですが，その候補の位置sposからはじまる文字列と， 現在の位置posからはじまる文字列を比較します． この比較した結果がmatchposとかmatchlenとかになります． で，候補になる位置からはじまる文字列を次々に比較していきます． 基本的に最長一致する位置の辞書を使うことになります． これが通常ですが，ある特定の3文字のハッシュ値を使うと リストが長くなる可能性があります． これを，現在の位置posから少し右にずらして例えば4くらいにし， そこのtext[pos+4],text[pos+5],text[pos+6]をハッシュ値として， ハッシュリストを検索していきます． ただし，候補の文字列の比較は，text[pos],text[pos+1],...から始めます. こうすると，3+4文字以内となる文字長の検索はできなくなってしまうの ですが，先頭のtext[pos]…をハッシュ値として検索するよりも， text[pos+4]…をハッシュ値として検索した方がリストが短く，検索時間が 短くなる可能性があります． あ，でも，今は長いリストを持つハッシュ値だけこうしていたのかな？ だんだん忘れかけているのですが，基本的な使い道はこういうことだったと 思います. ----------------------------------------------------- Tsugio Okamoto (E-Mail:tsugi****@muc*****)
Fork