15

Web アプリに検索候補機能を実装しており、使用中の手法の既存の実装を調べています。

主要なサイト (Amazon、Bing など) のほとんどは、あいまい検索を次のように実装しているようです。

Tokenize search string in to terms
processingSearchStringSet = {}
For each term
    if exact term is NOT in index
        Get possible terms (fuzzyTerms) from levenshtein(term, 1 (or 2))
        For each term in fuzzyTerms
            if term is in index
                processingSearchStringSet.intersect(stringsIndexedByTermsSet)
    else
        processingSearchStringSet.intersect(stringsIndexedByTermsSet)

結果セットのメンバーは、メトリクス (例: 用語の順序の保存、絶対的な用語の場所、検索の人気度) によってランク付けされ、ユーザーに返される前に、このランキングと事前に決定された結果セットのサイズに基づいて保存または除外されます。

一方、Google の実装は、これとはかなり異なります。

具体的には、検索文字列の構成用語で複数のエラーが許容されます。エラーのしきい値は、関心のある用語が文字列のどこにあるかに依存しているようですが、7 を超えることはありません。

興味深いのは、次のことです。

  1. ユーザーの文字列の各用語に対して、用語空間全体でしきい値 5 のレーベンシュタイン検索を実行すると、非常にコストがかかります。
  2. ＃1が行われたとしても、それでも誤った提案がないことを説明することはできません

N グラムも使用されていないようです。元の用語に存在するバイグラムが含まれないように用語を変更しても、結果には影響しないようです。

私の発見を説明する例を次に示します。

Example term: "Fiftyyyy shades of grey"

Amazon suggestions: none 
(if the error count exceeds 1 on any term, the search fails)

Bing suggestions: none
(if the error count exceeds 2 on any term, the search fails)

Google suggestions: 10 (max) 
(breaking the search would require 5 or more errors on any single term, 
or multiple errors on multiple terms)

私の質問は次のとおりです。ここではどのような種類の魔術が働いていますか? 彼らは、膨大な誤差許容範囲でレーベンシュタイン検索を使用しているだけですか、それとも私が知らない別の手法を使用していますか?

4

1 に答える 1

1

多分あなたはこのアプローチを試す必要があります: http://norvig.com/spell-correct.html

于 2012-09-11T15:06:50.360 に答える