単語を比較するためのアルゴリズム (アルファベット順ではない)

Question

特定の要件に合わせてソリューションをコーディングする必要があるのですが、それを実現できる既製のライブラリに詳しい人、またはベスト プラクティスを教えてくれる人がいるかどうかを知りたいと思いました。説明：

ユーザーは、いくつかの固定オプションの 1 つであると考えられる単語を入力します (オプションをリストに保持します)。入力はリスト内のメンバーにある必要があることはわかっていますが、これはユーザー入力であるため、入力を間違えた可能性があります。ユーザーが意味する可能性が最も高い単語を教えてくれるアルゴリズムを探しています。コンテキストがないので、ユーザーにリストからの選択を強制することはできません (つまり、単語を自由に手動で入力できなければなりません）。

たとえば、リストに「水」、「クォーター」、「ビール」、「ビート」、「地獄」、「こんにちは」、「ツチブタ」という単語が含まれているとします。

ソリューションでは、さまざまな種類の「通常の」エラーを考慮する必要があります。

• 速度のタイプミス (例:文字を二重にする、文字を削除するなど）
• キーボードの隣接文字のタイプミス (例:「qater」は「水」を意味します）
• 非ネイティブ英語のタイプミス (例:「四半期」は「四半期」）
• 等々...

明らかな解決策は、文字ごとに比較し、それぞれの異なる文字、余分な文字、欠落した文字に「ペナルティの重み」を与えることです。しかし、このソリューションは、どこかにリストされているはずの何千もの「標準」エラーを無視します。おそらく標準の不一致の大規模なデータベースを使用して、特定のケースと一般的なケースの両方に対処するヒューリスティックが世の中にあると確信しています (私はデータを大量に使用するソリューションを歓迎します)。

私は Python でコーディングしていますが、この質問は言語に依存しないと考えています。

何か推奨事項/考えはありますか?

Answer 1

http://norvig.com/spell-correct：

Googleがこれを行う方法を読んでもらいたいです。 HTML の

編集：一部の人々は、単語と候補語（レーベンシュタイン、同音）指定されたユーザー間のメトリックを定義するアルゴリズムを記載しています。 1はまた、効率的に非ユークリッド最近傍探索を実行するためにデータ構造を必要とするので、これは、しかし、問題の完全な解決策ではありません。これは、例えば行うことができますカバーツリーで： http://hunch.net/~jl/projects/cover_tree /cover_tree.htmlする

Answer 2

一般的な解決策を入力して、固定テキストの間レーベンシュタイン距離を計算することです。挿入、欠失、および単一文字の置換 - - 二つの文字列のレーベンシュタイン距離は、簡単な操作の数だけです。他に文字列のいずれかをオンにする必要

Answer 3

あなたは、このようなのsoundex のよう音韻で比較アルゴリズムを、と考えたことがありますか？それは、単語のリストのSOUNDEX表現を生成し、それらを保存し、ユーザー入力のSOUNDEXを取得し、そこに最も近いものを見つけるには余りにも難しいことではありません。

Answer 4

Bitapアルゴリズムを探してください。それはあなたがやりたいことのためによく資格、さらにはウィキペディアでのソースコードの例が付属しています。

Answer 5

データセットが非常に小さい場合は、すべての項目のレーベンシュタイン距離を個別に比較するだけで十分です。ただし、それより大きい場合は、 BKツリー または同様のインデックス システム。私がリンクした記事では、特定のレーベンシュタイン距離内で一致を見つける方法について説明していますが、最近傍検索を行うように適応させるのは非常に簡単です (読者の演習として残しています ;)。

Answer 6

それは全体の問題を解決できないかもしれないが、

、あなたはソリューションの一部としてのsoundexアルゴリズムを使用して検討する必要があります。 「SOUNDEX」と「パイソン」の迅速なGoogle検索は、アルゴリズムのいくつかのpythonの実装を示します。

Answer 7

「レーベンシュタイン距離」または「編集距離」を検索してください。これは、編集操作の回数をカウントする（挿入、変更文字を削除）あなたが別のものに一つの単語を変換する必要があります。それは一般的なアルゴリズムだが、問題に応じて、あなたがタイプミスの種類ごとに異なる重みを持つ特別な何かが必要な場合があります。