Aho-Corasickアルゴリズム：複数キーワードの高速検索を実現する仕組みと実装

Aho-Corasickアルゴリズムは、複数のキーワード（パターン）をテキスト内で同時に検索するための効率的な辞書照合アルゴリズムです。トライ木（プレフィックスツリー）とオートマトンの概念を組み合わせることで、テキストの長さに対して線形時間 O(N + L + Z) で全てのキーワードの出現位置を見つけ出せます。ここで N はテキスト長、L は全キーワードの総文字数、Z はマッチ数を表します。

アルゴリズムの3つのフェーズ

Aho-Corasickアルゴリズムは以下の3段階で構成されます。

• Go-to（遷移）フェーズ：全キーワードからトライ木を構築し、文字ごとの状態遷移を定義します。
• Failure（失敗）フェーズ：マッチしない場合にどこへ戻るか（最長の真の接尾辞が接頭辞となる状態）を示す失敗リンクを、幅優先探索で構築します。
• Output（出力）フェーズ：各状態で終了するキーワードの集合を記録します。失敗リンクを辿って得られる出力もマージします。

入力と出力の例

入力:
パターン集合: {their, there, answer, any, bye}
検索対象文字列: "isthereanyanswerokgoodbye"

出力:
Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22

アルゴリズムの詳細

buildTree(patternList, size) ― オートマトンの構築

入力: パターンのリストとそのサイズ
出力: 状態遷移テーブル（goto）、失敗関数（fail）、出力関数（output）

Begin
  output配列を全て0で初期化
  fail配列を全て-1で初期化
  goto行列を全て-1で初期化
  state := 1  // 状態0はルート

  // 1. Go-toフェーズ: トライ木の構築
  for 各パターン i in patternList do
    word := patternList[i]
    present := 0
    for 各文字 ch in word do
      if goto[present, ch] == -1 then
        goto[present, ch] := state
        state := state + 1
      present := goto[present, ch]
    output[present] := output[present] OR (1 << i)  // ビットマスクでパターンを記録
  done

  // 2. ルートからの遷移を初期化
  for 全文字 ch do
    if goto[0, ch] != 0 then
      fail[goto[0, ch]] := 0
      goto[0, ch] をキュー q に挿入
    else
      goto[0, ch] := 0  // ルートへの自己ループ
  done

  // 3. Failureフェーズ & Outputフェーズ: BFSで失敗リンクを構築
  while q が空でない do
    newState := q の先頭要素を取り出し
    for 全文字 ch do
      if goto[newState, ch] != -1 then
        failure := fail[newState]
        while goto[failure, ch] == -1 do
          failure := fail[failure]
        done
        fail[goto[newState, ch]] := goto[failure, ch]
        output[goto[newState, ch]] := output[goto[newState, ch]] OR output[failure]
        goto[newState, ch] を q に挿入
      done
    done
  done
  return state
End

getNextState(presentState, nextChar) ― 次状態の取得

入力: 現在の状態と次の文字
出力: 次の状態

Begin
  answer := presentState
  ch := nextChar
  while goto[answer, ch] == -1 do
    answer := fail[answer]
  done
  return goto[answer, ch]
End

patternSearch(patternList, size, text) ― パターン検索の実行

入力: パターンリスト、サイズ、検索対象テキスト
出力: マッチしたパターンの位置

Begin
  call buildTree(patternList, size)
  presentState := 0

  for テキストの各インデックス i do
    presentState := getNextState(presentState, text[i])
    if output[presentState] != 0 then
      for 各パターン j in patternList do
        if output[presentState] の j ビット目が立っている then
          位置 i - length(patternList[j]) + 1 を出力
        done
      done
    done
  done
End

C++ 実装例

以下はアルファベット小文字（26文字）に対応した実装です。ビットマスクで出力を管理し、キューを用いて失敗リンクを効率的に構築しています。

#include <iostream>
#include <queue>
#include <string>
#define MAXS 500  // 全パターンの文字数合計の上限
#define MAXC 26   // アルファベット数
using namespace std;

int output[MAXS];
int fail[MAXS];
int gotoMat[MAXS][MAXC];

int buildTree(string array[], int size) {
  // 初期化
  for (int i = 0; i < MAXS; i++) output[i] = 0;
  for (int i = 0; i < MAXS; i++) fail[i] = -1;
  for (int i = 0; i < MAXS; i++)
    for (int j = 0; j < MAXC; j++)
      gotoMat[i][j] = -1;

  int state = 1;

  // トライ木の構築
  for (int i = 0; i < size; i++) {
    string word = array[i];
    int presentState = 0;
    for (int j = 0; j < word.size(); ++j) {
      int ch = word[j] - 'a';
      if (gotoMat[presentState][ch] == -1) {
        gotoMat[presentState][ch] = state++;
      }
      presentState = gotoMat[presentState][ch];
    }
    output[presentState] |= (1 << i);
  }

  // ルートからの遷移を設定
  for (int ch = 0; ch < MAXC; ++ch) {
    if (gotoMat[0][ch] == -1)
      gotoMat[0][ch] = 0;
  }

  queue<int> q;
  // 深さ1のノードの失敗リンクはルート
  for (int ch = 0; ch < MAXC; ++ch) {
    if (gotoMat[0][ch] != 0) {
      fail[gotoMat[0][ch]] = 0;
      q.push(gotoMat[0][ch]);
    }
  }

  // BFSで失敗リンクを構築
  while (!q.empty()) {
    int state = q.front();
    q.pop();

    for (int ch = 0; ch < MAXC; ++ch) {
      if (gotoMat[state][ch] != -1) {
        int failure = fail[state];
        while (gotoMat[failure][ch] == -1)
          failure = fail[failure];
        failure = gotoMat[failure][ch];
        fail[gotoMat[state][ch]] = failure;
        output[gotoMat[state][ch]] |= output[failure];
        q.push(gotoMat[state][ch]);
      }
    }
  }
  return state;
}

int getNextState(int presentState, char nextChar) {
  int answer = presentState;
  int ch = nextChar - 'a';
  while (gotoMat[answer][ch] == -1)
    answer = fail[answer];
  return gotoMat[answer][ch];
}

void patternSearch(string arr[], int size, string text) {
  buildTree(arr, size);
  int presentState = 0;

  for (int i = 0; i < text.size(); i++) {
    presentState = getNextState(presentState, text[i]);
    if (output[presentState] == 0) continue;
    for (int j = 0; j < size; ++j) {
      if (output[presentState] & (1 << j)) {
        cout << "Word " << arr[j] << " location: "
             << i - arr[j].size() + 1 << endl;
      }
    }
  }
}

int main() {
  string arr[] = {"their", "there", "answer", "any", "bye"};
  string text = "isthereanyanswerokgoodbye";
  int k = sizeof(arr) / sizeof(arr[0]);
  patternSearch(arr, k, text);
  return 0;
}

実行結果

Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22

計算量と特徴のまとめ

Aho-Corasickアルゴリズムは、スパムフィルタ、侵入検知システム（IDS）、DNA配列解析、自然言語処理における固有表現抽出など、大量のキーワードを高速に検出する用途で広く採用されています。