前一章讲了搜索中的拼写纠错功能，里面一个很重要的概念就是莱文斯坦距离。这章会讲解搜索中提升用户体验的另一项功能 - [自动补全]。本章直接介绍 ES 中的实现方式以及真正的搜索引擎对自动补全功能的优化。

大家对上面的这个应该都不陌生，搜索引擎会根据你输入的关键字进行一些提示，这样用户只需要输入部分内容就可以进行选择了。尤其在移动端会比较方便。淘宝、京东的搜索也有类似的功能，只不过行业不同，提示出来的内容也不同罢了。

1. 导入 lucene-suggest 组件
2. 指定联想数据来源，lucene suggest 提供了几个 InputIteratior 的默认实现，也可以自定义实现

1. BufferedInputIterator：对二进制类型的输入进行轮询；
2. DocumentInputIterator：从索引中被 store 的 field 中轮询；
3. FileIterator：从文件中每次读出单行的数据轮询，以 t 进行间隔（且 t 的个数最多为 2 个）；
4. HighFrequencyIterator：从索引中被 store 的 field 轮询，忽略长度小于设定值的文本；
5. InputIteratorWrapper：遍历 BytesRefIterator 并且返回的内容不包含 payload 且 weight 均为 1；
6. SortedInputIterator：二进制类型的输入轮询且按照指定的 comparator 算法进行排序；

InputIteratior 中几个方法的作用：

1. 建立 suggest 索引：suggester.build(new InputIteratorWrapper{});// 根据 InputIterator 的具体实现决定数据源以及创建索引的规则
2. 索引建立完毕即可在索引上进行查询，输入模糊的字符，Lucene suggest 的内部算法会根据索引的建立规则提出 suggest 查询的内容。suggester.lookup(name, contexts, 2, true, false);

Lucene 使用 AnalyzingInfixSuggester 类中的 lookup 方法去联想数据来源进行查询，其实就是一个普通的 search，所以我们的关键是要维护好这个联想数据来源，各行各业都应该有自己单独的语料库。

应该从这几个方面入手：怎么优化 Suggest 词库、提升 Suggest 词准确率、怎么提高响应速度

• 冷启动可以从内容中提取热词数据来解决，或者人工设置
• 挖掘搜索日志：

• 挖掘近 1 个月搜索日志，按照每天独立 IP 进行统计频次，即每个 IP 用户天搜索同一关键词多次只记一次，用 IP 过滤也有其局限性，伪 IP，动态 IP，局域网共享同一公网 IP，都会影响到基于 IP 来判断用户的准确性，你也可以使用 sessionId 或者 userId 来判断
• 统计后搜索词频次之后，抽取搜索频次 > 100（自定阈值）的词，同时对日志数据进行清洗，过滤去除大于 10 个字（去除太长的长尾词），单字和符号内容
• 定时更新 suggest 词库中。

• 搜索日志里面包含大量 误输入词：

1. 需要在 suggest 词库里面去掉误输入词，对于搜索频次高的词，可以挖掘其对应的正确词，通过同义词进行查询改写。
2. 误输入词同义词挖掘可以通过挖掘搜索 session 序列，使用 word2vec 训练来获取误输入词的同义词，通过分词器同义词设置，对误输入词进行查询改写。

• 使用 fuzzy 模糊查询：基于编辑距离算法来匹配文档。编辑距离的计算基于我们提供的查询词条和被搜索文档。
• 排序：从搜索日志挖掘的 Suggest 词，可以根据搜索词的搜索频次作为热度来设置 weight，Suggest 会根据 weight 来排序。

当使用 completion suggester 的时候， 不是用于完成 类似于 " 关键词 " 这样的模糊匹配场景，而是用于完成关键词前缀匹配的。 对于汉字的处理，无需使用 ik/ HanLP 一类的分词器，直接使用 keyword analyzer，配合去除一些不需要的 stop word 即可。

代码参考：

搜索引擎的优化，需要更智能，每个人输入相同的关键字，提示出来的内容可能是完全不相同的，这就是所谓的 “千人千面”。这就用到了数据分析的知识，可以根据用户一段时间内的搜索历史，分析用户的搜索习惯，结合语料库实现对用户的精准提示。跟输入法的提升功能类似，会根据你过往的输入文本进行自动提示。所以，你付出了隐私，得到的是更大的便捷。这也是没有办法的事情。

• 搜索提示的一点小总结（重点）

1. 需要一个搜索词库 / 语料库，各行各业均应该不同
2. 对用户输入的关键字进行分词
3. 根据分词及其他搜索条件去语料库中查询若干条（百度是 10 条）记录返回
4. 为了提升准确率，通常都是前缀搜索
5. 会根据莱温斯坦距离进行拼写纠错

如你所见，各大搜索引擎都提供了智能提示的 API 供广大用户调用，如果你司没有自研的能力，可以直接 js 中跨域调用，先把系统跑起来再说，给大家提供主流搜索引擎的调用地址，包含电商的哦。

提示：URL 中的 #content# 为搜索的 关键字

谷歌（Google）

http://suggestqueries.google.com/complete/search?client=youtube&q=#content#&jsonp=window.google.ac.h

callback：window.google.ac.h

window.google.ac.h([“关键字”,[[“关键字”,0],[“关键字 歌词”,0],[“关键字参数”,0],[“关键字 lyrics”,0],[“关键字过滤”,0],[“关键字排名”,0],[“关键字查询”,0],[“关键字提取算法”,0],[“关键字规划师可通过以下哪种方式帮助您制作新的搜索网络广告系列”,0],[“关键字优化”,0]],{“k”:1,“q”:“uhaB8ZMjzJay-BACee_C0eVdUCA”}])

必应（Bing）

http://api.bing.com/qsonhs.aspx?type=cb&q=#content#&cb=window.bing.sug

callback：window.bing.sug

百度（Baidu）

http://suggestion.baidu.com/su?wd=#content#&cb=window.baidu.sug

callback：window.baidu.sug

好搜（So）

https://sug.so.360.cn/suggest?encodein=utf-8&encodeout=utf-8&format=json&word=#content#&callback=window.so.sug

**callback：**window.so.sug

搜狗（Sogou）

https://www.sogou.com/suggnew/ajajjson?type=web&key=#content#

**callback：**window.sogou.sug

淘宝（Taobao）

https://suggest.taobao.com/sug?code=utf-8&q=#content#&callback=window.taobao.sug

**callback：**window.taobao.sug

搜索建议使用方式

以百度为例，API 返回的是 JSONP 数据，JSONP 是跨域访问的一种方式。由于服务器返回的 JavaScript 代码可以直接引用，通过回调函数的方式就可以间接的获取服务器的数据。

下面是一个回调搜索建议的例子，window.baidu.sug 返回的是一个 json 对象：

控制台打印的结果：如果要将结果保存在一个字符串数组中，只需要 var arr = json.s 即可。

在使用搜索引擎时，当我们输入错误的关键词时，当然这里的错误是拼写错误，搜索引擎的下拉框中仍会显示以正确关键词为前前辍的提示，当你直接回车搜索错误的关键词时，搜索引擎的结果中仍包括正确关键词的结果。你有没有想过它是如何实现的呢?

这个的实现可以有多种方案，常见的方法就是我们前面学习过的最长公共子序列和今天要讲的莱文斯坦距离方式。

最长公共子序列可以查看我前面的博文程序员的算法课（6）- 最长公共子序列（LCS）。

这两种方案都需要跟正确的词典进行对照，**计算编辑距离或者最长公共子序列，将编辑距离最小或子序列最长的单词，作为纠正之后的单词，**返回给用户。

• 莱文斯坦距离

莱文斯坦距离，又称 Levenshtein 距离，是[编辑距离]的一种。指两个[字串]之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个[字符]，删除一个字符。

如单词 three，我不小心手误打成了 ethre，可以看到 ethre 只需要把首字母 e 移动到末尾即可变成正确的单词 three。此时 ethre 相对于 three 的编辑距离就是 1。

莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。

莱文斯坦距离和最长公共子串长度，从两个截然相反的角度，分析字符串的相似程度。莱文斯坦距离的大小，表示两个字符串差异的大小；而最长公共子串的大小，表示两个字符串相似程度的大小。

源码中，定义了两个 public 的静态成员变量， DEFAULT_ACCURACY 表示默认的最小分数，SpellCheck 会对字典里的每个词与用户输入的搜索关键字进行一个相似度打分，默认该值是 0.5，相似度分值范围是 0 到 1 之间，数字越大表示越相似，小于 0.5 会认为不是同一个结果。F_WORD 是对于字典文件里每一行创建索引时使用的默认域名称，默认值为：word。

几个重要的 API：

• **[getAccuracy](http://www.tuicool.com/admin/blogs/)：** accuracy 是精确度的意思，这里表示最小评分，评分越大表示与用户输入的关键字越相似
• suggestSimilar：这个方法就是用来决定哪些 word 会被判定为比较相似的然后以数组的形式返回，这是 SpellChecker 的核心；
• setComparator：设置比较器，既然涉及到相似度问题，那肯定有相似度大小问题，有大小必然存在比较，有比较必然需要比较器，通过比较器决定返回的建议词的顺序，因为一般需要把最相关的显示在最前面，然后依次排序显示；
• setSpellIndex：设置拼写检查索引目录的
• setStringDistance：设置编辑距离

看到了 setStringDistance 这个方法，想都不用想，Lucene 肯定也是使用编辑距离的方式进行匹配的。

源码中还有两个私有属性，分别代表前缀和后缀的权重，前缀要比后缀大。

几个重要的方法：

• formGrams：对输入的字符串按指定长度分割，返回分割后的数组。
• indexDictionary：将字典文件里的词进行 ngram 操作后得到多个词然后分别写入索引。
• suggestSimilar：用来计算最后返回的建议词。有三种建议模式：

• SUGGEST_WHEN_NOT_IN_INDEX：意思就是只有当用户提供的搜索关键字在索引 Term 中不存在我才提供建议，否则我会认为用户输入的搜索关键字是正确的不需要提供建议。
• SUGGEST_MORE_POPULAR：表示只返回频率较高的词组，用户输入的搜索关键字首先需要经过 ngram 分割，创建索引的时候也需要进行分词，如果用户输入的词分割后得到的 word 在索引中出现的频率比索引中实际存在的 Term 还要高，那说明不需要进行拼写建议了。
• SUGGEST_ALWAYS：永远进行建议，只是返回的建议结果受 numSug 数量限制即最多返回几条拼写建议。

最终返回用户输入关键字和索引中当前 Term 的相似度，这个取决于你 Distance 实现，默认实现是 LevenshteinDistance

（莱文斯坦距离）即计算编辑距离。采用三个一维数组代替了一个二维数组，一个数组为上一轮计算的值，一个数组保存本轮计算的值，最后一个数组用于交换两个数组的值。核心源码如下：

Lucene 还内置了另外几种相似度实现，都是基于距离计算的：JaroWinklerDistance、LuceneLevenshteinDistance 和 NGramDistance。

源码中还有大量同步锁的使用，跟本次内容关系不大，暂时先不考虑。

solr 的纠错依赖于 lucene，主要通过插件的方式进行使用。solr 通过配置文件的方式指定纠错的规则，里面一个非常重要的属性：

accuracy，这个值每下降 0.1 就可以纠错一个字母, 下降 0.2 可以纠错一个汉字，例如：将其调整到 0.8 时可以搜索到数据但是仅仅只能出错一个汉字或者两个字母。

官方公式：https://www.elastic.co/guide/en/elasticsearch/reference/current/search-suggesters-phrase.html

es 中使用 phrase Suggester 来进行拼写纠错。phrase suggester 在 term suggester 之上添加了额外的逻辑以选择整体更正的 phrase，而不是基于单个分词加权的 ngram 语言模型。在实际中 phrase suggester 能够根据单词的词频等信息作出更好的选择。

ES 中常用的 4 种 Suggester 类型：Term、Phrase、Completion、Context。

• Term suggester 正如其名，只基于 analyze 过的单个 term 去提供建议，并不会考虑多个 term 之间的关系。API 调用方只需为每个 token 挑选 options 里的词，组合在一起返回给用户前端即可。 那么有无更直接办法，API 直接给出和用户输入文本相似的内容？ 答案是有，这就要求助 Phrase Suggester 了。
• Phrase suggester 在 Term suggester 的基础上，会考量多个 term 之间的关系，比如是否同时出现在索引的原文里，相邻程度，以及词频等等。
• Completion Suggester，它主要针对的应用场景就是 “Auto Completion”。 此场景下用户每输入一个字符的时候，就需要即时发送一次查询请求到后端查找匹配项，在用户输入速度较高的情况下对后端响应速度要求比较苛刻。因此实现上它和前面两个 Suggester 采用了不同的数据结构，索引并非通过倒排来完成，而是将 analyze 过的数据编码成 FST 和索引一起存放。对于一个 open 状态的索引，FST 会被 ES 整个装载到内存里的，进行前缀查找速度极快。但是 FST 只能用于前缀查找，这也是 Completion Suggester 的局限所在。
• Context Suggester，会根据上下文进行补全，这种方式补全效果较好，但性能较差，用的人不多。这也是 es 中拼写纠错的高级用法。

Google 搜索框的补全 / 纠错功能，如果用 ES 怎么实现呢？我能想到的一个的实现方式:

1. 在用户刚开始输入的过程中，使用 Completion Suggester 进行关键词前缀匹配，刚开始匹配项会比较多，随着用户输入字符增多，匹配项越来越少。如果用户输入比较精准，可能 Completion Suggester 的结果已经够好，用户已经可以看到理想的备选项了。
2. 如果 Completion Suggester 已经到了零匹配，那么可以猜测是否用户有输入错误，这时候可以尝试一下 Phrase Suggester。
3. 如果 Phrase Suggester 没有找到任何 option，开始尝试 term Suggester。

精准程度上 (Precision) 看： Completion > Phrase > term， 而召回率上 (Recall) 则反之。从性能上看，Completion Suggester 是最快的，如果能满足业务需求，只用 Completion Suggester 做前缀匹配是最理想的。 Phrase 和 Term 由于是做倒排索引的搜索，相比较而言性能应该要低不少，应尽量控制 suggester 用到的索引的数据量，最理想的状况是经过一定时间预热后，索引可以全量 map 到内存。

真正的搜索引擎的拼写纠错优化，肯定不止我讲的这么简单，但是万变不离其宗。掌握了核心原理，就是掌握了解决问题的方法，剩下就靠你自己的灵活运用和实战操练了。