プロンプトとコンテキスト
これは、ログフィルタリング、センシティブワード検出、またはエディタのハイライト処理を想定した複数パターンマッチングの問題です。キーワードの総文字数をM、テキストの長さをNとします。各マッチの開始位置とキーワードIDを出力してください。事前処理中、辞書は固定されており、テキストは長い可能性があります。面接官は事前処理、スキャンの計算量、および重複の処理について評価します。
面接官が評価するポイント
面接官は、トライ木によるプレフィックスの共有を有限オートマトンへと拡張できるかを見ています。優れた回答では、失敗リンクを構築し、失敗リンクに沿って出力を継承し、各文字が有界な状態遷移を引き起こす理由を説明します。不十分な回答では「トライ木を使用する」と述べるにとどまり、サフィックスの重複やミスマッチ時のフォールバックを処理できません。
最初に確認すべき明確化のための質問
- マッチングは大文字・小文字を区別しますか？Unicode正規化されていますか？それともバイトベースですか？文字の定義によってトライ木や位置の単位が変わります。
- 重複するマッチや、同一位置で終了する複数のキーワードも返すべきですか？これにより出力チェーンを完全にする必要があるかが決まります。
- 辞書は頻繁に変更されますか？静的な辞書なら1つのオートマトンで対応できますが、動的な辞書ではバージョン管理された再構築が必要になる場合があります。
- 位置のカウントは文字数、バイト数、UTF-16コードユニットのいずれですか？呼び出し元の仕様に合わせてください。
- テキストはチャンク単位で届きますか？チャンクをまたぐスキャンでは、チャンクごとにリセットするのではなく状態を保持する必要があります。
30秒で答えるフレームワーク
「すべてのキーワードをトライ木に挿入し、幅優先探索（BFS）を用いて各ノードの失敗リンクを構築します。失敗リンクはミスマッチ後に利用可能な最長サフィックスを指します。各ノードは、自身の終端出力と失敗先のノードの出力を結合します。スキャン中は、遷移または失敗リンクをたどり、現在のノードの出力を生成します。事前処理はキーワードの合計長＋エッジ表現に対して線形であり、スキャンはO(N + マッチ数)です。チャンク化された入力では現在のオートマトンの状態を保持するだけで対応できます。」
ステップごとの詳細な解説
- トライ木を構築する。 各ノードには子エッジ、失敗リンク、およびキーワードIDを格納します。終端ノードにはIDを追加します（1つだけ保持して上書きしてはいけません）。
- 失敗リンクを初期化する。 ルートの直下の子ノードの失敗先はルートになります。残りのノードはキューを用いて深さ順に処理します。
- フォールバック遷移を計算する。 あるノードからのエッジについて、親の失敗リンクをたどり、同じ文字エッジが見つかるまで探索します。見つからなければルートに戻ります。これにより、スキャン時にテキストの過去の文字を再比較する必要がなくなります。
- 出力を集約する。 失敗先から出力をコピーするか、リストのコピーを避けるために出力リンク（output link）を保持します。出力リンクはマッチを報告する際にトラバースされます。
- テキストをスキャンする。 各文字に対して子エッジへの遷移を試みます。ミスマッチが発生した場合は、エッジが見つかるかルートに到達するまで失敗リンクをたどります。到達したノードですべての出力を生成します。開始位置は『現在のインデックス - キーワード長 + 1』です。
- 境界を処理する。 重複するキーワードは自然に出力されます。チャンク化された入力では、チャンク間で状態を引き継ぎます。マッチ数が膨大な場合は、すべてのO(マッチ数)の結果を保持する代わりに、コールバック、上限設定、またはページネーションを使用します。
一般的な文字集合にはハッシュマップを使用し、メモリが許す場合は小さな固定文字集合に対して配列を使用します。変更される辞書の場合は、バックグラウンドで新しいバージョンを構築し、リーダーのポインタをアトミックに切り替えることで、スキャンが部分的なオートマトンを参照しないようにします。
模範解答
「すべてのキーワードを挿入して各終端IDを記録し、BFSで失敗リンクを構築します。ルートの子ノードの失敗先はルートです。他のエッジについては、親の失敗チェーンをたどって同じ遷移を見つけるか、ルートにフォールバックします。出力にはノード自身の終端IDと失敗リンク先の出力が含まれるため、she をスキャンする際に he と she の両方が出力されます。各テキスト文字は子エッジまたは失敗遷移をたどるため、スキャン時間はO(N + Z)（Zはマッチ数）になります。事前処理はO(M)＋エッジのストレージです。チャンク化されたテキストでは状態を保持し、辞書の更新時は新しいバージョンを構築してから切り替えます。」
よくある間違い
- 間違い: ミスマッチ時にポインタとテキストの両方を巻き戻す → 失敗する理由: キーワードごとの再スキャンに退化してしまう → 修正方法: 失敗リンクを使用してテキストのインデックスを単調増加に保ちます。
- 間違い: ノードごとに1つの出力しか保持しない → 失敗する理由: サフィックスとなるキーワードや同一終了位置のキーワードが消失する → 修正方法: 失敗先の出力をマージするか、出力リンクを保持します。
- 間違い: スキャンが常にO(N)であると主張する → 失敗する理由: マッチの出力自体にO(Z)のコストがかかる可能性がある → 修正方法: O(N + Z)と明記し、出力をストリーミングします。
- 間違い: 各チャンクでルートにリセットする → 失敗する理由: チャンクをまたぐキーワードがマッチしなくなる → 修正方法: チャンク間でオートマトンの状態を引き継ぎます。
フォローアップ質問と回答
なぜキーワードごとに個別にKMPを実行しないのですか？
個別のKMP実行ではO(KN)のテキストスキャンが必要になります。Aho–Corasick法はトライ木のプレフィックスを共有し、テキストを1回だけ処理するため、固定された辞書と長いテキストに適しています。
なぜ失敗リンクですべてのマッチを見つけることができるのですか？
失敗リンクは利用可能な最長サフィックスを指すためです。失敗チェーンをたどり続けることで、キーワードのプレフィックスでもあるすべてのサフィックスを列挙できるため、出力の集約によってネストされたマッチや重複するマッチを見つけることができます。
子ノードのハッシュマップがメモリを使い果たす場合はどうしますか？
小さな文字セットには配列、コンパクトなエッジテーブル、またはダブル配列トライ（double-array trie）を選択し、リストのコピーを避けるために出力リンクを使用します。圧縮を行う前にノード数とエッジ数を測定してください。
辞書を頻繁に変更することはできますか？
辞書をバージョン管理し、バックグラウンドで新しいオートマトンを構築して検証した上で、リーダーポインタをアトミックに置き換えます。すでに進行中のストリームのために、古いバージョンを少しの間保持します。