Boyer-Mooreのアルゴリズム、略してBMアルゴリズムは、 KMPアルゴリズムよりもさらに高速。照合パターンがある程度以上(普通5文字以上くらい)の長さをもつ場合には、最も速い文字列照合アルゴリズムだと言われている。KMPアルゴリズムと同様、計算量は最悪の場合でも O(n) 。

BMアルゴリズムの長所は、テキスト中の文字の大部分を調べずにすむ可能性があること。素朴なアルゴリズムやKMPアルゴリズムでは、テキストの中の文字をそれぞれ1回は調べなければならない。比較は最低でも n 回になる。これに対して、BMアルゴリズムでは n/m 個(nはテキストの長さ、mは照合パターンの長さ)の文字とだけ比較すればよい。これによって、特に照合パターンが長いときに、計算時間の大幅な短縮が期待できる。

この特徴から、BMアルゴリズムは、実用上きわめて重要なアルゴリズムと見なされている。テキスト探索の使用頻度が高いだけにその価値は大きい。

BMアルゴリズムも、素朴なアルゴリズムと同様、テキストを左から順に調べていく。しかし、いったんテキスト上の位置がきまったら、照合パターンについては、逆に右から左に向かって調べる。照合パターンを逆向きに調べることがBMアルゴリズムの要点なのだ。もちろん、照合を進めるにあたっては、それ以前に行った比較の結果として得られた情報をできるだけ活用して、比較の回数を減らすように努める。これはKMPアルゴリズムと同様。

<関数名>
  bmMatch Boyer-Mooreによる文字列照合アルゴリズム
  bmSkip シフト表1の作成
  bmNext シフト表2の作成

<形式>
  文字列照合
    char *bmMatch(char *text, int len, char *pattern,
           int patlen, int *skip, int *next);

  シフト表1の作成
    int bmSkip(int *skip, int slen, char *pattern, int patlen);

  シフト表2の作成
    int bmNext(int *next, int nlen, char *pattern, int patlen);

<引数>
  文字列照合関数において
    text   (入力)テキスト
    len   (入力)テキストの長さ
    pattern (入力)照合パターン
    patlen  (入力)照合パターンの長さ
    skip   (入力)シフト表1
    next   (入力)シフト表2

  シフト表1の作成関数において
    skip   (入出力)シフト表1
    slen   (入力) skip配列の長さ
    pattern (入力) 照合パターン
    patlen  (入力) 照合パターンの長さ

  シフト表2の作成関数において
    next   (入出力)シフト表2
    nlen   (入力) next配列の長さ
    pattern (入力) 照合パターン
    patlen  (入力) 照合パターンの長さ

<関数値>
  文字列照合関数について
    照合パターンがテキストから見つかった場合はそのポインタ、
    見つからなかった場合は 0 (NULL)。

  シフト表1の作成関数について
    シフト表1を正常に作成できた場合は 0、失敗した場合は -1。

  シフト表2の作成関数について
    シフト表2を正常に作成できた場合は 0、失敗した場合は -1。

<注意事項>
  bmSkip()とbmNext() を呼び出してシフト表を作成した後、文字列照合関数 bmMatch() を利用すること。
  なお、漢字かな交じりの文字列照合にはこの関数では未対応。ご自分で修正すること。

用例

<関数本体>
  bmMatch.c

<説明>

Comments are closed.

Post Navigation