标点符(钱魏 Way)

PHP中文高速分词的原理和源码

一、正向最大匹配算法和反向最大匹配算法的缺点

正向最大匹配算法:从左到右将待分词文本中的几个连续字符与词表匹配,如果匹配上,则切分出一个词。但这里有一个问题:要做到最大匹配,并不是第一次匹配到就可以切分的。举个例子:中华人民共和国今天成立了。从左到右扫描,要分别检索:中,中华,中华人,中华人民,中华人民共,中华人民共和,中华人民共和国今,今,今天,今天成,成,成立,成立了,了。14 次检索词库,最后的切分结果:中华人民共和国/今天/成立了。所以,当遇到长词时,要反复检索多次数据库,效率非常差。还有,一个更严重的问题是:词的最大长度是有限制的,为了兼顾算法的效率,不可能将最大词长定的非常大,这就会导致更长的词汇不能正确切分。

反之,反向最大匹配算法,则会将长词分开,造成错误切分。比如,上面的待切分文本,从右向左扫描,要分别检索:了,立了,立,成立,天成立,天,今天,今天国,国,和国,共和国,民共和国,民,人民,华人民,华,中华。17 词查询数据库,最后切分结果:中华/人民/共和国/今天/成立/了。将中华人民共和国切分成了3 个词。

二、克服最大匹配算法的缺点的算法

为了克服最大匹配算法的低效和不能切分长词,将所有的能组成词汇的汉字,建立索引,作为词的首字母。然后将每个汉字开头的词汇,分成一类,按词长排序。词库结构如下:

分词时,由汉字找到该字开头的词组(长度3000左右的线性检索),然后按由长到短5,4,3,2的顺序检索词库,和待分词语句对比(线性),如果有匹配,则切分为一个词,然后继续匹配下一个词。通过这种方式,大大提高了检索词库效率,解决了任意长词汇匹配问题。

在PHP算法的实现上,为了加快在线匹配速度,上面的词库结构,用PHP的联想数组的形式实现,全部加载到内存。为了灵活增删词库,做了个字符串处理程序,自动生成PHP联想数组结构的词库。详细实现算法,见PHP源码。

PHP分词源码下载:http://www.box.net/shared/gryspzppsb

原文出处:http://bbs.goocnjp.com/thread-385.html

码字很辛苦,转载请注明来自标点符《PHP中文高速分词的原理和源码》

评论