15

我正在我的网络应用程序中实现搜索建议功能，并且一直在研究现有的实现以了解正在使用的技术。

似乎大多数主要网站（亚马逊、必应等）都通过以下方式实现模糊搜索：

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. 在整个术语空间上进行阈值为 5 的 Levenstein 搜索，因为用户字符串中的每个术语都非常昂贵
  2. 即使 #1 已经完成，它仍然不能解释没有错误的建议

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

这是一个例子来说明我的发现：

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 搜索，还是使用了我不知道的另一种技术？

4

1 回答 1

1

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

于 2012-09-11T15:06:50.360 回答