ポートフォリオ管理ツールの社内 Web サイトを開発しています。多くのテキスト データ、会社名などがあります。「もしかして: xxxx」というクエリに非常に迅速に応答するいくつかの検索エンジンの機能に、私は本当に感銘を受けました。
ユーザーのクエリをインテリジェントに取得し、生の検索結果だけでなく、「もしかして?」で応答できる必要があります。可能性の高い代替回答がある場合の応答など
[私はASP.NETで開発しています(VB - 私に反対しないでください!)]
更新: OK、何百万もの「無料ユーザー」なしでこれをどのように模倣できますか?
ソースからの直接の説明は次のとおりです（ほぼ）
22:03分
見る価値があります！
基本的に、Google の元 CTO である Douglas Merrill によると、次のようになります。
1) Google で (つづりを間違えた) 単語を書きます。
2) 欲しいものが見つからない (結果をクリックしないでください)
3) 単語のつづりが間違っていることに気付き、検索ボックスの単語を書き直します。
4) 欲しいものが見つかります (最初のリンクをクリックします)
このパターンは何百万回も倍増し、最も一般的なスペルミスと最も「一般的な」修正は何かを示しています。
このようにして、Google はほぼ瞬時にすべての言語でスペル修正を提供できます。
また、これは、夜間に誰もが夜を綴り始めた場合、Google が代わりにその単語を提案することを意味します。
編集
@ThomasRutter: Douglas はそれを「統計的機械学習」と表現しています。
彼らは、どのクエリがどのユーザーからのものかを知っているので、誰がクエリを修正したかを知っています (Cookie を使用)
ユーザーがクエリを実行し、ユーザーの 10% だけが結果をクリックし、90% が戻って別のクエリを入力し (修正された単語を使用)、今度は 90% が結果をクリックした場合、ユーザーは見つけたことがわかります。訂正。
また、それらが表示するすべてのリンクの情報を持っているため、それらが 2 つの異なるクエリの「関連する」クエリであるかどうかを知ることもできます。
さらに、スペル チェックにコンテキストが含まれるようになったため、コンテキストに応じて異なる単語を提案することもできます。
このgoogle wave のデモ(@ 44m 06s ) を参照してください。これは、スペルを自動的に修正するためにコンテキストがどのように考慮されるかを示しています。
ここでは、その自然言語処理の仕組みについて説明します。
そして最後に、自動機械翻訳(@ 1h 12m 47s ) をミックスに追加して何ができるかの素晴らしいデモです。
ビデオに分と秒のアンカーを追加して、コンテンツに直接スキップできるようにしました。機能しない場合は、ページをリロードするか、手でマークまでスクロールしてみてください。
しばらく前に、 Peter Norvig (Google Inc. のリサーチ ディレクター) が書いた次の記事を見つけました: How to Write a Spelling Corrector 。
「スペル修正」のトピックについては興味深い読み物です。例は Python ですが、明確で理解しやすく、アルゴリズムを他の言語に簡単に翻訳できると思います。
以下に、アルゴリズムの簡単な説明を示します。アルゴリズムは、準備と単語チェックの 2 つのステップで構成されます。
ステップ 1: 準備 - 単語データベースのセットアップ
実際の検索語とその出現を使用できる場合に最適です。それがない場合は、代わりに大量のテキストを使用できます。各単語の出現 (人気) をカウントします。
ステップ 2. 単語のチェック - チェックした単語に似た単語を見つける
同様に、編集距離が短い (通常は 0-1 または 0-2) ことを意味します。編集距離は、ある単語を別の単語に変換するために必要な挿入/削除/変更/交換の最小数です。
前のステップから最も人気のある単語を選択し、それを修正として提案します (単語自体以外の場合)。
うーん... Google は膨大なデータ (インターネット) のコーパスを使用して、本格的な NLP (自然言語処理) を行っていると思いました。
たとえば、彼らはインターネット全体から非常に多くのデータを持っているため、3 つの単語のシーケンスが発生する回数を数えることができます (トライグラムとして知られています)。したがって、"pink frugr concert" のような文が表示された場合、ヒット数が少ないことがわかり、コーパスで最も可能性の高い "pink * concert" を見つけることができます。
彼らはどうやらDavide Gualanoが言ったことのバリエーションをしているだけなので、必ずそのリンクを読んでください. もちろん、Google はコーパスとして認識しているすべての Web ページを使用しているため、そのアルゴリズムは特に効果的です。
私の推測では、彼らはレーベンシュタイン距離アルゴリズムと、実行された検索に関して収集した大量のデータを組み合わせて使用していると思われます。入力された検索文字列からレーベンシュタイン距離が最も短い一連の検索を引き出し、最も多くの結果が得られる検索を選択できます。
通常、実動スペル修正担当者は、いくつかの方法論を利用してスペル候補を提供します。いくつかは次のとおりです。
スペル修正が必要かどうかを判断する方法を決定します。これらには、不十分な結果、具体的ではない、または (ある尺度によると) 十分に正確でない結果などが含まれる場合があります。
大量のテキストまたは辞書を使用してください。すべてまたはほとんどのスペルが正しいことがわかっています。これらは、LingPipeなどの場所でオンラインで簡単に見つけることができます。次に、最適な提案を決定するために、いくつかの尺度に基づいて最も近い単語を探します。最も直感的なのは似たようなキャラクターです。研究と実験を通じて示されたのは、2 つまたは 3 つの文字シーケンスの一致がより効果的であるということです。(バイグラムとトライグラム)。結果をさらに改善するには、単語の先頭または末尾の一致でより高いスコアを重み付けします。パフォーマンス上の理由から、これらすべての単語をトライグラムまたはバイグラムとしてインデックス付けして、検索を実行するときに n-gram に変換し、ハッシュテーブルまたはトライを介して検索できるようにします。
文字の位置に基づいて、潜在的なキーボード ミスに関連するヒューリスティックを使用します。'w' は 'e' に近いので、"hwllo" は "hello" になるはずです。
音声キー (Soundex、Metaphone) を使用して単語にインデックスを付け、可能な修正を検索します。実際には、これは通常、上記のように n-gram インデックスを使用するよりも悪い結果を返します。
いずれの場合も、リストから最適な補正を選択する必要があります。これは、レーベンシュタイン、キーボード メトリックなどの距離メトリックである場合があります。
複数単語の句の場合、スペルが間違っている可能性がある単語は 1 つだけです。その場合、残りの単語をコンテキストとして使用して、最適な一致を判断できます。
レーベンシュタイン距離を使用して、メトリック ツリー (またはスリム ツリー) を作成し、単語にインデックスを付けます。次に、1-Nearest Neighbor クエリを実行すると、結果が得られました。
Googleは、スペルが正しいクエリではなく、最良の結果が得られるクエリを提案しているようです。ただし、この場合、おそらくスペルコレクターの方が実行可能です。もちろん、返される結果の良さのメトリックに基づいて、すべてのクエリに値を格納できます。
それで、
辞書が必要です（英語またはデータに基づく）
単語トレリスを生成し、辞書を使用して遷移の確率を計算します。
トレリスを使用して最小エラー距離を計算するデコーダーを追加します。もちろん、距離を計算するときは、挿入と削除に注意する必要があります。楽しいのは、QWERTYキーボードを使用すると、キーを互いに近づけて押すと距離が最大になることです（caeは車を回し、cayは猫を回します）
距離が最小の単語を返します。
次に、それをクエリデータベースと比較して、他の厳密な一致に対してより良い結果があるかどうかを確認できます。
推測として...可能性があります
ホップフィールド ネットワークやバック プロパゲーション ネットワークなどの AI からのもの、または「指紋の識別」、壊れたデータの復元、または Davide が既に述べたスペル修正などの何かである可能性があります ...
私はこれについて数年前に何かを見たので、その後変更された可能性がありますが、どうやら彼らは、同じユーザーが非常によく似たクエリを短時間で送信したログを分析することから始め、ユーザーがどのように修正したかに基づいて機械学習を使用したようです彼ら自身。
単純。彼らは大量のデータを持っています。クエリの頻度に基づいて、考えられるすべての用語の統計があり、通常、ユーザーがクリックする結果を生成するのはどのようなバリエーションか.より一般的な答え。
実際、スペルミスが実際に最も頻繁に検索される用語である場合、アルゴリズムはそれを正しいものと見なします。
あなたの質問に関して、大量のデータを持たずに動作を模倣する方法-Googleによって収集された大量のデータを使用してみませんか? スペルミスのある単語の Google 検索結果をダウンロードし、HTML で「もしかして:」を検索します。
私はそれが最近マッシュアップと呼ばれていると思います:-)
これは古い質問であり、Apache Solr を使用した OP を誰も提案していないことに驚いています。
Apache Solr は、他の多くの機能に加えて、スペルチェックやクエリの提案も提供する全文検索エンジンです。ドキュメントから：
デフォルトでは、Lucene スペル チェッカーは、最初に文字列距離計算のスコアで候補を並べ替え、次にインデックス内の候補の頻度 (利用可能な場合) で並べ替えます。
スペルチェッカーって言いたいの？フレーズ全体ではなくスペル チェッカーである場合は、python でアルゴリズムが開発されているスペル チェックに関するリンクがあります。このリンクを確認してください
一方で、テキストを使ってデータベースを検索するプロジェクトにも取り組んでいます。これで問題が解決すると思います
部分一致と近傍一致を自然にサポートする特定のデータ構造 (三分探索木) があります。
それを理解する最も簡単な方法は、Googleの動的計画法です。
これは、情報検索から借用されたアルゴリズムであり、現代のバイオインフォマティクスで2つの遺伝子配列がどれほど類似しているかを確認するために頻繁に使用されています。
最適なソリューションは、動的計画法と再帰を使用します。
これは、多くの解決策で非常に解決された問題です。オープンソースコードが見つかるまでグーグルで検索してください。