特集・プログラミング入門 Knuth•Morris•Pratt 前節の 2 番目の文字列探索プログラムをみれは分かるよ うに、文字列を探索している最中に文字列を逆向きに走査 することがあります。これがあるために引算量が 0 ( れ m ) となってしまうのですから、この逆向きの走査をおこなわ ないようにすれば、〇 ( れ ) で探索することが可能なはすで す。 文字列探索の理言勺な角斤の結果、れ十 m の手間での 探索カゞ可能と考えられました。これをもとに Knuth と pratt が考案したのが、これから紹介するアルゴリズムで す。角斤により、実際に必要な上は交回数は 2 ( れ + m) 以 下であることが分かっています。 一方、 Morris は逆向きの走査をなんとかして排除しよ うと努力した結果、同様なアルゴリズムにたどり着きまし た。たとえは、テープにオ内されている文字列から探索文 字列をみつけだす場合を考えてみてください。テーフ上に 記録された文字を前に向かって読み出す処理は高速におこ なえますが、一度逆戻りしてしまうとテープ自身の進行方 向を変えなけれはならす、処理に時間がかかってしまい ます。このような間題の発生を避けるために、逆戻りせ すにすむ探去を求めていたのです 1 。考案者の Knuth 、 Morris 、 pratt の頭文字を取って、このアルゴリズムを KMP 法と呼びます。 もっとも顕著な例を示すことで、このアルゴリズムの要 " という同じ文字列が を紹介しましよう。 abcdabcd. 連続する文字列から、探索文字列、、 abcde" を探索する場 合を考えてみます。 : 頁から上交をおこなっていくと、 5 文字目 ( 文字列では a 、探索文字列では e) に達したとき に初めて不一致が生します ( 図 1 ) 。 これまでの去であれば、今度は文字列の 2 文字目、探 索文字列の 1 文字目から探索を続けることになります。 こで、すでに一致している文字列に注目します。この文字 列のなかには探索文字列の先頭の文字と一致する可能生の ある文字、つまり a は先頭にしかありません。したがっ て、、、 bcd" と一致した部分は次の検査で上交する必要が 1 いまでは、テープなど見たことすらない人のはうが多いかもしれません。 昔はハードディスクの容量が小さかったため、大容量のデータを保存する ときはテープを利用していました。もちろん、テープに保存されたデータ 90 を杉きすることもしはしばでした。 図 1 不一致が発生した本好・ a b c d a b a b c d e 図 2 探索を再開する様子 a b c d a b c c c 図 3 不一致が発生した本好 ( 2 ) a b a b a b a a b a b e 図 4 探索を再開する本好・ ( 2 ) a b a b a b a a b a b e ないのです。ここに風がつけば、 d d d b b a a e a a 次の検査は現在注目して いる点から再開することができます ( 図 2 ) 。 こうすることで、文字列を指すポインタを逆戻りさせる ことなく探索を続けられます。 もう 1 つ、図 3 の例を見てください。今度は、 ab カ嗹 続している文字列のなかから、、 ababe" という文字列を探 索しています。 この場合も、不一致が発生するのは 5 文字目になりま す。しかしさきはどの例とは異なり、 5 文字目を探索文 : 列のう頁とすることはできません。探索文字列の 3 文字目 に a 、 4 文字目に b があるため、それらと一致する可能性 があるからです。この場合には、図 4 のような位置から探 索を続けなけれはなりません。 ここで注意してほしいのは、探索を再開するのは 5 文字 目からで、 3 文字目ではない点です。すでに、 : 頁から 4 文字目までは abab であることが分かっています。すなわ ち、 3 文字目と 4 文字目は探索文字列の頁の 2 文字と一 致することが分かっているので、探索は 5 文字目から再開 すれはよいのです。このようにすることで、不一致をみつ UNIX MAGAZINE 2003.5

特集・プログラミング入門 り返します。もう文字列か残っていないという状態になっ たときには、目自勺の探索文字列が含まれなかったことにな るため、文字列が存雀しないことを示す一 1 を返します。 while (i く = tlen) { if (hs (t) return 」 ; ()t + ASIZE * PRIME * b) % PRIME; ()t * ASIZE + t [ i + + ] ) ht return ー 1 ; % PRIME; ハッシュ値の更新においては、すでに計算してあるハ ッシュ値から、ハッシュ値の引算に関与・しなくなる先頭 の文字 ( 新 ) による景彡響をなくすために減算し、全体を ASIZE 倍したあとに新たな末尾の文字 (t[i]) の景斧加 えるために加算しています。 最初の行の計算で ASIZE x PRIME を加えているの は、その直後の減算により全体が負の数になってしまうの を避けるためです。残念ながら、負の数の値に対する剰余 演算の結果が正の数になる処理系と負の数になる処理系が あるため、どちらの処理系でも正しく動作するようによけ いな値を加えています。ここで加えた値は、最後に剰余演 算によって消えてしまうので、この値を加えたためにおか しくなるようなことはありません。 こで作成したプログラムは、 0 ( m 十れ ) で動作しま す。ところが、厳密にはこのプログラムは正しくありませ ん。というのも、ハッシュ値カ尊しい場合に文字列が一一致 していると判断していますが、これはかならずしも真では ありません 、で 1 ・算しているのはあくまでハッシュ値 ですから、ハッシュの衝突か起きる場合もあります。その ため、実際にはハッシュ値か等しいときにかならす文字列 自身の上交をおこなう必要があります。文字列の上師交をお こなって等しいときにのみ、探索文字列を検出したとする のです。 ノ、ツシュ値カ尊しいときに文字列を石忍するコードを付 けると、最悪の場合の引算量は 0 ( m れ ) となってしまいま す。これは、すべての部分文字列のハッシュ値か 1 司し値に なった場合を考えてみれは分かると思います。すべての部 分文字列を調べるために広そのそれぞれについて文字列 自身か等しいかどうかを調べるために m の手間がかかる ので、けっきよく 0 ( れ m ) となってしまいます。しかし実 98 際には、さきはども述べたように PRIME を大きな値に できるため、ハッシュの衝突はほとんど発生しないように することができます。したがって、実用的には 0 ( rn 十れ ) と考えても間題はありません。 実際のプログラミングにあたって これまでみてきたように、同じ問題を鮹夬するにも複数 の去があります。実際に間題を解決するためには何をす れはよいのでしようか。最初にやるべきことは間題の整理 問題の整理と分析 ーロに探索といっても、前回までにとりあげた、ある データ集合のなかから単一のデータを探しだす方法と、今 回紹介した文字列のなかから探索文字列を探しだす方法で は、利用するアルゴリズムか異なります。文字列のなかか らある探索文字列を探しだすために普通の探索のアルゴリ ズムを使おうとすれは、探索文字列の長さ倍の領域や時間 がかかるでしよう。 というのも、通常のでは、要素がキーの値と等しい かどうかは 1 回の上交で判定できるという前提て考えて きました。しかし文字列探索の場合には、それぞれの文字 の上交に対して手間を言算します。単純に考えても、上交 のために探索文字列の長さ倍の手間がかかってしまうはす です。 領域についても同様です。文字列として捉えれば途中の どこから始まっても同しだということが分かりますが、通 常の探索ではそれぞれのデータが独立して存在しているも のと仮定しています。すると、なえられた文字列から取り 出すことが可能な探索文字列と同じ長さのすべての文字列 か存在するものとして処理を進めることになるでしよう。 この場合には、領域カ甘架索文字列の長さ倍必要になってし まうわけです。 間題を分析して、どのような処理が可能かを検詞するこ とも重要になります。探索が必要となる場面は、これまで みてきたようなデータの探索や文字列架索といった基本 的な問題だけとはかぎりません。一見すると、もっと複雑 にみえるような間題の場合もあります。 たとえは、 DNA のなかから特定の遺伝子の部分を抽出 UNIX MAGAZINE 2003.5

特集プログラミング入門 トされて 1 となります。これは、いま注目しているところ が、 : 頁から 1 文字ぶんと等しいことを表しています。さ らに for まて戻って i がインクリメントされて、 3 文字目 の b に注目することになります。 ループのう頁で next[3] は 1 になります。これも内側 のループの条件は真とはなりません。 s[i] と s[j] 、つまり 3 文字目と 1 文字目が両方とも b だからです。けっきょ く、 j は 2 となりループは終了です。 4 文字目の e を処理する際、 next[4] は 2 になります が、今回は内側のループの条件が真になります。ます j が next[j], つまり 0 となります。この状態でもまだ条件は 真なので、今度は j が next[o] の一 1 になり、ループカ鮗 了します。 このようにして言算した next 配列があると、文字列を 探索する関数は次のようになります。 search(char *t, char *S) int int tlen, slen; int i , 」 ; 図 5 不一致か発生した好 ( 3 ) 図 6 探索をする第・ ( 3 ) a b a d a b a a b a b e a 図 7 a b a d a b a a b a b e 探索を再開する本好・ ( 4 ) b a d a b a a b a d d b d a a e a t1en strlen(t) ; strlen(s) ; while (i く tlen) { while ()j > = 0 ) & & j = next[j]; (t Ci] 十十 ; ret urn return ー 1 ; slen) 1 この関数では、 i は文字列のインデックスとして、 j は 探索文字列のインデックスとして用いています。外側の while ループは、文字列すべてを検査するためのもので、 i を 0 から始めて、インクリメントしながらループをまわ ります。 ループの本体には、さきはど next 配列を作成するとき に使ったのと同じような while ルーフ。があります。いま、 文字列の注目している文字カ甘架索文字列の注目している文 字と等しければ、文字列と探索文字列の両方をさきに進め 92 て同し処理をします。間題は等しくなかった場合です。 の場合には、 next 配列にオ内されている値にもとづき、探 索文字列のインデックスである j を変更して、再度上交を おこないます。探索文字列のインデックスを変更してもう まく一致するものかみつからない場合には、最終的に j の 値が一 1 となるので、ループを抜け、文字列の次の文字を 探索文字列のう頁から上交しなおすことになります。 KMP 法の改良 これで KMP 法を実現するプログラムを作成できます が、 next 配列の作成方法を工夫すればすこし改良するこ ここて紹介してお とができます。この改良は簡単なので、 きましよう。探索文字列が ababe のとき、その 3 文字目 で不一致を検出した場合を考えてみます ( 図 5 ) 。 これまでの方法では、 next は 1 となっているので、探 索文字列の 1 文字目から探索を再開することになります ( 図 6 ) 。ところが、この上交がうまくいかないことは明ら かです。というのも、上交に失敗した探索文字列の 3 文字 目と、今回上交しようとする探索文字列の 1 文字目は、ど ちらも同し b ですから、 3 文字目で上交が失敗しているの に、 1 文字目で成功するはずはありません。けっきよく、 さらに next をたどって一 1 となり、文字列の次の文字に 進むことになります ( 図 7 ) 。 UNIX MAGAZINE 2003.5

プログラ第ング入門 今泉貴史 アルゴリズムとデ - タ構造の基礎知識一文字列探索 前号まで、 3 回にわたって孑架索アルゴリズムについて説 明してきました。ーロに探索アルゴリズムといってもさま ざまなものがあり、それぞれに得手不得手があります。ア ルゴリズムを適用するときには、扱う問題をよく考え、適 切なものを選ぶことか重要です。 今月も、引き続き探索の間題をとりあげたいと思いま す。ただし、今回はすこし状況が限定されている探索問 題を扱います。ある文字列と探索文字列が与・えられたとき に、文字列のなかに探索文字列か存在するかどうか、存在 する場合にはどこにあるかをヾるアルゴリズムについて みていきましよう。 力すくの探索法 最初に間題を整理しておきましよう。長されの文字列 と長さ rn の探索文字列が与えられ > rn であるとしま す。このとき、文字列から探索文字列か含まれる部分をみ つけだすことが目標となります。いすれの文字列にも、任 意のアルファベットカ硬えるものとします。 たとえはテキストエデイタを考えてみてください。通 常、テキストエデイタには文字列の検索機能があります。 この場合、編集している内容のなかから指定された文字列 か存在する位置をみつけなければなりません。今回扱うの は、このような状況てす。 もっとも単純なアルゴリズムは、文字列のすべての位 置から、探索文字列と一 - 一致しているかどうかを調べるもの 88 でしよう。この素朴なアルゴリズムを実現するプログラム は、たとえは次のようになります。 int search(char *t , char *S) int i , j ; int 1en ; strlen(t) strlen(s) ; len 0 ; i く = len; i + + ) { for (i for (j if (t[i + j] ! = s[j]) break; if (sCj] return 土 ; return ー 1 ; 第 1 引数が文字列全体を指し、第 2 引数カ甘架索文字列 を指しています。外側の for ループで文字列全体に関する ループを作り、内側のループでは探索文字列に関するルー プを作りながら、すべての文字が一致するかを調べていま す。内側のループを実行しているあいだに一致しないこと が分かればループを抜けます。したがって、ルーフ。のあと で s[j] がヌル文字を指していれば、探索文字列すべてが -- - ・ 致したことになります。この場合、そのイ立置に探索文字列 があることになるので、その可立置を示す i の値を返し ます。文字列全体について調べても一致する文字列がみつ からなかった場合には、探索文字列か存在しないことを示 す一 1 を返します。 UNIX MAGAZINE 2003.5

特集・プログラミング入門 なお、この処理をおこなう際に、探索文字列の末尾の文 字に対する引・算はしていません。もし探索文字列の末尾の 文字を調べているときに不一致が発生するのであれは、 の文字ではないことは明らかです。ほかの場所で不一致が 発生した場合も、探索文字列の末尾の文字を不一致の発生 した位置に移動する必要はありません。移動しなけれはな らないのは、不一致が発生した場所よりも左側にある探索 文字列内の文字だからです。このように、末尾の文字を考 慮する必要はないため、 skip 配列の言算には含まれていま せん。 不一致を検出したときは、この配列を使って、探索文字 列をどれだけ進めてよいのかを匐十ヾます。この配列に↑巒内 されている値は、探索文字列の末尾の文字を十ヾていて不 一致が発生したときにどれだけ動かしてよいかを表してい るので、実際に移動する際には、末尾から何文字目を処理 している状態なのかを考慮に入れたうえで移動する必要が あります。このために作った関数は次のようなものです。 search(char *t , char *s) int 図 9 同じ文字か複数回出現する場合 a 図 10 a 図 11 a b a b a a e a b b a e i をインクリメントした場合 b a b a a a b b 2 文字進めた場合 b a b a a a b e a e b d d e d a a a a e int i , j ; int tlen, slen; tlen = strlen(t) ; strlen(s) ; slen 1 while (i く = tlen for (j SIen if (j くの return i ; slen) 1 ; j > = 0 return ー 1 ; if (skip[(int)t[i + j]] く 十十・ else i + = skip[(int)t[i + j] & & sCj] (slen ー 1 slen ー j) この関数では、 i は文字列のインデックスとして、 j は 探索文字列のインデックスとして利用しています。ます、 i を文字列のう巨頁に設定し、探索文字列の末尾から調べる ために j を slen—l から 0 になるまでデクリメントしな がら繰り返します。ここでチェックするのは文字列の一 分と探索文字列が -- ー・致していることです。もし、探索文字 列のすべてが・一致していれは、内側のループを終えたとき UNIX MAGAZINE 2003.5 に j の値は負の数になるはすです。この場合には、一致し た文字列の地可立置を表す i の値を返します。 不一致が発生した場合にも内側のループを終了します。 このとき、 j の値は 0 以 E で、不一致が発生した文字は探 索文字列側が s[j] 、文字列側が t[i + j] となります。 こで、文字列側の不一致文字に対応する skip 配列の値が slen—j よりも小さい、つまり skip 配列に登録されてい る値を言 fr 算するために利用した文字か不一致文字よりも右 側にある場合には、たんに i をインクリメントします。そ れ以外の場合、つまり skip 配列に登録されている値を計 算するために利用した文字か不一致文字よりも左側にあれ は、その文字のところまですらすために skip 配列の値を i に加えます。 skip 配列に登録されている値を計算するために利用し た文字か不一致文字よりも右側にある場合、実際には 1 文 字より多く移動させられる場合があります。図 9 の例を見 てください。 不一致が発生している文字列の文字は a です。この探 索文字列では、 skip 「 a'] は 1 となっています。これは注 目点よりも右にある文字 a に対して引・算された値です。 の場合、さきほどのプログラムでは i をインクリメントし ているので、次の探索の様子は図 10 のようになります。 しかし、文字 a は探索文字列の注目点よりも 2 文字左 まで存在しないので、実際には 2 文字進めることができま 95

特集・プログラミング入門 殞則のループでは文字列全体に対してルーフすると述べ ましたが、実際には文字列の長さから探索文字列の長さを 引いたぶんまでをループしています。う可立置がこれより も後ろになると、探索文字列の長さぶんの文字か残ってい ないため、この部分には探索文字列カ唸まれないことか明 らかだからです。もちろん、文字列の長さすべてについて 探索を実行してもかまいませんが、ありえない場合を幇餘 することで無駄な処理をおこなわないようにしています。 それでは、このアルゴリズムの計算量を考えてみましょ う。、、最悪の場合 " は、すべての位置から探索文字列の長 さぶん上交をおこなう場合です。ただし、、、すべての位置 から " といってもれではありません。末尾の rn に満たな い部分は調べないので、れ一 rn 十 1 通りあることになり ます。そして、探索文字列の長さは m ですから、 rn(n ー m 十 1 ) 回程度の上師交が必要になります。通常、文字列の 探索をおこなう場合にはれにくらべて m は十分小さいと 考えてよいので、けっきよく 0 ( れ m ) となります。 この最悪の場合となるような入力は、探索文字列とつね に一致しつつ、最後の文字でかならず異なってしまうとい う場合です。つまり、文字列は単一の文字か連続したもの であり、探索文字列としては単一の文字カ里続し、その後 ろに別の文字が付いたものが与えられた場合になります。 たとえば、 文字列 : 00000000000000000000000000000000000 探索文字列 : 00001 などと指定された場合か最悪の入力であり、その手間は上 て言算したような値になります。 さきはどのプログラムは、アルゴリズムをそのままプロ グラムに変換したものなので、すこし工夫すればアルゴリ ズムを変えすにプログラムを高速化することができます。 最悪の入力を考えると、内側のループを毎回佃度も実行す ることはありますが、はとんどの場合には麪頁の文字の比 較のみで一致しないことか判明すると思います。そこで、 探索文字列の地頁文字をあらかしめ取り出しておいて、そ の文字だけは特別に上交をおこない、それか等しいときに 限って探索文字列の 2 文字目以降をヾるというガ去が使 えます。 また、線幵架索を高速化するために使われる番兵の手法 こでも利用できます。たとえば、文字列の後ろに探 は、 UNIX MAGAZIN E 2003.5 索文字列を連結しておけは、探索はかならすそこで成功す るわけですから、文字列の長さを調べる必要はなくなりま す。逆に、探索文字列の後ろにどの文字とも一致しない文 字 ( 文字列に出現しない文字 ) を加え、文字列と探索文字 列との比較がかならずその文字で失敗するようにしておく こともできます。この場合には、上交が失敗したときにそ れまでに成功していた上交の回数か、探索が失敗したとき に調べていた探索文字列内の文字を確認することで、探索 文字列のすべてが含まれているかどうかカ吩かります。 ただし、実際にプログラムを作成してみたところ、番兵 として末尾に探索文字列を追加するガ去を用いたバージョ ンでは、それほど高速化されませんでした。というのも、 文字列の末尾に新たに文字を追加しなければならないの で、末尾をみつけるために ) 巨頁から順に 1 文字すっチェッ クする必要があるからです。この作業にかかる手間が番兵 を利用することで省ける手間とくらべて小さくないため、 さはど高速化にはつながらなかったわけです。文字列の末 尾がすぐに分かるような場合には有効なのですが、そうで ない場合には注意して用いる必要があります。 また、無理に 2 重ループを作らなくても、ループの内部 でおこなう更新処理を工夫すれば、 1 重のループ構造とす while (t Ci] ! = ) \ 0 , ) { int i , j ; search(char *t , char *s) int ることもできます。 if (t [i] if (s[j] } else { return ー 1 ; , \ 0 ' ) return i ただし、ループが 1 重になったからといって、計算量 も 0 ( れ rn ) からたとえは〇 ( れ ) に下がるわけではありませ ん。あくまでもループのまわし方を変えただけであって、 最悪の場合に 0 ( れ m ) の手間がかかるのは同しです。 89

特集・プログラミング入門 いのて探索文字列の長さぶんだけ進めることができます。 次の上交は文字 c で、これは一致しますから、その左の文 字を比較することになります。ここでは不一致が発生しま す。このとき、不一致の E{ した文字である a は探索文字 列の左側にあるため、探索文字列に含まれるもっとも右の a か現在注目している位置にくるように探索文字列を移動 します。この例では、探索文字列が 1 文字ぶん右へ移動す ることになります。 さらに探索文字列の末尾を上交すると、今度も不一一致が 発生します。不一一致の発生した文字はやはり a ですが、今 度は 2 文字ふ、ん探索文字列を移動することになります。す ると、ちょうど目的の探索文等冽と -- ーー・致する部分になるた め、 c 、 b 、 a と 3 文字を上交することて探索文字列か文字 列に含まれていることが分かります。 BM 法のポイントは、文字列探索においては探索文字列 に含まれない文字が多数存在するという点です。文字列の 探索をおこなっていく際に、最初の文字を上交したときに それか探索文字列に含まれないものであれは、一気に探索 文字列ぶんを進めてしまうことができます。多くの場合に 探索文字列ぶんを進めることができるのであれは、探索に かかる手間はれ + m となるのです。 BM 法で窈架索にかかる手間は、最悪の場合を考えると アルゴリズムの引・算量としては力すくの探索 1 去と変わらな い 0 ( れ m ) です。しかし、上記のように多くの場合には れ + rn の手間で探索をおこなうことができます。一般的 には、探索文字列カ張けれは長いほど BM 法による探索 は高速になります。前述の KMP 法とくらべても、実際に はある程度の長さ ( 5 文字程度 ) 以 E の探索文字列であれ は、 BM 法を用いるはうか効率がよいといわれています。 それでは、この BM 法を実現するプログラムをみてみ ましよう。 KMP 法では、不一致を発見したときにそれが 探索文字列の何文字目なのかにもとづいてどこから探索を 再開したらよいかを示す next 配列を計算しました。今度 は、どの文字が不一致文字となったかによってどれだけ進 めてよいのかを表す skip 配列を準備することになります。 さきほどの abc という探索文字列の場合、 a は 2 、 b は 1 、それ以外はすべて 3 となっている配列を準備します。 BM 法の実現 94 この配列を作成するのは簡単です。最初に配列自身を宣 言する必要がありますが、今回は文字列として 8 ビットの 文字すべてを考えましよう。そのため、配列のサイズとし ては 256 ( 28 ) を用います。 #define ASIZE 256 int VOid skip [ASIZE] ; search—sub(char *s) i nt i nt 1en len; strlen(s) ; for (i = 0 ; i く ASIZE; i + + ) skip [i] 1e ; for (i = 0 ; i く 1en ー 1 ; skip[(int)s[i]] len 1 ます、配列のすべての要素を文字列の長さに設定しま す。つまり、ほとんどの場合には文字列の長さぶんを進め ることができるわけです。このあと、探索文字列に使われ ている文字について特別な処理をおこないます。 特別な処理といっても、しつはたいした処理ではありま せん。探索文字列の i 文字目にその文字があれは、、、探索 文字列の長さー i ー 1 " を skip 配列に↑褓内すればよいの です。 探索文字列に同し文字が 2 つあったときには、右側の 文字に対して言算した値をイ褓内します。右側の文字と左側 の文字とでは、右側の文字に対する値のほうか移動する量 が少なくなります。左側の文字に対して引・算した値を採用 すると、本当は - ーー - - 数するかもしれない場所を通り越して移 動してしまう可能性があります。そのため、もっとも右に ある文字に対して計算した値を skip 配列にオ褓内するよう にします。 このために、探索文字列の : 頁から、すべての文字につ いて順番に値を計算し、 skip 配列にオ褓内しています。同 じ文字が複数存在する場合、最初は左側にある文字に対す る値かオ褓内されますが、あとから右側にある文字に対して 引算した値かオ褓内されるため、すべての計算カ鮗了したあ とは一 - 一番右にある文字に対する値かオ褓内されていることに なります。 UNIX MAGAZINE 2003.5

特集・プログラミング入門 表 2 改良した next 配列 next [ i] 図 8 BM 法による探索 a b d b a b C a C a b C a b d b a b a C C a b C a b d b a b a C C a b C a b d b a b a C C a b C a b d b a b a C C a b C ・ 1 一 0 1 ワ 1 つけ -4 0 0 2 このような場合は、探索文字列だけを詩ヾることでみつ けだすようにできます。さきほどの関数を使って next を 言 t 算するときに、探索文字列の j 番目と i 番目カ尊しい場 合はたんに j の値を代入するのではなく、 next[j] の値を 代入することにすれはよいのです。現在注目している点よ りも前の next の値はすでに計算されているため、このよ うに変更するだけでこの改良を実現できます。 next を計 算する関数の改良バージョンを以下に示します。 void search—sub(char *S) int i , j ; int 1en; strlen(s) ; len 1 next [ 0 ] while (i く le 取 ) { while ()j > = 0 ) & & (s Ci] j = nextCj]; next [i] else next [i] next Cj ] ; 効率的な文字列の探索を実現しました。 これとは異なる方 法で文字列探索の高速化を実現したのが Boyer と Moore です。 このガ去では、探索文字列を右から左に向かって詩・ヾる ことで、文字列と一致するかどうかを検査します。不一致 を発見した場合、不一致の原因となった文字列の文字を調 べます。もしこの文字か探索文字列に含まれないものであ れば、現在注目している文字列の文字は探索文字と一致す る可能性がないため、探索文字列の : 頁か注目している文 字の右にくるまで移動してから、探索を継続することがで きます。また、不一致が発生した文字列の文字カ甘架索文字 列の注目点よりも左にある場合は、その文字と不一致文字 が一致する点まで進めることが可能です。このアルゴリズ ムも KMP 法と同様、考案者の頭文字を取って BM 法と 呼はれます。 図 8 の例を見てください。これは、 BM 法を用いて ・という文字列から、、 abc " という探索文 abdbacabc. 字列を探索している様子です。 最初の上交は、地頁を揃えた状態で探索文字列の末尾の 文字を上交します。ここで不一致が発生しますが、不一致 KMP 法では、文字列をう頁から順番にみていくことで が盟 [ した文字は d であり、これは探索文字列に含まれな j の値が負の数のときに配列の中身を参照してしまわな いように、ルーフ。の最後で next の値を代入するかたちに 変更しているので、プログラムの形式がすこし変わってい ますが、 i 番目の文字と j 番目の文字を上交してこれらが 等しいときには next[j] の値を使うように変更しているの が分かると思います。この関数を使って ababe に対する next 配列を計算すると、表 2 のようになります。 Boyer•Moore 93 UNIX MAGAZINE 2003.5

特集・プログラミング入門 表 1 next 配列 next[i] は、 aba の後ろのはうの a と上交することになります。 この next 配列は、たとえば次のようなコードで作成す ることができます。 VOid search-sub(char *s) ・ 1 0 一 -1 っ 4 っ 4 0 一 0 一 -1 2 int i , j ; int 1en; けたときに逆戻りするのではなく、そこからさきを調べる ようにできます。つまり、文字列をひととおり調べるだけ で探索がおこなえるわけです。 このような探索を実現するには、それぞれの局面におい て、何文字すらしてどこから探索を酌刑したらよいのかを 言算しなけ川まなりません。入力の文字列はどのようなも のが与・えられるか分からないはかりか、長さにも制限がな いので、そのすべてに対してなんらかの値を引算すること この関数には、引数として探索文字列を渡します。 next は不可能だと考えなければなりません。しかし安じ、してく [ 0 ] を一 1 にしたあと、何文字目をみるかを表す変数 j を ださい 、て朝 1 ・算しておかなければならない値は、探索 インクリメントします。 next 配列の次の要素を言算する 文字列が分かれは訣定できます。なぜなら、そこまでに ときには、直前に検査した文字の次の文字と等しいかを調 致している文字列は、探索文字列の : 頁部分文字列になる べます。 わけですから、探索文字列のみから言 t 算できるのです。 これだけでは、ちょっと分かりにくいかもしれません ね。さきほどの ababe という探索文字列を使って、実際 に next 配列を言算してみましよう。 j を一 1 にしたあと、 今回は、、、 ababe" という探索文字列に対し、表 1 のよ i を添字として探索文字列すべてに関するループを開始し うな配列を準備して探索をおこないます。 ます。ループの本体では、ます next 回に一 1 を代入しま この配列は、 i 文字目のチェックをしていて不一致がみ す。内側の while ループは、まだ j が一 1 なので、 i が 0 つかったときに、何文字目からチェックを再開するかを表 の状態では実行されません。 j がインクリメントされて 0 しています。 C 言語をベースに考えているので、文字列は となり、 for まで戻って i がインクリメントされて 1 文字 0 文字目から数えています。 目の b に注目することになります。 探索文字列の 0 文字目を調べているときに不一致がみつ next[l] を 0 にしたあと、内側のループに入ります。 j かった場合、値は一 1 となっています。これは文字列のほ は 0 で、前半の条件は成立しています。 s[i] と s[j] 、つま うを 1 文字進めて、探索文字列の 0 文字目から再度上交 り 1 文字目と 0 文字目は異なっているので、ルーフの本 をおこなうことを表しています。 体を実行します。ルーフ本体では、 j を next[i] 、つまり 1 文字目と 2 文字目の場合、配列には 0 かオ褓内されて ー 1 に設定したところで while の条件が成立しなくなるの います。これはいま調べている文字を、そのまま探索文字 でルーフ。カ鮗了します。さらに j がインクリメントされて 列の 0 文字目と上交するという意味になります。 0 となり、 for まで戻って i がインクリメントされて 2 文 一方、 3 文字目と 4 文字目の場合は、配列にはそれぞ 字目の a に注目することになります。 れ 1 と 2 かイ絲されています。これは、 abab まで到達し next[2] を 0 にしたあと、内側のループではさきはどと たときに不一致を発見した、つまり aba までは一致して 異なり条負、が成立していません。 s[i] と slj] 、つまり 2 文 いることが分かっている場合には 1 文字目 ()b の b) と 字目と 0 文字目はともに a です。そのため、ルーフの本 上交し、 ababe まで達したときに不一致を発見した場合に 体を実行せすに後ろへ抜けます。そこで j がインクリメン strlen(s) ; 1en f or ( i = 0 ; i く len ; i + + ) { next [i] j = nextCj]; KMP 法の実現 91 UNIX MAGAZINE 2003.5

特集・プログラミング入門 す ( 図 11 ) 。 どのような場合にも最大の移重肋ゞおこなえるようにする には、探索文字列の何文字目まて処理したときかも考慮し ながら、それぞれの文字に対して skip の値を計算する必 要があります。さきほどの計算では、 skip は探索文字列の 長さぶんの領域が必要でしたが、この改良を施すと探索文 字列の長さの 2 乗ぶんの領域が必要になってしまいます。 そのため、探索文字列の右にある文字については、簡単に 1 文字すらすというガ去で対処しているわけです。 BM 法の改良 こまでに紹介してきた BM 法は、経験的には十分高 速に動作します。しかし、最悪の場合を考えると計算量は 0 ( れ m ) となり、力すくのガ去と変わらなくなってしまい ます。 BM 法を、最悪の場合の性能引正するようにした いと考えるのは自然なことでしよう。 BM 法においても、 KMP 法と同様に最悪の場合の手 間を抑えることができます。仕組みはいたって簡単です。 KMP 法の場合と同じように、不一致が発生したときにそ の時点まで一致していた文字列を利用して文字列を進める 量を計算すればよいのです。 たとえば、図 9 の場合には、すでに ae という文字列と 一致しています。この例では、 ae という文字列は探索文 字列の左側に存在しないため、探索文字列ぶん、つまり 5 文字すらすことができます。 しつは、このガ去は BM 法の完全版と呼ばれています。 Boyer や Moore も、 KMP 法で用いられる next 配列と 同様なものが B 法でも使えることは分かっていて、 skip 配列だけを用いた簡略版と、 skip 配列と next 酉改」を組み 合わせた完全版の両方を紹介しています。たしかに、完全 版を利用すれは 0 ( れ ) で処理をおこなえるようになりま す。しかし、一ヨ勺な入力て考えた場合、表を作成するた めのオーバーヘッドや、ループ内での処理かヤや複雑にな ることなどにより、かならすしも完全版のはうが速いわけ ではありません。実用上は簡略版だけで十分な結果か得ら れます。そのため、たんに BM 法と呼ぶときには、さき はど紹介した簡略版を指すこともあります。 図 8 では簡略版を用いていますが、同し例に対して完全 版を用いたときの様子は図 12 のようになります。 96 図 12 a a a 完全版 BM 法による探索 b d b a c a b c b d b a c a a b c b b C C 000000000 a b d a b b a C C a a b b C C もう 1 つ、これまでにとりあげたガ去とは基本的な考え 方が異なる方法を紹介しておきましよう。前号までの探索 間題では、要素を目的のキーと上交しながら探索するのが 普通でしたが、引算式を使ったハッシュというガ去もあり ました。文字列の探索においても、このハッシュをうまく 利用した方去があります。 考え方は簡単です。文字列のなかにある探索文字列の長 さぶんのすべての部分文字列に対してハッシュ値を計算 し、それカ甘架索文字列自身のハッシュ値と等しくなるかど うかを調べるのです。等しいハッシュ値になる部分文字列 がみつかれは、それは探索文字列と等しいとみなします。 この方法を採用する場合、間題となるのはそれぞれの部 分文字列のノ、ツシュ値を計算する手間です。この計算に 手間がかかるようでは、たんにすべての部分文字列と上交 したほうが高速だったという結果となりかねす、せつかく のアイデアも企画倒れに終ってしまいます。すべてのハッ シュ値を効率よく計算するために、ちょっと工夫をしてみ ましよう。簡略化のために、探索文字列は 4 文字としま す。このとき、たとえばハッシュ値は次のように引算する 図 8 の例よりも上は交回数が 1 回減っているのが分かり ます。 Rabin•Karp とします。 UNIX MAGAZINE 2003.5