algorithm - 製品検索でタイプミスを検出し、可能な修正を提案するにはどうすればよいですか？

Question

製品名の非常に大規模なデータベースを考えると、ユーザー検索で考えられるタイプミスをどのように検出し、考えられる修正を提案しますか（Googleがそれらを提示する方法のようにちょっと）？

例えば

ユーザーは「フォークハンドル」と入力し、「検索」を押します。

彼らは戻ってきます

「結果はありません。「フォークハンドル」という意味ですか？」

Answer 1

この問題にはいくつかのアプローチがあります。

1. データベースで最も一般的なスペルミスのテーブルを保持します。一般的なスペルミスが必要な場合:ここ)
2. 編集距離に基づくアルゴリズムの使用: 情報理論とコンピューター サイエンスでは、2 つの文字列間の編集距離は、文字列の一方を他方に変換するために必要な操作の数です。このメトリックを定義または計算するには、いくつかの異なるアルゴリズムがあります。たとえば、レーベンシュタイン アルゴリズムに関するウィキペディアの記事を読んでください。
3. 全文検索に Lucene を使用している場合は、"Did you mean" 機能を実装する方法を示す素晴らしい記事があります。
4. その機能を単純なスペル修正と見なす場合は、いくつかの言語での素晴らしい、非常に短い実装を次に示します。

Answer 2

Soundexなどの音声アルゴリズムを使用して、似ている一致を見つけることができます。

PostgreSQL にはfuzzystrmatchという名前のモジュールがあり、ドキュメントには Soundex、Levenshtein、Metaphone、Double Metaphone の使用例が示されています。

Answer 3

ユーザーが結果を返さないときに再入力したもののリストをGoogleが保持していることを読んだことは確かです。これらの値のマッピングを保持できます (再入力された文字列が同じ文字で始まる場合など)。