パターンをトライへまとめる
Aho–Corasick法は複数のパターンを前処理して一つのオートマトンへまとめ、本文を順に読みます。まずパターン集合の共通接頭辞を共有するトライを作ります。各状態は、ここまで読んだ本文の接尾辞として一致しているパターン接頭辞を表します。単にトライで一本のパターンを探すだけでは、不一致のときに再開する情報が不足します。そこで現在の文字列の最長の真の接尾辞で、ほかのトライ状態として存在するものへ失敗リンクを張ります。
heとsheを同じ位置で報告する
パターン集合をhe、she、his、hersとし、本文ushersを読みます。sheを読み終えた状態ではsheだけでなく、その接尾辞heも一致しています。その後のr、sでhersの一致も分かり、0始まりの位置はsheが1、heが2、hersが2です。終端状態そのものだけを見て出力するとheを落とすため、失敗リンクの先にある終端の出力も扱います。複数のパターンが同じ位置で終わることや、一つの文字が複数の一致に関わることは正常な動作です。
失敗リンクと出力の費用
失敗リンクは通常、トライの浅い状態から幅優先で構築します。検索時に直接の遷移がなければ失敗リンクをたどって候補を短くし、使える遷移を探します。アルファベットや遷移の表現を固定して定数時間に扱える条件では、本文長nと報告件数zに対しO(n+z)の検索を説明できます。出力件数を無視して常にO(n)とは言えません。また、失敗先の全出力一覧を各状態へ無制限にコピーすると、前処理や領域が膨らむため、出力リンクなどの設計を明記します。
辞書の更新と入力の定義
遷移を全アルファベットについて配列化する場合、状態数にアルファベットの大きさを掛けた領域が必要です。疎な辞書で辺を持つ場合には、検索や構築に使う辞書操作の費用を数えます。パターン追加で失敗リンクや出力関係の更新が必要になり、完成した索引へ単純に枝を足すだけでは済まない場合があります。空パターンを許すなら全境界への一致を別途定義し、同じパターンを複数IDで登録する場合の出力仕様も決めます。検出が必要なのは部分文字列なのか単語全体なのかも、アルゴリズムの外で区別します。