文字列 A があり、他にも多くの文字列があり、それらの他の文字列のいずれかが A にあるかどうかを確認したい場合.
可能な限り少ない繰り返しでこれを行うことができるアルゴリズムは何ですか?
元：
'こんにちは私の名前はボブです。'
そして、[11] から始まる 'name is b' が含まれているかどうかを確認したいと思います。
正規表現ライブラリを使用するつもりはありません。
ありがとう
1543 次
1 に答える
7
このための最も効率的なアルゴリズムはAho-Corasick アルゴリズムです。これは、長さ n の文字列と全長 m の文字列のセットを指定すると、時間 O(n + m + z) ですべての一致を見つけることができます。ここで、z は文字列の総数です。試合が報告されました。これは有限オートマトンに基づいており、KMP 文字列マッチング アルゴリズムを一般化したものです。
このアルゴリズムの優れた点の 1 つは、固定された一連のキーワードと検索する多数のテキスト文字列がある場合、O(m) 前処理を実行してマッチャーを構築することでアルゴリズムを高速化できることです。次に、時間 O(n + z) で長さ n の文字列内のすべての一致を見つけることができます。
一方、固定文字列があり、それに対してさまざまなパターン文字列のセットを照合する場合は、サフィックス ツリーを調べることを検討してください。これにより、同じランタイム保証が得られますが、テキストが固定されている場合は高速になります。
お役に立てれば！
于 2012-06-05T05:35:11.423 に答える