搜索引擎技术
-
2023年3月5日发(作者：百合种子)搜索引擎设计⼀（百度为例）
搜索引擎设计实⽤教程-以百度为例
之⼀:查询处理以及分词技术
中科院软件所张俊林
2005年11⽉
随着搜索经济的崛起，⼈们开始越加关注全球各⼤搜索引擎的性能、技术和⽇流量。作为企业，会根据搜索引擎的知名度以及⽇流量来选择是否要投放⼴告
等；作为普通⽹民，会根据搜索引擎的性能和技术来选择⾃⼰喜欢的引擎查找资料；作为技术⼈员，会把有代表性的搜索引擎作为研究对象.搜索引擎经济的崛
起，⼜⼀次向⼈们证明了⽹络所蕴藏的巨⼤商机。⽹络离开了搜索将只剩下空洞杂乱的数据，以及⼤量等待去费⼒挖掘的⾦矿。
但是,如何设计⼀个⾼效的搜索引擎?我们可以以百度所采取的技术⼿段来探讨如何设计⼀个实⽤的搜索引擎.搜索引擎涉及到许多技术点,⽐如查询处理,排序算
法,页⾯抓取算法,CACHE机制,ANTI-SPAM等等.这些技术细节,作为商业公司的搜索引擎服务提供商⽐如百度,GOOGLE等是不会公之于众的.我们可以将现有的
搜索引擎看作⼀个⿊盒,通过向⿊盒提交输⼊,判断⿊盒返回的输出⼤致判断⿊盒⾥⾯不为⼈知的技术细节.
查询处理与分词是⼀个中⽂搜索引擎必不可少的⼯作,⽽百度作为⼀个典型的中⽂搜索引擎⼀直强调其”中⽂处理”⽅⾯具有其它搜索引擎所不具有的关键技术和优
势.那么我们就来看看百度到底采⽤了哪些所谓的核⼼技术.
我们分两个部分来讲述:查询处理/中⽂分词.
⼀.查询处理
⽤户向搜索引擎提交查询,搜索引擎⼀般在接受到⽤户查询后要做⼀些处理,然后在索引数据库⾥⾯提取相关的信息.那么百度在接受到⽤户查询后做了些什么⼯
作呢?
1.假设⽤户提交了不只⼀个查询串,⽐如”信息检索理论⼯具”.那么搜索引擎⾸先做的是根据分隔符⽐如空格,标点符号,将查询串分割成若⼲⼦查询串,⽐如上
⾯的查询就会被解析为:三个⼦字符串;这个道理简单,我们接着往下看.
2.假设提交的查询有重复的内容,搜索引擎怎么处理呢?⽐如查询”理论⼯具理论”,百度是将重复的字符串当作只出现过⼀次,也就是处理成等价的”理论⼯
具”,⽽GOOGLE显然是没有进⾏归并,⽽是将重复查询⼦串的权重增⼤进⾏处理.那么是如何得出这个结论的呢?我们可以将”理论⼯具”提交给百度,返
回341,000篇⽂档,⼤致看看第⼀页的返回内容.OK.继续,我们提交查询”理论⼯具理论”,在看看返回结果,仍然是那么多返回⽂档,当然这个不能说明太多问题,那
看看第⼀页返回结果的排序,看出来了吗?顺序完全没有变化,⽽GOOGLE则排序有些变动,这说明百度是将重复的查询归并成⼀个处理的,⽽且字符串之间的先后出
现顺序基本不予考虑(GOOGLE是考虑了这个顺序关系的).
3.假设提交的中⽂查询包含英⽂单词,搜索引擎是怎么处理的?⽐如查询”电影BT下载”,百度的⽅法是将中⽂字符串中的英⽂当作⼀个整体保留,并以此为断
点将中⽂切分开,这样上述的查询就切为,不论中间的英⽂是否⼀个字典⾥能查到的单词也好,还是随机的字符也好,都会当作⼀个整体来对待.⾄于为
什么,你⽤查询”电影dfdfdf下载”看看结果就知道了.当然如果查询中包含数字,也是如此办理.
到⽬前为⽌,⼀切很简单,也很清楚,百度怎么处理⽤户查询的呢?归纳如下:⾸先根据分割符号将查询分开,然后看看是否有重复的字符串,如果有,就抛弃多余的,只保
留⼀个,接着判断是否有英⽂或者数字,如果有的话,把英⽂或者数字当作⼀个整体保留并把前后的中⽂切开.
接着该⼲什么呢?该考虑分词的问题了.
⼆.中⽂分词
⾸先,讲讲百度的分词时机或者条件问题,是否是个中⽂字符串百度就拿来切⼀下呢?⾮也,要想被百度的分词程序荣幸的切割⼀下也是要讲条件的,哪能是个字符串
就切割啊?你当百度是卖锯条的么?
那么什么样的字符串才满⾜被切割的条件呢?简单说来,如果字符串只包含⼩于等于3个中⽂字符的话,那就保留不动,当字符串长度⼤于4个中⽂字符的时候,百度的
分词程序才出马⼤⼲快上,把这个字符串肢解掉.
怎么证明呢?我们向百度提交”电影下载”,看看返回结果中标为红字的地⽅,不难看出来,查询已经被切割成两个单词了,说明分词程序已经开⼯了,如果
是⽐4个中⽂字符更长的字符串,那分词程序就更不客⽓了,⼀定⼤卸⼋块⽽后快.我们来看看三个字符的情况,提交查询”当然择”,看起来这个查询不伦不类,那是因为
我希望看到这个字符串被切分为,返回结果365篇相关页⾯,翻到最后⼀页,发现标红的关键字都是”当然择”连续出现的情况,好像没有切分,但是还不确
定,那么再提交⼈⼯分好的查询”当然择”看看,返回结果1,090,000篇,基本上可以确定没有进⾏分词了,当然另外⼀种解释是:对于三个字符先切分,然后将切分后的
结果当作⼀个短语查询,这样看到的效果和没有切分是相似的.但是我倾向于判断百度对于少于3个字符的串没有切分,奥卡姆不是说了么”如⽆必要,勿增实体”,⼲
吗做⽆⽤功呢.那么如果没有切分,会有⼀个随之⽽来的问题,怎么从索引库⾥⾯提取未切分的字符串呢?这牵扯到索引的问题,我觉得百度应该采取了两套索引机
制,⼀种是按照单词索引,⼀种是按照N-GRAM索引,⾄于索引的具体问题,以后在详细论述.
下⾯我们看看百度是采取的何种分词算法,现在分词算法已经算是⽐较成熟了,有简单的有复杂的,⽐如正向最⼤匹配,反向最⼤匹配,双向最⼤匹配,语⾔模型⽅法,最
短路径算法等等,有兴趣的可以⽤GOOGLE去搜索⼀下以增加理解.这⾥就不展开说了.但是要记住⼀点的是:判断⼀个分词系统好不好,关键看两点,⼀个是消除歧
义能⼒;⼀个是词典未登录词的识别⽐如⼈名,地名,机构名等.
那么百度⽤的是什么⽅法?我的判断是⽤双向最⼤匹配算法.⾄于怎么推理得出的,让我们⼀步步来看.当然,这⾥⾸先有个假设,百度不会采取⽐较复杂的算法,因为
考虑到速度问题.
我们提交⼀个查询”⽑泽东北京华烟云”,⼜⼀个不知所云的查询,尽管不知所云但是⾃有它的道理,我想看看百度的分词是如何消歧以及是否有词典未登录词的识别
的功能,如果是正向最⼤匹配算法的话,那么输出应该是:”⽑泽东/北京/华/烟云”,如果是反向最⼤匹配算法的话,那么输出应该是:”⽑/泽/东北/京华烟云”,我们看看百
度的分词结果:”⽑泽东/北/京华烟云”,⼀个很奇怪的输出,跟我们的期望相差较多,但是从中我们可以获得如下信息:百度分词可以识别⼈名,也可以识别”京华烟云”,这
说明有词典未登录词的识别的功能,我们可以假设分词过程分为两个阶段:第⼀阶段,先查找⼀个特殊词典,这个词典包含⼀些⼈名,部分地名以及⼀些普通词典没有
的新词,这样⾸先将”⽑泽东”解析出来,剩下了字符串”北京华烟云”,⽽”北/京华烟云”,可以看作是反向最⼤匹配的分词结果.这样基本说得通.为了证明这⼀点,我们提
交查询”发⽑泽东北”,我们期望两种分词结果,⼀个是正向最⼤匹配,⼀个是上述假设的结果,事实上百度输出是第⼆种情况,这样基本
能确定百度分词采取了⾄少两个词典,⼀个是普通词典,⼀个是专⽤词典(⼈名等).⽽且是专⽤词典先切分,然后将剩余的⽚断交由普通词典来切分.
继续测验,提交查询”古巴⽐伦理”,如果是正向最⼤匹配,那么结果应该是,如果是反向最⼤匹配,那么结果应该是,事实上百度的分词
结果是,从这个例⼦看,好像⽤了正向最⼤匹配算法;此外还有⼀些例⼦表明好像是使⽤正向最⼤匹配的;但是且慢,我们看这个查询”北京华烟云”,正向
最⼤匹配期望的结果是,⽽反向最⼤匹配期望的结果是,事实上百度输出的是后者,这说明可能采⽤的反向最⼤匹配;从这点我们可以
猜测百度采⽤的是双向最⼤匹配分词算法,如果正向和反向匹配分词结果⼀致当然好办,直接输出即可;但是如果两者不⼀致,正向匹配⼀种结果,反向匹配⼀种结
果,此时该如何是好呢?从上⾯两个例⼦看,在这种情况下,百度采取最短路径⽅法,也就是切分的⽚断越少越好,⽐如和相⽐选择后者,
和相⽐选择后者.还有类似的⼀些例⼦,这样基本可以解释这些输出结果.
但是仍然遗留的问题是:如果正向反向分词不⼀致,⽽且最短路径也相同,那怎么办?输出正向的还是反向的结果?我们再来看⼀个例⼦.提交查询”遥远古古巴⽐
伦”,这个查询被百度切分为,说明词典⾥⾯有”巴⽐伦”,但是是否有”古巴⽐伦”这个词汇不确定,此时看不出是正向切分还是反向切分得出的结
果,换查询为”遥远古巴⽐伦”,此时被切分为”遥远/古巴⽐伦”,这说明词典⾥⾯有”古巴⽐伦”这个词汇,这说明了”遥远古古巴⽐伦”是正向最⼤匹配的结果.那为什么”遥
远古古巴⽐伦”不会被反向切分为”遥/远古/古巴⽐伦”呢,百度的可能选择是这种情况下选择单字少的那组切分结果.
当然还可以继续追问:如果切分后单字也⼀样多,那怎么办?最后看⼀个例⼦,查询”王强⼤⼩:”,百度将其切分为”王/强⼤/⼩”,是正向切分的结果,如果是反向的会被切
分为”王/强/⼤⼩”,这说明有歧义⽽且单字也相同则选择正向切分结果.
OK,看到这⾥可能头已经有些晕了,最后总结⼀下百度的分词算法,当然⾥⾯还是有猜测的成分,算法如下:
⾸先查询专⽤词典(⼈名,部分地名等),将专有名称切出,剩下的部分采取双向分词策略,如果两者切分结果相同,说明没有歧义,直接输出分词结果.如果不⼀致,则输出
最短路径的那个结果,如果长度相同,则选择单字词少的那⼀组切分结果.如果单字也相同,则选择正向分词结果..
百度⼀直宣传⾃⼰在中⽂处理⽅⾯的优势,从上⾯看,分词算法并⽆特殊之处,消歧效果并不理想,即使百度采取⽐上述分词算法复杂些的算法也难以说成是优势,如
果说百度有优势的话,唯⼀的优势就是那个很⼤的专⽤词典,这个专⽤词典登录了⼈名(⽐如⼤长今),称谓(⽐如⽼太太),部分地名(⽐如阿联酋等),估计百度采⽤学术
界公布的⽐较新的命名实体识别算法从语料库⾥⾯不断识别出词典未登录词,逐渐扩充这个专门词典.如果这就是优势的话,那么这个优势能够保持多久就是个很明
显的问题
搜索引擎设计实⽤教程(2)-以百度为例
之⼆:SpellingChecker拼写检查错误提⽰(以及拼⾳提⽰功能)
中科院软件所张俊林
2005年11⽉
拼写检查错误提⽰是搜索引擎都具备的⼀个功能,也就是说⽤户提交查询给搜索引擎,搜索引擎检查看是否⽤户输⼊的拼写有错误,对于中⽂⽤户来说⼀般造成
的错误是输⼊法造成的错误.那么我们就来分析看看百度是怎么实现这⼀功能的.
我们分析拼写检查系统关注以下⼏个问题:
(1)系统如何判断⽤户的输⼊是有可能发⽣错误的查询呢?
(1)系统如何判断⽤户的输⼊是有可能发⽣错误的查询呢?
(2)如果判断是可能错误的查询输⼊,如何提⽰正确的词汇呢?
那么百度是如何做的呢?百度判断⽤户输⼊是否错误的标准,我觉得应该是查字典,如果发现字典⾥⾯不包含这个词汇,那么很有可能是个错误的输⼊,此时启动
错误提⽰功能,这个很好判断,因为如果是⼀个正常词汇的话,百度⼀般不会有错误提⽰,⽽你故意输⼊⼀个词典不可能包含的所谓词汇,此时百度⼀般会提⽰你正确
的检索词汇.
那么百度是怎么提⽰正确词汇的呢?很明显是通过拼⾳的⽅式,⽐如我输⼊查询”制才”,百度提供的提⽰词汇为:“:制裁质材纸材”,都是同⾳字.所以百度
必然维持着⼀个同⾳词词典,⾥⾯保留着同⾳词信息,⽐如可能包含着下⾯这条词条:“zhicaià制裁,质材,纸材”,另外还有⼀个标注拼⾳程序,现在能够看到的基
本流程是:⽤户输⼊”制才”,查词典,发现没有这个词汇,OK,启动标注拼⾳程序,将”制才”标注为拼⾳”zhicai”,然后查找同⾳词词典,发现同⾳词”制裁,质
材,纸材”,那么提⽰⽤户可能的正确拼写.
整体流程看起来很简单,但是还有⼀些遗留的⼩问题,⽐如是否将词表⾥⾯所有同⾳词都作为⽤户的提⽰信息呢?⽐如某个拼⾳有10个同⾳词,是否都输出呢?
百度并没有将所有同⾳词都输出⽽是选择⼀定筛选标准,选择其中⼏个输出.怎么证明这⼀点?我们看看拼⾳”liuli”的同⾳词,紫光输⼊法提⽰同⾳词汇有”流丽
流离琉璃流利”4个,我们看看百度返回⼏个,输⼊”流厉”作为查询,这⾥是故意输⼊⼀个词典不包含的词汇,这样百度的拼写检查才开始⼯作,百度提⽰:"琉璃刘
丽刘莉",这说明什么?说明不是所有同⾳词都输出,⽽是选择输出,那么选择的标准是什么?我能够猜测到的⽅法是对于⽤户查询LOG进⾏统计,提取⽤户查询次数
多的那些同⾳词输出,如果是这样的话,上⾯的例⼦说明⽤户搜索”琉璃”次数⽐其它的都要⾼些,次之是”刘丽”,再次是”刘莉”,看来⼤家都喜欢查询⾃⼰或者
认识的⼈的名字.
另外⼀个⼩问题:同⾳词词典包含2字词,3字词,那么是否包含4字词以及更长的词条?是否包含⼀字词?这⾥⼀字词好回答,不⽤测试也能知道肯定不包含,因为
你输⼊⼀个字,谁知道是否是错误的呢?反正只要是汉字就能在词表⾥⾯找到,所以没有判断依据.⼆字词是包含的,上⾯有例⼦,三字词也包含,⽐如查询"中城药"百度
错误提⽰:”中成药”,修改查询为"重城药",还是提⽰”中成药”,再次修改查询"重城要",百度依然提⽰”中成药”.那么4字词汇呢?
百度还是会给你提⽰的,下⾯是个例⼦:
输⼊:静华烟云提⽰京华烟云
输⼊静话烟云提⽰京华烟云
输⼊静话阎晕提⽰京华烟云
那么更长的词汇是否提⽰呢?也提⽰,⽐如我输⼊:"落花世界有风军",这个查询是什么意思,估计读过古诗的都知道,看看百度的提⽰”落花时节⼜逢君”,这说明
什么?说明同⾳词词典包含不同长度的同⾳词信息,另外也说明了百度的核⼼中⽂处理技术,也就是那个词典,还真挺⼤的.
但是,如果⽤户输⼊的查询由两个或者两个以上⼦字符串构成,那么百度的错误提⽰功能就罢⼯了,⽐如输⼊查询"哀体",百度提⽰”艾提挨踢”,但是.输⼊为
"我哀体",则没有任何错误提⽰.
还有⼀个⽐较重要的问题:如果汉字是多⾳字那么怎么处理?百度呢⽐较偷懒,它根本就没有对多⾳字做处理.我们来看看百度的⼀个标注拼⾳的错误,在看这个
错误前先看看对于多⾳字百度是怎么提⽰错误的,我们输⼊查询"俱长",百度提⽰”剧场局长”,“俱长”的拼⾳有两个:”juzhang/juchang”,可见如果是多
⾳字则⼏种情况都提⽰..现在我们来看看错误的情况,我们输⼊查询”剧常”,百度提⽰”:剧场局长”,提⽰为”剧场"当然好解释,因为是同⾳字,但是为什么"局
长"也会被提⽰呢?这说明百度的同⾳字词典有错误,说明在”juchang”这个词条⾥⾯包含”局长”这个错误的同⾳词.让我们顺藤摸⽠,这个错误⼜说明什么问题
呢?说明百度的同⾳词典是⾃动⽣成的,⽽且没有⼈⼯校对.还说明在⾃动⽣成同⾳词典的过程中,百度不是根据对⼀篇⽂章标注拼⾳然后在抽取词汇和对应的拼⾳
信息获得的,⽽是完全按照某个词典的词条来标注⾳节的,所以对于多⾳字造成的错误⽆法识别出来,如果是对篇章进⾏拼⾳标注,可能就不会出现这种很容易发现的
错误标注.当然还有另外⼀种解释,就是"局长"是故意被百度提⽰出来可能的正确提⽰词汇,因为考虑到南⽅⼈"zh'和"ch"等前后⿐⾳分不清么,那么是这样的么?我
们继续测试到底是何种情况.是百度有错误还是这是百度的先进的算法?
我们考虑词汇"长⼤",故意错误输⼊为"赃⼤",如果百度考虑到了前后⿐⾳的问题,那么应该会提⽰"长⼤",但是百度提⽰是"藏⼤".这说明什么?说明百度并没有考
虑前后⿐⾳问题,根本就是系统错误.我们输⼊查询"悬赏",故意将之错误输⼊为"悬桑",没有错误提⽰,说明确实没有考虑这种情况.前⿐⾳没有考虑,那么后⿐⾳考虑
了么,我们输⼊”:经常”,故意改为后⿐⾳"经缠",百度提⽰为"经产经忏",还是没有考虑后⿐⾳.这基本可以确定是百度系统的错误导致.
根据以上推导,我们可以得出如下结论:百度是将分词词典⾥⾯每个词条利⽤拼⾳标注程序标注成拼⾳,然后形成同⾳词词典,所以两个词典是同样⼤的,⽽且这
个词典也随着分词词典的增长⽽在不断增长.⾄于标注过程中多⾳字百度没有考虑,如果是多⾳字就标注成多个发⾳组合,通过这种⽅式形成同⾳词词典.这样的同
⾳词词典显然包含着很多错误.
最后⼀个问题:百度对于英⽂进⾏拼写检查么?让我们试试看,输⼊查询”china”,不错,搜到不少结果,专注中⽂搜索的百度还能搜索到英⽂,真是意外的惊喜.变
换⼀下查询”chine”,会更加意外惊喜的给我们提⽰”china”吗?百度提⽰的是:吃呢持呢,原来是不⼩⼼触发了百度的拼⾳搜索功能了.那么拼⾳搜索和中⽂检
查错误是否采⽤同⼀套同⾳词词典呢,让我们来实验⼀下,搜索”rongji”,百度提⽰”榕基溶剂容积”,OK,换个中⽂查询”容机”,百度提⽰”榕基溶剂容积”,
看来使⽤的是同⼀套同⾳词词典.也就是说百度的中⽂纠错和拼⾳检索使⽤的机制相同,中⽂纠错多了⼀道拼⾳注⾳的过程⽽已.难道这就是传说中那个百度的”事
实上是⼀个⽆⽐强⼤的拼⾳输⼊法”的拼⾳提⽰功能么?
最后让我们总结归纳⼀下百度的拼写检查系统:
后台作业:(1)前⾯的⽂章我们说过,百度分词使⽤的词典⾄少包含两个词典⼀个是普通词典,另外⼀个是专⽤词典(专名等),百度利⽤拼⾳标注程序依次扫描所
有词典中的每个词条,然后标注拼⾳,如果是多⾳字则把多个⾳都标上,⽐如”长⼤”,会被标注为”zhangda/changda”两个词条.
(2)通过标注完的词条,建⽴同⾳词词典,⽐如上⾯的”长⼤”,会有两个词条:zhangdaà长⼤”,changdaà长⼤.
(3)利⽤⽤户查询LOG频率信息给予每个中⽂词条⼀个权重;
(4)OK,同⾳词词典建⽴完成了,当然随着分词词典的逐步扩⼤,同⾳词词典也跟着同步扩⼤;
拼写检查:
(1)⽤户输⼊查询,如果是多个⼦字符串,不作拼写检查;
(2)对于⽤户查询,先查分词词典,如果发现有这个单词词条,OK,不作拼写检查;
(2)对于⽤户查询,先查分词词典,如果发现有这个单词词条,OK,不作拼写检查;
(3)如果发现词典⾥⾯不包含⽤户查询,启动拼写检查系统;⾸先利⽤拼⾳标注程序对⽤户输⼊进⾏拼⾳标注;
(4)对于标注好的拼⾳在同⾳词词典⾥⾯扫描,如果没有发现则不作任何提⽰;
(5)如果发现有词条,则按照顺序输出权重⽐较⼤的⼏个提⽰结果;
拼⾳提⽰:
(1)对于⽤户输⼊的拼⾳在同⾳词词典⾥⾯扫描,如果没有发现则不作任何提⽰;
(2)如果发现有词条,则按照顺序输出权重⽐较⼤的⼏个提⽰结果;
搜索引擎设计实⽤教程(3)-以百度为例
之三:对百度分词算法的进⼀步分析
中科院软件所malefactor
2005年11⽉
上⾯说过,经过分析得出百度的分词系统采⽤双向最⼤匹配分词,但是后来发现推理过程中存在⼀个漏洞,⽽且推导出来的百度分词算法步骤还是过于繁琐,所以进
⼀步进⾏分析,看看是否前⾯的推导有错误.
那么以前的分析有什么漏洞呢?我们推导百度分词有反向最⼤匹配的依据是百度将"北京华烟云"分词为,从这⾥看好像采⽤了反向最⼤匹配,因为正
向最⼤匹配的结果应该是,但是由此就推论说百度采⽤了双向最⼤匹配还是太仓促了,前⾯⽂章我们也讲过,百度有两个词典,⼀个普通词典,⼀个专
有词典,⽽且是专有词典的词汇先切分,然后将剩余⽚断交给普通词典去切分.所以上⾯的"北京华烟云"之所以被切分成,另外⼀个可能是:京华烟云这
个词汇是在专有词典⾥⾯存储的,所以先分析,这样得出"京华烟云",剩下"北",没什么好切分的,所以输出.
这⾥只是假设,那么是否确实"京华烟云"在专有词典呢?我们再看⼀个例⼦"⼭东北京华烟云",百度切分的结果是,如果"京华烟云"在普通词典,如
果是反向切分,那么结果应该是,如果是正向切分应该是,⽆论如何都分不出.这说明什么?说明"京华烟
云"是在那个专有词典,所以先切分出"京华烟云",然后剩下的"⼭东北"交由普通词典切分,明显是正向最⼤匹配的结果输出.当然按照我们在第⼀篇⽂章的
算法推导"⼭东北"的切分也会得出的结论,但是明显⽐正向最⼤匹配多⼏个判断步骤,既然效果⼀样,另外⼀个更加简洁的⽅法也能说得通,那当然选择简
便的⽅法了.所以初步判断百度采取的是正向最⼤匹配.
我们继续测试采⽤何种分词算法,为了减少专有词典⾸先分词造成的影响,那么查询⾥⾯不能出现相对特殊的词汇,构筑查询"天才能量级",这⾥应该没有专有词典出
现过的词汇,百度切分为,看来是正向最⼤匹配的结果.另外,如果所有查询词汇都出现在专有词典,那么采取的是何种⽅法?这样⾸先就得保证词汇都
出现在专有词典,这么保证这⼀点呢?我们构造查询"铺陈晓东⽅",百度切分为,可以看出"陈晓东"是在专有词典的所以先切分出来.另外⼀个例⼦"⼭
东京城",百度切分为,说明"东京"是在普通词典的.OK,构造查询"陈晓东京华烟云",通过前⾯分析可以看出两个词汇都在专有词典⾥⾯,百度切分为<陈晓
东,京华烟云>,说明对于专有词典词汇也是采取正向最⼤匹配或者双向最⼤匹配.那么使⽤反向最⼤匹配了吗?构造查询例⼦"陈晓东⽅不败",⾸先我们肯定"陈晓
东"和"东⽅不败"都是在专有词典出现的,如果是正向切分,那么应该是或者如果是反向切分则是,可以看出百
度的切分是或者,说明采⽤的是正向最⼤匹配.通过分析,百度的词典不包含"不败"这个单词,所以实际上百度的切分结果是<陈
晓东,⽅,不,败>,很明显这和我们以前推导的算法是有⽭盾的,所以以前的分析算法确实有问题,所以结论是百度采取的是正向最⼤匹配算法.
重新归纳⼀下百度的分词系统:⾸先⽤专有词典采⽤最⼤正向匹配分词,切分出部分结果,剩余没有切分交给普通词典,同样采取正向最⼤匹配分词,最后输出结果.
另外,GOOGLE也是采⽤正向最⼤匹配分词算法,不过好像没有那个专⽤词典,所以很多专名都被切碎了.
从这点讲,GOOGLE在中⽂词典构建上⽐百度差些,还需要加把⼦⼒⽓才⾏,不过这也不是什么多难的事.
搜索引擎设计实⽤教程(4)-以百度为例
之四:相关提⽰功能
中科院软件所malefactor
2005年11⽉
相关提⽰也是⼏乎所有搜索引擎提供的⼀个附加功能,所谓相关提⽰,就是对于⽤户提交的查询进⾏分析,然后根据其它⽤户相似的查询给予⽤户提⽰,⽐如我输⼊
查询”⼤长今”,检索系统会提⽰其它象”⼤长今主题曲”,”⼤长今下载”等等相关的⼀些其它⽤户查询.
那么搜索引擎是根据什么原则对于其它⽤户的查询进⾏选择来提⽰⽤户相关查询呢?我们还是以百度为例⼦来看看怎么实现这个功能.要实现这个功能主要解决
如下三个问题:
问题⼀.从哪⾥获得其它⽤户的查询信息?这个问题对于搜索引擎来说不是难事,因为搜索引擎都有⽤户查询LOG的功能,在⼀段时间内每⼀个⽤户提交给搜索引
擎的查询都被记录在LOG⽂件⾥⾯,所以从这个⽂件⾥⾯可以获得其它⽤户的查询信息.这个LOG还可以⽤作其它功能的基本素材,⽐如搜索排⾏榜或者搜索风云
榜,就是根据这个LOG⽂件,对⽤户查询归类,相同的归为⼀类,然后统计⼀段时间内这个类别的出现次数,按照降序排列,选择前列K个作为输出即可.
问题⼆.搜索引擎拿到⽤户的查询⽐如”⼤长今”,⽤户查询LOG⾥⾯有成千上万的不同查询,那么选择哪些作为提⽰呢?这⾥⾯牵涉到⼀个字符串相似性计算的过
程.
问题三.假设已经从查询LOG⾥⾯选择了⼀批⽤户相关查询信息,按照什么顺序输出呢?为什么”⼤长今主题曲”排列在”⼤长今下载”前⾯呢?这⾥⾯牵涉到排序原
则的问题.
我们⼀步步分析看看百度是如何解决上⾯的第⼆和第三个问题的.
⾸先,百度在计算字符串相似性的计算过程是⾸先对于⽤户查询进⾏分词,然后对于分词后的结果来进⾏相似性计算的.怎么证明这⼀点?第⼀个证明:⾸先⽤”新
闻”作为查询,看看百度提⽰的相关词汇是什么,然后将查询修改为”新闻新闻新闻”,再看看提⽰的相关词汇是什么,提⽰是完全⼀样的,基本说明是分词后进⾏计算
的.第⼆个证明:⾸先⽤”娱乐新闻报道”作为查询,看看百度提⽰的相关查询是什么,然后⼈⼯分好词”娱乐新闻报道”,再看看提⽰的相关查询是什么.,提⽰仍然是完全
⼀样的,我们再颠倒⼀下词汇顺序,⽤”新闻娱乐报道”作为查询,再看看相关查询是什么,完全没有变化.所以得出结论:百度在计算字符串相似性之前⾸先要对⽤户查
询进⾏分词,当然查询LOG⾥⾯的查询也要⾸先进⾏分词.
第⼆步,怎么计算相似性并排序输出呢?如果⽤户输⼊查询只有⼀个单词,那么处理起来好像⽐较简单,只要⽤户查询LOG⾥⾯包含这个单词的字符串都被纠出来,然
后根据⽤户总共查询这个字符串的次数进⾏排序,选择前列K个作为相关提⽰就可以了.好像很简单,但是问题真的这么简单就被解决了么?并⾮如此.
如果⽤户输⼊的查询⽐较长,问题就出来了,⽐如我们⽤“清脆的鸟叫声”作为查询，百度返回的相关提⽰中，前列1－35个相关查询包含“鸟”和“叫声”，
这⼏个查询排序原则是按照⽤户查询次数多少排列的，在36－40的相关查询仅仅包含“清脆”⼀个单词,排列顺序和⽤“清脆”查询时候顺序相同,说明也是按照
⽤户查询次数多少排列的；41－100的相关查询仅仅包含“叫声”，第41个查询”动物的叫声”是所有100个查询⽤户查询次数最多的⼀个.为什么包含”清脆”的
查询排列在包含”叫声”的查询前⾯⽽不是反过来呢?
在给个例⼦,⽤“咆哮⼩⽼⿏”作为查询，排在最前⾯的是匹配了“咆哮，⼩，⽼⿏”三个词汇的相关查询，次之是匹配了“咆哮，⽼⿏”的相关查询，再次
是匹配“咆哮，⼩”的相关查询，最次是匹配“⼩，⽼⿏”的相关查询，总共输出92个相关查询，对于只有⼀个匹配的查询没有输出。那么为什么是“咆哮，
⽼⿏”》“咆哮，⼩”》“⼩,⽼⿏”呢？原则是什么呢？
多次实验后,发现⾥⾯其实有⼀个匹配单词的权重设置问题,拿”咆哮⼩⽼⿏”做例⼦,切分后是,假设⽤户查询LOG⾥⾯有两个查询,⼀个是”咆哮⽼
⿏论坛”,切分后是.匹配的有两个单词(咆哮,⽼⿏),另⼀个查询是”咆哮⼩”,切分后是,匹配的也有两个单词(咆哮,⼩),怎么给这两个查询排
序呢?假设每个单词都有⼀个权重设置,⽐如Weight(咆哮)=aWeight(⼩)=bWeight(⽼⿏)=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）当然，为了更加加快查询速度，第三步骤的⼯作也可以预先算好，存储在数据库⾥⾯，⽤户查询直接在数据库⾥⾯存取。这个数据库可以每隔⼀段时间
更新⼀次以反映最新的情况
参考出处：来⾃布拉格的博客。