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

3 sec read

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

正向最大匹配算法:从左到右将待分词文本中的几个连续字符与词表匹配,如果匹配上,则切分出一个词。但这里有一个问题:要做到最大匹配,并不是第一次匹配到就可以切分的。举个例子:中华人民共和国今天成立了。从左到右扫描,要分别检索:中,中华,中华人,中华人民,中华人民共,中华人民共和,中华人民共和国今,今,今天,今天成,成,成立,成立了,了。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

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

C语言学习:size_t

在学习C语言的时候,遇到了一个新的数据类型size_t,截止目前也没有完全理清这个类似的具体场景及出现的原因。
44 sec read

C语言学习:main()函数的正确写法

C语言虽然是一门古老的语言,但是其标准一直在完善,所以很多以前支持的语法在到当前已经不能在使用了。 C语言的版
41 sec read

Scipy数学函数的Scala实现

最近在推进项目的时候,遇到需要将线下的Python代码转化成线上的集群代码,由于机器代码环境是Scala,所以
4 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注