C++で実装する有限状態オートマトンによる文字列検索プログラム

これは、有限状態オートマトン(Finite State Automaton)をベースに文字列検索を実行するC++プログラムの解説です。状態の数が有限であるオートマトンは「有限オートマトン(Finite Automaton)」と呼ばれます。ここでは、テキスト text[0 … t-1] とパターン p[0 … p-1] が与えられたとき、テキスト中からパターンを検索し、そのすべての出現位置(インデックス)を出力します。

アルゴリズム

まず、与えられたパターンに対して「遷移表(Transition Table)」を構築します。この表は、現在の状態と入力文字の組み合わせに応じて、次に遷移すべき状態を定義するものです。構築手順は以下の通りです。

開始
    関数 void transitiontable():
    1) 最初の行のエントリをすべて埋める。最初の行のエントリは、文字 p[0] に対応する
       エントリを除いて常に 0 となる。p[0] に対しては常に状態 1 へ遷移する必要がある。
    2) longestprefixsuffix(最長接頭辞・接尾辞の長さ)を 0 で初期化する。
    3) i = 1 から P まで繰り返す(ここで P はパターンの長さ)
       a) インデックス longestprefixsuffix の行からエントリをコピーする。
       b) 文字 p[i] に対応するエントリを i+1 に更新する。
       c) longestprefixsuffix = TT[lps][pat[i]] を更新する。
          ここで TT は構築中の2次元配列である。
終了

サンプルコード

#include<iostream>
#include<cstring>
#define NO_OF_CHARS 512
using namespace std;
// 指定されたパターンに対する有限オートマトンを表すTFテーブルを構築する
void transitiontable(char *p, int P, int TT[][NO_OF_CHARS]) {
    int i, longestprefixsuffix = 0, y;
    // 最初の行にエントリを設定する
    for (y =0; y < NO_OF_CHARS; y++)
    TT[0][y] = 0;
    TT[0][p[0]] = 1;
    // 残りの行にエントリを設定する
    for (i = 1; i<= P; i++) { // インデックスlongestprefixsuffixの行から値をコピー
        for (y = 0; y < NO_OF_CHARS; y++)
        TT[i][y] = TT[longestprefixsuffix][y];
        // エントリを更新する
        TT[i][p[i]] = i + 1;
        // 次に埋める行のためのlpsを更新する
        if (i < P)
            longestprefixsuffix = TT[longestprefixsuffix][p[i]]; // TTは構築中の2次元配列
    }
}
// テキスト中のパターンのすべての出現位置を出力する
void patternsearch(char *p, char *t) {
    int P = strlen(p);
    int T = strlen(t);
    int TT[P+1][NO_OF_CHARS];
    transitiontable(p, P, TT);
    // 有限オートマトン上でテキストを処理する
    int i, j=0;
    for (i = 0; i < T; i++) {
        j = TT[j][t[i]];
        if (j == P) {
            cout<<"\n pattern is found at index: "<< i-P+1;
        }
    }
}
int main() {
    char *text = "AABAA ABBAACCDD CCDDAABAA"; // テキストを入力
    char *pattern = "AABAA"; // パターンを入力
    patternsearch(pattern, text);
    getchar();
    return 0;
}

実行結果

pattern is found at index: 0
pattern is found at index: 20

この実行結果から、パターン「AABAA」はテキスト内のインデックス 0 と 20 の2箇所で見つかったことがわかります。

計算量のポイント

遷移表の構築には O(P × NO_OF_CHARS) の時間が必要ですが、一度表を作成してしまえば、テキストの走査は1文字につき1回の状態遷移だけで済むため、検索本体はテキスト長を T として O(T) で完了します。前処理に時間をかける代わりに検索を高速に行える点が、この手法の大きな特徴です。