查看文章 |
(1)-(4) http://blog.csdn.net/malefactor/archive/2005/11.aspx (5) http://blog.csdn.net/malefactor/archive/2006/01/04/570025.aspx 中科院软件所 张俊林 查询处理以及分词技术 随着搜索经济的崛起，人们开始越加关注全球各大搜索引擎的性能、技术和日流量。作为企业，会根据搜索引擎的知名度以及日流量来选择是否要投放广告等；作为 普通网民，会根据搜索引擎的性能和技术来选择自己喜欢的引擎查找资料；作为技术人员，会把有代表性的搜索引擎作为研究对象。 搜索引擎经济的崛起，又一次向人们证明了网络所蕴藏的巨大商机。网络离开了搜索将只剩下空洞杂乱的数据，以及大量等待去费力挖掘的金矿。 但是，如何设计一个高效的搜索引擎？我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎。搜索引擎涉及到许多技术点，比如查询处理，排序算法，页面抓取算法，CACHE机制，ANTI-SPAM等等。这些技术细节，作为商业公司的搜索引擎服务提供商比如百度，GOOGLE等是不会公之于众的。我们可以将现有的搜索引擎看作一个黑盒，通过向黑盒提交输入，判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节。 查询处理与分词是一个中文搜索引擎必不可少的工作，而百度作为一个典型的中文搜索引擎一直强调其“中文处理”方面具有其它搜索引擎所不具有的关键技术和优势。那么我们就来看看百度到底采用了哪些所谓的核心技术。 我们分两个部分来讲述：查询处理/中文分词。 一、查询处理 用户向搜索引擎提交查询，搜索引擎一般在接受到用户查询后要做一些处理，然后在索引数据库里面提取相关的信息。那么百度在接受到用户查询后做了些什么工作呢？ 1、假设用户提交了不只一个查询串，比如“信息检索 理论 工具”。那么搜索引擎首先做的是根据分隔符比如空格，标点符号，将查询串分割成若干子查询串，比如上面的查询就会被解析为：<信息检索，理论，工具>三个子字符串；这个道理简单，我们接着往下看。 2、假设提交的查询有重复的内容，搜索引擎怎么处理呢？比如查询“理论 工具 理论”，百度是将重复的字符串当作只出现过一次，也就是处理成等价的“理论 工具”，而GOOGLE显然是没有进行归并，而是将重复查询子串的权重增大进行处理。那么是如何得出这个结论的呢？我们可以将“理论 工具”提交给百度，返回341,000篇文档，大致看看第一页的返回内容。OK。继续，我们提交查询“理论 工具 理论”，在看看返回结果，仍然是那么多返回文档，当然这个不能说明太多问题，那看看第一页返回结果的排序，看出来了吗？顺序完全没有变化，而GOOGLE 则排序有些变动，这说明百度是将重复的查询归并成一个处理的，而且字符串之间的先后出现顺序基本不予考虑（GOOGLE是考虑了这个顺序关系的）。 3、假设提交的中文查询包含英文单词，搜索引擎是怎么处理的？比如查询”电影BT下载”，百度的方法是将中文字符串中的英文当作一个整体保留，并以此为断点将 中文切分开，这样上述的查询就切为<电影，BT，下载>，不论中间的英文是否一个字典里能查到的单词也好，还是随机的字符也好，都会当作一个 整体来对待。至于为什么，你用查询“电影dfdfdf下载”看看结果就知道了。当然如果查询中包含数字，也是如此办理。 到目前为止，一切很简单，也很清楚，百度怎么处理用户查询的呢？归纳如下：首先根据分割符号将查询分开，然后看看是否有重复的字符串，如果有，就抛弃多余的，只保留一个，接着判断是否有英文或者数字，如果有的话，把英文或者数字当作一个整体保留并把前后的中文切开。 接着该干什么呢？该考虑分词的问题了。 二、中文分词 首先，讲讲百度的分词时机或者条件问题，是否是个中文字符串百度就拿来切一下呢？非也，要想被百度的分词程序荣幸的切割一下也是要讲条件的，哪能是个字符串就切割啊？你当百度是卖锯条的么？ 那么什么样的字符串才满足被切割的条件呢？简单说来，如果字符串只包含小于等于3个中文字符的话，那就保留不动，当字符串长度大于4个中文字符的时候，百度的分词程序才出马大干快上，把这个字符串肢解掉。 怎么证明呢？我们向百度提交“电影下载”，看看返回结果中标为红字的地方，不难看出来，查询已经被切割成<电影，下载>两个单词了，说明分词程序已经开工了，如果是比4个中文字符更长的字符串，那分词程序就更不客气了，一定大卸八块而后快。我们来看看三个字符的情况，提交查询“当然择”，看起来这个查询不伦不类，那是因为我希望看到这个字符串被切分为<当然，择>，返回结果365篇相关页面，翻到最后一页，发现标红的关键字都是” 当然择”连续出现的情况，好像没有切分，但是还不确定，那么再提交人工分好的查询“当然 择”看看，返回结果1，090，000篇，基本上可以确定没有进行分词了，当然另外一种解释是：对于三个字符先切分，然后将切分后的结果当作一个短语查 询，这样看到的效果和没有切分是相似的。但是我倾向于判断百度对于少于3个字符的串没有切分，奥卡姆不是说了么“如无必要，勿增实体”，干吗做无用功呢。 那么如果没有切分，会有一个随之而来的问题，怎么从索引库里面提取未切分的字符串呢？这牵扯到索引的问题，我觉得百度应该采取了两套索引机制，一种是按照 单词索引，一种是按照N-GRAM索引，至于索引的具体问题，以后在详细论述。 下面我们看看百度是采取的何种分词算法，现在分词算法已经算是比较成熟了，有简单的有复杂的，比如正向最大匹配，反向最大匹配，双向最大匹配，语言模型方 法，最短路径算法等等，有兴趣的可以用GOOGLE去搜索一下以增加理解。这里就不展开说了。但是要记住一点的是：判断一个分词系统好不好，关键看两点， 一个是消除歧义能力；一个是词典未登录词的识别比如人名，地名，机构名等。 那么百度用的是什么方法？我的判断是用双向最大匹配算法。至于怎么推理得出的，让我们一步步来看。当然，这里首先有个假设，百度不会采取比较复杂的算法，因为考虑到速度问题。 我们提交一个查询“毛泽东北京华烟云”，又一个不知所云的查询，尽管不知所云但是自有它的道理，我想看看百度的分词是如何消歧以及是否有词典未登录词的识 别的功能，如果是正向最大匹配算法的话，那么输出应该是：”毛泽东/北京/华/烟云”，如果是反向最大匹配算法的话，那么输出应该是：”毛/泽/东北/京 华烟云”，我们看看百度的分词结果：”毛泽东/北/京华烟云”，一个很奇怪的输出，跟我们的期望相差较多，但是从中我们可以获得如下信息：百度分词可以识 别人名，也可以识别”京华烟云”，这说明有词典未登录词的识别的功能，我们可以假设分词过程分为两个阶段：第一阶段，先查找一个特殊词典，这个词典包含一 些人名，部分地名以及一些普通词典没有的新词，这样首先将”毛泽东”解析出来，剩下了字符串”北京华烟云”，而”北/京华烟云”，可以看作是反向最大匹配 的分词结果。这样基本说得通。为了证明这一点，我们提交查询”发毛泽东北”，我们期望两种分词结果，一个是正向最大匹配<发毛，泽，东北>， 一个是上述假设的结果<发，毛泽东，北>，事实上百度输出是第二种情况，这样基本能确定百度分词采取了至少两个词典，一个是普通词典，一个是 专用词典（人名等）。而且是专用词典先切分，然后将剩余的片断交由普通词典来切分。 继续测验，提交查询“古巴比伦理”，如果是正向最大匹配，那么结果应该是<古巴比伦，理>，如果是反向最大匹配，那么结果应该是<古 巴，比，伦理>，事实上百度的分词结果是<古巴比伦，理>，从这个例子看，好像用了正向最大匹配算法；此外还有一些例子表明好像是使用 正向最大匹配的；但是且慢，我们看这个查询“北京华烟云”，正向最大匹配期望的结果是<北京，华，烟云>，而反向最大匹配期望的结果是 <北，京华烟云>，事实上百度输出的是后者，这说明可能采用的反向最大匹配；从这点我们可以猜测百度采用的是双向最大匹配分词算法，如果正向 和反向匹配分词结果一致当然好办，直接输出即可；但是如果两者不一致，正向匹配一种结果，反向匹配一种结果，此时该如何是好呢？从上面两个例子看，在这种 情况下，百度采取最短路径方法，也就是切分的片断越少越好，比如<古巴，比，伦理>和<古巴比伦，理>相比选择后者，<北 京，华，烟云>和<北，京华烟云>相比选择后者。还有类似的一些例子，这样基本可以解释这些输出结果。 但是仍然遗留的问题是：如果正向反向分词不一致，而且最短路径也相同，那怎么办？输出正向的还是反向的结果？我们再来看一个例子。提交查询“遥远古古巴比 伦”，这个查询被百度切分为<遥远，古古，巴比伦>，说明词典里面有”巴比伦”，但是是否有”古巴比伦”这个词汇不确定，此时看不出是正向切 分还是反向切分得出的结果，换查询为“遥远古巴比伦”，此时被切分为“遥远/古巴比伦”，这说明词典里面有”古巴比伦”这个词汇，这说明了“遥远古古巴比 伦”是正向最大匹配的结果。那为什么“遥远古古巴比伦”不会被反向切分为”遥/远古/古巴比伦”呢，百度的可能选择是这种情况下选择单字少的那组切分结 果。 当然还可以继续追问：如果切分后单字也一样多，那怎么办？最后看一个例子，查询“王强大小：”，百度将其切分为“王/强大/小”，是正向切分的结果，如果是反向的会被切分为“王/强/大小”，这说明有歧义而且单字也相同则选择正向切分结果。 OK，看到这里可能头已经有些晕了，最后总结一下百度的分词算法，当然里面还是有猜测的成分，算法如下： 首先查询专用词典（人名，部分地名等），将专有名称切出，剩下的部分采取双向分词策略，如果两者切分结果相同，说明没有歧义，直接输出分词结果。如果不一 致，则输出最短路径的那个结果，如果长度相同，则选择单字词少的那一组切分结果。如果单字也相同，则选择正向分词结果。 百度一直宣传自己在中文处理方面的优势，从上面看，分词算法并无特殊之处，消歧效果并不理想，即使百度采取比上述分词算法复杂些的算法也难以说成是优势， 如果说百度有优势的话，唯一的优势就是那个很大的专用词典，这个专用词典登录了人名（比如大长今），称谓（比如老太太），部分地名（比如阿联酋等），估计 百度采用学术界公布的比较新的命名实体识别算法从语料库里面不断识别出词典未登录词，逐渐扩充这个专门词典。如果这就是优势的话，那么这个优势能够保持多久就是个很明显的问题。 Spelling Checker拼写检查错误提示(以及拼音提示功能) 我们分析拼写检查系统关注以下几个问题: (1)系统如何判断用户的输入是有可能发生错误的查询呢? (2)如果判断是可能错误的查询输入,如何提示正确的词汇呢? 那么百度是怎么提示正确词汇的呢?很明显是通过拼音的方式,比如我输入查询" 制才",百度提供的提示词汇为: “:制裁 质材 纸材",都是同 音字.所以百度必然维持着一个同音词词典,里面保留着同音词信息,比如可能包含着下面这条词条: “ zhi cai à制裁,质材,纸材",另外还有一 个标注拼音程序,现在能够看到的基本流程是: 用户输入" 制才",查词典,发现没有这个词汇,OK,启动标注拼音程序,将" 制才"标注为拼音"zhi cai",然后查找同音词词典,发现同音词" 制裁,质材,纸材",那么提示用户可能的正确拼写. 整体流程看起来很简单,但是还有一些遗留 的小问题,比如是否将词表里面所有同音词都作为用户的提示信息呢?比如某个拼音有10个同音词,是否都输出呢?百度并没有将所有同音词都输 出而是选择一定筛选标准,选择其中几个输出.怎么证明这一点?我们看看拼音"liu li"的同音词,紫光输入法提示同音词汇有" 流丽 流离 琉璃 流利"4个,我们看看百度返回几个,输入"流厉"作为查询,这里是故意输入一个词典不包含的词汇,这样百度的拼写检查才开始工作,百度提示: " 琉璃刘丽 刘莉 ",这说明什么?说明不是所有同音词都输出,而是选择输出,那么选择的标准是什么?我能够猜测到的方法是对于用户查询LOG进行 统计,提取用户查询次数多的那些同音词输出,如果是这样的话,上面的例子说明用户搜索"琉璃"次数比其它的都要高些,次之是" 刘丽",再次是" 刘莉",看来大家都喜欢查询自己或者认识的人的名字. 另外一个小问题:同音词词典包含2字词,3字词,那么是否包含4字词以及更长的词 条?是否包含一字词? 这里一字词好回答,不用测试也能知道肯定不包含,因为你输入一个字,谁知道是否是错误的呢?反正只要是汉字就能在词表 里面找到,所以没有判断依据.二字词是包含的,上面有例子,三字词也包含,比如查询 "中城药"百度错误提示:"中成药",修改查询为"重城药",还 是提示"中成药" ,再次修改查询 "重城要",百度依然提示"中成药". 那么4字词汇呢? 百度还是会给你提示的,下面是个例子: 输入:静华烟云 提示 京华烟云 输入:静话烟云 提示 京华烟云 输入:静话阎晕 提示 京华烟云 那么更长的词汇是否提 示呢?也提示,比如我输入: "落花世界有风军",这个查询是什么意思,估计读过古诗的都知道,看看百度的提示"落花时节又逢君",这说明什么?说 明同音词词典包含不同长度的同音词信息,另外也说明了百度的核心中文处理技术,也就是那个词典,还真挺大的. 但是,如果用户输入的 查询由两个或者两个以上子字符串构成,那么百度的错误提示功能就罢工了,比如输入查询"哀体",百度提示"艾提 挨踢",但是.输入为 "我 哀体 ",则没有任何错误提示. 还有一个比较重要的问题:如果汉字是多音字那么怎么处理?百度呢比较偷懒,它根本就没有对多音字做处理.我 们来看看百度的一个标注拼音的错误,在看这个错误前先看看对于多音字百度是怎么提示错误的,我们输入查询"俱长",百度提示"剧场 局长", “俱长"的拼音有两个:"ju zhang /ju chang" ,可见如果是多音字则几种情况都提示..现在我们来看看错误的情况, 我们输入查询"剧常",百度 提示":剧场局长",提示为"剧场"当然好解释,因为是同音字,但是为什么 "局长"也会被提示呢?这说明百度的同音字词典有错误,说明在"ju chang"这个词条里面包含"局长"这个错误的同音词.让我们顺藤摸瓜,这个错误又说明什么问题呢?说明百度的同音词典是自动生成的,而且没有 人工校对.还说明在自动生成同音词典的过程中,百度不是根据对一篇文章标注拼音然后在抽取词汇和对应的拼音信息获得的,而是完全按照某个 词典的词条来标注音节的,所以对于多音字造成的错误无法识别出来,如果是对篇章进行拼音标注,可能就不会出现这种很容易发现的错误标注. 当然还有另外一种解释,就是"局长"是故意被百度提示出来可能的正确提示词汇,因为考虑到南方人"zh"和 "ch"等前后鼻音分不清么,那么是这 样的么?我们继续测试到底是何种情况.是百度有错误还是这是百度的先进的算法? 我们考虑词汇"长大 ",故意错误输入为"赃大",如果 百度考虑到了前后鼻音的问题,那么应该会提示"长大",但是百度提示是"藏大".这说明什么?说明百度并没有考虑前后鼻音问题,根本就是系统错 误. 我们输入查询"悬赏",故意将之错误输入为"悬桑",没有错误提示,说明确实没有考虑这种情况.前鼻音没有考虑,那么后鼻音考虑了么,我们 输入":经常",故意改为后鼻音 "经缠",百度提示为"经产 经忏",还是没有考虑后鼻音.这基本可以确定是百度系统的错误导致. 根据以 上推导, 我们可以得出如下结论:百度是将分词词典里面每个词条利用拼音标注程序标注成拼音,然后形成同音词词典,所以两个词典是同样大的 ,而且这个词典也随着分词词典的增长而在不断增长. 至于标注过程中多音字百度没有考虑,如果是多音字就标注成多个发音组合,通过这种方式 形成同音词词典.这样的同音词词典显然包含着很多错误. 最后一个问题:百度对于英文进行拼写检查么?让我们试试看,输入查 询"china",不错,搜到不少结果,专注中文搜索的百度还能搜索到英文,真是意外的惊喜.变换一下查询"chine",会更加意外惊喜的给我们提 示"china"吗?百度提示的是: 吃呢持呢,原来是不小心触发了百度的拼音搜索功能了.那么拼音搜索和中文检查错误是否采用同一套同音词词典 呢,让我们来实验一下,搜索"rongji",百度提示" 榕基 溶剂 容积",OK,换个中文查询"容机",百度提示" 榕基 溶剂容积",看来使用的是同一套 同音词词典.也就是说百度的中文纠错和拼音检索使用的机制相同,中文纠错多了一道拼音注音的过程而已.难道这就是传说中那个百度的"事实 上是一个无比强大的拼音输入法"的拼音提示功能么? 最后让我们总结归纳一下百度的拼写检查系统: 后台作业: (1)前面的文 章我们说过,百度分词使用的词典至少包含两个词典一个是普通词典,另外一个是专用词典(专名等),百度利用拼音标注程序依次扫描所有词典中 的每个词条,然后标注拼音,如果是多音字则把多个音都标上,比如"长大",会被标注为"zhang da/chang da"两个词条. (2)通过标注完的 词条,建立同音词词典,比如上面的"长大",会有两个词条: zhang daà长大" , chang daà长大. (3)利用用户查询LOG频率信息给予每个 中文词条一个权重; (4)OK,同音词词典建立完成了,当然随着分词词典的逐步扩大,同音词词典也跟着同步扩大; (1)用户输入查询,如果是多个子字符串,不作拼写检查; (2)对于用户查询,先查分词词典,如果发现有这个单词词条,OK, 不作拼写检查; (3)如果发现词典里面不包含用户查询,启动拼写检查系统;首先利用拼音标注程序对用户输入进行拼音标注; (4)对于标注好的拼音在同音词词典里面扫描,如果没有发现则不作任何提示; (5)如果发现有词条,则按照顺序输出权重比较大的几个提 示结果; (1)对于用户输入的拼音在同音词词典里面扫描,如果没有发现则不作任何提示; (2)如果 发现有词条,则按照顺序输出权重比较大的几个提示结果; 百度分词算法的进一步分析 上面说过,经过分析得出百度的分词系统采用双向最大匹配分词,但是后来发现推理过程中存在一个漏洞,而且推导出来的百度分词算法步骤还是过于繁琐,所以进一步进行分析,看看是否前面的推导有错误. 那么以前的分析有什么漏洞呢?我们推导百度分词有反向最大匹配的依据是百度将"北京华烟云"分词为<北,京华烟云>,从这里看好像采用了反向最大匹配,因为正向最大匹配的结果应该是<北京,华,烟云>,但是由此就推论说百度采用了双向最大匹配还是太仓促了,前面文章我们也讲过,百度有两个词典,一个普通词典,一个专有词典,而且是专有词典的词汇先切分,然后将剩余片断交给普通词典去切分.所以上面的"北京华烟云"之所以被切分成<北,京华烟云>,另外一个可能是:京华烟云这个词汇是在专有词典里面存储的,所以先分析,这样得出"京华烟云",剩下"北",没什么好切分的,所以输出<北,京华烟云>. 这里只是假设,那么是否确实"京华烟云"在专有词典呢?我们再看一个例子"山东北京华烟云",百度切分的结果是<山东,北,京华烟云>,如果"京华烟云"在普通词典,如果是反向切分,那么结果应该是<山,东北,京华烟云>,如果是正向切分应该是<山东,北京,华,烟云>,无论如何都分不出<山东,北,京华烟云>.这说明什么?说明"京华烟云"是在那个专有词典,所以先切分出"京华烟云",然后剩下的"山东北"交由普通词典切分,明显是正向最大匹配的结果输出<山东,北>.当然按照我们在第一篇文章的算法推导"山东北"的切分也会得出<山东,北>的结论,但是明显比正向最大匹配多几个判断步骤,既然效果一样,另外一个更加简洁的方法也能说得通,那当然选择简便的方法了.所以初步判断百度采取的是正向最大匹配. 我们继续测试采用何种分词算法,为了减少专有词典首先分词造成的影响,那么查询里面不能出现相对特殊的词汇,构筑查询"天才能量级",这里应该没有专有词典出现过的词汇,百度切分为<天才,能量,级>,看来是正向最大匹配的结果.另外,如果所有查询词汇都出现在专有词典,那么采取的是何种方法?这样首先就得保证词汇都出现在专有词典,这么保证这一点呢?我们构造查询"铺陈晓东方",百度切分为<铺,陈晓东,方>,可以看出"陈晓东"是在专有词典的所以先切分出来.另外一个例子 "山东京城",百度切分为<山东,京城>,说明"东京"是在普通词典的.OK,构造查询"陈晓东京华烟云",通过前面分析可以看出两个词汇都在专有词典里面,百度切分为<陈晓东,京华烟云>,说明对于专有词典词汇也是采取正向最大匹配或者双向最大匹配.那么使用反向最大匹配了吗?构造查询例子"陈晓东方不败",首先我们肯定"陈晓东"和"东方不败"都是在专有词典出现的,如果是正向切分,那么应该是<陈晓东,方,不败>或者<陈晓东,方,不,败>如果是反向切分则是<陈,晓,东方不败>,可以看出百度的切分是<陈晓东,方,不败>或者<陈晓东,方,不,败>,说明采用的是正向最大匹配.通过分析,百度的词典不包含"不败"这个单词,所以实际上百度的切分结果是<陈晓东,方,不,败>,很明显这和我们以前推导的算法是有矛盾的,所以以前的分析算法确实有问题,所以结论是百度采取的是正向最大匹配算法. 重新归纳一下百度的分词系统:首先用专有词典采用最大正向匹配分词,切分出部分结果,剩余没有切分交给普通词典,同样采取正向最大匹配分词,最后输出结果. 另外,GOOGLE也是采用正向最大匹配分词算法,不过好像没有那个专用词典,所以很多专名都被切碎了. 从这点讲,GOOGLE在中文词典构建上比百度差些,还需要加把子力气才行,不过这也不是什么多难的事. 相关提示功能 相关提示也是几乎所有搜索引擎提供的一个附加功能,所谓相关提示,就是对于用户提交的查询进行分析,然后根据其它用户相似的查询给予用户提示,比如我输入查询”大长今”,检索系统会提示其它象”大长今主题曲”,”大长今下载”等等相关的一些其它用户查询. 那么搜索引擎是根据什么原则对于其它用户的查询进行选择来提示用户相关查询呢?我们还是以百度为例子来看看怎么实现这个功能.要实现这个功能主要解决如下三个问题: 问题一.从哪里获得其它用户的查询信息?这个问题对于搜索引擎来说不是难事,因为搜索引擎都有用户查询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. |
