BM法についてわかりやすく解説（C言語サンプル付き）

SHARE

このページにはプロモーションが含まれています

今回は文字列検索アルゴリズムの１つである「ボイヤー – ムーア法」、略して BM 法について解説していきたいと思います。

結構 BM 法について解説されているウェブページや参考書も多いですが、BM 法の簡略版についての解説が多いようで、実は完全な BM 法について解説されていることは少ないです。

MEMO

簡略版というよりかは広義の BM 法といった方が良いかもしれないです

とりあえずこのページでは、必要に応じて BM 法を簡略版と完全版とで区別して呼び分けるようにさせていただきます

BM 法の簡略版でも十分高速な文字列検索を行えますし、実装する際に求められる BM 法も簡略版であることも多いかもしれませんが、このページでは簡略版だけでなく、完全版の BM 法についても解説していきたいと思います。

正直 BM 法の簡略版に関しては考え方も実装も簡単だと思います。それに対し、BM 法の完全版に関しては考え方も実装もややこしいです…。

特に考え方は文章で説明すると分かりにくくなってしまいますので、図を用いて補足しながらできるだけ分かりやすく解説していきたいと思います！

ちなみに BM 法の簡略版のソースコードは BM 法（簡略版）のサンプルプログラム で、BM 法の完全版のソースコードは BM 法（完全版）のサンプルプログラム で紹介していますので、すぐにソースコードが読みたい方はリンクをクリックしてスキップしていただければと思います。

MEMO

このページでは、テキスト（text）を検索先の文字列、パターン（pattern）を見つけ出す文字列として解説を行なっていきます

つまり、このページにおける文字列検索とは、”テキスト” の中から “パターン” を見つけ出す処理となります

力まかせ法の復習

結局 BM 法も、下記ページで紹介している “力まかせ法” を改良したアルゴリズムになります。ですので、BM 法を理解したり、実装したりするためには、まずは “力まかせ法” について理解しておいた方が良いと思います。

力まかせ法の解説ページアイキャッチ 力まかせ法（単純な文字列検索方法）について解説（C言語サンプル付き）

ただ、これに関しては後述で解説しますが、BM 法は「パターンの “後ろ側から” 文字の一致を確認していく」という特徴があります。

それに対し、上記ページで紹介している力まかせ法の解説やソースコードは「パターンの “前側から” 文字の一致を確認していく」ことを前提としたものになっています。

そのため、まずは力まかせ法をパターンの後ろ側から文字の一致の確認を行なっていく形式に変形した関数を紹介しておきたいと思います。

その関数が下記の forceSearch になります。引数で受け取った text の中から pattern を探し出す関数であり、text と pattern の文字数はそれぞれ text_len と pattern_len となります。text の中に pattern が存在する場合、pattern が存在する text 上の位置を返却し、text の中に pattern が存在しない場合は -1 を返却するようになっています。text と pattern ともに、位置は 0 から始まるものとしています。

また、text_pos はテキスト上の比較位置、pattern_pos はパターン上の比較位置となります。これらの比較位置をうまく移動させながら比較を行なっていくところが、文字列検索を実現する上でのポイントとなります。

力まかせ法(パターンの後ろから照合 
#include <stdlib.h>
#include <string.h> /* strlen */

#define MAX_PATTERN 256
#define MAX_TEXT 1024

int forceSearch(char text[], int text_len, char pattern[], int pattern_len) {
    int text_pos; /* テキストの比較位置 */
    int pattern_pos; /* パターンの比較位置*/

    /* パターンの比較位置を末尾にセット */
    pattern_pos = pattern_len - 1;

    /* テキストの比較位置をパターンの末尾の位置にセット */
    text_pos = pattern_len - 1;

    /* テキストの比較位置がテキストの最後を超えるまでループ */
    while (text_pos < text_len) {

        /* テキストの比較位置の文字とパターンの比較位置の文字が一致するかを判断 */
        if (text[text_pos] == pattern[pattern_pos]) {
            /* 一致した場合 */

            /* パターンの先頭の文字までテキストの文字が一致したかどうかを判断 */
            if (pattern_pos == 0) {
                /* パターンが存在するテキストの位置を返却 */
                return text_pos;
            }

            /* テキストとパターンの比較位置を１文字分前側に移動する */
            text_pos--;
            pattern_pos--;

        } else {
            /* 不一致した場合 */

            /* 次のテキストの比較位置を前回のテキストの比較開始位置の１つ後ろに移動 */
            text_pos += pattern_len - pattern_pos;

            /* パターンの比較位置を末尾に戻す */
            pattern_pos = pattern_len - 1;
            
        }
    }

    /* パターンが見つからなかった場合は-1を返却 */
    return -1;
}

int main(void) {
    char text[MAX_TEXT] =  "abceabcababceabcabc";
    char pattern[MAX_PATTERN] = "abceabcabc";
    int find;

    find = forceSearch(text, strlen(text), pattern, strlen(pattern));
    if (find != -1) {
        printf("パターンはテキストの第%d文字に存在します\n", find);
    } else {
        printf("パターンはテキスト内に存在しません...\n");
    }

    return 0;
}

文字の一致の確認をパターンの後ろ側から行うようになっているものの、基本は先ほど紹介したページで解説している力まかせ法と同じ考え方でパターンの検索を行なっています。

最初のテキストの比較位置（text_pos）とパターンの比較位置（patern_pos）はそれぞれ pattern_len - 1 となります。そして、比較した結果、文字が一致している場合は両方の比較位置を前側に移動させ、同様に比較を行なっていきます。

力まかせ法の説明図１

pattern_len 分の文字が連続して一致すれば、その一致した時点のテキストの比較位置（text_pos）がパターンが存在するテキストの位置となりますので、その比較位置を return で返却しています。

pattern_len 分の文字が一致する前に文字が不一致した場合、次はテキストの比較位置 text_pos を前回のテキストの比較開始位置から１文字分後ろにずらし、その位置から同様に比較を行なっていきます。この不一致した際のテキストの比較位置 text_pos の移動が、力まかせ法においても、後述で説明する BM 法においてもポイントになります。

また、不一致した場合の次のパターンの比較位置 pattern_pos は必ずパターンの末尾、すなわち pattern_len - 1 となります。

力まかせ法の説明図２

この、文字の不一致があった際に、次のテキストの比較位置 text_pos を前回のテキストの “比較開始位置” の１つ後ろ側に移動する処理が下記になります。

次回のテキスト比較位置の設定 
/* 次のテキストの比較位置を前回のテキストの比較開始位置の１つ後ろに移動 */
text_pos += pattern_len - pattern_pos;

text_pos はテキストの比較位置を表す変数ですので、それに足し算を行なっているということはテキストの比較位置 text_pos が後ろ側に移動するということになります。そして、その移動文字数が右辺の pattern_len - pattern_pos となります。

また、この処理は不一致が発生した際に実行されるのですから、text_pos は不一致が発生した際のテキストの比較位置であり、pattern_pos は不一致が発生した際のパターンの比較位置となります。

さらに、パターンの比較開始位置は毎回 pattern_len - 1 ですので、(pattern_len - 1) - pattern_pos は不一致が発生するまでに比較位置が移動した文字数を表すことになります。なので、text_pos += (pattern_len - 1) - pattern_pos を実行すれば、text_pos がテキストの比較開始位置に戻ることになります。

さらに、その text_pos を +1 すれば、text_pos が前回のテキストの比較開始位置の１つ後ろに移動することになります。そして、これらの計算を行うのが、上記の処理となります。

力まかせ法でtext_posを後ろに１つずらす様子

ちょっとややこしいですが、不一致が発生した際に text_pos に (pattern_len - 1) - pattern_pos を足せば、text_pos がテキストの比較を開始した位置に戻ることは頭に入れておくと良いと思います。

さて、力まかせ法においては、不一致が発生した際に text_pos は必ず前回のテキストの比較開始位置の１文字分後ろの位置に移動します。つまり、テキストの比較を開始する位置に注目すれば、不一致が発生した際には１文字分後ろに移動するのみです。

力まかせ法ではテキストの比較の開始位置が毎回１文字分後ろにずれるのみであることを示す図

それに対して BM 法においては、文字の不一致があった際に、テキストの比較を開始する位置を一度に複数文字数分移動させます。要は、その位置にパターンが存在しないと分かりきっている場合に、その位置での文字の比較をスキップするように text_pos を移動させます。

BM法ではテキストの比較の開始位置が複数文字分後ろにずれることを示す図

比較を開始する位置が一度に複数文字分後ろに移動することになるので、力まかせ法よりも高速に検索を行うことが可能です。

このような移動を実現するため、不一致時の text_pos の移動文字数は、BM 法（簡略版）においては、”パターンの文字列” と “不一致したテキストの文字” を考慮して決定します。

BM法で次のテキスト比較開始位置を求める際に考慮するデータを表す図

BM 法の簡略版においては上記のみを考慮して移動文字数を決定しますが、BM 法（完全版）においては、上記に加え、”パターンの文字列” 及び、不一致する前に “一致したパターンの文字列” も考慮して決定します。

BM法完全版で次のテキスト比較開始位置を求める際に考慮するデータを表す図

逆に言えば、検索実行時の処理において、力まかせ法と BM 法との違いは「不一致が発生した際のテキスト比較位置 text_pos の移動文字数」のみです。

ですので、検索実行時の処理としては、BM 法を実現するために力まかせ法から変更が必要になる処理は、不一致が発生した際の次のテキストの比較位置 text_pos を決定する下記部分のみとなります。

次回のテキスト比較開始位置の設定 
/* 次のテキストの比較開始位置を前回の比較位置の１つ後ろに移動 */
text_pos += pattern_len - pattern_pos;

ただし、検索実行時の処理として変更が必要になるのは上記部分のみですが、検索実行時に不一致時の text_pos の移動文字数を配列から取得できるよう、検索実行前に予め配列を作成しておくという前準備が必要になります。

BM 法（簡略版）の考え方

力まかせ法については理解していただけたでしょうか？

ここからは本題の BM 法について解説していきます。

まずは、BM 法の簡略版の考え方について解説していきます。

前述の通り、BM 法の特徴の１つはパターンの後ろ側から文字の一致の確認を行なっていく点にあります。

さらに、BM 法の簡略版においては、”パターンの文字列” と “不一致したテキストの文字” との関係からテキストの比較位置 text_pos の移動文字数を決定するという特徴があります。

分かりやすいのが、”不一致したテキストの文字” がパターン内に存在しないケースです。この場合、この不一致したテキストの文字は、当然ながら絶対に他のパターン内の文字とも一致しません。

不一致したテキストの文字がパターン内に存在しない様子

そのため、このテキストの文字を他のパターン内の文字と比較するのは無駄です。したがって、この場合はパターンの先頭の位置を不一致したテキストの文字の位置の１つ後ろに移動させることができます。

この移動は、テキストの位置 text_pos で考えると、text_pos をパターンの文字数 pattern_len だけ足すことによって実現できます。このようにテキストの比較位置 text_pos を後ろ側に移動してから比較を開始してもパターンの検索漏れは発生しません。

不一致したテキストの文字がパターン内に存在しない場合のtext_posの移動文字数を示す図

そのため、BM 法の簡略版では、文字の不一致が発生した際、不一致したテキストの文字がパターン内に存在しなければ text_pos += pattern_len を行ってテキストの比較位置を移動させます（不一致直後のパターンの比較位置は毎回 pattern_len - 1 となります）。

MEMO

ちょっと話が逸れるのですが、上の図を見て違和感を覚えた方もおられるのではないでしょうか？

上の図において、最初の比較において文字は一致しているわけですから、テキストの G の１つ後ろの文字は必ず F ということになります

ですので、不一致が発生した後に上図のようにテキストの比較位置 text_pos を移動させて比較を開始したとしても、絶対にこの位置にパターンは見つかりません

これは、最後の比較で文字 A と文字 F の比較が行われて必ず不一致が発生するからです

つまり、上の図のようにテキストの比較位置 text_pos を移動させてから比較を開始するのは無駄です

このような無駄な比較を行なってしまうのは、BM 法が簡略版であり、不一致が発生したテキストの文字のみを考慮しているからです

完全な BM 法においては、不一致が発生する前に比較を行なったテキストの文字も考慮してテキストの比較位置 text_pos を移動させるため、上記のような無駄な比較が起こらないようになります

では、上記のようなケースと異なり、不一致したテキストの文字がパターン内に存在する場合はどうすれば良いでしょうか？

この場合、それらの文字が同じ位置で比較されるようにテキストの比較位置を移動させれば、そこでパターンが見つかる可能性があります。

不一致したテキストの文字がパターン内に存在するため、他の位置でパターンが見つかる可能性があることを示す図

そのため、不一致したテキストの文字がパターン内に存在する場合、不一致したテキストの文字の位置にパターン内の同じ文字が移動するようにテキストの比較位置を移動させ、比較を行なっていく必要があります。

具体的には、不一致が発生した際に、テキストの比較位置 text_pos を pattern_len - 1 - パターン内の同じ文字の位置 だけ移動させてから、次のテキストの比較を開始することになります。 

不一致したテキストの文字とパターン内のその文字の位置が重なるようにtext_posを移動させる様子

基本は上記に従って不一致時にテキストの比較位置 text_pos を設定すれば良いのですが「不一致したテキストの文字と同じ文字がパターン内に複数存在する場合」は注意が必要です。この場合は、パターン内のより後ろ側の位置の文字と不一致したテキストの文字が同じ位置に来るようにテキストの比較位置を移動させます。

テキストの不一致した文字と同じ文字がパターン内に複数存在する場合のtext_posの移動文字数を示す図

このような場合、パターンと完全に一致する可能性のある “テキストの比較の開始位置” が複数存在することになります。パターン内の前側の位置に合わせてテキストの比較位置 text_pos を移動を行なってしまうと、パターンが存在する可能性のある “テキストの比較の開始位置” の確認を飛ばしてしまうことになりますので、パターンの検索漏れが発生しうることになります。

ですので、検索漏れが発生しないよう、パターン内のより後ろ側の位置の文字と不一致したテキストの文字が同じ位置に来るようにテキストの比較位置 text_pos を移動させる必要があります。

スポンサーリンク

BM 法（簡略版）のずらし表の作り方

以上が BM 法（簡略版）の考え方であり、この考え方に基づいて処理を行うことで、パターンの検索を漏れなく行うことが可能です。

ただし、テキストの不一致が発生するたびに毎回テキストの比較位置 text_pos の移動文字数を計算してしまうと検索処理が遅くなってしまいます。

そのため、検索を行う前に、あらかじめ “不一致したテキストの文字” に対するテキストの比較位置 text_pos の移動文字数を配列に格納しておき、検索実行時には配列を参照するだけで移動文字数を取得できるようにしておきます。

このような配列は「ずらし表」と呼ばれます。

ということで、次はこの「ずらし表」の作り方について解説していきます。

ここで、以降で解説時に使用する変数についておさらいしておきます。これらは 力まかせ法の復習 で紹介したソースコードでも利用した変数であり、各変数の意味合いは下記のようになります。

  • text_pos：テキストの比較位置
  • pattern_pos：パターンの比較位置
  • pattern_len：パターンの文字数
  • text：テキストの文字列
  • pattern：パターンの文字列

ずらし表の配列のサイズ

まず、前述の通り、不一致時のテキストの比較位置 text_pos の移動文字数は、不一致した位置のテキストの文字によって変化します。そのため、移動文字数を格納するずらし表の配列のサイズ（配列の要素数）は、テキスト内で扱う文字の種類数以上にしておく必要があります。

今回は、テキストの文字としては１バイト文字全てを考慮することにしたいと思います。つまり、テキスト内では文字コードが 0 〜 255 の文字を扱うものとします。そのため、配列のサイズは 256 が必要になります。

半角の英数字や基本的な半角記号等は基本的に１バイト文字で表現可能ですので、基本的な半角文字はテキスト内で扱うことができることになります。逆に１バイト文字以外、例えば全角の漢字や平仮名などは扱えないので注意してください。

ずらし表の配列の各要素の役割

また、不一致時のテキストの比較位置 text_pos の移動文字数は、その不一致したテキストの文字を添字とする配列の要素に格納していきます。

例えば、ずらし表を扱う配列を table1、不一致したテキストの文字を c とすれば、不一致したテキストの文字が c の場合の移動文字数は table1[[c]] に格納していくことになります。

つまり、テキストの比較位置 text_pos で不一致が発生した場合、不一致したテキストの文字は text[text_pos] ということになりますので、この際には text_pos を table1[[text[text_pos]]] だけ移動することになります（すなわち text_pos += table1[[text[text_pos]]] を実行する）。

スポンサーリンク

ずらし表への移動文字数の格納

ずらし表の配列の各要素の役割を理解したところで、次は実際に各要素に移動文字数を格納していきます。

BM 法（簡略版）の考え方 で解説したように、不一致したテキストの文字がパターン内に存在しない場合、テキストの比較位置 text_pos の移動文字数は pattern_len となります。

さらに、不一致したテキストの文字がパターン内に存在する場合、テキストの比較位置 text_pos の移動文字数は pattern_len - 1 - パターン内の同じ文字の位置 となります。

そのため、まずは全ての文字がパターン内に存在しないと仮定して一旦配列全ての要素に pattern_len を格納していきます。そして、後からパターン内に存在する文字の要素のみ、pattern_len - 1 - パターン内の同じ文字の位置 で値を上書きするようにすることで、ずらし表の配列を完成させていきたいと思います。

不一致したテキストの文字がパターン内に存在しない場合の移動文字数

配列全ての要素に pattern_len を格納するのですから、これは下記の for ループで実現することができます。

前述の通り、256 は配列の要素数であり、下記により不一致したテキストの文字が “文字コード 0 〜 255 の文字” である場合の移動文字数を pattern_len に設定したことになります。

パターン内に存在しない場合の移動文字数を設定 
for (int c = 0; c < 256; c++) {
    table1[c] = pattern_len;
}

不一致したテキストの文字がパターン内に存在する場合の移動文字数

次は、table1 における “パターン内に存在する文字” の要素を移動文字数 pattern_len - 1 - パターン内の同じ文字の位置 で上書きしていきます。

まず、パターンの位置 pos に存在する文字は pattern[pos] となります。

また、table1[pattern[pos]] は不一致した際のテキストの文字が pattern[pos] である場合の移動文字数となり、さらに pattern[pos] は当然パターン内に存在する文字ですので、table1[pattern[pos]] には不一致したテキストの文字がパターン内に存在する場合の移動文字数を格納する必要があります。

そして、pattern[pos] はパターンの位置 pos に存在するのですから、table1[pattern[pos]] に格納すべき値は pattern_len - 1 - pos  となります。

つまり、前述の for ループが完了した後に次の for ループを実行することで、table1 における “パターン内に存在する文字” の要素を移動文字数 pattern_len - 1 - pos で上書くことができます。

パターン内に存在する場合の移動文字数で上書き 
for (int pos = 0; pos < pattern_len; pos++) {
    table1[pattern[pos]] = pattern_len - 1 - pos;
}

この for ループではパターン上の位置 pos を小さな値から大きな値に変化させて行っているため、pattern 内に同じ文字が存在する場合、より後ろ側に存在する方の位置に合わせて table1 の値が上書きされていくことになります。

すなわち、文字の不一致が発生した際に text_pos += table1[[text[text_pos]]] を実行すると、不一致したテキストの文字（text[text_pos]）が pattern 内に複数存在する場合、その中の一番後ろの位置にある文字とテキストの不一致した文字とが重なるように、text_pos の位置が変化することになります。

つまり、上記の for ループを実行することで、BM 法（簡略版）の考え方 で解説した “不一致したテキストの文字と同じ文字がパターン内に複数存在する場合、パターン内のより後ろ側の位置の文字とテキストの文字が同じ位置に来るようにテキストの比較位置を移動させる” を実現することができることになります。

ということで、前述の２つの for ループを実行することで、文字の不一致が発生した際に BM 法（簡略版）の考え方 で解説した通りの比較位置 text_pos の移動を実現可能な配列 table1 が完成したことになります。

BM 法（簡略版）のサンプルプログラム

ずらし表の配列の作成手順の解説も終わりましたので、次は実際に BM 法（簡略版）で文字列検索を行うプログラムのソースコードを紹介していきます。

ソースコード

下記が、そのプログラムのソースコードになります。main 関数等は省略していますので、必要に応じて 力まかせ法の復習 で紹介したソースコードを参照してください。

BM法(簡略版) 
void makeTable1(int table1[], char pattern[], int pattern_len) {

    for (int c = 0; c < 256; c++) {
        table1[c] = pattern_len;
    }

    for (int pos = 0; pos < pattern_len; pos++) {
        table1[pattern[pos]] = pattern_len - 1 - pos;
    }
}

int bmSimpleSearch(char text[], int text_len, char pattern[], int pattern_len) {
    int text_pos; /* テキストの比較位置 */
    int pattern_pos; /* パターンの比較位置*/
    int table1[256];

    makeTable1(table1, pattern, pattern_len);

    /* パターンの比較位置を末尾にセット */
    pattern_pos = pattern_len - 1;

    /* テキストの比較位置をパターンの末尾の位置にセット */
    text_pos = pattern_len - 1;

    /* テキストの比較位置がテキストの最後を超えるまでループ */
    while (text_pos < text_len) {

        /* テキストの比較位置の文字とパターンの比較位置の文字が一致するかを判断 */
        if (text[text_pos] == pattern[pattern_pos]) {
            /* 一致した場合 */

            /* パターンの先頭の文字までテキストの文字が一致したかどうかを判断 */
            if (pattern_pos == 0) {
                /* パターンが存在するテキストの位置を返却 */
                return text_pos;
            }

            /* テキストとパターンの比較位置を１文字分前側に移動する */
            text_pos--;
            pattern_pos--;

        } else {
            /* 不一致した場合 */

            if (table1[text[text_pos]] > pattern_len - 1 - pattern_pos) {
                /* 次回の比較位置が前回の比較開始位置よりも後ろに移動する場合 */

                /* ずらし表に従ってテキストの比較位置を移動させる */
                text_pos += table1[text[text_pos]];
            } else {
                /* 次回の比較位置が前回の比較開始位置以前に移動してしまう場合 */

                /* 力まかせ法と同様にテキストの比較位置を移動させる */
                text_pos += pattern_len - pattern_pos;
            }

            /* パターンの比較位置を末尾に戻す */
            pattern_pos = pattern_len - 1;
            
        }
    }

    /* パターンが見つからなかった場合は-1を返却 */
    return -1;
}

力まかせ法の復習 で紹介した forceSearch 関数と上記の bmSimpleSearch 関数との違いは２つあります。１つ目は下記の処理が加わった点になります。要は、ずらし表を作成する処理を追加しています（makeTable1 がずらし表の配列を作成する関数）。

ずらし表の作成 
int table1[256];

makeTable1(table1, pattern, pattern_len);

ここで実行している makeTable1 関数の内部の処理は BM 法（簡略版）のずらし表の作り方 で解説した通りです。

また、力まかせ法の復習 で紹介した forceSearch 関数と上記の bmSimpleSearch 関数との違いの２点目は、下記部分の、文字が不一致した際にテキストの比較位置 text_pos を移動させる処理になります。

テキストの比較位置の移動 
if (table1[text[text_pos]] > pattern_len - 1 - pattern_pos) {
    /* 次回の比較位置が前回の比較開始位置よりも後ろに移動する場合 */

    /* ずらし表に従ってテキストの比較位置を移動させる */
    text_pos += table1[text[text_pos]];
} else {
    /* 次回の比較位置が前回の比較開始位置以前に移動してしまう場合 */

    /* 力まかせ法と同様にテキストの比較位置を移動させる */
    text_pos += pattern_len - pattern_pos;
}

思ったよりもややこしいと感じた方が多いのではないかと思いますが、基本的には BM 法（簡略版）の考え方 や BM 法（簡略版）のずらし表の作り方 で解説した通り、文字の不一致が発生した際に text_pos += table1[[text[text_pos]]] を実行することで、ずらし表にしたがってテキスト比較位置移動させているだけです。

ただ、単に text_pos += table1[[text[text_pos]]] を行うだけだと、移動後の text_pos が、前回テキストの比較を開始した位置よりも前側 or 同じ位置に移動してしまう可能性があります。

次回のテキストの比較開始位置が前回のテキストの比較開始位置よりも前側に移動してしまう様子

テキストの比較を開始する位置が後ろ側に移動したのは、それよりも前の位置からテキストの比較を開始してもパターンが見つからないと判断できたからです。

それなのに、テキストの比較の開始位置を前回のテキストの比較の開始位置よりも前側に移動してしまうのは無駄です。

また、文字の不一致が発生したからテキストの比較開始位置を移動させているのに、再度同じ位置から比較を開始してしまうのも無駄です（これらを行うと、おそらく多くの場合で無限ループになってしまうと思います）。

そのため、text_pos += table1[[text[text_pos]]] を行なった場合に text_pos の位置が前回テキストの比較を開始した位置よりも前側 or 同じ位置 になってしまう場合は、text_pos が前回テキストの比較を開始した位置の１つ後ろに移動するように text_pos の値を設定するようにしています。

これはつまり、力まかせ法で不一致発生時に text_pos の値を設定する時と同じ処理であり、text_pos += pattern_len - pattern_pos を実行することになります。

そして、これらを考慮して不一致発生時の text_pos の移動を行なっているのが、上記の処理となります。

スポンサーリンク

（参考）ずらし表の参照のみで text_pos を決定する

実は、上記のようにわざわざ場合分けを行なわずに、不一致した際の text_pos の移動位置の決定を毎回ずらし表を参照するだけで実現することも可能です。

ただし、これを実現するためには、BM 法（簡略版）の考え方 で解説したように不一致した際の text_pos の移動文字数を下記のように設定するのではなく、

  • “不一致したテキストの文字” がパターン内に存在しない場合：
    • 移動文字数を pattern_len とする
  • “不一致したテキストの文字” がパターン内に存在する場合：
    • 移動文字数を pattern_len - 1 - パターン内の同じ文字の位置 とする

下記のように移動文字数を設定する必要があります。

  • “不一致したテキストの文字” がパターンの比較位置よりも前側に存在しない場合：
    • 移動文字数を pattern_len とする
  • “不一致したテキストの文字” がパターンの比較位置よりも前側に存在する場合：
    • 移動文字数を pattern_len - 1 - パターン内の同じ文字の位置 とする

つまり、文字が不一致した際のパターンの比較位置も考慮して、移動文字数の設定を行う必要があります。

パターンの比較位置の前側に不一致したテキストの文字が存在するかどうかで計算式を変更する様子

そして、この場合は、不一致した際のパターンの比較位置も考慮してずらし表を作成する必要があります。すなわち、「不一致した際のテキストの文字」と「不一致した際のパターンの比較位置」の２つを添字に指定して移動文字数を取得することができるよう、ずらし表の配列は２次元配列としておく必要があります（１次元配列を２次元配列として扱っても良い）。

この辺りを考慮するようにした BM 法の簡略版のソースコードは下記のようになります。MAX_PATTERN は扱うパターンの文字数の最大値として定義しています。

不一致が発生した際の text_pos の移動が全て text_pos += table1[pattern_pos][text[text_pos]] で行えるので、この方がソースコードとしてはスッキリするかなぁと思います。

不一致時のパターン上の位置も考慮するBM法(簡略版) 
#define MAX_PATTERN 256

void makeTable1(int table1[][256], char pattern[], int pattern_len) {

    for (int c = 0; c < 256; c++) {
        for (int pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {
            table1[pattern_pos][c] = pattern_len;
        }
    }

    for (int pos = 0; pos < pattern_len; pos++) {
        for (int pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {
            if (pos < pattern_pos) {
                /* posが不一致する位置pattern_posよりも前側の場合 */
                table1[pattern_pos][pattern[pos]] = pattern_len - 1 - pos;
            }
        }
    }
}

int bmSimpleSearch(char text[], int text_len, char pattern[], int pattern_len) {
    int text_pos; /* テキストの比較位置 */
    int pattern_pos; /* パターンの比較位置*/
    int table1[MAX_PATTERN][256];

    makeTable1(table1, pattern, pattern_len);

    /* パターンの比較位置を末尾にセット */
    pattern_pos = pattern_len - 1;

    /* テキストの比較位置をパターンの末尾の位置にセット */
    text_pos = pattern_len - 1;

    /* テキストの比較位置がテキストの最後を超えるまでループ */
    while (text_pos < text_len) {

        /* テキストの比較位置の文字とパターンの比較位置の文字が一致するかを判断 */
        if (text[text_pos] == pattern[pattern_pos]) {
            /* 一致した場合 */

            /* パターンの先頭の文字までテキストの文字が一致したかどうかを判断 */
            if (pattern_pos == 0) {
                /* パターンが存在するテキストの位置を返却 */
                return text_pos;
            }

            /* テキストとパターンの比較位置を１文字分前側に移動する */
            text_pos--;
            pattern_pos--;

        } else {
            /* 不一致した場合 */

            /* ずらし表に従ってテキストの比較位置を移動させる */
            text_pos += table1[pattern_pos][text[text_pos]];
            
            /* パターンの比較位置を末尾に戻す */
            pattern_pos = pattern_len - 1;
            
        }
    }

    /* パターンが見つからなかった場合は-1を返却 */
    return -1;
}

table1 の１つ目の添字に不一致発生時のパターンの比較位置 pattern_pos を指定することで、pattern_pos の位置も考慮した移動文字数を取得することがでます。

また、ずらし表の配列を作成する makeTable1 関数の後ろ側のループで、下記のようにパターン上の位置 pos が不一致する位置 pattern_pos よりも前側の場合のみ table1 を上書きするようにしているため、これ以外の場合は全て table1 に格納されるテキストの比較位置 text_pos の移動文字数は pattern_len となります。

不一致した位置より前側の場合のみ移動文字数を上書き 
for (int pos = 0; pos < pattern_len; pos++) {
    for (int pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {
        if (pos < pattern_pos) {
            /* posが不一致する位置pattern_posよりも前側の場合 */
            table1[pattern_pos][pattern[pos]] = pattern_len - 1 - pos;
        }
    }
}

つまり、文字の不一致が発生した際、パターンの比較位置よりも前側に “不一致したテキストの文字” がある場合以外は全て、text_pos の移動文字数が pattern_len となります。そして、これによって text_pos が前回のテキストの比較開始位置よりも必ず後ろ側に移動することになります。

そのため、前述で紹介したソースコードのように、ずらし表 table1 の値で場合分けして text_pos の移動文字数を設定する必要がなくなります。

個人的にはこっちの方がソースコードがスッキリして好きなのですが、makeTable1 関数の中で２重ループを行う必要があり、その分ずらし表の配列を作成する時間が長くなるので注意してください。

BM 法（完全版）の考え方

ここまでが BM 法の簡略版の解説になります。

ここから、BM 法の完全版の解説をしていきます。

BM 法の完全版においても簡略版同様に、パターンの後ろ側から文字の比較を行い、文字の不一致が発生した際にはずらし表を参照してテキストの比較位置 text_pos の移動文字数を決定します。

ただし、BM 法の完全版においては２つのずらし表を利用します。そのうちの１つは  BM 法（簡略版）のずらし表の作り方 で紹介した table1 になります（もう１つのずらし表については後述で解説します）。

そして、文字の不一致が発生した際には、２つのずらし表の両方を参照し、大きい方の移動文字数に従ってテキストの比較位置 text_pos を移動させます。

ですので、不一致が発生した際のテキストの比較位置 text_pos の移動文字数は簡略法以上になり、検索実行時の処理としても簡略版よりも早くなります（ただし、ずらし表を２つ作る必要がある分、ずらし表の作成は遅くなる）。

以降では、２つ目のずらし表を作成するにあたって必要になる考え方や移動文字数の設定手順に絞って解説していきます。ただ、前述の通り、実際に検索処理を実装する際には２つのずらし表を利用する必要がありますので、この点は忘れないようにご注意ください。

最終的なソースコードを紹介する BM 法（完全版）のサンプルプログラム では、この辺りも含めてソースコードの解説をさせていただきます。

一致したパターンの文字を利用する

簡略版では、不一致が発生したテキストの文字を利用してテキストの比較位置 text_pos の移動文字数を決定していました。

それに対し、完全版においては、不一致が発生する前にテキストと一致したパターンの文字を利用することで、テキストの比較位置 text_pos の移動文字数を決定していきます。

ここでまず、テキストの文字とパターンの文字が不一致する意味合いについて整理しておきましょう。

ある位置でテキストとパターンの文字が不一致したということは、その不一致が発生した位置のテキストの文字は比較先のパターンの文字以外の文字であるということになります。逆に、不一致が発生するより前に連続して比較を行なったテキストの文字は比較先のパターンの文字と同じ文字ということになります

パターンの不一致が発生した際にテキストの文字の一部が判明する様子

これは当たり前のようにも感じるかもしれないですが、非常に重要な情報です。

これらの情報があれば、後述の２つの条件に当てはまらない限り、文字の不一致が発生した際にテキストの比較位置 text_pos を pattern_len + (pattern_len - 1 + pattern_pos) だけ移動させることができます。

特定の条件を満たしていない場合、一気にテキストの比較位置を移動できることを示す図

簡略版では一度に移動できる移動文字数の最大は pattern_len でしたので、それに比べると大きくテキストの比較位置を移動することができることが分かります。

スポンサーリンク

パターンの末尾の文字列がパターンの他の部分に存在する場合

ただし、前述の通り、上記のようにテキストの比較位置 text_pos が移動できるのは特定の条件を満たしていない場合のみであり、特定の条件を満たしている場合はもう少し工夫してテキストの比較位置 text_pos を移動させる必要があります。

この特定の条件は２つあります。

その条件の１つ目は、不一致が発生した際の パターンの比較位置 に対して下記が成立することになります。

  • パターンの末尾以外に “パターンの比較位置 + 1 〜 末尾 の文字列” と同じ文字列が存在する
    • これらの２つの文字列の１つ前の文字が異なる

下の図は、この条件が成立するパターンの一例を示す図となります（不一致が発生した際の パターンの比較位置 を pattern_pos としています）。

１つ目の条件の説明図

“パターンの比較位置 + 1 〜 末尾 の文字列” とは、要は「不一致が発生する前に一致した文字列」です。

パターンの末尾以外に「不一致が発生する前に一致した文字列」と同じ文字列が存在する場合、次にパターンが見つかる可能性があるのは、その文字列の末尾が元々のパターンの末尾の位置に移動するようテキストの比較の開始位置を移動させた時となります。

元々のパターン末尾の位置に同じ文字列の末尾が来るようにテキストの比較位置を移動させる様子

逆に、その位置より前の位置から比較を開始した場合、パターンが見つからないことは明らかです。前回比較を行なった際に一致した部分のテキストの文字列は既に確定していますので、そのテキストの文字列との比較対象が同じ文字列でない限り、必ずそのテキストの文字列との比較を行う際に文字の不一致が発生します。

同じ文字列が元々のパターンの末尾の位置にまで移動しない限り必ずいずれかの位置で比較が不一致することを示す図

また、前回比較を行なった際に不一致したテキストの文字は、その際に比較を行なったパターンの文字 “以外” の文字であることが確定しています。

ですので、パターンの末尾以外に “パターンの比較位置 + 1 〜 末尾 の文字列” と同じ文字列が存在したとしても、その文字列の１つ手前の文字が パターンの比較位置 の文字と同じである場合、その文字列の末尾が元々のパターンの末尾の位置に移動するようテキストの比較の開始位置を移動させて比較を開始すると、前回不一致が発生したテキストの文字は再度同じ文字と比較されることになります。

したがって、この場合も必ず不一致が発生することになるので、比較を開始するのは無駄です。

パターンの末尾と一致する文字列であっても移動後に必ず比較が不一致する例

つまり、下記の条件が成立する場合、次にパターンが見つかる可能性があるのは、その存在する文字列の末尾が元々のパターンの末尾の位置に移動するようテキストの比較の開始位置を移動させた時であり、それよりも前の位置にテキストの比較の開始位置を移動させて比較を開始しても無駄です。

  • パターンの末尾以外に “パターンの比較位置 + 1 〜 末尾 の文字列” と同じ文字列が存在する
    • これらの２つの文字列の１つ前の文字が異なる

なので、不一致が発生した際には、上記を満たす文字列の末尾が元々のパターンの末尾の位置に移動するようにテキストの比較位置を移動させてから比較を開始してやることで、無駄な比較をスキップすることができます。

元々のパターン末尾の位置に同じ文字列の末尾が来るようにテキストの比較位置を移動させる様子

また、上記の条件を満たす文字列がパターン内に複数存在する場合は、その中の “一番後ろ側にある文字列” の末尾が元々のパターンの末尾の位置に来るように移動を行う必要があります。

具体的な不一致発生時のテキストの比較位置 text_pos の移動文字数は、不一致したパターンの比較位置を pattern_pos とし、”パターンの比較位置 + 1 〜 末尾 の文字列” と同じ文字列の末尾の位置を tail_pos とすれば、下記の式により求めることができることになります。

１つ目の条件を満たす場合の移動文字数 
pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos

図で表すと下の図のようになります。要は上式において、青色背景部分は元々の pattern_len - 1 の位置に tail_pos の位置を移動させるための項であり、赤色背景部分は pattern_pos を元々のテキストの比較開始位置に戻すための項となります。

１つ目の条件が成立する場合のテキストの比較位置の移動文字数の計算式の説明図

パターンの末尾の文字列がパターンの先頭にも存在する場合

前述の通り、特定の条件の１つ目は、不一致が発生した際の パターンの比較位置 に対して下記が成立することになります。

  • パターンの末尾以外に “パターンの比較位置 + 1〜 末尾 の文字列” と同じ文字列が存在する
    • これらの２つの文字列の１つ手前の文字が異なる

もし、この条件が満たされない場合であっても、不一致が発生した際の パターンの比較位置 に対して下記に示す特定の条件の２つ目が成立する場合、そのことを考慮してテキストの比較位置 text_pos を移動させる必要があります。

  • パターンの先頭から始まる文字列とパターンの末尾で終わる文字列とが同じ
    • その文字列の文字数は 末尾の位置 - パターンの比較位置 以下である

下の図は、この条件が成立するパターンの一例を示す図となります（不一致が発生した際の パターンの比較位置 を pattern_pos としています）。

２つ目の条件の説明図

末尾の位置 - パターンの比較位置 とは、要は不一致する前にテキストの文字とパターンの文字との比較が一致した文字数です。

特定の条件の１つ目が成立しない場合であっても、パターンの先頭から始まる文字列とパターンの末尾で終わる文字列とが一致する場合、前者のパターンの先頭から始まる文字列の末尾が元々のパターンの末尾の位置に来るようにテキストの比較位置を移動させてから比較を開始すれば、その位置にパターンが見つかる可能性があります。

末尾に一致する先頭の文字列が元々の末尾に移動するようにテキストの比較位置を移動させる様子

ただし、上記のようにテキストの比較位置を移動させてから比較を開始したとしても、これらの２つの文字列が移動前の比較で一致した文字数（つまり 末尾の位置 - パターンの比較位置）よりも長い場合、前回不一致したテキストの文字が再度同じ文字と比較されることになるため、必ず不一致が発生することになります。

移動後に必ず不一致が発生する様子

そのため、パターンの先頭から始まる文字列とパターンの末尾で終わる文字列とが同じで、かつ、それらの文字数が 末尾の位置 - パターンの比較位置 以下である場合のみ、上記のようにテキストの比較位置を移動させます。

もし、上記の条件が成立する文字列が複数存在する場合は、より長い方の文字列に対して前述のようにテキストの比較位置を移動させます。

末尾の文字列と一致する文字列が先頭側に複数存在する場合のテキストの比較位置の移動

さらに、具体的な不一致発生時のテキストの比較位置 text_pos の移動文字数は、不一致したパターンの比較位置を pattern_pos とし、パターンの先頭から始まる文字列の末尾の位置を tail_pos とすれば、下記の式により求めることができます。

２つ目の条件を満たす場合の移動文字数 
pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos

図で表すと下の図のようになります。要は上式において、青色背景部分は元々の pattern_len - 1 の位置に tail_pos の位置を移動させるための項であり、赤色背景部分は pattern_pos を元々のテキストの比較開始位置に戻すための項となります。

２つ目の条件が成立する場合のテキストの比較位置の移動文字数の計算式の説明図

移動文字数の決定の流れ

ここまでをまとめると、文字の不一致が発生した際には、下記のようにテキストの比較位置 text_pos を移動させていくことになります。

まず、不一致が発生した際の パターンの比較位置 に対して下記が成立する時、

  • パターンの末尾以外に “パターンの比較位置 + 1〜 末尾 の文字列” と同じ文字列が存在する
    • これらの２つの文字列の１つ前の文字が異なる

テキストの比較位置 text_pos は下記の文字数だけ移動させ、移動した先からテキストとパターンの比較を開始します。

１つ目の条件を満たす場合の移動文字数 
pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos

上式において、tail_pos は上記条件における「パターンの末尾以外に存在する “パターンの比較位置 + 1〜 末尾 の文字列” と同じ文字列」の末尾の位置となります。

上記の条件が成立しない、かつ、不一致が発生した際の パターンの比較位置 に対して下記が成立する時、

  • パターンの先頭から始まる文字列とパターンの末尾で終わる文字列とが同じ
    • その文字列の文字数は 末尾の位置 - パターンの比較位置 以下である

テキストの比較位置 text_pos は下記の文字数だけ移動させ、移動した先からテキストとパターンの比較を開始します。

２つ目の条件を満たす場合の移動文字数 
pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos

上式において、tail_pos は上記条件における「パターンの先頭から始まる “パターンの末尾と同じ文字列”」の末尾の位置となります。

ここまで示した２つの条件両方が成立しない場合、パターンと一致したテキストの文字を利用する で解説した通り、テキストの比較位置 text_pos は下記の文字数だけ移動させ、移動した先からテキストとパターンの比較を開始します。

条件を両方満たさない場合の移動文字数 
pattern_len + pattern_len - 1 - pattern_pos

スポンサーリンク

ずらし表はパターンのみから作成できる

また、ここまで解説してきたテキストの比較位置の移動文字数は、パターンの文字と一致したテキストの文字列を利用した考え方に基づいたものであるものの、その一致したテキストの文字列はパターンの末尾にも存在するため、パターンの文字列のみから求めることが可能です。

つまり、テキストの文字列が与えられる前に、不一致が発生すると仮定したパターンの比較位置に応じて移動文字数を決定しておくことができます。

なので、ずらし表としてサイズを “パターンの文字数” とする配列を用意しておき、パターンの比較位置を添字とする要素に、その位置で不一致が発生した際のテキストの比較位置の移動文字数を格納しておけば、検索実行時に移動文字数を配列から参照するだけで取得することができて効率的に検索を行うことができます。

ただ、これを行うためには事前に配列を用意しておく必要がありますので、次はその手順について解説していきます。

BM 法（完全版）のずらし表の作成

続いてずらし表を作成していきたいと思います。

BM 法の完全版においては、２つのずらし表を作成する必要があります。１つは BM 法（簡略版）のずらし表の作り方 で作成した table1 であり、もう１つが以降で解説する table2 となります。

まず、前述の通り、ずらし表を扱う配列 table2 のサイズはパターンの文字数となります。table2 の各要素に対し、パターン上のその添字の位置で文字の不一致が発生した際の移動文字数を格納していくことで、ずらし表の配列を作成していきます。

  • table2[pattern_pos]：
    • パターン上の pattern_pos の位置で文字が不一致した際のテキストの比較位置の移動文字数

さらに、移動文字数の決定の流れ でまとめたように、条件に当てはまるかどうかで移動文字数の求め方が異なります。

そのため、下記のように条件を満たす位置 pattern_pos の要素から順に段階を踏みながら移動文字数を格納していくことで、ずらし表を作成していきたいと思います。

  1. table2 の全ての要素に -1 を格納（-1 は、まだ移動文字数を設定していないことを示す目印）
  2. 不一致した際のパターンの比較位置 pattern_pos において パターンの末尾の文字列がパターンの他の部分に存在する場合 で示した条件が成立する場合、table2[pattern_pos] に移動文字数を格納
  3. 不一致した際のパターンの比較位置 pattern_pos において パターンの末尾の文字列がパターンの先頭にも存在する場合 で示した条件が成立する、かつ table2[pattern_pos] が -1 の場合、table2[pattern_pos] に移動文字数を格納
  4. table2 において値が -1 の要素全てに pattern_len + pattern_len - 1 - pattern_pos を格納

ここからは、上記の４つそれぞれに対して移動文字数の設定手順を解説していきます。

特に 2. と 3. における移動文字数の格納を行う処理に関しては、ストレートに実装してしまうとずらし表の配列を作成するのに時間がかかり、検索全体の処理時間が力まかせ法よりも遅くなってしまう可能性があります。

そのため、効率的にずらし表を作成していく必要があります。その辺りも踏まえながら解説していきたいと思います。

1. に対する移動文字数の設定

1. に関しては単純で、下記のように table2の全要素に -1 を格納すれば良いだけです。

1.に対する移動文字数の設定 
for (int pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {
    table2[pattern_pos] = -1;
}

全ての要素に -1 を格納しておくことで、以降で移動文字数が設定されていない要素を見分けることができるようになります。 

スポンサーリンク

2. に対する移動文字数の設定

2. では パターンの末尾の文字列がパターンの他の部分に存在する場合 で示した条件を満たす位置の要素に移動文字数を設定していきます。

まず、パターンの末尾の文字列がパターンの他の部分に存在する場合 で示した条件は、変数名を使用して下記のように書き換えることができます。pattern_pos は不一致が発生した際のパターンの比較位置を示しており、ここでは下記を満たす pattern_pos の要素 table2[pattern_pos] に移動文字数を設定することになります。

  • pattern[pattern_pos + 1] 〜 pattern[pattern_len - 1] と同じ文字列がパターンの末尾以外に存在する（その文字列の末尾の位置を tail_pos とする）
    • pattern[pattern_pos] != pattern[tail_pos - (pattern_len - 1 - pattern_pos)] が成立する

各変数の関係を図で表すと下の図のようになります。

１つ目の条件に現れる変数の関係性を示した図

また、上記を満たす pattern_pos の要素 table2[pattern_pos] に設定する文字数は パターンの末尾の文字列がパターンの他の部分に存在する場合 で説明した通り下記となります。

１つ目の条件を満たす場合の移動文字数 
pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos

結局 pattern_pos から条件を満たす tail_pos を見つけ、そこから移動文字数を計算すれば良いのですが、結構この tail_pos を見つけ出すのが大変です。

ですので、逆に tail_pos から pattern_pos を求め、その pattern_pos の位置の要素（table2[pattern_pos]）に移動文字数を設定していくようにしていきたいと思います。

そのために、上記の条件を次のように書き換えます。ここで eq_len はテキストとパターンとの文字が不一致する前に連続して一致した文字数となります。

  • pattern[pattern_len - eq_len] 〜 pattern[pattern_len - 1] と同じ文字列がパターンの末尾以外に存在する（その文字列の末尾の位置を tail_pos とする）
    • pattern[pattern_len - eq_len - 1] != pattern[tail_pos - eq_len] が成立する

各変数の関係を図で表すと下の図のようになります。

１つ目の条件に現れる変数の関係性を示した図（pattern_posなし）

また、eq_len はテキストとパターンとの文字が不一致する前に連続して一致した文字数なのですから、pattern_len - eq_len - 1 が不一致する位置 pattern_pos ということになります。すなわち、上記の条件を満たす場合、table2[pattern_len - eq_len - 1] に下記の移動文字数を設定することができます。

１つ目の条件を満たす場合の移動文字数(式変形後) 
pattern_len - 1 - tail_pos + eq_len

さて、上記の条件の１行目に関して成立するかどうかは、パターン内の任意の位置 tail_pos において、pattern[pattern_len - 1] 以前の文字と pattern[tail_pos] 以前の文字が 1 文字以上一致するかどうかで判断することができます。

すなわち、下記が終了した際に eq_len が 1 以上であれば、上記の条件の１行目が成立すると考えることができます。

  1. eq_len を 0 とする
  2. 下記の２つのいずれか一方でも成立しない場合は終了
    1. eq_len < tail_pos
    2. pattern[pattern_len - 1 - eq_len] == pattern[tail_pos - eq_len]
  3. eq_len++ を行って 2. に戻る

上記が終了した際に eq_len が 1 以上なのであれば次の２つの文字列が同じであることになります。

  • pattern[pattern_len - eq_len] 〜 pattern[pattern_len - 1]
  • pattern[tail_pos - eq_len + 1] 〜 pattern[tail_pos]

逆に eq_len が 0 の場合は、上記の条件の１行目が “成立しない” ということになります。

なので、eq_len が 1 以上の場合、かつ、pattern[pattern_len - eq_len - 1] != pattern[tail_pos - eq_len] が成立する場合のみ移動文字数を table2 に格納するようにすれば、上記の条件の１行目と２行目が成立する位置に対してのみ移動文字数を設定することができることになります。

したがって、この場合のみ、前述の通り table2[pattern_len - eq_len - 1] に移動文字数 pattern_len - 1 - tail_pos + eq_len を格納します。

あとは、これらを tail_pos を 0 〜 pattern_len - 2 まで変化させながら繰り返し行えば、tail_pos から eq_len 等の必要な変数の値を求めて table2 の適切な添字の位置に text_pos の移動文字数を格納していくことができます。

ちなみに tail_pos が pattern_len - 1 ということは tail_pos がパターンの末尾ということになり、上記の条件の１行目と矛盾するため、tail_pos は pattern_len - 2 になるまでの繰り返しで十分です。

また、tail_pos を小さな値から大きな値に変化させるようにすることで、条件を満たす文字列が複数存在する場合、より後ろ側にある文字列を用いて移動文字数を決定することができるようになります。

上記の処理をソースコードとして記述すれば次のようになります。

2. に対する移動文字数の設定 
for (int tail_pos = 0; tail_pos < pattern_len - 1; tail_pos++) {

    int eq_len = 0;

    while (
        eq_len < tail_pos &&
        pattern[tail_pos - eq_len] == pattern[pattern_len - 1 - eq_len]
    ) {

        eq_len++;
    }

    if (eq_len == 0) {
        continue;
    }

    if (pattern[tail_pos - eq_len] != pattern[pattern_len - 1 - eq_len]) {
        table2[pattern_len - 1 - eq_len] = pattern_len - 1 - tail_pos + eq_len;
    }
}

3. に対する移動文字数の設定

3. では パターンの末尾の文字列がパターンの先頭にも存在する場合 で示した条件を満たす パターンの比較位置 の要素に移動文字数を設定していきます。

  • パターンの先頭から始まる文字列とパターンの末尾で終わる文字列とが同じ
    • その文字列の文字数は 末尾の位置 - パターンの比較位置 以下である

上記の条件が成立する場合、pattern_pos を不一致したパターンの比較位置、tail_pos をパターンの先頭から始まる文字列の末尾の位置とすれば、table2[pattern_pos] には下記の移動文字数を格納することになります。

２つ目の条件を満たす場合の移動文字数 
pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos

ここからは、不一致が発生するよりも前に一致した文字数（末尾の位置 - パターンの比較位置）を eq_len として解説していきます。

実は、上式における tail_pos を求めるのは結構大変です。大変なのは、パターンの先頭から始まる文字列とパターンの末尾で終わる文字列の文字数が eq_len の場合だけでなく、eq_len 未満の場合も認められているからです。

もし２つの文字列の文字数が eq_len のみに限定されているのであれば、pattern[0] 〜 pattern[eq_len - 1] と pattern[pattern_len - eq_len] 〜 pattern[pattern_len - 1] の文字列が一致するかどうかを調べ、一致した際に tail_pos = eq_len -1 を行えば良いだけになります（tail_pos はパターンの先頭から始まる文字列の末尾の位置）。

パターンの先頭と末尾のeq_lenが等しいかどうかの判断を行うだけの様子

それに対し、実際には２つの文字列の文字数が eq_len 未満であることも認められているため、pattern[0] 〜 pattern[eq_len - 1] と pattern[pattern_len - eq_len] 〜 pattern[pattern_len - 1] が一致しない場合は、文字数を短くしながら、パターンの先頭から始まる文字列とパターンの末尾で終わる文字列とが一致するかどうかを繰り返し判断していく必要があります。そして一致した場合に、一致したパターンの先頭から始まる文字列の末尾の位置を tail_pos とする必要があります。

文字数を小さくしながらパターンの先頭と末尾の文字列の比較を繰り返し行う必要があることを示す図

つまり、２つの文字列の文字数を eq_len から小さくしながら tail_pos を求めることになるのでループ処理が必要になり、ずらし表の配列を作成するのに時間がかかってしまいます。

ここで注目していただきたいのが、pattern[0] 〜 pattern[eq_len - 1] と pattern[pattern_len - eq_len] 〜 pattern[pattern_len - 1] の文字列が一致しなかった時の次の処理です。

最初の比較で文字列が一致しなかった時に次に行われる処理を示す図

ここでは、２つの文字列の文字数が eq_len - 1 であると仮定して文字列の比較を行うわけですから、要は pattern[0] 〜 pattern[eq_len - 2] と pattern[pattern_len - eq_len + 1] 〜 pattern[pattern_len - 1] の文字列が一致するかどうかの判断が行われます。そして一致する場合は tail_pos が求まります（tail_pos = eq_len - 2）。

ただ、この処理は、不一致した際のパターンの比較位置が pattern_pos + 1 である時に最初に行われる tail_pos を求める処理と同じものになります。

pattern_pos=5の時に２回目に実行される処理とpattern_pos=6の時に１回目に実行される処理が同じであることを示す図

また、上記で pattern[0] 〜 pattern[eq_len - 2] と pattern[pattern_len - eq_len + 1] 〜 pattern[pattern_len - 1] が一致しなかった場合は、さらに２つの文字列の文字数を短くして同様の処理が行われることになります。

ただし、ここで行われる処理は、先ほどと同じように、不一致した際のパターンの比較位置が pattern_pos + 1 の時に２回目に行われる処理と同じです（不一致した際のパターンの比較位置が pattern_pos + 2 の時に１回目に行われる処理とも同じ）。

pattern_pos=5の時に３回目に実行される処理とpattern_pos=6の時に２回目に実行される処理が同じであることを示す図

上の図の場合は tail_pos が求まっているので、この時点で table2[pattern_pos] に格納する移動文字数が決まることになりますが、tail_pos が求まらない場合はさらに２つの文字列の文字数を短くして同様の処理を行なっていく必要があります。ただし、その処理も pattern_pos + 1 に対する tail_pos を求める際に行ういずれかの処理と同じになります。

つまり、不一致した際のパターンの比較位置が pattern_pos である場合に tail_pos を求めるために行う処理の２回目以降の繰り返しは、パターンの比較位置が pattern_pos + 1 である場合に tail_pos を求めるために行う処理と全く同じになります。

であれば、事前にパターンの比較位置が pattern_pos + 1 である場合の tail_pos を求めるための処理を行なって tail_pos を求めておき、それを覚えておけば、パターンの比較位置が pattern_pos である場合に tail_pos を求めるために２回目以降の繰り返しの処理が必要であるとしても、その処理は行わずに、パターンの比較位置が pattern_pos + 1 である場合の tail_pos をそのまま利用すれば良いことになります。

まとめると、パターンの比較位置を大きな値から降順に移動文字数を求めるようにすれば、パターンの比較位置が pattern_pos である場合の tail_pos は、pattern[0] 〜 pattern[eq_len - 1] と pattern[pattern_len - eq_len] 〜 pattern[pattern_len - 1] の文字列が一致する場合は eq_len - 1、それ以外の場合はパターンの比較位置が pattern_pos + 1 の場合の tail_pos として求めることができます。

このような tail_pos の求め方は、各 pattern_pos に対する tail_pos を格納する配列を tail_pos_arr とすれば、下記のように処理を行うことで実現することができます（pattern_pos + 1 と pattern_len - eq_len は同じ値になります）。

  1. tail_pos_arr の全ての要素を -1 にする
  2. pattern_pos を pattern_len - 2 とする
  3. eq_len を pattern_len - 1 - pattern_pos とする
  4. pattern[0] から始まる文字列と pattern[pattern_pos + 1] から始まる文字列が eq_len 文字数分一致するかどうかを判断する
    •  一致する場合：
      • tail_pos を eq_len - 1 とする
    • 一致しない場合：
      • tail_pos を tail_pos_arr[pattern_pos + 1] とする
  5. tail_pos_arr[pattern_pos] を tail_pos とする
    • （table2[pattern_pos - 1] を求める時のために覚えておく）
  6. tail_pos が -1 でない場合のみ下記を実行
    • table2[pattern_pos] を pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos とする
  7. pattern_pos-- を行う
  8. pattern_pos が 0 以上なら 2. に戻り、それ以外の場合は終了する

tail_pos が -1 の場合は条件を満たさないことを意味するため、その場合は table2[pattern_pos] への移動文字数の格納は行わないようにしています。

また、pattern_pos が pattern_len - 1 の場合は eq_len が 0 になるため、この場合も処理を行わないようにしています（なので pattern_pos の初期値は pattern_len - 2 としている）。

コードとして実装すれば下記のようになります。6. は table2[pattern_pos] が -1 の場合のみ実行するようにしています。また、MAX_PATTERN はパターンとして扱う文字列の最大文字数としています。

3. に対する移動文字数の設定(配列利用) 
int tail_pos_arr[MAX_PATTERN];

for (int pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {
    tail_pos_arr[pattern_pos] = -1;
}

int tail_pos;
for (int pattern_pos = pattern_len - 2; pattern_pos >= 0; pattern_pos--) {
    int eq_len = pattern_len - 1 - pattern_pos;

    /* pattern[0]から始まる文字列とpattern[pattern_pos + 1]から始まる文字列が
       eq_len文字数分一致するかどうかを確認 */
    int i = 0;
    while (
        i < eq_len &&
        pattern[i] == pattern[pattern_pos + 1 + i]
    ) {
        i++;
    }

    if (eq_len == i) {
        /* eq_len文字数分一致する場合 */
        tail_pos = eq_len - 1;
    } else {
        /* eq_len文字数分一致しない場合 */
        tail_pos = tail_pos_arr[pattern_pos + 1];
    }

    tail_pos_arr[pattern_pos] = tail_pos;

    if (table2[pattern_pos] == -1) {
        /* 2. に対する移動文字数設定が行われていない場合のみ */
        if (tail_pos != -1) {
            table2[pattern_pos] = 
                pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos;
        }
    }
}

上記によって移動文字数を求めて table2 の要素に格納していくことはできるのですが、table2[pattern_pos] の値を計算する際に必要なのは tail_pos_arr[pattern_pos + 1] のみですので、わざわざ配列 tail_pos_arr を利用しなくても次のように実装して同様の処理を実現することも可能です。

3. に対する移動文字数の設定 
int tail_pos = -1;
for (int pattern_pos = pattern_len - 2; pattern_pos >= 0; pattern_pos--) {
    int eq_len = pattern_len - 1 - pattern_pos;

    /* pattern[0]から始まる文字列とpattern[pattern_pos + 1]から始まる文字列が
       eq_len文字数分一致するかどうかを確認 */
    int i = 0;
    while (
        i < eq_len &&
        pattern[i] == pattern[pattern_pos + 1 + i]
    ) {
        i++;
    }

    if (eq_len == i) {
        /* eq_len文字数分一致する場合 */
        tail_pos = eq_len - 1;
    }

    if (table2[pattern_pos] == -1) {
        /* 2. に対する移動文字数設定が行われていない場合のみ */
        if (tail_pos != -1) {
            table2[pattern_pos] = 
                pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos;
        }
    }
}

要は、tail_pos に pattern_pos + 1 の時の値を保持させておき、必要に応じて pattern_pos に対する tail_pos を求める際にその値を利用するようにしています。

考え方として分かりやすいかなぁと思って配列を利用する場合の実装も紹介しましたが、配列を利用しなくても良い分メモリ使用量も減らすことができるため、配列を利用しない実装の方がオススメです。

4. に対する移動文字数の設定

ここまでの処理により、パターンの末尾の文字列がパターンの他の部分に存在する場合 で示した条件を満たす位置と パターンの末尾の文字列がパターンの先頭にも存在する場合 で示した条件を満たす位置に対する table2 の要素に移動文字数が設定されたことになります。

最後に、まだ格納されている値が -1 である要素に対し、移動文字数を設定しておきます。

これは下記の処理によって行うことができます。

4. に対する移動文字数の設定 
for (int pattern_pos = pattern_len - 2; pattern_pos >= 0; pattern_pos--) {
    if (table2[pattern_pos] == -1) {
        table2[pattern_pos] = pattern_len + (pattern_len - 1 - pattern_pos);
    }
}

ちなみに、上記の処理は、3. に対する移動文字数の設定 の最後に紹介したコードの下記部分において、tail_pos を -1 とした場合と全く同じものになります。

3. に対する移動文字数の設定の一部 
table2[pattern_pos] = 
    pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos;

したがって、3. に対する移動文字数の設定 の最後に紹介したコードを下記のように書き換えれば、わざわざ別のループを組まなくても 4. に対する移動文字数の設定を実現することができます。

3. と 4. に対する移動文字数の設定 
int tail_pos = -1;
for (int pattern_pos = pattern_len - 2; pattern_pos >= 0; pattern_pos--) {
    int eq_len = pattern_len - 1 - pattern_pos;

    /* pattern[0]とpattern[pattern_pos + 1]がeq_len文字数分一致するかどうかを確認 */
    int i = 0;
    while (
        i < eq_len &&
        pattern[i] == pattern[pattern_pos + 1 + i]
    ) {
        i++;
    }

    if (eq_len == i) {
        /* eq_len文字数分一致する場合 */
        tail_pos = eq_len - 1;
    }

    if (table2[pattern_pos] == -1) {
        /* 2. に対する移動文字数設定が行われていない場合のみ */
        table2[pattern_pos] = 
           pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos;
    }
}

ループを分けて記述するか一緒に記述するかの違いだけなので、どちらで実装して 4. に対する移動文字数の設定を行なっても問題ありません。

以上で table2 が完成したことになります。

table2[pattern_len - 1] が -1 のままになっていますが、これは pattern_len - 1 で不一致した場合は一致したテキストの文字数が 0 であり、上記の考え方では移動文字数が求められないためです。

ですが、table2[pattern_len - 1] を負の値にしておくことで、pattern_len - 1 で不一致した場合は table1 の方の移動文字数が必ず使用されることになり、これによって辻褄が合って正常に文字列検索を行うことができます。

スポンサーリンク

BM 法（完全版）のサンプルプログラム

長かったですが、BM 法の解説は以上となります。

あとは、文字の不一致が発生した際に、BM 法（簡略版）のずらし表の作り方 で作成した table1 と BM 法（完全版）のずらし表の作成 で作成した table2 それぞれを参照し、大きい方の移動文字数だけテキストの比較位置 text_pos を増加させるようにすれば良いだけです（table1 には（参考）ずらし表の参照のみで text_pos を決定する で紹介したものを利用しても良いです）。

ちなみに、BM 法（完全版）のずらし表の作成 で作成した table2 において table2[pattern_len - 1] は -1 のままになっているため、不一致した際のパターンの比較位置が pattern_len - 1 の場合は、必ず table1 から参照した移動文字数が使用されることになります。

また、table1 の添字は不一致した際のテキストの文字であり、table2 の添字は不一致した際のパターンの比較位置であることに注意してください。

以上を踏まえた、BM 法（完全版）のサンプルプログラムのソースコード例は下記のようになります。main 関数等は省略していますので、必要に応じて 力まかせ法の復習 で紹介したソースコードを参照してください。

BM法(完全版) 
#define MAX_PATTERN 256

void makeTable1(int table1[], char pattern[], int pattern_len) {

    for (int c = 0; c < 256; c++) {
        table1[c] = pattern_len;
    }

    for (int pos = 0; pos < pattern_len; pos++) {
        table1[pattern[pos]] = pattern_len - 1 - pos;
    }
}

void makeTable2(int table2[], char pattern[], int pattern_len) {

    for (int pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {
        table2[pattern_pos] = -1;
    }

    for (int tail_pos = 0; tail_pos < pattern_len - 1; tail_pos++) {

        int eq_len = 0;

        while (
            eq_len < tail_pos &&
            pattern[tail_pos - eq_len] == pattern[pattern_len - 1 - eq_len]
        ) {

            eq_len++;
        }

        if (eq_len == 0) {
            continue;
        }

        if (pattern[tail_pos - eq_len] != pattern[pattern_len - 1 - eq_len]) {
            table2[pattern_len - 1 - eq_len] = pattern_len - 1 - tail_pos + eq_len;
        }
    }

    int tail_pos = -1;
    for (int pattern_pos = pattern_len - 2; pattern_pos >= 0; pattern_pos--) {
        int eq_len = pattern_len - 1 - pattern_pos;

        int i = 0;
        while (
            i < eq_len &&
            pattern[i] == pattern[pattern_pos + 1 + i]
        ) {
            i++;
        }

        if (eq_len == i) {
            tail_pos = eq_len - 1;
        }

        if (table2[pattern_pos] == -1) {
            if (tail_pos != -1) {
                table2[pattern_pos] = 
                    pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos;
            }
        }
    }

    for (int pattern_pos = pattern_len - 2; pattern_pos >= 0; pattern_pos--) {
        if (table2[pattern_pos] == -1) {
            table2[pattern_pos] = pattern_len + (pattern_len - 1 - pattern_pos);
        }
    }
}

int bmSearch(char text[], int text_len, char pattern[], int pattern_len) {
    int text_pos; /* テキストの比較位置 */
    int pattern_pos; /* パターンの比較位置*/
    int table1[256];
    int table2[MAX_PATTERN];

    makeTable1(table1, pattern, pattern_len);
    makeTable2(table2, pattern, pattern_len);

    /* パターンの比較位置を末尾にセット */
    pattern_pos = pattern_len - 1;

    /* テキストの比較位置をパターンの末尾の位置にセット */
    text_pos = pattern_len - 1;

    /* テキストの比較位置がテキストの最後を超えるまでループ */
    while (text_pos < text_len) {

        /* テキストの比較位置の文字とパターンの比較位置の文字が一致するかを判断 */
        if (text[text_pos] == pattern[pattern_pos]) {
            /* 一致した場合 */

            /* パターンの先頭の文字までテキストの文字が一致したかどうかを判断 */
            if (pattern_pos == 0) {
                /* パターンが存在するテキストの位置を返却 */
                return text_pos;
            }

            /* テキストとパターンの比較位置を１文字分前側に移動する */
            text_pos--;
            pattern_pos--;

        } else {
            /* 不一致した場合 */

            if (table1[text[text_pos]] > table2[pattern_pos]) {
                text_pos += table1[text[text_pos]];
            } else {
                text_pos += table2[pattern_pos];
            }

            /* パターンの比較位置を末尾に戻す */
            pattern_pos = pattern_len - 1;
            
        }
    }

    /* パターンが見つからなかった場合は-1を返却 */
    return -1;
}

bmSearch 関数が、BM 法により引数で受け取った text の中から pattern を探し出す関数であり、text と pattern の文字数はそれぞれ text_len と pattern_len となります。

table2 のサイズを MAX_PATTERN としている点に注意してください。パターンの文字列の文字数が MAX_PATTERN を超える場合は MAX_PATTERN の定義値も増やす必要があります。

また、文字が不一致した際のテキストの比較位置 text_pos の移動は bmSearch 関数の下記部分で行っており、前述の通り table1 と table2 の参照結果が大きいほうの値を用いてテキストの比較位置 text_pos を移動させるようにしています。

テキストの比較位置の移動 
if (table1[text[text_pos]] > table2[pattern_pos]) {
    text_pos += table1[text[text_pos]];
} else {
    text_pos += table2[pattern_pos];
}

table2 は bmSearch 関数の先頭部分で makeTable2 関数を呼び出すことで作成しています。makeTable2 関数で行っていることは BM 法（完全版）のずらし表の作成 にて解説していますので、何をやっているか分からない場合は BM 法（完全版）のずらし表の作成 を参照していただければと思います。

BM 法の計算量

特に BM 法の簡略版の仕組みから分かるように、不一致したテキストの文字がパターン内に存在しない場合は非常に検索効率が良いです。この場合、一気にパターンの文字数分、テキストの比較位置を移動させることができます。

ですので BM 法は、テキストやパターンで用いられる文字の種類が多いほど検索効率が高い検索アルゴリズムということができるでしょう。最良の場合、BM 法の計算量のオーダーは O (N / M) となります（N はテキストの文字数、M はパターンの文字数）。

実際の英文などでも用いられる文字の種類は多いので、実用性の高い検索アルゴリズムということができます。

ただし、BM 法の簡略版の場合、毎回最後のパターンとの比較、すなわちパターンの先頭の文字との比較で不一致が発生するような場合、計算量のオーダーは O (N * M) にまで悪化してしまいます（といっても、このようなケースは稀です）。

BM法の簡略版では最悪の計算量が力まかせ法と同じになってしまうことを示す図

それに対し、BM 法の完全版の場合は、パターンの先頭の文字との比較で不一致した場合でも一気にテキストの比較位置を進めることができるケースがあります。そして、これにより最悪パターンにおいても計算量のオーダーが O (N) となるようです（参考）。

BM法の完全版では最悪の計算量が力まかせ法よりも改善されることを示す図

まとめ

このページでは、文字列検索アルゴリズムの１つである「ボイヤー – ムーア法」、略して BM 法について解説しました！

パターンの後ろ側から文字の比較を行うことを利用したアルゴリズムであり、不一致した際にどんどんテキストの比較位置を後ろ側に移動させることができます。

特に一般的なテキストやパターンにおいて効率の良い検索アルゴリズムとなります。

特に簡略版の BM 法の考え方や実装の仕方はそれなりに分かりやすいのではないかと思います。要は不一致したテキストの文字を利用し、無駄な比較をスキップするようにテキストの比較位置を移動しているだけです。

ただ、完全版まで理解して実装しようと思うと結構難しいかなぁと思います。さらに、ずらし表を作成する際のループの組み方が悪いと、ずらし表を作成するのに時間がかかって逆に力まかせ法よりも検索が遅くなる可能性もあるので注意してください。

BM 法は簡略版でも十分高速なアルゴリズムですし、まずは簡略法を実現し、興味があれば完全版について挑戦してみていただくのが良いと思います！

また、文字列検索アルゴリズムには BM 法だけでなく色んなアルゴリズムがあります。その１つの KMP 法については下記ページで解説していますので、KMP 法について詳しく知りたい方は是非下記ページも読んでみてください！

KMP法の解説ページアイキャッチ KMP法についてわかりやすく解説（C言語サンプル付き）

同じカテゴリのページ一覧を表示

前の記事

最小公倍数の求め方の解説ページアイキャッチ
【C言語】最小公倍数の求め方（３つ以上も可）

次の記事

【C言語/アルゴリズム】深さ優先探索と幅優先探索
深さ優先探索と幅優先探索の解説ページアイキャッチ