アルゴリズム・データ構造図鑑 · 基礎から応用へ

Aho–Corasick法:複数パターンを一つの探索状態で追う

トライと失敗リンク・出力リンクを組み合わせ、接尾辞になっている別パターンも見落とさず報告する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. パターンをトライへまとめる
  2. heとsheを同じ位置で報告する
  3. 失敗リンクと出力の費用
  4. 辞書の更新と入力の定義
  5. この記事をロゲイアに質問する理解を確かめる

パターンをトライへまとめる

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で登録する場合の出力仕様も決めます。検出が必要なのは部分文字列なのか単語全体なのかも、アルゴリズムの外で区別します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ