ボイヤー・ムーア法の不良文字ヒューリスティックとは？仕組みとC++実装例を解説

不良文字ヒューリスティックとは

不良文字ヒューリスティック（Bad Character Heuristic）は、文字列検索アルゴリズムの一つであるボイヤー・ムーア法（Boyer-Moore Algorithm）で用いられる手法のひとつです。ボイヤー・ムーア法には、このほかに「良好接尾辞ヒューリスティック（Good Suffix Heuristic）」というアプローチもあります。

この手法では、テキスト（主文字列）側の文字のうち、パターンと一致しない文字、すなわち「不良文字（Bad Character）」を見つけます。不一致が発生した場合、その不一致箇所が一致するようにパターン全体をシフトします。それが不可能な場合は、パターンが不良文字の位置を通り越すまでシフトを行います。

計算量は、最良の場合で O(m/n)、最悪の場合で O(mn) となります。ここで n はテキストの長さ、m はパターンの長さを表します。

不良文字ヒューリスティックの仕組み

不一致が見つかったときのシフト量は、次のように決まります。

• 不一致文字がパターン内に存在する場合：パターン内でその文字が最後に出現する位置と不一致位置が重なるように、パターンを右へシフトします。
• 不一致文字がパターン内に存在しない場合：不一致文字の位置をパターンが完全に通り越すまでシフトします。
• シフト量が 0 以下になる場合：比較位置が後退しないよう、最低でも 1 文字分シフトします（max(1, ...) の処理）。

入力と出力

Input:
Main String: "ABAAABCDBBABCDDEBCABC", Pattern: "ABC"
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

※出力される位置は 0 起点のインデックスです。

アルゴリズム

badCharacterHeuristic（不良文字配列の構築）

入力：検索対象のパターン、位置を格納するための不良文字配列

出力：後の検索処理で使用できるよう、不良文字配列を埋める

Begin
    n := パターンの長さ
    badCharacterArray のすべての要素について
        すべての要素を -1 に設定
    done

    パターンのすべての文字について
        各文字の最後の出現位置を badCharacterArray に設定
    done
End

searchPattern（パターン検索）

入力：検索するパターンと主文字列（テキスト）

出力：パターンが見つかった位置

Begin
    patLen := パターンの長さ
    strLen := テキストの長さ
    badCharacterHeuristic(pattern, badCharacterArray) を呼び出す
    shift := 0

    shift <= (strLen - patLen) の間繰り返す
        j := patLen - 1
        j >= 0 かつ pattern[j] = text[shift + j] の間繰り返す
            j を 1 減らす
        done
        もし j < 0 ならば
            一致したので shift の位置を出力
            もし shift + patLen < strLen ならば
                shift := shift + patLen - badCharacterArray[text[shift + patLen]]
            そうでなければ
                shift を 1 増やす
        そうでなければ
            shift := shift + max(1, j - badCharacterArray[text[shift+j]])
    done
End

C++による実装例

#include<iostream>
#define MAXCHAR 256
using namespace std;

int maximum(int data1, int data2) {
    if(data1 > data2)
        return data1;
    return data2;
}

void badCharacterHeuristic(string pattern, int badCharacter[MAXCHAR]) {
    int n = pattern.size();                    // パターンの長さを求める
    for(int i = 0; i<MAXCHAR; i++)
        badCharacter[i] = -1;                  // すべての文字の距離を -1 に初期化

    for(int i = 0; i < n; i++) {
        badCharacter[(int)pattern[i]] = i;     // 配列に各文字の位置を設定
    }
}

void searchPattern(string mainString, string pattern, int *array, int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int badCharacter[MAXCHAR];                 // 不良文字の位置を格納する配列
    badCharacterHeuristic(pattern, badCharacter);  // 不良文字配列を構築
    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;

            if((shift + patLen) < strLen) {
                shift += patLen - badCharacter[mainString[shift + patLen]];
            }else {
                shift += 1;
            }
        }else {
            shift += maximum(1, j - badCharacter[mainString[shift+j]]);
        }
    }
}

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

まとめ

不良文字ヒューリスティックは、不一致が発生した位置の情報を活かして無駄な比較を減らし、高速な文字列検索を実現する手法です。テキストが長くパターンが短い場合に特に効果を発揮します。実務では、より安定した検索性能を得るために、良好接尾辞ヒューリスティックと組み合わせて使われるのが一般的です。