Baidu分词算法分析

机器学习 4798 Views

大家好,这里是“黑龙江大学自然语言处理实验室”。我们将成为大家了解科研,了解自然语言处理的一个很好的途径。如果大家有什么意见或者看法,都可以和我留言的。欢迎大家提问,多多互动~

本文源自 百度经验

点击“阅读原文”即可查看该链接

随着搜索经济的崛起,人们开始越加关注全球各大搜索引擎的性能、技术和日流量。作为企业,会根据搜索引擎的知名度以及日流量来选择是否要投放广告等;作为 普通网民,会根据搜索引擎的性能和技术来选择自己喜欢的引擎查找资料;作为技术人员,会把有代表性的搜索引擎作为研究对象。 搜索引擎经济的崛起,又一次向人们证明了网络所蕴藏的巨大商机。网络离开了搜索将只剩下空洞杂乱的数据,以及大量等待去费力挖掘的金矿。

但是,如何设计一个高效的搜索引擎?我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎。搜索引擎涉及到许多技术点,比如查询处理,排序算法,页面抓取算法,CACHE机制,ANTI-SPAM等等。这些技术细节,作为商业公司的搜索引擎服务提供商比如百度,GOOGLE等是不会公之于众的。我们可以将现有的搜索引擎看作一个黑盒,通过向黑盒提交输入,判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节。

查询处理与分词是一个中文搜索引擎必不可少的工作,而百度作为一个典型的中文搜索引擎一直强调其“中文处理”方面具有其它搜索引擎所不具有的关键技术和优势。那么我们就来看看百度到底采用了哪些所谓的核心技术。

中文分词

什么样的字符串才满足被切割的条件呢?

简单说来,如果字符串只包含小于等于3个中文字符的话,那就保留不动,当字符串长度大于4个中文字符的时候,百度的分词程序才出马大干快上,把这个字符串肢解掉。

【主页君小叶个人认为:百度这个图是不是有点小瑕疵,是不是应该如此改一下呢~

怎么证明呢?

我们向百度提交“电影下载”,看看返回结果中标为红字的地方,不难看出来,查询已经被切割成《电影,下载》两个单词了,说明分词程序已经开工了,如果是比4个中文字符更长的字符串,那分词程序就更不客气了,一定大卸八块而后快。我们来看看三个字符的情况,提交查询“当然择”,看起来这个查询不伦不类,那是因为我希望看到这个字符串被切分为《当然,择》,返回结果365篇相关页面,翻到最后一页,发现标红的关键字都是” 当然择”连续出现的情况,好像没有切分,但是还不确定,那么再提交人工分好的查询“当然 择”看看,返回结果1,090,000篇,基本上可以确定没有进行分词了,当然另外一种解释是:对于三个字符先切分,然后将切分后的结果当作一个短语查询,这样看到的效果和没有切分是相似的。但是我倾向于判断百度对于少于3个字符的串没有切分,奥卡姆不是说了么“如无必要,勿增实体”,干吗做无用功呢。 那么如果没有切分,会有一个随之而来的问题,怎么从索引库里面提取未切分的字符串呢?这牵扯到索引的问题,我觉得百度应该采取了两套索引机制,一种是按照单词索引,

一种是按照N-GRAM索引,至于索引的具体问题,以后在详细论述。

下面我们看看百度是采取的何种分词算法

现在分词算法已经算是比较成熟了,有简单的有复杂的,比如正向最大匹配,反向最大匹配,双向最大匹配,语言模型方法,最短路径算法等等,有兴趣的可以用GOOGLE去搜索一下以增加理解。这里就不展开说了。但是要记住一点的是:判断一个分词系统好不好,关键看两点,一个是消除歧义能力;一个是词典未登录词的识别比如人名,地名,机构名等。

那么百度用的是什么方法?

我的判断是用双向最大匹配算法。至于怎么推理得出的,让我们一步步来看。当然,这里首先有个假设,百度不会采取比较复杂的算法,因为考虑到速度问题。

我们提交一个查询“胡深东北京华烟云”,又一个不知所云的查询,尽管不知所云但是自有它的道理,我想看看百度的分词是如何消歧以及是否有词典未登录词的识别的功能,如果是正向最大匹配算法的话,那么输出应该是:”胡深东/北京/华/烟云”,如果是反向最大匹配算法的话,那么输出应该是:”胡/深/东北/京华烟云”,我们看看百度的分词结果:”胡深东/北/京华烟云”,一个很奇怪的输出,跟我们的期望相差较多,但是从中我们可以获得如下信息:百度分词可以识别人名,也可以识别”京华烟云”,这说明有词典未登录词的识别的功能,我们可以假设分词过程分为两个阶段:第一阶段,先查找一个特殊词典,这个词典包含一些人名,部分地名以及一些普通词典没有的新词,这样首先将”胡深东”解析出来,剩下了字符串”北京华烟云”,而”北/京华烟云”,可以看作是反向最大匹配的分词结果。这样基本说得通。为了证明这一点,我们提交查询”发胡深东北”,我们期望两种分词结果,一个是正向最大匹配《发胡,深,东北》, 一个是上述假设的结果《发,胡深东,北》,事实上百度输出是第二种情况,这样基本能确定百度分词采取了至少两个词典,一个是普通词典,一个是专用词典(人名等)。而且是专用词典先切分,然后将剩余的片断交由普通词典来切分。

继续测验,提交查询“古巴比伦理”,如果是正向最大匹配,那么结果应该是《古巴比伦,理》,如果是反向最大匹配,那么结果应该是《古巴,比,伦理》,事实上百度的分词结果是《古巴比伦,理》,从这个例子看,好像用了正向最大匹配算法;此外还有一些例子表明好像是使用正向最大匹配的;但是且慢,我们看这个查询“北京华烟云”,正向最大匹配期望的结果是《北京,华,烟云》,而反向最大匹配期望的结果是 《北,京华烟云》,事实上百度输出的是后者,这说明可能采用的反向最大匹配;从这点我们可以猜测百度采用的是双向最大匹配分词算法,如果正向和反向匹配分词结果一致当然好办,直接输出即可;但是如果两者不一致,正向匹配一种结果,反向匹配一种结果,此时该如何是好呢?从上面两个例子看,在这种情况下,百度采取最短路径方法,也就是切分的片断越少越好,比如《古巴,比,伦理》和《古巴比伦,理》相比选择后者,《北京,华,烟云》和《北,京华烟云》相比选择后者。还有类似的一些例子,这样基本可以解释这些输出结果。

本周“语言分析”环节已经结束,是不是还没看过瘾,想不想知道百度采用双向最大匹配算法和最短路径算法后,是否还存留隐患;百度又是如何查询处理的等等。敬请期待下周一小叶为你揭晓答案哦~

您可以查找公众号:hlju_nlp 或扫描如下二维码,即可关注“黑龙江大学自然语言处理实验室”:

如未说明则本站原创,转载请注明出处:NULL » Baidu分词算法分析