は、私は言葉を持つファイル持って言う：Stringに辞書ファイルの単語が含まれているかどうかを確認する方法はありますか？
I was eating some *****-***** when the ***** rang.
：私はにつながるための高速な方法を見つけようとしている
I was eating some Apple-bacon when the phoNe rang.
：
私はその文字列を持っています。私はベクトルを反復するよりも良い方法があるのかどうか疑問に思っています。私は標準ライブラリを使用しているので、boost hashmapは可能ではありません。
私は最初の試みは、フレーズをトークン化し、マップまたはsetですべての単語を検索することですC++ 98
ベクトルを繰り返し処理するよりも良い方法があるかどうかは分かりません。
保証O（LG N）検索時間のためにソートされたベクター又はstd::setの使用のいずれかbinary_search。 lg（2000）= 7.6、理論上は263倍の速度増加であり、一定の要因は無視している。
（これは本当に正規表現のためのより良いフィット感ですが。）
を使用しています。
しかし、多くのメッセージを処理する必要のあるサーバーをお持ちの場合は、それを少し賢明に実装することが考えられます。その後に文字を置き換えるすべての単語の
の
サフィックスツリーは本当に高速である必要がありますが、多くのメモリが浪費されます。ハッシュ値は設定された実装より速いかもしれませんが、巧妙なアルゴリズムを考え出す必要があります。
検索を高速化するには、いくつかの選択肢があります。
すでに単語のベクトルを持っている場合は、sortにベクトルでシンプルなアプローチの一つと文字列が検閲される場合binary_search
を行うには非常に長いあなたは一度だけ文字列を繰り返すことによって最適化しようとするかもしれないです。
検索している単語のリストの文字でツリーを構成し、このマップを使用して単語を検索する関数を作成します。デザインは複雑ですが、長い弦では検索する言葉がおそらく最も速くなります。
例：
言葉：猿、エース、アパ、ことで、
ツリー
A B
/| |
p c y
/| |
e a e
検索：
1）は、トラフトップレベルの文字の文字列内のすべての文字を反復（AまたはB）
2）見つかった場合、次の文字が最初の子かどうかを確認します。
strchrの文字列の反復文字列はいずれも、branch predictionのために高速であり、regexpのプリミティブな実装である必要があります。
アルゴリズムが単純化され、すべての26+単語のルートが単一ルートの子になることがわかりました。 –
これはトライ検索として知られています – stefaanv
はい、確かに。 Stefaanvに感謝します。私は名前ではなくアイデアだけを覚えていた。 http://en.wikipedia.org/wiki/Trie – cprogrammer
おそらく最も良い方法は検索です。辞書内のすべての単語のツリーを構築し、上からの入力を比較する。非アルファベット文字を見ると、再びツリーの先頭からリセットして開始します。
C++ 11は 'unordered_map'を提供します。標準ライブラリではなくSTLです。 –
「Apple」という言葉は何が間違っていますか？私は悪い言葉を検閲すると思います！ – Matt
@Matt私は実際の言葉を書いたくないので、これは単なる例です。 – jmasterx