else end = buf + size ; *endp = end; while (beg > buf & & beg[—l] ! = —beg ; return beg; kwset-t となっています。 kwset. h ファイルを調べると、 この関数の引数はキーワード集合を表す kws で、型は kwset_t kws ; kwsprep(kws) Char * います。 みましよう。この関数は kwset. c ファイルで定義されて 次に、検索のための前処理をおこなう kwsprep をみて kwset (struct kwset * ) kws ; という変数に代入可能な値であり、 register struct kwset *kwset ; には、ソースコードのすぐ次にあるように、 などとなっており、何でも参照できるポインタです。実際 typedef void *kwset—t ; kwset-t 型は、 UNIX MAG AZIN E 2000.4 の文字列の長さか格納されています。この delta 配列は kwset->mind には、パターンとして指定された最短 255 ; delta[i] for (i = 0 ; i く NCHAR; + + i ) else kwset—>mind; delta[i] for (i = 0 ; i く NCHAR; + + i ) if (kwset—>mind く 256 ) その次に、ます delta 配列を初期化しています。 ています。 型を旦言しておき、実際には構造体へキャストして利用し に、ヘッダファイルでは何でも参照できるポインタとして 性があります。ここでは、型に関する情報を隠蔽するため を変更したときにうまく重川しないプログラムとなる可能 に依存した処理をおこなってしまい、 kwset 型の内音財冓造 関数に kwset 型の詳細を伝えると、 kwset 型の内音財冓造 kwset 型を秘密にしておくための処置です。呼出し側の これは、 kwsexec 関数を呼び出す側の関数に対して、 インタです。 も、 kwset. c ファイルで定義されている kwset 型へのホ プログラミング・テクニック 97 = の 再度 1 に書き換えられます。 : 麪頁から順番に処理していけ 初は 3 になりますが、 3 文字目の処理をおこなった段階で 2 、 delta 「 b'] は 1 、 delta['c'] は 0 になります。 b は、最 照合文字列が babc であれは、この処理で delta 「 a'] は kwset—>mind delta[(unsigned char) kwset—>target [i]] 0 ; i く kwset—>mind; 十十 i ) for (i 続いて、 delta 配列を正しく調整します。 しています。 たいため、 こで kwset->target に照合文字列を取り出 するときは照合文字列を盟凾の文字列としてもアクセスし ていることが重要となりますが、 Boyer-Moore 法を利用 です ) 。はかのアルゴリズムで検索する場合には構造をもっ れる構造を使って一尉寺されています (trie というメンバー 次回に紹介する予定ですが、照合文字列はトライと呼ば curr—>links—>trie ; kwset—>target [i] = curr—>links—>label; curr = kwset—>trie; i > = 0 ; for (i = kwset—>mind ー 1 , (&kwset—>obstack, kwset—>mind) ; obstack_alloc kwset—>target 次に、照合文字列を取り出しています。 いを無視しないことを石忍しています。 こで大文字と小文字の違 けれはなりません。そのため、 も、 ABC や Abc など、いくつもの文字列とマッチしな るときには、たとえはパターンとして abc カ甘旨定されて に 0 以外の値となります。大文字と小文字の違いを無視す 字と小文字の違いを無視するオプションカ甘旨定された場合 半部分で指定している trans は、文字を上交する際に大文 れたパターンが 1 つだけであることを石忍しています。後 牛の前半部分は、文字どおりキーワード集合に登録さ 1 & & kwset—>trans if (kwset—>words 用できます。次はその検査です。 Boyer-Moore 法は、照合文字列が 1 つだけの場合に利 ます。 照合文字列が長すぎるときには、 255 を最高値としてい 入します。しかし、 delta は unsigned char の配列です。 れ、すべての文字に対して、最初に照合文字列の長さを代 Boyer-Moore 法の不一致文翁去を実現するために用いら

ば、けっきよくはもっとも右イ則にある文字のための計算が 有効になるので、正しい delta の値か得られます。 次は一致文字列法を利用するための処理です。厳密に は、照合文字列の長さの配列を作り、それぞれの文字の前 まで一致していたらどれくらい移動するのかをすべて言算 します。しかし、 fgrep の場合にはそこまで丁寧な処理は していません。末尾からみて 1 文字目に一致し、 2 文字目 以降は成功したか失敗したか分からない状態での移重丿胤を 言 t 算しています。 kwset—>mind2 = kwset—>mind ; / * Find the minimal de1ta2 shift that we might make after a backwards match has failed. * / fo て (i = 0 ; i く kwset->mind ー 1 ; + + i ) if (kwset—>target Ci] kwset—>target [kwset—>mind ー 1 ] ) kwset—>mind2 = kwset—>mind ー (i + 1 ) ; 次に、変数を設定したあと、実際のメインループに入り 照合文字列の末尾にある文字がそこ以外に照合文字列に 現れないのであれば、実際には照合文字列の長さぶんだけ 照合したい文字列の長さ以 E であれは一致するはすがあり 照合文字列の長さが 0 であれはかならす成功しますし、 return memchr(text, kwset—>target [ 0 ] , size) ; = 1 ) if (len return 0 ; if (len > size) return text ; if (len = = 0 ) Ien = kwset—>mind ; の長さに合わせて特別な処理をおこなっています。 bmexec の麪頁では、ます照合文字列の長さを十ヾ、そ bmexec も kwset. c ファイルで定義されています。 能な場合、 bmexec を使って実際の処理をおこないます。 ません。長さが 1 であれは、 理できます。 ます。 これは騙屯な memchr で処 とることができます。 より厳密に処理するなら、 bcaca という照合文字列に対しては、 5 5 2 5 1 Boyer-Moore 法での検索が可能かどうかを調べます。可 検索をおこなう kwsexec 関数も、 kwsprep と同様に 高速に重川したのでしよう。 列として 1 文字しか利用しないという簡単な去のはうが 照合をおこなうループでの処理を増やすよりも、一致文字 ません。おそらく経験的にみて、これらの計算をしたり、 かみませんし、 ここで述べたような複雑な計算もおこない ができます。しかし fgrep の場合には、最後の 1 文字し しないことか分かるのです。そのため、 5 文字すらすこと かっているので、 ca と並んでいる 2 ~ 3 文字目とは一致 もっと進めることができます。 a の前に c がないことが分 と合わせたくなるかもしれません。しかし、この場合には すでに一致している a を 2 文字すらして 3 文字目の a す。末尾の a には一致して次の c で不一致となった場合、 まだ 1 文字も一致していないのですから 1 文字すらせま という引・算が可能です。末尾の a で不一致がみつかれは、 98 dl sp md2 tp kwset->delta; kwset—>target 十 1en; kwset—>mind2 ; text 十 1en; sp を、照合文字列のすぐ後ろを指すように設定してい ます。これにより、 gc への代入のように sp[-2] が照合 文字列の後ろから 2 文字目を指すようになります。 tp は 照合対象となるテキストの、現在注目している点を指して います。 実際のメインループは条件文のなかです。これは、ルー プの最中に、 tp か調べる範囲を超えてしまわないように するためです。ループのなかで調べると、条件文を実行す るだけのよけいな日がかかってしまうので、あえてタ材則 て検査しています。プログラムを高速化するには、このよ うにループ内でおこなう処理をできるだけループの外側に 追い出すことか重要です。 if (size > 12 * len) / * 11 is not a bug, the initial offset happens 0 Ⅱ ly once . * / for ()p = text 十 size while ()p く = ep) さらに、ルーフ。が安全に調べられる範囲を示す ep を初 期化しています。 11 * 1 en ; ; ) UNIX MAGAZINE 2000.4

kwsincr によりキーワード集合に追加します ( 誌面の都合 do beg = pattern; 上て折り返しています。以下扣犲兼 ) 。 for (lim = beg; lim く pattern + size while (beg く pattern 十 size) ; beg = lim; 十十 lim ; if (1im く pattern 十 size) fatal(err, 0 ) ; lim ー beg) ) ! = の if ( (err = kwsincr(kwset, beg, 最後に、 kwsprep を使って検索に必要な言算をあらか しめおこないます。 けておき、最後にこれらの条「Ⅱこ合っているかをもう一度謌ヾます。 2 パターンとして行本や単語を指定するのは大変なので、とりあえすみつ & & beg[len] ! = if (beg + len く buf + size - continue ; if (beg > buf & & beg[-l] ! = ' \ Ⅱ ) ) if (match—lines) len = kwsmatch. size [ 0 ] , とき、続いて行本に一致しているかどうかを調べます 2 。 場合には目的のパターンか存在したことになります。この これを見ても分かるように、 kwsexec が 0 以外を返す return 0 ; buf + size ー beg, &kwsmatch) ) ) if ( ! (beg = kwsexec(kwset, beg, for (beg = buf ; beg く = buf + size; + + beg) おこなっています。 返します。しかし、実際の処理は kwsexec という関数で ンを検索し、みつけた頁の文字の位置を示すアドレスを す。具イ勺な処理は、バッフアのなかで指定されたパター どこまで上交したのかを返すためのアドレス引数の 3 つで オ褓内されたバッフアのう曰頁アドレス、バッフアの大きさ、 こで紹介しておきます。 Fexecute の引数は、テキストが このあとに記述されている Fexecute についても、 fatal(err, 0 ) ; if ( (err = kwsprep(kwset) ) ! = 0 ) 96 continue ; goto success ; 単語単位で一致しているかどうかを調べるのもこの関数 else if (match—words) for (try = beg; len & & try;) 域を短くして再度検索をおこない、ループの : 頁に戻りま ンが一致する可能性があります。そこで、上交に用いる領 直後に単語としての文字がある場合は、より短いパター break; if (try > buf & & WCHAR((unsigned char) try[-l] ) ) がないかを検索します。 ループに戻り、現在の位置よりも後ろで対応するパターン ていないことになります。その場合は break して最初の の一部として使われるものであれは、単語として検索でき 使われる文字かどうかで調べています。直前の文字も単語 こでは、マッチした範囲の前後が単語の一部として す。 WCHAR( (unsigned char) try C1en] ) ) if (try + Ien く buf + size & & try 1en else kwsexec(kwset , beg, —len , &kwsmatch) ; kwsmatch. size [ 0 ] ; goto success; goto success; UNIX MAGAZINE 2000.4 十十 end ; (buf + size) (beg + len))) ! = 0 ) if ( (end = memchr(beg 十 len, ' \ Ⅱ ) , - St1CCeSS : したり、値を返すための引数に代入したりします。 頭と末尾をそれぞれ beg と end に入 return 文で返 パターンをみつけた場合には、それがみつかった行の先 みつけられなかったことを報告します。 これらの条件に一 -- 一致しなければ、 0 を返してパターンが return 0 ;