Path: katsu From: katsu@sra.co.jp (WATANABE Katsuhiro) Message-ID: Date: 19 Jun 1996 00:58:13 GMT Organization: Software Research Associates, Inc., Japan In-reply-to: kenn@basie-slip-67.rutgers.edu's message of 27 Jan 96 12:05:51 GMT Newsgroups: fj.questions.unix Subject: Re: Please tell me origin of grep. References: <42301@ume.cc.tsukuba.ac.jp> <42313@ume.cc.tsukuba.ac.jp> <4eam9g$90j@ns.src.ricoh.co.jp> <42317@ume.cc.tsukuba.ac.jp> <4e9hj9$p3o@ns.src.ricoh.co.jp> Distribution: Mime-Version: 1.0 (generated by tm-edit 7.47) Content-Type: text/plain; charset=ISO-2022-JP あまりのフォローの遅さが議論の妨げになっていたらごめんなさい。 egrep の lazy transition evaluation 法に関して、 記事 <42301@ume.cc.tsukuba.ac.jp> で kenn@basie-slip-67.rutgers.edu (Ken Nakata) さんいはく > また、最近の egrep は NFA(非決定性有限オートマトン)から DFA(決定性)へ > の変換は動的というか lazy にやっているので正規表現が大きい場合でもオー > バヘッドが少ないのだ、とこれはたぶん Kernighan か Aho かとにかく Bell > Lab. の人の書いたもので読んだ記憶があります。 Aho でしょう。 A. V. Aho;「文字列中のパターン照合のためのアルゴリズム」; 仙波一郎訳; コンピュータ基礎理論ハンドブックI pp.263-304; 丸善; から引用すると、 筆者によって,UNIX システムの egrep コマンドで使われた効果的な 手法は「のろまな遷移評価(lazy transition evaluation)」法である. だそうですから。 lazy transition evaluation については、通称 dragon book A. V. Aho, Ravi Sethi, J. D. Ullman "Compilers"; Addison-Wesley; 1986; にも記述があります。1986 年ですから「最近の」ではなく結構以前から かもしれませんね。 次に egrep と fgrep の比較に関して、 記事 <42313@ume.cc.tsukuba.ac.jp> で kenn@branford-asy-6.rutgers.edu (Ken Nakata) さんいはく > 実際には egrep が fgrep より速いというのは一体何なん > でしょうか。 一般に(fgrep が本来の使われる領域なら) egrep は fgrep より速く *ない* と私は主張します。あるいは控えめに、 fgrep の方が速い領域がある ぐらいにしておきましょうか。 これに続いて記事 <42317@ume.cc.tsukuba.ac.jp> で kenn@branford-asy-6.rutgers.edu (Ken Nakata) さんいはく > In article <4eam9g$90j@ns.src.ricoh.co.jp>, > Junn Ohta wrote: > ] fj.questions.unixの記事<42313@ume.cc.tsukuba.ac.jp>で > ] kenn@branford-asy-6.rutgers.eduさんは書きました。 > ] > ちょっと調べてみました。ネタ本は、古い本ですが Aho、Hopcroft、Ullman > ] > の『アルゴリズムの設計と解析II』(サイエンス社)です。で、意外だったのが、 > ] > fgrep(というか Morris & Pratt のアルゴリズム)の処理時間は O(m + n) で > ] > 線形でした。 > ] > ] fgrepがMorris-Prattのアルゴリズムを使っている、と > ] いうのはちょっとびっくりでした。その本に書かれてい > ] ることなのでしょうか? > > あ、これは大変失礼しました。「fgrep でできることは Morris&Pratt のアル > ゴリズムでできて、その処理時間は O(m+n)、だから fgrep も O(m+n) で走ら > ないと変ですね」くらいのつもりだったんです…。すごくまぎらわしい表現で > した。 _o_ この出発点「fgrep のやっていることは (Knuth-)Morris-Pratt でできる」 も間違っているのではないでしょうか。(できないことはないにしても、 fgrep のやっていることを KMP でやるのは効率が悪いでしょう。) fgrep は、文献検索や索引作成の研究から生まれ、本来は(単一のキーワード でなく)多数のキーワードの *集合* に対して効率よく働くように設計された プログラムです。(単一キーワードや少ないキーワード数で他と比較するのは、 fgrep の目的に沿わず不公平だと思います。)一方、KMP, Boyer-Moore などは 単一のキーワードに対して照合を行なうアルゴリズムです。KMP を使って fgrep を作ったら、複数のキーワードがあった時、各キーワード毎に探索を 繰り返すことになってしまうことでしょう。 fgrep は、KMP を複数キーワードへ一般化したAho-Corasick アルゴリズムを 使っています(see. dragon book)。Aho-Corasick は、キーワード数が大きい ほど有利です。お手元の egrep,fgrep で、キーワードが多い時の速度を 比べてみてください。キーワード数が多いほど fgrep が有利になって いくのがわかると思います。ただし、そもそも速度以前の話として、egrep の 実装によっては、キーワード列を何十個も (|) でつなげたようなパターンを 処理しきれないこともあります。記事の最後にも比較用の perl script を つけておきます。 ちなみに、Aho-Corasick の時間計算量は O(m+n)、空間計算量は O(m)で、 KMP と同じです。 egrep が検索一般に適用範囲が広いのに比較すると、fgrep を適用すべき 状況というのはかなり限られています。(私は今まで egrep なら 2^12 回 ぐらい起動したかもしれませんが、fgrep が便利だと思った局面に会った のは 2^3 ぐらいの気がします。それも、キーワードが多くて速度が気に なったというより、.*+ などの文字を escape するのを面倒くさく思った 時です。)それでも fgrep を使うべき場面は確実に存在すると思ってます。 話を GNU grep の実装に移して、 記事 <4e9hj9$p3o@ns.src.ricoh.co.jp> で ohta@src.ricoh.co.jp (Junn Ohta) さんいはく > うろ憶えなのでちょっといいかげんですが...。 > 4.4BSD-Liteのegrep(grep、fgrepも同じ)は、検索パタ > ーン中で最長の固定文字列をBoyer-Moore(Gosper拡張を > 含む)法で検索し、その前後の正規表現を非決定性有限 > オートマトンで検索するという方針をとっています。正 > 規表現検索エンジンはHenry Spencerのregexp()です。 > > GNU grepもほぼ同じですが、正規表現検索エンジンには > GNU regex()が使われています。 GNU grep(egrep, fgrep と同一バイナリ)は確かに GNU regex() を 使ってはいますが、ver 2.0 の README によれば、 README> GNU grep is based on a fast lazy-state deterministic README> matcher (about twice as fast as stock Unix egrep) hybridized README> with a Boyer-Moore-Gosper search for a fixed string... と、決定性オートマトンである旨を言明しています。ソースにも dfa.c という、いかにもという名前のファイルがありますし。 4.4BSD-Lite の egrep にしても本当に非決定性オートマトンでしょうか? (e|f)?grep の使い分け方について某所で発表させて頂いた時の OHP を http://www.sra.co.jp/people/katsu/grep/ に置いてあります。詳しい方からの御意見や誤りの指摘、最新情報を お待ちしております。また、若干のヨタ話が http://www.sra.co.jp/people/katsu/article/241 http://www.sra.co.jp/people/katsu/article/266 http://www.sra.co.jp/people/katsu/article/267 にあります。 -- 渡邊克宏@SRA どこを読んでるんだろう? fj はこんなに楽しい議論がされている場所なのに。 #!/bin/sh # This is a shell archive (produced by shar 3.52.3) # To extract the files from this archive, save it to a file, remove # everything above the "!/bin/sh" line above, and type "sh file_name". # # made 06/19/1996 00:56 UTC by katsu@sras49 # Source directory /var/home/katsu/hack/grep # # existing files will NOT be overwritten unless -c is specified # # This shar contains: # length mode name # ------ ---------- ------------------------------------------ # 1779 -rwxr-xr-x efgrep # touch -am 1231235999 $$.touch >/dev/null 2>&1 if test ! -f 1231235999 && test -f $$.touch; then shar_touch=touch else shar_touch=: echo 'WARNING: not restoring timestamps' fi rm -f 1231235999 $$.touch # # ============= efgrep ============== if test -f 'efgrep' && test X"$1" != X"-c"; then echo 'x - skipping efgrep (File already exists)' else echo 'x - extracting efgrep (Text)' sed 's/^X//' << 'SHAR_EOF' > 'efgrep' && #!/usr/local/bin/perl # # compare speed of egrep and fgrep for many keywords. # X X # configuration params $egrep="/usr/bin/egrep"; #$egrep="/usr/local/gnu/bin/egrep"; $fgrep="/usr/bin/fgrep"; #$fgrep="/usr/local/gnu/bin/fgrep"; X # don't touch following lines $words="/usr/dict/words"; ($nwords)=split(' ', `wc -l $words`); $keywords_e_pref="/tmp/ke"; $keywords_f_pref="/tmp/kf"; X do efgrep(16); do efgrep(32); do efgrep(64); do efgrep(128); do efgrep(256); X sub efgrep { X local($nkeywords) = @_; X local($keywords_e) = ("$keywords_e_pref$nkeywords"); X local($keywords_f) = ("$keywords_f_pref$nkeywords"); X X open(WORDS, $words) || die "cannot open $word.\n"; X open(KEYWORDSE, ">$keywords_e") || die "cannot open $keywords_e.\n"; X open(KEYWORDSF, ">$keywords_f") || die "cannot open $keywords_f.\n"; X printf KEYWORDSE "("; X srand(time + $$); X $k = 0; X while () { X if (&sane_rand($nwords - $. + 1) < ($nkeywords - $k)) { X printf KEYWORDSF; X chop; X if (++$k == $nkeywords) { X printf KEYWORDSE "$_)"; X last; X } else { X printf KEYWORDSE "$_|"; X } X } X } X close(WORDS); X close(KEYWORDSE); X close(KEYWORDSF); X X printf STDERR "$nkeywords keywords:\n"; X # -q option is not used intentionally. X do time_command("$fgrep -f $keywords_f $words > /dev/null"); X do time_command("$egrep -f $keywords_e $words > /dev/null"); X printf STDERR "\n"; X X #unlink($keywords_f); X #unlink($keywords_e); X } X sub time_command { X local($command) = @_; X X printf STDERR "execute: $command\n"; X system("time $command"); } X sub sane_rand { X # Almost same as rand function. X # I couldn't have confidence that rand(X) never returns X. X local($r) = @_; X local($n); X X for(; $n >= $r; $n = rand($r)) {} X $n; } SHAR_EOF $shar_touch -am 0618133396 'efgrep' && chmod 0755 'efgrep' || echo 'restore of efgrep failed' shar_count="`wc -c < 'efgrep'`" test 1779 -eq "$shar_count" || echo "efgrep: original size 1779, current size $shar_count" fi exit 0