namazu-ml(avocado)


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

simple method to implement regexp search



高林です

pnamazu を見習って中間一致検索の実装をしていてふと気付いたのですが、
わざわざ中間一致用のインデックスを用意しなくても単純に

% wdnmz NMZ.i > words

みたいな感じで登録単語の一覧表を作っておいて、これを grep するのは
どうでしょう。これだと十分な速度が出ますし、何より正規表現が使える
のが嬉しいです。しかも考え方はすごくシンプルで私好み :-)。

手元にある RFCのインデックス(30MBくらい) で上記のファイルを作って 
grepするとキャッシュが効いている場合は Pentium133MHzのマシンで

% time grep smtp words >/dev/null 

real    0m0.313s
user    0m0.160s
sys     0m0.150s

くらいで検索できます。grepでひっかかったリストを OR でマージすれば
いいわけですね。ちなみに words は

% wc words 
 376859  753718 5238302 words

と約 5MBです。実際にこの方法を実装するなら NMZ.i へのポインタをつ
けるかな。

# Ruby の正規表現ライブラリを使わせてもらえば良いのかな? 日本語の
# 正規表現が使えると嬉しいのだけど…。


でもよく考えたらこれと同じようなことを glimpse がやっていたような
気もします。なんとなくコロンブスの卵みたいな方法ですね。

# 正規表現対応の全文検索システムというとものすごく高度な感じがして
# 楽しいですね。実際は単純な仕掛けでも :-)。

--
高林 哲 Satoru Takabayashi