java - Javaでの効率的な文字列照合

Question

私は文章（ツイート）と1000万以上の名前のストリームを持っています。1つの文（ツイート）に1,000万の名前の1つについての言及が含まれているかどうかを確認したいと思います。考えられるすべてのパターンの正規表現をコンパイルできましたが、それを実行するための効率的なアルゴリズムがあるかどうかを本当に知りたいと思います。

ありがとう、

Answer 1

トライ（プレフィックスツリー）を作成できます。

Answer 2

ブルームフィルターを使ってみてください。ここでデモ。

Answer 3

単純な文字列（名前）の出現のみを求める場合は、パターンマッチングはまったく必要ないと思います。あなたが実際にツイッターの名前を狙っているのなら、ツイートで言及されているときに@記号が前に付いていませんか？もしそうなら、最初は@記号を探して、そこから進んでください。

@の後の文字列が1,000万個の文字列のいずれかであるかどうかを確認するには、ruakhによって提案されたプレフィックスツリーが間違いなく良いアイデアです。

Answer 4

あなたは逆からそれについて行くことができます。文が入ったら、それをトークンに分割し、^トークン\s*のような各トークンの正規表現パターンを作成します。それらのそれぞれを、それぞれがオンラインであると仮定して、1,000万の名前と比較します。