【エイホコラシックほう】
エイホ・コラシック法 とは？
公開:
💡 たくさんの合言葉を、ひとつの見張り役で探す
複数の文字列パターンをまとめて探すアルゴリズム。パターンをトライ木にまとめ、不一致時に使うリンクなどを加えて、本文を左から走査する。
📌 このページのポイント
- 複数パターンの共通の接頭辞をトライ木で共有する
- 失敗リンクを使って一致済みの末尾を再利用し、本文を巻き戻さずに進む
- 重なる一致を含めて報告できるが、列挙方針と出力件数に注意する
ひよこ 探す単語が何十個もあるときは？
ペンギン先生 単語ごとに本文を最初から調べる代わりに、検索用の機械を一つ作る方法があるよ。エイホ・コラシック法は、パターンの共通の書き出しをトライ木にまとめ、本文を読みながら状態を移して複数の語を探すんだ。
ひよこ 途中で一致しなくなったら、最初へ戻るの？
ペンギン先生 本文を巻き戻す必要はないよ。すでに読んだ部分の末尾が、ほかのパターンの先頭に使えるかもしれないよね。失敗リンクでその状態へ移り、そこから続きを調べるんだ。何も引き継げなければ開始状態へ戻るよ。
ひよこ 単語が重なっていても見つかる？
ペンギン先生 全一致を報告する設定なら見つかるよ。パターンがhe、she、hersで、本文がushersなら、0始まりでsheは1、heとhersは2から始まる。sheを読み終えた時点では、その末尾にあるheも一致として扱う仕組みが必要なんだ。
ひよこ ライブラリなら同じ結果が返る？
もっと詳しく知りたい人へ
パターン数が増えても検索時間は変わりませんか？
オートマトンの準備と結果の列挙は別に数えます。遷移を効率よく扱える条件で、全一致を報告する走査は本文長nと一致件数zに対しO(n＋z)と表せます。パターン集合が大きいほど構築時間やメモリが必要になり、結果が多ければ出力にも時間がかかります。