剑客
关注科技互联网

搜索时的动态提示

上周跟大家聊了文本检索的算法和原理。然后有朋友就跟老王提了个问题,如何实现搜索时的提示?比如输入“老王”,怎么出现“老王很帅”、“老王很酷”的?

搜索时的动态提示

那借着上周的内容,我们这周就聊聊这个算法的实现吧。

这个提示一般被叫做 suggestion ,为的是减少用户在查询时的输入。那我们为了保证有足够好 & 多的 suggestion ,一般需要解决以下两个问题。

第一个问题: suggestion 数据来源问题

这个问题要解决的就是你在输入的时候,我给的提示的数据源从哪里来?一般情况下有多种途径:

1 、根据所有用户的历史查询输入,对用户的检索内容做统计和排序,生成大量用作 suggestion 的字符串;

比如:用户 A 搜索了:老王好帅;用户 B 搜索了:老王很酷;用户 C 搜索了:老王很帅。这个时候,当用户 D 来搜索:“老王”的时候,检索系统就会把之前热搜的“老王很帅”、“老王很酷”展示出来当做搜索提示,方便 D 用户来输入。

2 、根据文本内的高频词汇、句子和短语建立 suggestion 字符串。

我们的文本搜索引擎会收录大量的文本,并且会对这些文本进行分段落、划句、切词等等操作。其中有些句子或者短语是非常高频的,这一部分的句子或者短语也可以用做检索时的提示。

以上列出了两种 suggestion 内容的来源。其实根据不同的业务,还可以有其他不同的来源。比如,如果是做好友系统,那么在添加好友的时候, suggestion 里面就可以优先出现好友的好友等等。

好了,解决了数据源的问题,接下来要解决的就是如何做索引,达到高效的检索提示的性能。

第二个问题:高效的检索

在用户检索的时候,一般都是前缀匹配提示。比如:你输入“老”,会提示“老王 XXX ”。但是如果输入“王”,就一般不会再出现“老王 XXX ”这样的提示了,而是出现“王者归来”这样以“王”开头的提示。所以,这样的业务模式就大大简化了我们做 suggestion 的难度。

那具体怎么做呢?

上周我们讲了文本检索的几种方法,大家还记得嘛?

第一种: Trie (字典)树

搜索时的动态提示

字典树的特点就是前缀匹配。那根据我们上面对的 suggestion 的分析,他是非常适合用这样的方法来建立索引的。

所以,我们只需要将我们所有的 suggestion 条目建立成对应的字典树即可。如果内容过多,就考虑拆分成多机,然后由一个结点来做合并即可。

搜索时的动态提示

第二种:倒排索引(改进型)

还是上周讲到的老方法。不过在建立索引的时候,有一点不一样。上周我们讲的时候,是将文本进行单词或者中文词组分词,然后建立倒排索引。当检索的时候,进行合并。

suggestion 就没有那么麻烦,因为提示一般会是一个词组、短句等等,字数都很少。不会有那种长篇的文章,所以再按原来的方法,效率会比较低。

那怎么样改进呢?其实可以这样来实现。我们只需要将热搜或者高频词组进行前缀拆分,然后分别建立索引,即可达到效果。如下图:

搜索时的动态提示

我们将“老王很帅”拆分成“老”、“老王”、“老王很”、“老王很帅”四个 term ,然后将他们作为倒排索引的 key value 都指向实体的内容( id=100 content= 老王很帅)。当用户输入“老”或者“老王”,被检索的 key 都能被索引到,而指向真正的数据。

当然,每个 key 后面挂的都是一个按权重排序好的实体数据指针链。这样,我们检索的时候,只需要查一次索引,便可以方便的得到想要的结果。

但是这种方法也有一个问题,就是数据膨胀。如果按照平均每一个提示内容的长度为 5 个字符的话,我们索引的空间需要增加 5 倍。不过按照空间换时间的原则,这一部分的开销,其实还是比较划算的。

如果确实不愿意增加空间开销,也可以用上周我们讲到的方案,分词 + 归并的方法。只是查询效率上会降低一些。

额外的需求

如果用户的输入中含有拼音,怎么办?比如:“老 wang ”……

作为技术人员,不得不感叹:用户的需求怎么这么多?(其实更直接的反馈是:产品经理真是变态)。

wang 可能有很多汉字与之对应,比如:“王、网、旺……”他们其实都有相同的拼音 wang 。所以,当用户输入“老 wang ”的时候,他有可能表达的是“老王”、“老网”或者是“老旺”。这个时候,我们就要将这几个词放到我们的倒排索引系统中,去找找,看看到底有哪些是通过索引能匹配的。如果遇到那种拼音对饮汉字再多一点的,比如“ a ”,这个时候程序员要疯了……

不过作为有追求的程序员,我们还是有办法去解决这样的问题。大家还记得一个词叫做“归一化”吗?就是将表象不同的 N 个东西,通过一定的分析和处理,找到他们相同的本质,从而用另外一个东西去代替这一堆的东西。

拼音,即是汉字做归一化的一个途径。既然正着做不行,那我们就反着做。比如“老王很帅”,我们是否可以将汉字转化成拼音“ lao-wang-hen-shuai , 将这个拼音词组也按之前的方式,拆成四个倒排索引,指向 id=100 的那个实体内容。当用户查询“老 wang ”的时候,我们检测到有拼音,即可将他们转换成“ laowang ”,再去倒排系统中查询。

对于多音字,比如“了”,我们在建立倒排索引的时候,注意做一下这个字在句子或者短语中的发音处理即可。

对于 suggestion ,根据不同的业务,有很多不同的实现方案,好不好关键看是否适合相关的业务。所谓的没有最好的架构,只有更适合的方案。如果本身的业务规模并不大,或者是产品要求没那么高,或许,只需要一条 sql select * from simplemain where word like ‘ 老王 %’ 就可以解决了。所以,大家不用迷信所谓的各种高级架构。更适合的才是最好的!

好了,今天扯了这么多,大家都看懂了嘛?

搜索时的动态提示

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址