C++で実装するAho-Corasickアルゴリズム――複数パターンを同時に検索する強力な手法

この記事では、入力文字列とキーワード配列 arr[] が与えられた際に、文字列中に出現する配列内の全単語の位置を検出する問題を扱います。これを解決するために使用するのがAho-Corasick(エイホ・コラシック)アルゴリズムです。

文字列やパターンの検索はプログラミングにおいて非常に重要なテーマであり、優れたアルゴリズムほど実用的な応用範囲が広がります。Aho-Corasickアルゴリズムは、文字列検索を容易にする非常に重要かつ強力なアルゴリズムです。いわば辞書マッチング型のアルゴリズムで、複数の文字列を一度に同時照合できる点が最大の特徴です。実装にはTrie(トライ)データ構造が用いられます。

Trie(トライ)データ構造とは

Trieとは、接頭辞木(プレフィックスツリー)やデジタル探索木とも呼ばれるデータ構造で、各辺に1文字のラベルが付けられています。同一ノードから出る辺には、必ず異なる文字が割り当てられます。

Aho-Corasickアルゴリズムの動作を例で確認

入力:

string = "bheythisghisanexample"
arr[] = {"hey", "this", "is", "an", "example"}

出力:

Word hey starts from 2
Word this starts from 5
Word is starts from 11
Word an starts from 13
Word example starts from 15

このように、テキスト中のどの位置から各単語が始まるのかを一括して取得できます。このアルゴリズムの計算量はO(N+L+Z)です。それぞれの記号は以下を意味します。

• N: 入力文字列(テキスト)の長さ
• L: キーワード(配列内の単語)の長さの合計
• Z: マッチした件数

実装の全体像

Aho-Corasickアルゴリズムは、次の簡単なステップで構築できます。

• キューを利用してTrieを構築し、各文字をキューからポップしてTrieのノードとして登録する。
• 次の文字と現在の文字を保持できるよう、失敗リンク(サフィックスリンク)を配列として構築する。
• マッチした単語を保存するため、出力リンクを配列として構築する。
• すべての文字を処理するための遷移関数(FindNextState)を実装する。

失敗リンク(サフィックスリンク): 文字を読み進められなくなった地点に到達したとき、可能な限り多くの文脈を保持するために失敗リンクを辿って後退します。端的に言えば、現在の文字に対応する辺がTrie上に存在しない場合に、代わりに辿るべき辺をすべて格納したものです。

出力リンク: 現在の状態に存在する最長の単語に対応するノードを常に指す仕組みで、これによりすべてのパターンを出力リンクで連結することが保証されます。

C++実装例

以下は、C++でAho-Corasickアルゴリズムを実装した完全なサンプルコードです。

#include<iostream>
#include <string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int MaxStates = 6 * 50 + 10;
const int MaxChars = 26;
int OccurenceOfWords[MaxStates];
int FF[MaxStates];
int GotoFunction[MaxStates][MaxChars];
int BuildMatchingMachine(const vector<string> &words, char lowestChar = 'a', char highestChar = 'z'){
    memset(OccurenceOfWords, 0, sizeof OccurenceOfWords);
    memset(FF, -1, sizeof FF);
    memset(GotoFunction, -1, sizeof GotoFunction);
    int states = 1;
    for (int i = 0; i < words.size(); ++i){
        const string &keyword = words[i];
        int currentState = 0;
        for (int j = 0; j < keyword.size(); ++j){
            int c = keyword[j] - lowestChar;
            if (GotoFunction[currentState][c] == -1){
                GotoFunction[currentState][c] = states++;
            }
            currentState = GotoFunction[currentState][c];
        }
        OccurenceOfWords[currentState] |= (1 << i);
    }
    for (int c = 0; c < MaxChars; ++c){
        if (GotoFunction[0][c] == -1){
            GotoFunction[0][c] = 0;
        }
    }
    queue<int> q;
    for (int c = 0; c <= highestChar - lowestChar; ++c){
        if (GotoFunction[0][c] != -1 && GotoFunction[0][c] != 0){
            FF[GotoFunction[0][c]] = 0;
            q.push(GotoFunction[0][c]);
        }
    }
    while (q.size()){
        int state = q.front();
        q.pop();
        for (int c = 0; c <= highestChar - lowestChar; ++c){
            if (GotoFunction[state][c] != -1){
                int failure = FF[state];
                while (GotoFunction[failure][c] == -1){
                    failure = FF[failure];
                }
                failure = GotoFunction[failure][c];
                FF[GotoFunction[state][c]] = failure;
                OccurenceOfWords[GotoFunction[state][c]] |= OccurenceOfWords[failure];
                q.push(GotoFunction[state][c]);
            }
        }
    }
    return states;
}
int FindNextState(int currentState, char nextInput, char lowestChar = 'a'){
    int answer = currentState;
    int c = nextInput - lowestChar;
    while (GotoFunction[answer][c] == -1){
        answer = FF[answer];
    }
    return GotoFunction[answer][c];
}
vector<int> FindWordCount(string str, vector<string> keywords, char lowestChar = 'a', char highestChar = 'z') {
    BuildMatchingMachine(keywords, lowestChar, highestChar);
    int currentState = 0;
    vector<int> retVal;
    for (int i = 0; i < str.size(); ++i){
        currentState = FindNextState(currentState, str[i], lowestChar);
        if (OccurenceOfWords[currentState] == 0)
            continue;
        for (int j = 0; j < keywords.size(); ++j){
            if (OccurenceOfWords[currentState] & (1 << j)){
                retVal.insert(retVal.begin(), i - keywords[j].size() + 1);
            }
        }
    }
    return retVal;
}
int main(){
    vector<string> keywords;
    keywords.push_back("All");
    keywords.push_back("she");
    keywords.push_back("is");
    string str = "Allisheall";
    cout<<"The occurrences of all words in the string ' "<<str<<" ' are \n";
    vector<int> states = FindWordCount(str, keywords);
    for(int i=0; i < keywords.size(); i++){
        cout<<"Word "<<keywords.at(i)<<' ';
        cout<<"starts at "<<states.at(i)+1<<' ';
        cout<<"And ends at "<<states.at(i)+keywords.at(i).size()+1<<endl;
    }
}

実行結果

The occurrences of all words in the string ' Allisheall ' are
Word All starts at 5 And ends at 8
Word she starts at 4 And ends at 7
Word is starts at 1 And ends at 3

この例では、"Allisheall" という文字列から "All"、"she"、"is" の3つのキーワードについて、それぞれの出現開始位置と終了位置を正しく検出できています。Aho-Corasickアルゴリズムを活用すれば、大量のキーワードを含む大規模テキスト検索でも、テキスト長に対してほぼ線形時間で処理が可能になります。ウイルススキャン、不適切語フィルタリング、DNA配列解析など、多様な分野で応用されている強力な手法です。