Baidu查询分词算法
查询处理以及分词技术
如何设计一个高效的搜索引擎?我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎.搜索引擎涉及到许多技术点，比如查询处理，排序算法，页面抓取算法,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，看到这里可能头已经有些晕了，最后总结一下百度的分词算法，当然里面还是有猜测的成分，算法如下:
首先查询专用词典(人名，部分地名等)，将专有名称切出，剩下的部分采取双向分词策略，如果两者切分结果相同，说明没有歧义，直接输出分词结果.如果不一致，则输出最短路径的那个结果，如果长度相同，则选择单字词少的那一组切分结果.如果单字也相同，则选择正向分词结果..
百度一直宣传自己在中文处理方面的优势，从上面看，分词算法并无特殊之处，消歧效果并不理想，即使百度采取比上述分词算法复杂些的算法也难以说成是优势，如果说百度有优势的话，唯一的优势就是那个很大的专用词典，这个专用词典登录了人名(比如大长今)，称谓(比如老太太)，部分地名(比如阿联酋等)，估计百度采用学术界公布的比较新的命名实体识别算法从语料库里面不断识别出词典未登录词，逐渐扩充这个专门词典.如果这就是优势的话，那么这个优势能够保持多久就是个很明显的问题.
baidu分词算法分析之二
文章作者: 张俊林
文章来源: 中科院软件所文章编辑: url
Spelling Checker拼写检查错误提示(以及拼音提示功能)
baidu分词算法分析之二
拼写检查错误提示是搜索引擎都具备的一个功能，也就是说用户提交查询给搜索引擎，搜索引擎检查看是否用户输入的拼写有错误，对于中文用户来说一般造成的错误是输入法造成的错误.那么我们就来分析看看百度是怎么实现这一功能的.
我们分析拼写检查系统关注以下几个问题:
(1)系统如何判断用户的输入是有可能发生错误的查询呢?
(2)如果判断是可能错误的查询输入，如何提示正确的词汇呢?
那么百度是如何做的呢?百度判断用户输入是否错误的标准，我觉得应该是查字典，如果发现字典里面不包含这个词汇，那么很有可能是个错误的输入，此时启动错误提示功能，这个很好判断，因为如果是一个正常词汇的话，百度一般不会有错误提示，而你故意输入一个词典不可能包含的所谓词汇，此时百度一般会提示你正确的检索词汇
.
那么百度是怎么提示正确词汇的呢?很明显是通过拼音的方式，比如我输入查询" 制才"，百度提供的提示词汇为: “制裁质材纸材"，都是同音字.所以百度必然维持着一个同音词词典，里面保留着同音词信息，比如可能包含着下面这条词条: “ zhi cai à制裁，质材，纸材"，另外还有一个标注拼音程序，现在能够看到的基本流程是: 用户输入" 制才"，查词典，发现没有这个词汇,OK，启动标注拼音程序，将" 制才"标注为拼音"zhi cai"，然后查同音词词典，发现同音词" 制裁，质材，纸材"，那么提示用户可能的正确拼写
整体流程看起来很简单，但是还有一些遗留的小问题，比如是否将词表里面所有同音词都作为用户的提示信息呢?比如某个拼音有10个同音词，是否都输出呢?百度并没有将所有同音词都输出而是选择一定筛选标准，选择其中几个输
出.怎么证明这一点?我们看看拼音"liu li"的同音词，紫光输入法提示同音词汇有" 流丽流离琉璃流利"4个，我们看看百度返回几个，输入"流厉"作为查询，这里是故意输入一个词典不包含的词汇，这样百度的拼写检查才开始工作，百度提示: " 琉璃刘丽刘莉"，这说明什么?说明不是所有同音词都输出，而是选择输出，那么选择的标准是什么?我能够猜测到的方法是对于用户查询LOG进行统计，提取用户查询次数多的那些同音词输出，如果是这样的话，上面的例子说明用户搜索"琉璃"次数比其它的都要高些，次之是" 刘丽"，再次是" 刘莉"，看来大家都喜欢查询自己或者认识的人的名字.
另外一个小问题：同音词词典包含2字词,3字词，那么是否包含4字词以及更长的词条?是否包含一字词? 这里一字词好回答，不用测试也能知道肯定不包含，因为你输入一个字，谁知道是否是错误的呢?反正只要是汉字就能在词表里面到，所以没有判断依据.二字词是包含的，上面有例子，三字词也包含，比如查询"中城药"百度错误提示:"中成药"，修改查询为"重城药"，还是提示"中成药" ，再次修改查询"重城要"，百度依然提示"中成药". 那么4字词汇呢?
百度还是会给你提示的，下面是个例子:
输入：静华烟云提示京华烟云
输入：静话烟云提示京华烟云
输入：静话阎晕提示京华烟云
那么更长的词汇是否提示呢?也提示，比如我输入: "落花世界有风军"，这个查询是什么意思，估计读过古诗的都知道，看看百度的提示"落花时节又逢君"，这
说明什么?说明同音词词典包含不同长度的同音词信息，另外也说明了百度的核心中文处理技术，也就是那个词典，还真挺大的.
但是，如果用户输入的查询由两个或者两个以上子字符串构成，那么百度的错误提示功能就***了，比如输入查询"哀体"，百度提示"艾提挨踢"，但是.输入为"我哀体"，则没有任何错误提示.
还有一个比较重要的问题：如果汉字是多音字那么怎么处理?百度呢比较偷懒，它根本就没有对多音字做处理.我们来看看百度的一个标注拼音的错误，在看这个错误前先看看对于多音字百度是怎么提示错误的，我们输入查询"俱长"，百度提示"剧场局长", “俱长"的拼音有两个:"ju zhang /ju chang" ，可见如果是多音字则几种情况都提示..现在我们来看看错误的情况, 我们输入查询"剧常"，百度提示"：剧场局长"，提示为"剧场"当然好解释，因为是同音字，但是为什么"局长"也会被提示呢?这说明百度的同音字词典有错误，说明在"ju chang"这个词条里面包含"局长"这个错误的同音词.让我们顺藤摸瓜，这个错误又说明什么问题呢?说明百度的同音词典是自动生成的，而且没有人工校对.还说明在自动生成同音词典的过程中，百度不是根据对一篇文章标注拼音然后在抽取词汇和对应的拼音信息获得的，而是完全按照某个词典的词条来标注音节的，所以对于多音字造成的错误无法识别出来，如果是对篇章进行拼音标注，可能就不会出现这种很容易发现的错误标注. 当然还有另外一种解释，就是"局长"是故意被百度提示出来可能的正确提示词汇，因为考虑到南方人"zh"和"ch"等前后鼻音分不清么，那么是这样的么?我们继续测试到底是何种情况.是百度有错误还是这是百度的先进的算法?
我们考虑词汇"长大"，故意错误输入为"赃大"，如果百度考虑到了前后鼻音的问题，那么应该会提示"长大"，但是百度提示是"藏大".这说明什么?说明百度并没有考虑前后鼻音问题，根本就是系统错误. 我们输
入查询"悬赏"，故意将之错误