python - スペルチェッカーの遺伝的アルゴリズムの実装

Question

テキスト ファイルのスペルをチェックし、エラーと修正を出力するスペル チェッカーを実装したいと考えています。これをpythonで作成したいと思います。

しかし、主なことは、遺伝的アルゴリズムを使用してそれを実装したいということです。スペルチェッカーの遺伝的アルゴリズムを実装するにはどうすればよいですか?

Answer 1

ここでの私のアイデアが完璧または最適であるとは思わないでください。しかし、このルートに進むことにした場合、それはあなたにとって良い出発点になるかもしれません. ただし、遺伝的アルゴリズムは、スペル チェッカーに最適な選択肢ではない場合があります。

遺伝的アルゴリズムの場合、開始集団、遺伝子を「次の世代」に渡す方法 (クロスオーバー)、突然変異を作成する明確な手段、およびどの遺伝子を次の世代に渡すかを選択する方法が必要です。 （別名フィットネス機能）。これに加えて、もちろんコーパスが必要です。良い場合は、dictionary.com API を試すことができます (私は一度も使用したことがありません) http://www.programmableweb.com/api/dictionary.com。

開始母集団については、開始母集団が何千ものまったく同じ単語 (つまり ['hello']*1000) になるという恐ろしい問題があります。ここから、それが単語であるかどうかを確認できます。単語である場合は True を返します (そことその単語との文法チェックは面倒だからです)。

最初は、多様性を得るために突然変異に完全に依存する必要があるため、前の世代であれば突然変異の可能性を高くし、多様性が大きくなると突然変異の可能性は減少します. ミューテーションは、ランダムな文字をどこかに挿入する、どこかの文字を削除する、どこかの文字を変更する、これらの複数を実行する、のいずれかです。

フィットネス関数については、シーケンス アラインメント アルゴリズムを使用することをお勧めします。http://en.wikipedia.org/wiki/Sequence_alignmentを参照してください。本当に上達したい場合は、母集団の各単語の音声スペルを作成して、それらがコーパス内の何かと一致するかどうかを確認し、それに基づいてスコアを上げてください (つまり、tho と than は同じ発音になります)。私はそれについて何も知っているとは言えません。これらすべてがアプリケーションの速度を著しく低下させることを心に留めておいてください。人口を 1000 から 2000 に制限するのが最善かもしれません。

クロスオーバーのために、いくつかのサンプルを取得する必要があります (早い段階でルーレットを使用して最も適合するものを選択する必要がある場合がありますが、後でスピードの目的でトーナメントを使用できます)。ここでも、各「親」間の配列アラインメントを使用して、各親からどの文字を取得するかを決定できます (つまり、soeed と s_eeo は、soeed、seed、seeo、または soeeo になる可能性があります)。

これを専門的な解決策と見なさないでください。さらに、私はこれについて数分間考えただけですが、遺伝的アルゴリズムを使用することに決めた場合は、これが良い出発点になる可能性があります。