string - ランダムな文字列が英語のように聞こえるかどうかを判断するにはどうすればよいですか?

Question

入力単語のリストに基づいて文字列を生成するアルゴリズムがあります。英単語のように聞こえる文字列だけを分離するにはどうすればよいですか? すなわち。LORDを維持しながらRDLOを破棄します。

編集:明確にするために、それらは辞書内の実際の単語である必要はありません。英語のように聞こえる必要があるだけです。たとえば、KEALは受け入れられます。

score 28 · Accepted Answer

巨大な英文のマルコフ連鎖を構築できます。

その後、単語をマルコフ連鎖にフィードし、その単語が英語である確率がどのくらい高いかを確認できます。

ここを参照してください: http://en.wikipedia.org/wiki/Markov_chain

ページの下部に、マルコフテキストジェネレーターが表示されます。あなたが望むのは、まさにその逆です。

一言で言えば: マルコフ連鎖は、各文字について次の文字が続く確率を格納します。十分なメモリがある場合は、このアイデアを 2 つか 3 つの文字に拡張できます。

score 18 · Accepted Answer

ベイジアンフィルターを使用した簡単な方法 ( http://sebsauvage.net/python/snyppets/#bayesianの Python の例)

from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')

>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]

>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]

score 4 · Accepted Answer

候補文字列をバイグラム (隣接する文字のペア) にトークン化し、各バイグラムを英語のバイグラム頻度の表と照合することで、これにアプローチできます。

単純: バイグラムが度数表で十分に低い場合 (または完全に存在しない場合)、その文字列を信じられないものとして拒否します。(文字列に「QZ」バイグラムが含まれていますか?拒否します!)
それほど単純ではありません: 文字列全体の全体的な妥当性を、たとえば、各バイグラムの頻度をその長さの有効な英語の文字列の平均頻度で割った積として計算します。これにより、(a) 高周波バイグラムの中で奇数の低周波バイグラムを含む文字列を受け入れることと、(b) いくつかの個々の低いがしきい値をかなり下回っていないバイグラムを含む文字列を拒否することができます。 .

これらのいずれも、しきい値の調整が必要であり、2 番目の手法は最初の手法よりも重要です。

トライグラムで同じことを行うと、より堅牢になる可能性がありますが、「有効な」文字列のセットがより厳密になる可能性もあります。それが勝つかどうかは、アプリケーションによって異なります。

既存の研究コーパスに基づくバイグラムおよびトライグラムテーブルは、無料または購入で入手できる場合があります (無料で入手できるものは見つかりませんでしたが、これまでのところ大雑把にグーグルで検索しただけです)。英文のコーパスサイズ。各単語をトークンとしてクランクし、各バイグラムを集計するだけです。これを、特定のバイグラムをキーとし、インクリメントされた整数カウンターを値とするハッシュとして処理できます。

英語の形態学と英語の音声学は (有名なことに!) アイソメトリックよりも小さいため、この手法は、英語に「見える」が厄介な発音を示す文字列を生成する可能性があります。これは、バイグラムではなくトライグラムのもう 1 つの議論です。複数の文字を連続して使用して特定の音素を生成する音の分析によって生じる奇妙さは、n グラムが音全体に及ぶ場合に軽減されます。（たとえば、「鋤」や「津波」を考えてみてください。）

score 4 · Accepted Answer

マルコフ連鎖を使用して英語の発音の単語を生成するのは非常に簡単です。ただし、後退することはより困難です。結果の許容誤差範囲は? 一般的な文字のペア、トリプルなどのリストをいつでも作成し、それに基づいて評価することができます。

score 3 · Accepted Answer

英語の単語の辞書に対してsoundexアルゴリズムを実行して結果をキャッシュし、候補の文字列をsoundexして、キャッシュと照合したいと思います。

パフォーマンス要件に応じて、soundexコードの距離アルゴリズムを作成し、特定の許容範囲内の文字列を受け入れることができます。

Soundexの実装は非常に簡単です。アルゴリズムの説明については、ウィキペディアを参照してください。

実行したいことの実装例は次のとおりです。

def soundex(name, len=4):
    digits = '01230120022455012623010202'
    sndx = ''
    fc = ''

    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c
            d = digits[ord(c)-ord('A')]
            if not sndx or (d != sndx[-1]):
                sndx += d

    sndx = fc + sndx[1:]
    sndx = sndx.replace('0','')
    return (sndx + (len * '0'))[:len]

real_words = load_english_dictionary()
soundex_cache = [ soundex(word) for word in real_words ]

if soundex(candidate) in soundex_cache:
    print "keep"
else:
    print "discard"

明らかに、read_english_dictionaryの実装を提供する必要があります。

編集：「KEEL」と同じsoundexコード（K400）を持っているので、「KEAL」の例は問題ありません。失敗率を把握したい場合は、拒否された単語をログに記録し、手動で確認する必要があります。

score 3 · Accepted Answer

同じタスクを達成しようとしているため、「発音可能な」パスワードジェネレーターを調査する必要があります。

Perl ソリューションはCrypt::PassGenであり、辞書でトレーニングできます (必要に応じてさまざまな言語にトレーニングできます)。辞書を調べて、1 文字、2 文字、および 3 文字のシーケンスに関する統計を収集し、相対頻度に基づいて新しい「単語」を作成します。

score 2 · Accepted Answer

MetaphoneとDouble Metaphoneは SOUNDEX と似ていますが、SOUNDEXよりも目的に合わせて調整できる点が異なります。それらは、音声学的な「音」に基づいて単語を「ハッシュ」するように設計されており、英語に対してこれを行うのが得意です (ただし、他の言語や固有名詞はあまり得意ではありません)。

3 つのアルゴリズムすべてで留意すべきことは、単語の最初の文字に非常に敏感であるということです。たとえば、KEALが英語に聞こえるかどうかを調べようとしている場合、最初の文字が異なるため、REALと一致するものは見つかりません。

score 1 · Accepted Answer

それらは本物の英単語である必要がありますか、それとも英単語のように見える単なる文字列である必要がありますか?

可能性のある英語の単語のように見えるだけでよい場合は、実際の英語のテキストを統計分析して、どの文字の組み合わせが頻繁に発生するかを調べることができます。それができたら、ありそうもない文字列を捨てることができますが、その中には本当の言葉かもしれません。

または、辞書を使用して、辞書に含まれていない単語を拒否することもできます (複数形やその他のバリエーションを考慮して)。

score 0 · Accepted Answer

私はおそらく、英語の単語のデータベースに対してSOUNDEXアルゴリズムを使用して各単語を評価します。SQLサーバーでこれを行う場合、ほとんどの英語の単語のリストを含むデータベースをセットアップするのは非常に簡単です（無料で利用できる辞書を使用）。MSSQLサーバーには、利用可能な検索アルゴリズムとしてSOUNDEXが実装されています。

もちろん、必要に応じて、どの言語でもこれを自分で実装できますが、かなりの作業になる可能性があります。

このようにして、各単語が既存の英語の単語のように聞こえる場合の評価を取得し、結果を受け入れる程度に制限を設定できます。おそらく、複数の単語の結果を組み合わせる方法を検討したいと思うでしょうし、テストに基づいて受け入れ制限を微調整するでしょう。

score 0 · Accepted Answer

ファイテストと一致指数を見ることをお勧めします。 http://www.threaded.com/cryptography2.htm

score 0 · Accepted Answer

それらを辞書 (インターネットで無料で入手可能) と比較することもできますが、CPU 使用率の点でコストがかかる可能性があります。それ以外に、それを行うための他のプログラム的な方法は知りません。

score 0 · Accepted Answer

それはかなり複雑な作業のように聞こえます! 頭のてっぺんから、子音の音素にはその前後に母音が必要です。ただし、音素が何であるかを判断するのは非常に困難です。おそらく、それらのリストを手動で書き出す必要があります。たとえば、「TR」は問題ありませんが、「TD」は問題ありません。

score -1 · Accepted Answer

いくつかの簡単なルールと、標準的なペアとトリプレットが良いと思います。

たとえば、英語の発音の単語は、母音-子音-母音のパターンに従う傾向がありますが、いくつかの二重母音と標準的な子音のペア (例: th、ie と ei、oo、tr) は別です。このようなシステムでは、英語とは思えないほとんどすべての単語を削除する必要があります。よく調べてみると、おそらく英語のように聞こえる多くの単語も削除されることがわかりますが、その後、より広い範囲の単語を許可するルールを追加し、アルゴリズムを手動で「トレーニング」することができます。

すべての偽陰性を削除するわけではありません (たとえば、リズムが単語であることを明示的にコーディングせずに「リズム」を含めるルールを考え出すことはできないと思います) が、フィルタリングの方法は提供されます。

また、間違いなく英語の意味を持つ単語である文字列ではなく、英語の単語である可能性のある文字列 (発音すると妥当に聞こえる) が必要であると想定しています。

string - ランダムな文字列が英語のように聞こえるかどうかを判断するにはどうすればよいですか?

13 に答える 13

Related

Reference