2

要件

  1. 現在、1万を超えるキーワードまたは文章を含むリストがあります（数はNです）
  2. 入力は長い文字列で、長さは L

質問: 文字列に、与えられたリストのキーワードまたは文章が含まれているかどうかを確認してください

質問はwikipediaの単語フィルターとして説明できますが、そのページにはアルゴリズムが見つかりませんでした。この問題を解決する最も簡単な方法は、すべてのキーワードまたは文をイテレータし、長いテキストにそのような部分文字列が含まれているかどうかを毎回確認することです。キーワードが多いため、テキストが長いことを考えると、パフォーマンスは非常に悪いです。O(NL)時間を使用します

より良い解決策は O(L) で終了する必要があるようです。誰かがこれについて何か提案をすることができますか?

4

1 に答える 1

4

時間計算量O（M + L）を持つこの問題には、いくつかのアプローチがあります。ここで、Lは文字列の長さであり、Mはすべてのパターンの長さを組み合わせたものです。

  1. Aho–Corasick文字列照合アルゴリズム。
  2. Ukkonenのアルゴリズムを使用して文字列の接尾辞木を作成し、各パターンのこの接尾辞木との一致を見つけます。
  3. パターンのセットに対して一般化された接尾辞木を作成し、入力文字列とこの接尾辞木の間の一致を見つけます。
  4. 文字列のサフィックス配列を作成し、それを使用して各パターンを検索します。このアプローチには、時間計算量O（M + L + N log L）があります。ここで、Nはパターンの数です。
  5. Commentz-Walterアルゴリズム。

これらすべてのアルゴリズム（Commentz-Walterアルゴリズムを除く）の詳細については、この本を参照してください：Dan Gusfieldによる文字列、ツリー、およびシーケンスのアルゴリズム。

入力文字列から個別の単語/文を明確に抽出できる場合は、いくつかの異なる（より単純な）アプローチを使用できます。

  1. Nパターンの誤検知の可能性が低いことを保証するのに十分な大きさのブルームフィルターを準備します。キーワード/文のハッシュ関数によって決定されるブルームフィルタービットに追加します。次に、文字列をスキャンして連続する単語/文を抽出し、これらの単語/文がブルームフィルターで見つかるかどうかを確認します。ブルームフィルターに単語/文が存在する場合のみ、パターンのリストでそれを検索します。このアルゴリズムは、時間計算量O（M + L）を想定しており、スペース効率が高くなっています。
  2. すべてのパターンをハッシュセットに挿入します。次に、文字列をスキャンして連続する単語/文を抽出し、それらのいずれかがハッシュセットに含まれているかどうかを確認します。これは、予想される時間計算量O（M + L）と同じであり、ブルームフィルターアプローチよりも単純ですが、スペース効率が良くありません。
  3. すべてのパターンを基数木に挿入します（試行）。次に、それを使用して、文字列から単語/文を検索します。これは、一般化された接尾辞木アプローチとそれほど違いはありませんが、より単純でパフォーマンスが優れています。最悪の場合の時間計算量O（M + L）があり、おそらくブルームフィルターまたはハッシュセットアプローチよりもいくらか遅く、必要に応じて非常にスペース効率が高くなる可能性があります。
于 2012-11-22T16:37:51.027 に答える