谷歌模糊搜索（又称“建议”）：使用了哪些技术？

Question

我正在实现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)

从搜索结果来看，成员们可能会根据指标进行排名（例如：保留术语顺序、绝对术语位置、搜索热度），并根据这个排名和预先确定的结果集大小进行保留或消除，然后再返回给用户。

而谷歌的实现则与此有很大不同。

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

有趣的是：

1. 使用Levenstein搜索在整个术语空间上进行阈值为5的搜索，对于用户字符串中的每个术语都将非常昂贵
2. 即使执行了#1，仍无法解释错误建议的缺失

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

以下是一个例子，用于说明我的发现：

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搜索，还是使用我不知道的其他技术？

- Kevin

---

Peter Norvig（Google研究主管）在这次演讲中（大约从28:30开始）讨论了基于语料库的概率模型用于拼写纠正的应用。 - lccarrasco

@lccarasco：谢谢！我想语料库的方法（特别是测量某些错误概率的部分）解释了我所观察到的现象。 - Kevin

我不知道谷歌实际使用的算法是什么，所以这只是猜测：我一直认为他们监控同一用户搜索query_1但没有点击任何链接的情况，然后搜索类似的词*(query_2)。在足够大的样本集上取平均值。如果有100人搜索了query1，然后是query2，那么当另一个用户搜索query_1时，就会将query_2*作为建议呈现出来。您可以通过首先将查询拆分成单个单词或短语来进一步优化该过程。 - HugoRune

@HugoRune 我相信这是正确的，谷歌的算法通过大量数据将您的搜索与其他人的类似搜索进行比较来解决此问题，而不是将您的搜索与实际数据进行比较。我记得在某个地方读到过，即使他们针对拼写错误的“你是不是想找X”也不是基于某个规范字典中的单词列表，而是纯粹基于用户在犯类似错误后的搜索行为。 - Daniel Kinsman

@HugoRune，这可能是为什么有时会出现“您是否意味着……”而不是“正在搜索 x 而非 y”的原因之一，以验证这是否是打字错误。 - Pieter Bos

Answer 1

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

- f13o