搜索时的动态提示

   <p>上周跟大家聊了文本检索的算法和原理。然后有朋友就跟老王提了个问题，如何实现搜索时的提示？比如输入“老王”，怎么出现“老王很帅”、“老王很酷”的？</p>    <p><img src="https://simg.open-open.com/show/184266a2c48cb87349db261bd5b8b8ed.jpg"></p>    <p>那借着上周的内容，我们这周就聊聊这个算法的实现吧。</p>    <p>这个提示一般被叫做 suggestion ，为的是减少用户在查询时的输入。那我们为了保证有足够好 & 多的 suggestion ，一般需要解决以下两个问题。</p>    <h3><strong>第一个问题： suggestion 数据来源问题 </strong></h3>    <p>这个问题要解决的就是你在输入的时候，我给的提示的数据源从哪里来？一般情况下有多种途径：</p>    <p>1 、根据所有用户的历史查询输入，对用户的检索内容做统计和排序，生成大量用作 suggestion 的字符串；</p>    <p>比如：用户 A 搜索了：老王好帅；用户 B 搜索了：老王很酷；用户 C 搜索了：老王很帅。这个时候，当用户 D 来搜索：“老王”的时候，检索系统就会把之前热搜的“老王很帅”、“老王很酷”展示出来当做搜索提示，方便 D 用户来输入。</p>    <p>2 、根据文本内的高频词汇、句子和短语建立 suggestion 字符串。</p>    <p>我们的文本搜索引擎会收录大量的文本，并且会对这些文本进行分段落、划句、切词等等操作。其中有些句子或者短语是非常高频的，这一部分的句子或者短语也可以用做检索时的提示。</p>    <p>以上列出了两种 suggestion 内容的来源。其实根据不同的业务，还可以有其他不同的来源。比如，如果是做好友系统，那么在添加好友的时候， suggestion 里面就可以优先出现好友的好友等等。</p>    <p>好了，解决了数据源的问题，接下来要解决的就是如何做索引，达到高效的检索提示的性能。</p>    <h3><strong>第二个问题：高效的检索</strong></h3>    <p>在用户检索的时候，一般都是前缀匹配提示。比如：你输入“老”，会提示“老王 XXX ”。但是如果输入“王”，就一般不会再出现“老王 XXX ”这样的提示了，而是出现“王者归来”这样以“王”开头的提示。所以，这样的业务模式就大大简化了我们做 suggestion 的难度。</p>    <p>那具体怎么做呢？</p>    <p>上周我们讲了文本检索的几种方法，大家还记得嘛？</p>    <p><strong>第一种： Trie （字典）树 </strong></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/632b3ae360cb7bd2c3745dfc949d2702.jpg"></p>    <p>字典树的特点就是前缀匹配。那根据我们上面对的 suggestion 的分析，他是非常适合用这样的方法来建立索引的。</p>    <p>所以，我们只需要将我们所有的 suggestion 条目建立成对应的字典树即可。如果内容过多，就考虑拆分成多机，然后由一个结点来做合并即可。</p>    <p><img src="https://simg.open-open.com/show/edb10edeac0853b47685c29d947fefe9.jpg"></p>    <p><strong>第二种：倒排索引（改进型）</strong></p>    <p>还是上周讲到的老方法。不过在建立索引的时候，有一点不一样。上周我们讲的时候，是将文本进行单词或者中文词组分词，然后建立倒排索引。当检索的时候，进行合并。</p>    <p>做 suggestion 就没有那么麻烦，因为提示一般会是一个词组、短句等等，字数都很少。不会有那种长篇的文章，所以再按原来的方法，效率会比较低。</p>    <p>那怎么样改进呢？其实可以这样来实现。我们只需要将热搜或者高频词组进行前缀拆分，然后分别建立索引，即可达到效果。如下图：</p>    <p><img src="https://simg.open-open.com/show/e3f68fdd361216504ed7be2ff46fd8e1.jpg"></p>    <p>我们将“老王很帅”拆分成“老”、“老王”、“老王很”、“老王很帅”四个 term ，然后将他们作为倒排索引的 key ， value 都指向实体的内容（ id=100 ， content= 老王很帅）。当用户输入“老”或者“老王”，被检索的 key 都能被索引到，而指向真正的数据。</p>    <p>当然，每个 key 后面挂的都是一个按权重排序好的实体数据指针链。这样，我们检索的时候，只需要查一次索引，便可以方便的得到想要的结果。</p>    <p>但是这种方法也有一个问题，就是数据膨胀。如果按照平均每一个提示内容的长度为 5 个字符的话，我们索引的空间需要增加 5 倍。不过按照空间换时间的原则，这一部分的开销，其实还是比较划算的。</p>    <p>如果确实不愿意增加空间开销，也可以用上周我们讲到的方案，分词 + 归并的方法。只是查询效率上会降低一些。</p>    <h3><strong>额外的需求</strong></h3>    <p>如果用户的输入中含有拼音，怎么办？比如：“老 wang ”……</p>    <p>作为技术人员，不得不感叹：用户的需求怎么这么多？（其实更直接的反馈是：产品经理真是变态）。</p>    <p>wang 可能有很多汉字与之对应，比如：“王、网、旺……”他们其实都有相同的拼音 wang 。所以，当用户输入“老 wang ”的时候，他有可能表达的是“老王”、“老网”或者是“老旺”。这个时候，我们就要将这几个词放到我们的倒排索引系统中，去找找，看看到底有哪些是通过索引能匹配的。如果遇到那种拼音对饮汉字再多一点的，比如“ a ”，这个时候程序员要疯了……</p>    <p>不过作为有追求的程序员，我们还是有办法去解决这样的问题。大家还记得一个词叫做“归一化”吗？就是将表象不同的 N 个东西，通过一定的分析和处理，找到他们相同的本质，从而用另外一个东西去代替这一堆的东西。</p>    <p>拼音，即是汉字做归一化的一个途径。既然正着做不行，那我们就反着做。比如“老王很帅”，我们是否可以将汉字转化成拼音“ lao-wang-hen-shuai ” , 将这个拼音词组也按之前的方式，拆成四个倒排索引，指向 id=100 的那个实体内容。当用户查询“老 wang ”的时候，我们检测到有拼音，即可将他们转换成“ laowang ”，再去倒排系统中查询。</p>    <p>对于多音字，比如“了”，我们在建立倒排索引的时候，注意做一下这个字在句子或者短语中的发音处理即可。</p>    <p>对于 suggestion ，根据不同的业务，有很多不同的实现方案，好不好关键看是否适合相关的业务。所谓的没有最好的架构，只有更适合的方案。如果本身的业务规模并不大，或者是产品要求没那么高，或许，只需要一条 sql ： select * from simplemain where word like ' 老王 %' 就可以解决了。所以，大家不用迷信所谓的各种高级架构。更适合的才是最好的！</p>    <p>好了，今天扯了这么多，大家都看懂了嘛？</p>    <p style="text-align:center"> </p>    <p> </p>    <p>来自：http://mp.weixin.qq.com/s?__biz=MzA3MDExNzcyNA==&mid=2650392332&idx=1&sn=afde4f7887059800681b9a5d05d9fee2&chksm=86ccd73fb1bb5e290617155d27de64fa5b1dd333a186b47ab15e14761abd37622f7c100b67c5&scene=0</p>    <p> </p>