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

tonwei139

一、正向最大匹配算法和反向最大匹配算法的缺点
正向最大匹配算法：从左到右将待分词文本中的几个连续字符与词表匹配，如果匹配上，则切分出一个词。但这里有一个问题：要做到最大匹配，并不是第一次匹配到就可以切分的。举个例子：中华人民共和国今天成立了。从左到右扫描，要分别检索：中，中华，中华人，中华人民，中华人民共，中华人民共和，中华人民共和国今，今，今天，今天成，成，成立，成立了，了。14 次检索词库，最后的切分结果：中华人民共和国/今天/成立了。所以，当遇到长词时，要反复检索多次数据库，效率非常差。还有，一个更严重的问题是：词的最大长度是有限制的，为了兼顾算法的效率，不可能将最大词长定的非常大，这就会导致更长的词汇不能正确切分。
反之，反向最大匹配算法，则会将长词分开，造成错误切分。比如，上面的待切分文本，从右向左扫描，要分别检索：了，立了，立，成立，天成立，天，今天，今天国，国，和国，共和国，民共和国，民，人民，华人民，华，中华。17 词查询数据库，最后切分结果：中华/人民/共和国/今天/成立/了。将中华人民共和国切分成了3 个词。
二、克服最大匹配算法的缺点的算法
为了克服最大匹配算法的低效和不能切分长词，将所有的能组成词汇的汉字，建立索引，作为词的首字母。然后将每个汉字开头的词汇，分成一类，按词长排序。词库结构如下：

分词时，由汉字找到该字开头的词组（长度3000左右的线性检索），然后按由长到短5，4，3，2的顺序检索词库，和待分词语句对比（线性），如果有匹配，则切分为一个词，然后继续匹配下一个词。通过这种方式，大大提高了检索词库效率，解决了任意长词汇匹配问题。
在PHP算法的实现上，为了加快在线匹配速度，上面的词库结构，用PHP的联想数组的形式实现，全部加载到内存。为了灵活增删词库，做了个字符串处理程序，自动生成PHP联想数组结构的词库。详细实现算法，见PHP源码。
PHP分词源码下载：http://www.box.net/shared/gryspzppsb