Please tell me origin of grep.
SANETO Takanori
qko...@rssun1.cs.shinshu-u.ac.jp (Koide Hiroshi) writes:
> grepと言う名の由来はどこから来ているのですか？
UNIX のエディタである ed には、g (global かな?)コマンドというのがあり
ます。
<範囲>g/<正規表現>/<command>
という形で、<範囲>の中の<正規表現>にマッチする行に<command>を適用する、
というコマンドです。<範囲>のデフォルトはファイル全体です。これを使うと、
ファイルの中である正規表現にマッチする行を表示(pコマンド)する、という
操作は、
g/<正規表現>/p
と書くことができます。ここで、<正規表現>の部分を re と書くと、
g/re/p
はい、grep の出来上がりです。(^_^)
「マッチする行」の代わりに「マッチしない行」を対象とするコマンドもあり
ます。(v コマンド)(なんの略だろう?)(QWERTY キーボードで、g の近くにあ
るからかな。(^_^;) それで、grep には -v オプションというのがあるんです
ね。
> また、egrep,fgrepの e と f は何を意味しているのですか。
> ご存知の方、教えて下さい。
e は enhanced/extended (ed の正規表現に対し、(A|B) という表現や A? と
いう表現ができるよう拡張されている)、f は fixed (指定できるのは固定文
字列のみ)だと思います。
ちなみに、マニュアルを見ると、fgrep の f を fast だと誤解されることも
あるようです。
---
さねを@ソニー
san...@strg.sony.co.jp
Kusakabe Youichi
: grep に関しては global/regular_expression/print のこと、egrep の eは
: extended のこと。ただ、fgrep の f は fast という意見と、fixed（固定文
: 字列のサーチ）という意見の２通りがありました。
「fast」っていうのは私は昔そう教わっただけで、
裏をとったわけではないのであやしいです。
実際にちっとも速くないし ;-)
ヘ_ヘ ------------------------
ミ・・ ミ vo...@merope.opus.or.jp
( ° )～ 日下部陽一
----------------------------------
菊谷誠
記事<1996Jan21.2...@merope.opus.or.jp>でこう書きました:
> : grep に関しては global/regular_expression/print のこと、egrep の eは
> : extended のこと。ただ、fgrep の f は fast という意見と、fixed（固定文
> : 字列のサーチ）という意見の２通りがありました。
>
> 「fast」っていうのは私は昔そう教わっただけで、
> 裏をとったわけではないのであやしいです。
> 実際にちっとも速くないし ;-)
SunOS-4.1.3JLEで man grep すると
「一般にこれらの3種類プログラムの中で最も処理速度の早いのはegrep です。」
なんて書いてあって、なんで一番難しいことしてそうなegrepが速いのだろう
とかねがね思っておりました。
GNUのgrepは三つとも実体は同じみたいですが。
--
人生を背負い投げ
菊谷 誠 (Kikutani Makoto)
E-Mail: kiku...@eis.or.jp,kiku...@bekkoame.or.jp
hgf0...@niftyserve.or.jp
OZAWA Sakuro
>> grepと言う名の由来はどこから来ているのですか？
については，g/RE/p である，と答えが出てますね．
SANETO> 「マッチする行」の代わりに「マッチしない行」を対象とするコマンドもあり
SANETO> ます。(v コマンド)(なんの略だろう?)(QWERTY キーボードで、g の近くにあ
SANETO> るからかな。(^_^;) それで、grep には -v オプションというのがあるんです
SANETO> ね。
「トル(とりのぞけ)」って意味の「レ印」に形が似てるからじゃないでしょう
か？
--
They say that NetHack is never what it used to be.
小澤索郎 <mailto:oz...@prince.pe.u-tokyo.ac.jp>
<http://www.arai.pe.u-tokyo.ac.jp/~ozawa/>
GCS/E C++ UL++S+@ P+++ L++>+++ E+>++ W++@ N++ w-- M+() R+>+++ tv+ b+++
Junn Ohta
oz...@prince.pe.u-tokyo.ac.jpさんは書きました。
> SANETO> 「マッチする行」の代わりに「マッチしない行」を対象とするコマンドもあり
> SANETO> ます。(v コマンド)(なんの略だろう?)(QWERTY キーボードで、g の近くにあ
> 「トル(とりのぞけ)」って意味の「レ印」に形が似てるからじゃないでしょう
> か？
「inver{se,t}」の「v」ではないでしょうか。
いまちょっと調べられませんが、4.2BSDのころのgrepの
マニュアルに「inverted match」のような表現が含まれ
ていたような記憶があります。grep属のユーティリティ
ーの中には、agrepの「inverse mode」のような表現を
使っているものもあります。
--
太田純(Junn Ohta) (株)リコー ソフトウェア事業部
oh...@src.ricoh.co.jp/JCF0...@niftyserve.or.jp
Junn Ohta
kiku...@ams.co.jpさんは書きました。
> SunOS-4.1.3JLEで man grep すると
> 「一般にこれらの3種類プログラムの中で最も処理速度の早いのはegrep です。」
> なんて書いてあって、なんで一番難しいことしてそうなegrepが速いのだろう
> とかねがね思っておりました。
fgrepとgrepはテキスト中の各文字位置からパターンと
の照合を行うため、テキスト長をm、パターン長をnとす
と検索にO(m*n)の時間がかかるが、egrepはパターンか
ら決定性有限オートマトンを生成してテキストと比較す
るため後戻りがなく、mが大きい場合はO(m)の時間で検
索できる、ということだった、ような、気がします。
# でも、ああ、自信がない。どなたかご神託を。(_ _;)
IIDA, Yosiaki
# ナレッジブルユーザー(knowledgeable user)は、固定文字列を grep で探
# 索する。
# エキスパートは、誰かに「こっちが速い」と言われて fgrep を使う。
# ハッカーは、処理速度を測った結果、egrep を使うことにした。
# グルは今度の UNIX リリース時に James Wood/Henry Spencer の egrep
# を入れるつもり。
なんだそうです。
--
GNU's Not UNIX. UNG's Not GNU. IIDA, Yosiaki the Epigonen of RMS.
Ken Nakata
Junn Ohta <oh...@src.ricoh.co.jp> wrote:
>fj.questions.unixの記事<4dv5tt$n...@thesun.ams.co.jp>で
> kiku...@ams.co.jpさんは書きました。
>> SunOS-4.1.3JLEで man grep すると
>> 「一般にこれらの3種類プログラムの中で最も処理速度の早いのはegrep です。」
>> なんて書いてあって、なんで一番難しいことしてそうなegrepが速いのだろう
>> とかねがね思っておりました。
>
>fgrepとgrepはテキスト中の各文字位置からパターンと
>の照合を行うため、テキスト長をm、パターン長をnとす
>と検索にO(m*n)の時間がかかるが、egrepはパターンか
>ら決定性有限オートマトンを生成してテキストと比較す
>るため後戻りがなく、mが大きい場合はO(m)の時間で検
>索できる、ということだった、ような、気がします。
>
># でも、ああ、自信がない。どなたかご神託を。(_ _;)
ご信託などというものでは全然なく、私も調べてみないと自信がないんですが
(Hopcroft & Ullman どこいった)、その上 fgrep と grep の O(m*n) もどう
だったか憶えていないのですが、egrep の場合 O(m+n) で普通は m >> n なの
で O(m)、という話だったような気がします。
また、最近の egrep は NFA(非決定性有限オートマトン)から DFA(決定性)へ
の変換は動的というか lazy にやっているので正規表現が大きい場合でもオー
バヘッドが少ないのだ、とこれはたぶん Kernighan か Aho かとにかく Bell
Lab. の人の書いたもので読んだ記憶があります。
# 趣味で私が Common Lisp で書いた regex マッチング関数では、力まかせに
# NFA を直接走らせてました(^^;)。CL 組込の REDUCE 使うと簡単なんです。
中田 健 <ke...@remus.rutgers.edu>
--
"He who refuses to do arithmetic is doomed to talk nonsense." -- John McCarthy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
http://remus.rutgers.edu/~kenn/, ftp://remus.rutgers.edu/pub/NetBSD/index.html
Ken Nakata . . . . Cook College, Rutgers - The State University of New Jersey
Junn Ohta
ii...@secom-sis.co.jpさんは書きました。
> # グルは今度の UNIX リリース時に James Wood/Henry Spencer の egrep
> # を入れるつもり。
4.4BSDはそうなってますよね。:-)
Yutaka Kaneko
In article <4e4s4c$6...@ns.src.ricoh.co.jp>
oh...@src.ricoh.co.jp writes:
>> fgrepとgrepはテキスト中の各文字位置からパターンと
>> の照合を行うため、テキスト長をm、パターン長をnとす
>> と検索にO(m*n)の時間がかかるが、egrepはパターンか
>> ら決定性有限オートマトンを生成してテキストと比較す
>> るため後戻りがなく、mが大きい場合はO(m)の時間で検
>> 索できる、ということだった、ような、気がします。
文字列検索のアルゴリズムとしては、時間がO(mn)のものもO(n)
のものもあるようです。手元の本(*1)には`Knuth-Morris-Pratt'の
アルゴリズムとか、`Boyer-Moore'のアルゴリズムとかが載ってい
ますがきちんと読んだわけではありません。ざっと見た感じでは、
テキストをn文字ごとにとりだし、その文字がパタン中にあらわれ
る文字かどうか比較するといったもののようです。
fgrepでどんなアルゴリズムを使っているかは知りません。
*1) 石畑清, 「アルゴリズムとデータ構造(岩波講座ソフトウェア科学3)」,
岩波書店, 1989年
ISBN 4-00-010343-1
## 「簡単に」作るなら、strstr(3)を使ってしまうだろうから、多
## 分O(mn)になるんだろうな。
main(i,j){j=time(0);do for(i /* 金子 裕(Yutaka Kaneko) */
=0;i<79;i++)printf(j%512>>4? /* Sendai National College of Technology */
" ":"*"),j=j*331+113;while( /* kan...@cc.sendai-ct.ac.jp */
printf("\n\033[H\033[1L"));} /* or kan...@akiu.gw.tohoku.ac.jp */
Junn Ohta
kan...@ccedu.sendai-ct.ac.jpさんは書きました。
> 文字列検索のアルゴリズムとしては、時間がO(mn)のものもO(n)
> のものもあるようです。手元の本(*1)には`Knuth-Morris-Pratt'の
> アルゴリズムとか、`Boyer-Moore'のアルゴリズムとかが載ってい
> ますがきちんと読んだわけではありません。ざっと見た感じでは、
> テキストをn文字ごとにとりだし、その文字がパタン中にあらわれ
> る文字かどうか比較するといったもののようです。
うろ憶えなのでちょっといいかげんですが...。
いずれのアルゴリズムも、検索パターンを前処理し、パ
ターン中の特定の位置の文字とテキスト中の文字が一致
しなかったときに検索開始位置をどれだけ右にずらせる
かを示すテーブルを作ります。
Boyer-Mooreでは比較をパターンの終端から行うところ
が特徴だったように記憶しています。たとえば検索パタ
ーンの終端に対応する位置のテキスト中の文字が検索パ
ターンに含まれないものだった場合、検索開始位置をま
るまる検索パターンの長さ分だけ右にずらすことができ
るわけです。このため、最善の場合の処理時間はO(m/n)
になるわけですが、grepのような応用では読み飛ばす部
分もファイルアクセスして読み込まなければならないた
め、実際にはそこまで劇的に高速化されるわけではあり
ません。
4.4BSD-Liteのegrep(grep、fgrepも同じ)は、検索パタ
ーン中で最長の固定文字列をBoyer-Moore(Gosper拡張を
含む)法で検索し、その前後の正規表現を非決定性有限
オートマトンで検索するという方針をとっています。正
規表現検索エンジンはHenry Spencerのregexp()です。
GNU grepもほぼ同じですが、正規表現検索エンジンには
GNU regex()が使われています。また、GNU grep 2.0で
は可能であればメモリーマップトファイルを利用するた
め、そのことも高速化に寄与しているようです。
Junn Ohta
ke...@branford-asy-6.rutgers.eduさんは書きました。
> ちょっと調べてみました。ネタ本は、古い本ですが Aho、Hopcroft、Ullman
> の『アルゴリズムの設計と解析II』(サイエンス社)です。で、意外だったのが、
> fgrep(というか Morris & Pratt のアルゴリズム)の処理時間は O(m + n) で
> 線形でした。
fgrepがMorris-Prattのアルゴリズムを使っている、と
いうのはちょっとびっくりでした。その本に書かれてい
ることなのでしょうか?
Ken Nakata
Junn Ohta <oh...@src.ricoh.co.jp> wrote:
] fj.questions.unixの記事<42...@ume.cc.tsukuba.ac.jp>で
] ke...@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_
上記の本には grep や egrep、fgrep といった名前は出てきません(何せ UNIX
が今ほどポピュラーでない時代の本ですから…)。
WATANABE Katsuhiro
あまりのフォローの遅さが議論の妨げになっていたらごめんなさい。
egrep の lazy transition evaluation 法に関して、
記事 <42...@ume.cc.tsukuba.ac.jp> で
ke...@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 の比較に関して、
記事 <42...@ume.cc.tsukuba.ac.jp> で
ke...@branford-asy-6.rutgers.edu (Ken Nakata) さんいはく
> 実際には egrep が fgrep より速いというのは一体何なん
> でしょうか。
一般に(fgrep が本来の使われる領域なら)
egrep は fgrep より速く *ない*
と私は主張します。あるいは控えめに、
fgrep の方が速い領域がある
ぐらいにしておきましょうか。
これに続いて記事 <42...@ume.cc.tsukuba.ac.jp> で
ke...@branford-asy-6.rutgers.edu (Ken Nakata) さんいはく
> In article <4eam9g$9...@ns.src.ricoh.co.jp>,
> Junn Ohta <oh...@src.ricoh.co.jp> wrote:
> ] fj.questions.unixの記事<42...@ume.cc.tsukuba.ac.jp>で
> ] ke...@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$p...@ns.src.ricoh.co.jp> で
oh...@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
にあります。
--
渡邊克宏＠ＳＲＡ
どこを読んでるんだろう？ fj はこんなに楽しい議論がされている場所なのに。