「もしかして」を実装するにはどうすればよいですか?[重複]

StackOverflow https://stackoverflow.com/questions/41424

  •  09-06-2019
  •  | 
  •  

質問

重複の可能性:
グーグルはどういう意味ですか？アルゴリズムが機能しますか？

Web サイトにすでに検索システムがあるとします。「もしかして:<spell_checked_word>「Google が一部で行っているように 検索クエリ?

役に立ちましたか？

解決

実際、Google が行っていることは非常に簡単ではなく、また最初は直感に反します。辞書との照合などは行わず、むしろ統計を利用して、クエリよりも多くの結果を返した「類似の」クエリを特定します。もちろん、正確なアルゴリズムは不明です。

ここで解決すべきさまざまなサブ問題があります。すべての自然言語処理統計に関連する基本的な基礎として、必携の本があります。 統計的自然言語処理の基礎.

具体的には、単語/クエリの類似性の問題を解決するために、使用して良い結果が得られました。 距離の編集, 、驚くほどうまく機能する文字列の類似性の数学的尺度です。私は以前は Levenshtein を使用していましたが、他のものも検討する価値があるかもしれません。

私の経験から言えば、Soundex はクソです。

実際に、スペルミスの大きな辞書を効率的に保存および検索し、1 秒以内に取得することは簡単ではありません。最善の策は、既存の全文インデックス作成および取得エンジンを利用することです (つまり、あなたのデータベースのものではありません)、そのうち ルシーン は現在最高のものの 1 つであり、偶然にも多くのプラットフォームに移植されています。

他のヒント

Google の Norvig 博士は、それがどのように機能するかを概説しています。彼は 20 行ほどの Python 実装も示しています。

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

http://www.norvig.com/spell-correct.html

ノーヴィグ博士は、「つまり」についても議論しています。 この素晴らしい講演. 。ノーヴィグ博士は 研究責任者 Google で - 「どういう意味ですか」をどのように実装するかと尋ねたとき、彼の答えは次のとおりです。 権威ある.

つまり、おそらく他の検索や実際のインターネットフレーズなどから構築された動的な辞書を使用したスペルチェックです。でもそれはまだ スペルチェック.

SOUNDEX やその他の推測は調べられません、皆さん！

チェック これ レーベンシュタイン距離に関するウィキペディアの記事。「考えられる改善点」をよく読んでください。

検索エンジン用の最先端のスペル提案システムを作成する方法を尋ねた人がいることに、私は嬉しい驚きを感じました。私は検索エンジン会社で 1 年以上このテーマに取り組んでおり、このテーマに関するパブリック ドメインの情報を紹介できます。

以前の投稿で述べたように、Google (および Microsoft と Yahoo!) は事前定義された辞書を使用しておらず、クエリのスペルミスの可能性について熟考する言語学者の大群を雇用していません。それは問題の規模を考えると不可能ですが、クエリのスペルがいつ間違っているかどうかを人々が実際に正確に識別できるかどうかも明らかではないからです。

その代わりに、すべてのヨーロッパ言語にも当てはまる、シンプルでかなり効果的な原則があります。検索ログ上のすべての一意のクエリを取得し、参照クエリが最大数を持つクエリであると仮定して、クエリのすべてのペア間の編集距離を計算します。

この単純なアルゴリズムは、さまざまな種類のクエリにうまく機能します。次のレベルに進みたい場合は、そのテーマに関する Microsoft Research の論文を読むことをお勧めします。見つけられますよ ここ

この論文には素晴らしい導入部がありますが、その後は隠れマルコフ モデルなどの概念についての知識が必要になります。

見ることをお勧めします サウンデックス データベース内で類似した単語を検索します。

を使用して Google 独自の辞書にアクセスすることもできます。 Google API スペル提案リクエスト.

Peter Norvig の「」を参照してください。スペル修正ツールの書き方" 記事。

Google はすべてのクエリをログに記録し、誰かがスペルを修正したことを特定すると思います。この修正は、他のユーザーが同じ最初のクエリを提供したときに提案されることがあります。これは、どの言語でも、実際にはどのような文字列でも機能します。

これはウェブサイトの規模によって決まると思います。約 500 人のスタッフが使用するローカル イントラネットでは、結果が 0 件も返された検索フレーズを確認し、その検索フレーズと新しい提案された検索フレーズを SQL テーブルに入力します。

検索結果が返されなかった場合はそのテーブルを呼び出しますが、これはサイトが比較的小さい場合にのみ機能し、最も一般的な検索フレーズに対してのみ実行します。

同様の質問に対する私の回答も参照してください。

業界固有の翻訳がある場合は、シソーラスが必要になる可能性があります。たとえば、私はジュエリー業界で働いていましたが、説明には kt - カラット、rd - ラウンド、cwt - カラット重量などの略語がありました。Endeca (その検索エンジン) には、よくあるスペルミスを翻訳するシソーラスがありますが、手動による介入が必要です。

でやります ルシーンさんの スペルチェッカー.

Soundex は発音の一致には適していますが、人の名前に最適です (元々は国勢調査データ用に開発されました)

また、フルテキスト インデックス作成もチェックしてください。構文は Google ロジックとは異なりますが、非常に高速で、同様の言語要素を処理できます。

Soundex と「ポーター ステミング」 (soundex は簡単ですが、ポーター ステミングについてはわかりません)。

それを助けるかもしれない aspell と呼ばれるものがあります。http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

これには Ruby gem がありますが、Python からそれと対話する方法がわかりません。http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

以下は Ruby 実装からの引用です

使用法

Aspell を使用すると、単語をチェックして修正を提案できます。例えば：

  string = "my haert wil go on"

  string.gsub(/[\w\']+/) do |word|
    if !speller.check(word)
      # word is wrong
      puts "Possible correction for #{word}:"
      puts speller.suggest(word).first
    end
  end

これにより次の出力が出力されます。

ハートの修正の可能性:Wilの心臓の可能性のある補正：意思

検索エンジンに効果的な方法でスペル修正を実装することは簡単ではありません (考えられるすべての単語までの編集/レーベンシュタイン距離を計算するだけでは済みません)。k-gram インデックスに基づくソリューションについては、次のセクションで説明されています。 情報検索の概要 (全文はオンラインで入手可能)。

比較には ngram を使用できます。 http://en.wikipedia.org/wiki/N-gram

Python ngram モジュールを使用する: http://packages.python.org/ngram/index.html

import ngram

G2 = ngram.NGram([  "iis7 configure ftp 7.5",
                    "ubunto configre 8.5",
                    "mac configure ftp"])

print "String", "\t", "Similarity"
for i in G2.search("iis7 configurftp 7.5", threshold=0.1):
    print i[1], "\t", i[0]

得られるもの:

>>> 
String  Similarity
0.76    "iis7 configure ftp 7.5"    
0.24    "mac configure ftp"
0.19    "ubunto configre 8.5"

コードで Google を使用しないのはなぜですか。その方法については、ここを参照してください。http://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top