algorithm - 谷歌模糊搜索(又名 "suggestions"): What technique(s) are in use?

Question

我正在我的网络应用程序中实现搜索建议功能，并且一直在寻找现有技术的实现。

似乎大多数主要站点(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 的实现与此有很大不同。

具体来说，它允许在搜索字符串的组成词中出现 1 个以上的错误。错误阈值似乎取决于感兴趣的术语在字符串中的位置，尽管它永远不会超过 7。

有趣的是:

1. 在整体上以 5 的阈值进行 Levenstein 搜索术语空间，对于用户字符串中的每个术语来说都是疯狂的贵
2. 即使#1 已经完成，它仍然无法解释没有错误的建议

N-grams 也没有被使用:修改一个术语使其不包含原始术语中存在的二元组似乎不会影响结果。

这里有一个例子来说明我的发现:

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)

我的问题是:什么类型的巫术在这里起作用？他们只是在使用容错率很高的 Levenshtein 搜索，还是他们使用了我不知道的另一种技术？

Answer 1

也许您应该尝试这种方法:http://norvig.com/spell-correct.html