搜索引擎查询相关提示功能（搜索建议）

   相关提示也是几乎所有搜索引擎提供的一个附加功能,所谓相关提示,就是对于用户提交的查询进行分析,然后根据其它用户相似的查询给予用户提示,比如我输入查询”大长今”,检索系统会提示其它象”大长今主题曲”,”大长今下载”等等相关的一些其它用户查询.

那么搜索引擎是根据什么原则对于其它用户的查询进行选择来提示用户相关查询呢?我们还是以百度为例子来看看怎么实现这个功能.要实现这个功能主要解决如下三个问题:

问题一.从哪里获得其它用户的查询信息?这个问题对于搜索引擎来说不是难事,因为搜索引擎都有用户查询LOG的功能,在一段时间内每一个用户提交给搜索引擎的查询都被记录在LOG文件里面,所以从这个文件里面可以获得其它用户的查询信息.这个LOG还可以用作其它功能的基本素材,比如搜索排行榜或者搜索风云榜,就是根据这个LOG文件,对用户查询归类,相同的归为一类,然后统计一段时间内这个类别的出现次数,按照降序排列,选择前列K个作为输出即可.

问题二.搜索引擎拿到用户的查询比如”大长今”,用户查询LOG里面有成千上万的不同查询,那么选择哪些作为提示呢?这里面牵涉到一个字符串相似性计算的过程.

问题三.假设已经从查询LOG里面选择了一批用户相关查询信息,按照什么顺序输出呢?为什么”大长今主题曲”排列在”大长今下载”前面呢?这里面牵涉到排序原则的问题.

我们一步步分析看看百度是如何解决上面的第二和第三个问题的.

首先,百度在计算字符串相似性的计算过程是首先对于用户查询进行分词,然后对于分词后的结果来进行相似性计算的.怎么证明这一点? 第一个证明:首先用”新闻”作为查询,看看百度提示的相关词汇是什么,然后将查询修改为”新闻新闻新闻”,再看看提示的相关词汇是什么,提示是完全一样的,基本说明是分词后进行计算的. 第二个证明: 首先用”娱乐新闻报道”作为查询,看看百度提示的相关查询是什么,然后人工分好词”娱乐 新闻 报道”,再看看提示的相关查询是什么.,提示仍然是完全一样的,我们再颠倒一下词汇顺序,用”新闻娱乐报道”作为查询,再看看相关查询是什么,完全没有变化.所以得出结论:百度在计算字符串相似性之前首先要对用户查询进行分词,当然查询LOG里面的查询也要首先进行分词.

第二步,怎么计算相似性并排序输出呢? 如果用户输入查询只有一个单词,那么处理起来好像比较简单,只要用户查询LOG里面包含这个单词的字符串都被纠出来,然后根据用户总共查询这个字符串的次数进行排序,选择前列K个作为相关提示就可以了. 好像很简单,但是问题真的这么简单就被解决了么? 并非如此.

如果用户输入的查询比较长,问题就出来了,比如我们用“清脆的鸟叫声”作为查询，百度返回的相关提示中，前列1－35个相关查询包含“鸟”和“叫声”，这几个查询排序原则是按照用户查询次数多少排列的，在36－40的相关查询仅仅包含“清脆”一个单词,排列顺序和用“清脆”查询时候顺序相同,说明也是按照用户查询次数多少排列的；41－100的相关查询仅仅包含“叫声”，第41个查询”动物的叫声”是所有100个查询用户查询次数最多的一个. 为什么包含”清脆”的查询排列在包含”叫声”的查询前面而不是反过来呢?

在给个例子,用“咆哮小老鼠”作为查询，排在最前面的是匹配了“咆哮，小，老鼠”三个词汇的相关查询，次之是匹配了“咆哮，老鼠”的相关查询，再次是匹配“咆哮，小”的相关查询，最次是匹配“小，老鼠”的相关查询，总共输出92个相关查询，对于只有一个匹配的查询没有输出。那么为什么是“咆哮，老鼠”》“咆哮，小”》“小,老鼠”呢？原则是什么呢？

多次实验后,发现里面其实有一个匹配单词的权重设置问题,拿”咆哮小老鼠”做例子,切分后是<咆哮,小,老鼠>, 假设用户查询LOG里面有两个查询,一个是”咆哮老鼠论坛”,切分后是<咆哮,老鼠,论坛>.匹配的有两个单词(咆哮,老鼠), 另一个查询是”咆哮小”,切分后是<咆哮,小>,匹配的也有两个单词(咆哮,小),怎么给这两个查询排序呢? 假设每个单词都有一个权重设置,比如 Weight(咆哮)=a Weight(小)=b Weight(老鼠)=c . 我们计算”咆哮小老鼠”和”咆哮老鼠论坛”的相似性等于重复单词权重之和,也就是等于a+c,而另外一个查询的相似性等于a+b,然后按照顺序输出就行了.所以这里面关键是如何设置单词的权重.

那么单词权重怎么衡量呢，作为搜索引擎很容易获得的一个单词权重评价因素是IDF，所谓IDF,就是说如果一个单词如果在很多文档中都出现,那么这个单词重要性就很低,比如说”的”,几乎在每个中文网页都出现,那么这个单词的IDF值就非常低.具体计算IDF的公式是

IDF(word)＝log(N/DF(word)),

这里,DF(word)指的是包含单词word的文档数目个数，N指的是文档集合的总的文件个数，我们假设百度索引了6亿个网页,那么这里N=600000000.

我们用IDF来解释百度的相关查询排序因子.首先来解释“清脆的鸟叫声”这个查询的相关查询排序，我们分别用“清脆”“鸟”“叫声”来作为查询，看看有多少网页包含这些词,百度返回结果是：

清脆：找到相关网页约2,390,000篇

鸟： 找到相关网页约14,000,000篇

叫声：到相关网页约3,370,000篇

把这些数值带入上面的公式计算得出IDF权重 IDF(清脆)＝2.39975335 》IDF(叫声)=2.25052135 》IDF(鸟)=1.63202321. 所以前列匹配了“鸟”和“叫声”的权重最大，都包含这两个查询按照用户查询数目多少输出，其他的按照包含”清脆”或者”叫声”的顺序输出.

对于查询“咆哮小老鼠”来说，我们看看是否成立：

百度返回结果：

咆哮：找到相关网页约2,090,000篇

小：找到相关网页约29,600,000篇

老鼠：找到相关网页约11,900,000篇

IDF(咆哮)=2.45800496

IDF(小)=1.30685954

IDF(老鼠)=1.70260429

所以权重是 咆哮>老鼠>小

我们看到前面分析输出顺序是： <咆哮,老鼠> > <咆哮，小> > <小，老鼠>

我们根据上面单词的权重可以看出：

<咆哮,老鼠>＝IDF(咆哮)＋IDF(老鼠)＝4.15

<咆哮，小>=IDF(咆哮)+IDF(小)=3.75

<小，老鼠>=IDF(小)+IDF(老鼠)=3.01

所以百度的顺序按照这个顺序输出。

再看个例子：查询“娱乐新闻报道”百度返回结果：

娱乐：找到相关网页约31,600,000篇

新闻：找到相关网页约93,500,000篇

报道：找到相关网页约17,000,000篇

IDF(娱乐)=1.27846417

IDF(新闻)= 0.80733964

IDF(报道)=1.54770233

我们可以预测：

包含《娱乐，新闻，报道》的相关查询排名最高，次之是《娱乐，报道>,再次是《新闻，报道》,可以看出百度的排序果然是如此。所以我们的推理基本上是正确的.

最后归纳一下相关查询的算法流程:

(1) 用户输入查询，分词;

(2) 计算用户查询和历史用户查询的相似性，相似性计算是通过计算两者重复单词的权重之和来计算的

(3) 每个单词的权重用单词的IDF来计算，大的排序原则根据这个权重进行排序输出，如果两个历史查询包含相同的重复词汇集合，那么查询权重相同，则按照用户查询次数有高到低排序输出。

后台作业：为了加快查询反映速度，搜索引擎不会每次用户查询都重新计算相关查询，可以在后台算好以后存储在数据库里面，用户查询的时候直接查找数据库输出，那么后台如何处理呢？

（1）对于最近一段时间（比如一个月或者一个星期）用户查询LOG进行统计分析，选择列在前列比如1千万条最频繁的用户查询，

（2）然后对于每个查询分词，按照倒排文档进行存储，比如“新闻报道 10000”，则在索引里面登录 “新闻－－》新闻报道 10000” “报道－－>新闻报道 10000”，其他查询都是如此处理进入索引。

（3）对于用户查询，在索引里面查找最相似的历史查询，并按照上面介绍的方法计算权重，按照权重输出；

（4）当然，为了更加加快查询速度，第三步骤的工作也可以预先算好，存储在数据库里面，用户查询直接在数据库里面存取。这个数据库可以每隔一段时间更新一次以反映最新的情况。

CACHE结构

Cache是目前实用的搜索引擎都必备的功能,因为研究表明用户的查询有相当比例(30%-40%)是重复的,而且大多数重复的用户查询会在较短的间隔时间被再次重复访问.比如说目前"芙蓉姐姐"成为街头巷议的美谈,那么不仅张三想搜索"芙蓉姐姐",王二麻子同样也想搜索,以免被隔壁的李四笑话赶不上时代潮流.既然大家的关注焦点是差不多的,那么没有必要每次接受到查询后都从索引库里面查找,把大量的用户查询放到CACHE里面,肯定能够节省不少计算资源.

那么如何设计一个CACHE能够更加有效的节省计算资源呢?我们还是照旧分析一下百度是如何做的，当然，因为CACHE分析可以获得的外部信息非常少而且即使是获得的信息也不太可靠所以分析起来难度还是比较大的，所以下面的分析中有很大的比例是猜测的成分.

CACHE设计主要关注两个大的方面:

一个是CACHE的结构是怎样的?是只设计一个CACHE就拉倒呢?还是设计两级CACHE乃至三级CACHE?当然这里的二级三级不是咱们大老爷们们喜闻乐见的电影分级标准,而是优先级别的意思,你别指望从三级CACHE里面看到的都是清凉图片.

第二个方面是采取何种替换算法?毕竟CACHE是宝贵的资源,当CACHE里面已经被塞满的时候,把哪个记录踢出CACHE才合算呢?

我们看看百度的CACHE结构是怎样的.经过分析加推测,百度的CACHE系统可能有三个CACHE,用鲁迅先生的说法:百度有三个加快查询匹配的结构,其中一个是CACHE,另外一个也是CACHE,还有一个同样是CACHE.也就是说有一级CACHE,有二级CACHE,还有三级CACHE.

这个一级CACHE是相当容易看出来的,我们可以随便想一个比较古怪的查询,之所以这样是避免CACHE里面已经保存了这个查询条件,以免影响我们的判断,比如说用"可见阿斯蒂芬健康法",这个查询够怪了吧,不会有哪位老兄象我一样无聊到要查这个东西吧,提交给百度,百度提示"找到相关网页约9,890篇，用时0.236秒",至于这个查询是否在CACHE里面，除了上帝,我估计连百度设计CACHE系统的技术人员也不知道.接着我们再次把这个查询提交给百度,百度提示"找到相关网页约9,890篇，用时0.001秒",嗯,这下有了一些线索了,看看时间的变化,从0.236秒到0.001秒(当然,分析CACHE是相当困难的,因为可以看到的线索太少,这里如果只凭借搜索时间是无法判断是否从CACHE里面存取的,必须结合几个方面:时间变化,找到的页面个数以及首页内容排序是否变化.如果找到页面个数不变,首页内容排序不变,即使时间变得很大,也极有可能是从CACHE里面获得的结果),从时间变化和返回结果以及首页排序来说,虽然我不知道第一次查询是否从CACHE里面返回结果,但是可以肯行的是第二次查询肯定是从CACHE里面获取的.再用其它几个例子测试,你会发现,只要是你两次提交同样的查询,第二次返回时间总是0.001秒.这明显是从第一级CACHE取得的结果,也就是说如果百度第一次检索发现查询不在一级CACHE里面,那么立即把这个查询调入一级CACHE.同时,这个一级CACHE是完全精确匹配的,如果查询有任何细微的变化,那么都无法从一级CACHE里面找到,百度对于一级CACHE的匹配很有可能是采用HASH计算,这样速度会相当快.我们可以设想百度的一级CACHE里面记录结构如下:

HASH_id--->|record1<Query1,doc1_info,doc2_info,....docn_info>|record2<Query2,doc1'_info,doc2'_info,...docm'_info>...

当然,上面是个简略的表达,还有很多其它的信息比如加入CACHE的时间长短以及命中次数等其它信息.

二级CACHE是否存在呢?为了能够将故事讲明白,在分析其它CACHE是否存在之前,我们首先需要介绍一下搜索引擎的索引.

简单来说,搜索引擎的最核心的索引是倒排文档,这种数据结构是为了加快信息提取的速度,倒排文档的结构如下:

word--><doc_id1,other info>|<doc_id2,other info>|....<doc_idk,other info>

倒排文档记录了哪些文件出现过词汇word,上面的结构表明了doc_id1,doc_id2一直到doc_idk这么K个文档都出现过单词word.有了这个数据结构,假设用户的查询是单词"word",那么直接查找倒排文档表,就能把包含单词word的网页信息全部提取出来,然后按照一定规则排序输出即可.假设用户的查询有两个单词"word1 word2",那么从倒排文档里面提取包含word1的网页ID列表,再提取包含word2的网页ID列表,然后求两个列表的交集(搜索引擎一般假设用户查询是"与"的关系)这个交集里面的网页就是同时包含word1和word2的页面,然后按照一定规则排序输出,对于包含更多查询词汇的用户查询,基本上道理是一样的.

好了,我们在转回来分析二级CACHE的问题,假设让我们来设计CACHE系统的话,一个最容易想到的方法是设立两个CACHE,一个放在内存,另外一个放在磁盘,两者都采取精确匹配,如果在内存CACHE里面没有找到,那么就到磁盘CACHE里面查找,如果找到则只执行一次磁盘I/O就可以输出结果,如果还是没有找到,那么在索引库里面按照切分好的单词进行查找,一方面切分出多少单词,就查找索引几次,另外一方面索引库总是远远大于磁盘CACHE,所以搜索时间肯定比磁盘CACHE查找慢.所以我们可以假定百度的二级CACHE是存储在磁盘的常用用户查询,当然至于百度是否有这么个CACHE我也不知道,全当猜测好了.

至于三级CACHE是否存在的问题，只能说很可能存在，之所以这么说，这里面有部分证据因素,也有部分推理因素。我们先说一下三级CACHE应该存在的推理因素,通过上面的分析,我们已经确认的是:百度的一级CACHE是存在的,而且是完全精确匹配.如果有两个查询:查询1:"芙蓉 姐姐" 查询2:"芙蓉 姐夫" 假设第一个查询已经进入一级CACHE,再搜索第二个查询的时候,因为一级CACHE要求精确匹配,所以第二个查询会被认为没有在CACHE找到,如果二级CACHE存在,也同样无法找到,那么这两个查询单词都必须从索引里面提取,但是事实上两个查询是存在交集"芙蓉"这个词汇的,没有理由每次都从索引里面提取,更合理的方式是把常用单词的倒排文档信息放在另外一个内存的CACHE里面,假设用户新的查询经过分词后包含若干单词,如果发现这个三级CACHE包含这个单词那么直接从CACHE里面读取,如果CACHE没有那么需要通过读磁盘文件来获得单词的倒排文档信息,这个CACHE的作用主要是节省磁盘I/O时间,直接在内存读取信息当然比读取磁盘快很多.所以从道理上是应该有这么一个在内存的三级CACHE的.

接着提供一些证据来确认,输入查询"流浪",百度提示"找到相关网页约11,000,000篇，用时0.001秒",说明这个查询是在一级CACHE里面找到的,修改查询为"流浪 流浪"百度提示为"找到相关网页约11,000,000篇，用时0.144秒",从时间信息看说明一级CACHE里面没有找到,另外由于找到的页面没有变化,首页内容排序没有变化,所以很有可能是从CACHE里面读取的,当然这只能是一种可能性,并不能排除是从磁盘读取的.另外一个证据,输入查询"流浪 在线",百度提示"找到相关网页约2,080,000篇，用时0.174秒",修改查询为"在线 流浪",百度返回信息"找到相关网页约2,080,000篇，用时0.178秒 ",同时首页排序没有变化,另外时间0.178秒也不是很长. 所以很有可能是从CACHE里面读取的,当然同样并不能排除是从磁盘读取的.然而,如果一个查询是从磁盘读取的,那么必然查询越长,磁盘读写次数越多,时间越慢.但是构造一个很长的查询"在线 流浪 在线 流浪 在线 流浪 在线 流浪",百度提示"找到相关网页约2,080,000篇，用时0.179秒",时间基本上没有增加,页面排序也没有变化,所以有很大的可能是采用了上面讲的第三级CACHE。

至于CACHE淘汰算法,现有的成熟并常用的CACHE淘汰算法包括LRU,SLRU,FBR,LRU/2等等,因为研究表明如果CACHE足够大的话,这些算法的效率尽管有细微的差别,但是总体上差不多,在实现的时候选择最简单的一个即可.

所以,归纳上面的叙述内容,可以得到如下的三级CACHE算法:

1.存在三级CACHE,一级CACHE在内存中,采取完全精确匹配,二级CACHE在磁盘中,采取完全精确匹配,三级CACHE在内存中,采取非完全精确匹配;

2.得到用户查询编码,HASH计算得到HASH编码,在一级CACHE里面查找,如果找到输出,同时该查询命中次数计数器加1；

3.如果在一级CACHE没有命中,则在二级CACHE精确查找,如果找到输出,同时该查询命中次数计数器加1并将该查询相关信息加载到一级CACHE;

4.如果在二级CACHE没有找到,用户查询分词,判断组成查询的各个词汇是否在三级CACHE里面存在,如果存在则直接得到倒排文档列表,如果不存在则从索引库里面查找该词汇的倒排文档列表,并将该词汇及其倒排文档列表加入三级CACHE,计算各个查询词汇倒排文档列表的交集,并将其放入一级CACHE和二级CACHE.
[size=x-small][/size][align=left][/align][u][/u]