文字列に英語の音声が含まれているかどうかを確認するための効率的なアルゴリズムが必要です

Question

私は多くの文字列を持っています。それらのすべてには文字のみが含まれています。文字と単語は、スペースで区切られていません。いくつかの文字は英語の単語と他のちょうどバグを構成します。ストリングは文全体を含むことはできません。

有効な英語の言葉で書かれたものを見つける必要があります。私が言いたいのは、ストリングはよく書かれた英語の単語を連結することで構築できるということです。私は単語リストで何かをすることができることを知っています。しかし、その言葉は互いに分裂しているわけではありません。したがって、すべての可能な単語の組み合わせをテストするのは非常に時間がかかることがあります。

私は、文字列が英単語または英語の音声で構築されているかどうかをチェックする高性能のアルゴリズムまたは方法を探しています。たぶん、文字列に英語の音声が入っている可能性があります。

私を助ける方法やアルゴリズムをご存知ですか？ Sphinxのようなものがありますか？

Answer 1

これはsegmentationという問題です。

これを解決する簡単な方法はありません。あなたの知識レベルの推測に基づいて私があなたに提案できるのは、辞書の中にtrieを作り、可能な単語を最初に見つけたらそれが単語であると仮定してみてください。

後で、単語の最後の部分が不安定であることが判明した場合、最後に文字列が単語であると判断したときに戻ってその単語を無視します。

Answer 2

スフィンクスはおそらくあなたを助けません。アルゴリズムRabin-Karpを試してください。標準的な検索ではひどいですが、この特定の問題に対してはうまくいくはずです。基本的には、英語の単語の辞書を持っていて、検索したいと思うでしょう。大きすぎる辞書はかなり遅いですが、一般的な単語に小さな辞書を使用し、一般的な単語にヒットした場合にのみ大きな辞書に切り替えると、おそらくあまりにも多くの偽のネガティブを取得することはありません。

Answer 3

あなたのワードリストをTrieに保存してみませんか？次に、入力を繰り返し、トライで一致する単語を探します。これは非常に効率的に行うことができます。見つけたら、単語の最後に進み、続行してください。

Answer 4

Nグラム言語モデルを確認してください。多分またバイグラム頻度、トライグラム頻度など - - あなたの文字列が十分な長さであるかletter frequencies、十分にごbufflegab奇妙な場合

は

Answer 5

http://en.wikipedia.org/wiki/N-gramを参照してください（代わりに、より一般的なN-グラムで）十分であるかもしれません。たとえば、一部のブラウザでは、コードページを推測するためにそれを使用します。

Answer 6

どの程度の精度が必要か、必要な効率性、処理しているテキストの種類によって異なります。