有限オートマトンを活用した効率的な文字列パターン検索の実装

有限オートマトン(Finite Automata)を構築することで、テキストの中から特定のパターンをシンプルかつ効率的に検索することができます。

まず、2次元配列を埋めて有限オートマトンの遷移表(Transition Table)を作成します。この表さえ完成してしまえば、検索処理そのものは非常に単純です。オートマトンの初期状態から出発し、テキストを1文字ずつ読み進めながら状態を遷移させていき、最終状態に到達した時点で「その位置にパターンが存在する」と判断します。

計算量

有限オートマトンの構築に必要な時間計算量は O(M×K) です。ここで M はパターンの長さ、K は異なる文字の種類数(アルファベットのサイズ)を表します。一方、メインとなるパターン検索処理の計算量は O(n)(n はテキスト長)であり、遷移表を一度作成してしまえば、ナイーブな全走査よりも高速にマッチングを行えます。

入力と出力

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

※ 位置は 0 始まりのインデックスで表しています。

アルゴリズム

fillTransTable(pattern, transTable)

入力: パターンと、遷移情報を書き込む遷移表

出力: 完成した遷移表

Begin
    longPS := 0
    遷移表の全要素を 0 で初期化する
    transTable[0, pattern[0]] = 1    // パターンの先頭文字に対する設定

    パターン内の各文字のインデックス i について繰り返す
        すべての取り得る文字 j について
            transTable[i, j] := transTable[longPS, j]

        transTable[i, pattern[i]] := i + 1
        i がパターンのサイズ未満であれば
            longPS := transTable[longPS, pattern[i]]
End

patternSearch(text, pattern)

入力: 検索対象の主テキストとパターン

出力: パターンが見つかった位置(インデックス)

Begin
    patLen := パターンの長さ
    strLen := 文字列の長さ
    fillTransTable(pattern, transTable) を呼び出す
    present := 0

    テキスト内の各文字のインデックス i について繰り返す
        present := transTable[present, text[i]]
        present = patLen であれば
            (i − patLen + 1) をパターンの出現位置として出力する
End

C++ による実装例

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

void fillTransitionTable(string pattern, int transTable[][MAXCHAR]) {
    int longPS = 0;

    for (int i = 0; i < MAXCHAR; i++) {
        transTable[0][i] = 0;              // 初期状態のエントリを作成
    }

    transTable[0][pattern[0]] = 1;         // 先頭文字で最初の状態へ遷移
    for (int i = 1; i <= pattern.size(); i++) {

        for (int j = 0; j < MAXCHAR; j++)  // 接頭辞と接尾辞を利用して状態を更新
            transTable[i][j] = transTable[longPS][j];
        transTable[i][pattern[i]] = i + 1;
        if (i < pattern.size())
            longPS = transTable[longPS][pattern[i]]; // 次の状態向けに最長の接頭辞・接尾辞を更新
    }
}

void FAPatternSearch(string mainString, string pattern, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int transTable[patLen+1][MAXCHAR];     // パターンごとの遷移表を作成

    fillTransitionTable(pattern, transTable);
    int presentState = 0;

    for(int i = 0; i <= strLen; i++) {
        presentState = transTable[presentState][mainString[i]]; // 遷移可能なら次の状態へ
        if(presentState == patLen) {       // 現在の状態が最終状態ならパターンを発見
            (*index)++;
            array[(*index)] = i - patLen + 1;
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    FAPatternSearch(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

このように、遷移表を事前に構築しておくことで、テキストを一巡するだけでパターンのすべての出現位置を検出できます。同じパターンで大量のテキストを繰り返し検索するような場面では、前処理のコストを払っても検索を O(n) に抑えられる有限オートマトン法が特に有効です。