搜索词纠错、相关搜索的原理与实现_百度搜索纠偏怎么实现的

  相关搜索是检索功能的一个扩展，用来告诉用户自己输入查询词的情况。

如果输入错了，可能会纠错提示用户：“想找的是不是”

     。

另外还会在显著位置提供与输入查询词相关的其他查询词，例如百度结果页下面的提示，

而对于电商网站这两个功能会合在一起，下面分别说说我对这两个任务的理解。

一、纠错功能，英文叫做spellcheck，在英文上做纠错比较直接，就是看单词的编辑距离，目标当然就是对于任意一个输入，能在大量正确而靠谱的查询词中找出编辑距离满足要求的一个或者几个。

面对这样的spellcheck任务，模型上就是要推算用户输入错误单词w的条件下，是正确单词c的概率，也就是argmaxc P(c|w)。一般有两种方案：一种，是http://norvig.com/spell-correct.html 介绍的办法，另一种是lucene-suggest里spellchecker的方法。 

      1. 第一种，在norvig介绍的方法中，详细的阐述了argmaxc P(c|w)的转换和求解办法。 这个概率不好直接算，但可以根据贝叶斯定理等价于argmaxc P(w|c)*P(c) / P(w)，因为是比较各个c之间的大小所以P(w)可以省略，最后就变成求argmaxc P(w|c)*P(c)就行了。P(c)可以看作是c在文本集合中出现的可能性；P(w|c)意味着本来心里想成是c结果打成了w的概率。那就很好办了，P(c)可以从靠谱的语料中统计；P(w|c)可以用编辑距离来模拟关系，即编辑距离小的概率大。在实现上，对一个输入word，产生出有编辑距离1的字符串，就包括几种情况：删除一个字符、交换临近字符、把一个字符改成另一个、增加一个字符。这样产生的候选集会比较大，接近80%的纠错要求是满足了。如果在编辑距离1的基础上再产生编辑距离为2的更大的候选集，几乎就覆盖所有错别字了。原文讲得比较精细，建模思路也很清晰，建议仔细阅读，这就不细说了。

      2. 第二种方案就是lucene的spellchecker方法，上面方案是把编辑距离的临时产生到词典中检查，这种方案就是预先进行词典索引，当然是ngram的，对一个word任意2位或者3位字符进行索引，对用户输入的一个字符，也同理按2或3位产生字符片段，利用OR的关系去检索，命中多的word得分更高最可能是拼写错误的。当然因为是OR查询关系，所以会有很多也只“沾边”的词也被命中，所以最后除了考虑查询命中高分的，还要对命中的和输入的进行一步编辑距离阈值过滤。举个例子“word”，我们会有n2:wo/n2:or/n2:rd/n3:wor/n3:ord 这些碎片进行索引，当用户输入一个worg,会产生n2:wo/n2:or/n2:rg/n3:wor/n3:org，这些检索条件，会查到很多work, worth等等。细节上可以有一些增强，比如单词两头的字符碎片权重更大等等。

这两种求解argmax P(c|w)的办法，norvig的办法比lucene-spellcheck的办法在线上的环节多一些，效率上估计还是差一点，但提供了很巧妙的求解思路，值得细细品味。

二、相关搜索的功能，学术界研究的比较多，有各种提法，query rewrite，query substitution, query extension等等，算法也五花八门，大多为了结果好看加入了复杂的计算，和针对数据情况的考量。一般工程上需要的是通用的办法，再增加一些特殊的考虑来提高效果。过去曾经有幸看到一篇貌似不是很正规的论文，方法非常简单，思路清晰，非常适合在实际工程上应用起来。论文也不记得标题了，不过思想还记得很清楚：就是寻找query词之间的强弱联系。