中文分词逆向最大匹配法项目实践
Tag 中文分词, 逆向最大匹配法, on by view 5749

最近在自己的项目中实现了中文分词,项目是pinyin-php,是一个用C语言完成的原生php扩展。 其主要作用是将中文汉字翻译成汉语拼音,其中用到中文分词主要是为了识别多音字,因为多音字一般是在特定词语环境中出现的。 因此系统需要识别汉字词语,也就是说要实现简单的分词,当然分词准确率越高的话多音字识别率也会越高。

pinyin-php中实现中文分词达到识别多音字的目的,这一想法在pinyin-php上一版本开发的时候就已经想到了。只是自己从来都没有实践过,而且据别人说,中文分词用C语言实现起来比较麻烦,反倒是脚本语言实现起来比较方便。我多方查阅资料后知道现有中文分词方法有如下几种

  1. 字符匹配

  2. 理解法

  3. 统计法

其中字符匹配是基于字典的字符串匹配,理解法是在字符串匹配的同时还对句子进行语义分析,统计法是基于大量的语料库来实现的。其中字符匹配法最为简单,后两者首先是算法比较复杂,是我目前尚未接触到的方法,其次他们均要基于大量的语料库进行数据分析,这对于我以及pinyin-php这个项目来说是不现实的。不过对于搜索引擎这种大型的系统来说是可以实现的。因此,我采用字符匹配法。字符匹配又有如下四种方式

  1. 正向最大匹配法(由左到右的方向);

  2. 逆向最大匹配法(由右到左的方向);

  3. 最少切分(使每一句中切出的词数最小);

  4. 双向最大匹配法(进行由左到右、由右到左两次扫描);

上面四种字符匹配方法要算『双向最大匹配法』最为准确,由于汉语的特性,『逆向最大匹配法』比『正向最大匹配法』要更精确。

pinyin-php采用的便是『逆向最大匹配法』。下面看个分词实例

硕士研究生产

正向最大匹配法的结果会是『硕士研究生 / 产』,而逆向最大匹配法利用逆向扫描,可得到正确的分词结果『硕士 / 研究 / 生产』。

项目中有一个字词库,其实是我自己实现的一个hashtable,系统初始化的时候从字词库中读取汉字和词语以及其对应的汉语拼音。

key,value
一,yī
丁,dīng
七,qī
万,wàn
丈,zhàng
三,sān
上,shàng
下,xià
……
阿Q,āQ
阿爸,ābà
阿鼻,ābí
阿呆,ādāi
阿弟,ādì
阿爹,ādiē
阿斗,ādǒu
阿飞,āfēi
阿哥,āgē
……

假设hashtable中的key的最大长度为10个汉字,那么有一段文字,我首先从尾部开始截取10个汉字,放入buffer{10}中然后在hashtable中查buffer[1~10],查到后就截取后续的10个汉字,未查到的话继续查字符串buffer[2~10],未查到继续查buffer[3~10],直到buffer[10],例如若是在buffer[4~10]的时候查到了,则将buffer[1~3]退回段落的原处。匹配到的词直接总hashtable中读取其拼音如此便翻译出来了,若是查找不到则直接保持为原来的字符不变。

分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。

paragraph								buffer					segments
分词就是将连续的字序列按照一定的规范重新		组合成词序列的过程。
分词就是将连续的字序列按照一定的规范重		新组合成词序列的过程		/。
分词就是将连续的字序列按照一定的规			范重新组合成词序列的		/过程。
分词就是将连续的字序列按照一定的				规范重新组合成词序列		/的/过程。
分词就是将连续的字序列按照一				定的规范重新组合成词		/序列/的/过程。
分词就是将连续的字序						列按照一定的规范重新		/组/合成词/序列/的/过程。
分词就是将连续的							字序列按照一定的规范		/重新/组/合成词/序列/的/过程。

如果想了解我是如何编码实现的,欢迎参阅我的项目pinyin-php(https://github.com/duguying/pinyin-php)。