1

より良い解決策があるかもしれませんが、私が最初に考えるのは次の2つです。

1) リスト内の各単語について、テキストにその単語が含まれているかどうかを確認します。2) 単語をセットに格納します。別のセットのテキストから単語 (スペースで区切られたもの - 正確である必要はありません) を保存し、2 つのセットの交点が空かどうかを確認します

どちらが優れているか、またはそれらがほぼ同じかどうかはわかりません。

4

3 に答える 3

2

これがセットマッチング問題です。

Sパターンのセット、Tテキスト、およびnT で見つかった S の要素の数を考えます。次に、時間 O(|T| + |S| + n) [*]で、テキスト内の S の要素のすべての出現を見つけることができます。 Aho–Corasick 文字列マッチング アルゴリズムを使用します。

最初のオカレンスを見つけたいだけだとすると、最悪の場合、実行時間は O(|T| + |S|) に短縮されます。S が十分に小さい場合、テキストの長さは線形になります!

[*] |S| セット内のすべての単語の長さ

于 2013-02-04T21:59:13.423 に答える
0

セットの1つからトライを作成し、その中の2番目のセットのすべての単語を検索します。文字列の平均長をkとすると、トライの構築にはΘ（n * k）時間がかかり、文字列がトライに属しているかどうかのチェックにはO（k）がかかります。簡単にするために、実行時間をO（（n + m）* k）
と見なすことができます。ただし、より正確な分析では、2番目のセット全体をスキャンするずっと前に実際に終了できるため、Θ（n * k）+ O（n * k）が得られます。これは、小さいセットからトライを作成し、大きいセットからルックアップ要素を作成する方がよいことを示しています。

于 2013-02-05T09:23:02.557 に答える
0

Java、Python、および C++ の最も洗練された実装では、このタイプの検索に単一のアルゴリズムは使用されません。

使用するアルゴリズムの決定は、テキスト サイズ、検索頻度、単語の分布などの結果として決定されます。 (複数のアルゴリズムを一緒に使用することもできます)

テキストが大きく、テキスト内のいくつかの単語のみを検索する必要がある場合、実装のほとんどは、Boyer-Moore または Rabin-Karp アルゴリズムの拡張バージョンを使用します。

たとえば Rabin-Karp のようなアルゴリズムは、ハッシュ一致を検索し、それが見つかった場合は、単語全体を検索します。適切なローリング ハッシュ関数を使用すると、めったに発生しません。

テキストの単語のセットを保存することは、最初の提案よりも優れたソリューションのようですが、単語のハッシュ値を保存することは、さらに優れたソリューションになる可能性があります (ハッシュ値と実際の単語の間の追加のマッピングを使用)。

テキストの識別性が高い場合、セットを保持するために測定されません。あなたが提案したよりもはるかに多くの解決策があります。Googleを使用することをお勧めします。

于 2013-02-04T17:13:38.673 に答える