ボイヤー・ムーア法のグッドサフィックス（良い接尾辞）ヒューリスティックとは？擬似コードとC++実装例で解説

ボイヤー・ムーア法にはいくつかのバリエーションがありますが、ここで紹介するのは「グッドサフィックス（良い接尾辞）ヒューリスティック」と呼ばれるアプローチです。この手法では、検索に先立って事前処理としてサフィックステーブル（接尾辞表）を作成します。

最大の特徴は、パターンの末尾の文字から照合を開始する点です。テキスト側の部分文字列がパターンの一部と一致した場合、その一致した部分が再び現れる可能性のある位置へとパターンをずらし（シフトし）ながら探索を続けます。さらに、パターンの接頭辞（プレフィックス）がテキストの接尾辞（サフィックス）と一致する箇所を探して移動することもあります。どちらにも該当しない場合は、パターン全体の長さ分をまとめて移動します。

この工夫により、不一致の際に得られた情報を無駄にせず活かせるため、比較回数を大幅に削減できるのがポイントです。

入力と出力

入力:
主文字列: “ABAAABCDBBABCDDEBCABC”、パターン: “ABC”
出力:
パターンが見つかった位置: 4
パターンが見つかった位置: 10
パターンが見つかった位置: 18

アルゴリズム

処理は大きく分けて3つの関数で構成されます。fullSuffixMatch と partialSuffixMatch が事前処理としてシフト配列とボーダー配列を構築し、searchPattern が実際の文字列検索を行います。

fullSuffixMatch(shiftArray, borderArray, pattern)

入力 − シフト位置を格納する配列、ボーダー配列、検索対象のパターン

出力 − シフト配列とボーダー配列をすべて埋める

Begin
    n := パターンの長さ
    i := n
    j := n + 1
    borderArray[i] := j

    while i > 0, do
        while j <= n かつ pattern[i-1] ≠ pattern[j-1], do
            if shiftArray[j] = 0, then
                shiftArray[j] := j - i   // i から j へパターンをシフト
            j := borderArray[j]          // ボーダーを更新
        done

        i と j をそれぞれ 1 減らす
        borderArray[i] := j
    done
End

partialSuffixMatch(shiftArray, borderArray, pattern)

入力 − シフト位置を格納する配列、ボーダー配列、検索対象のパターン

出力 − シフト配列とボーダー配列をすべて埋める

Begin
    n := パターンの長さ
    j := borderArray[0]

    for パターンの各文字のインデックス i, do
        if shiftArray[i] = 0, then
            shiftArray[i] := j       // シフトが未設定ならボーダーの値を設定
        if i = j then
            j := borderArray[j]      // ボーダーの値を更新
    done
End

searchPattern(text, pattern)

入力 − 検索対象となる主テキストとパターン

出力 − パターンが見つかったインデックス（位置）

Begin
    patLen := パターンの長さ
    strLen := テキストのサイズ

    for shiftArray の全要素, do
        すべての要素を 0 に初期化
    done

    fullSuffixMatch(shiftArray, borderArray, pattern) を呼び出す
    partialSuffixMatch(shiftArray, borderArray, pattern) を呼び出す
    shift := 0

    while shift <= (strLen - patLen), do
        j := patLen - 1
        while j >= 0 かつ pattern[j] = text[shift + j], do
            j を 1 減らす
        done

        if j < 0, then
            // パターン全体が一致した場合
            一致位置として shift を出力する
            shift := shift + shiftArray[0]
        else
            shift := shift + shiftArray[j+1]
    done
End

C++による実装例

以下は、上記のアルゴリズムをC++で実装した例です。主文字列 "ABAAABCDBBABCDDEBCABC" からパターン "ABC" を検索します。

#include<iostream>
using namespace std;

void fullSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
    int n = pattern.size();          // パターンの長さを求める
    int i = n;
    int j = n+1;
    borderArr[i] = j;

    while(i > 0) {
        // (i-1)番目と(j-1)番目の文字が異なる場合は右方向へ探索
        while(j <= n && pattern[i-1] != pattern[j-1] ) {
            if(shiftArr[j] == 0)
                shiftArr[j] = j-i;   // i から j へパターンをシフト
            j = borderArr[j];        // ボーダーを更新
        }
        i--;
        j--;
        borderArr[i] = j;
    }
}

void partialSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
    int n = pattern.size();          // パターンの長さを求める
    int j;
    j = borderArr[0];

    for(int i = 0; i<n; i++) {
        if(shiftArr[i] == 0)
            shiftArr[i] = j;         // シフトが未設定の場合はボーダーの値を設定
        if(i == j)
            j = borderArr[j];        // ボーダーの値を更新
    }
}

void searchPattern(string mainString, string pattern, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int borderArray[patLen+1];
    int shiftArray[patLen + 1];

    for(int i = 0; i<=patLen; i++) {
        shiftArray[i] = 0;           // シフト配列をすべて 0 で初期化
    }

    fullSuffixMatch(shiftArray, borderArray, pattern);
    partialSuffixMatch(shiftArray, borderArray, pattern);
    int shift = 0;

    while(shift <= (strLen - patLen)) {
        int j = patLen - 1;
        while(j >= 0 && pattern[j] == mainString[shift+j]) {
            j--;                     // パターンと主文字列の文字が一致している間は j を減らす
        }

        if(j < 0) {
            (*index)++;
            array[(*index)] = shift;
            shift += shiftArray[0];
        }else {
            shift += shiftArray[j+1];
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    searchPattern(mainString, pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i]<<endl;
    }
}

実行結果

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

パターン「ABC」は、主文字列の 4 文字目、10 文字目、18 文字目（0 始まりのインデックス）にそれぞれ見つかりました。

計算量の目安

事前処理（サフィックステーブルの構築）はパターン長 m に対して O(m) の時間で行えます。検索フェーズは、最良の場合 O(n/m) と非常に高速で、テキスト長 n に対して効率的に動作します。この特性から、ボイヤー・ムーア法はテキストエディタの検索機能や grep などの実用的な文字列検索ツールで広く採用されています。