中文分词算法初探之最大匹配

2017-05-26 本文已影响0人 galois_xiong

中文分词是中文自然语言处理中十分重要的基础性工作，基本后续的一切工作都依赖分词。
本文主要探讨MMSEG这个分词系统；因为这个的效率十分不错，准确率也还行。

最大匹配算法

最大匹配算法是一种比较简单，但有效的方法。其属于一种查词典的方法。就是说前提有一个较好的词典。
下面主要讲讲最大匹配算法：

简单最大匹配算法
给定待分词的句子：C1, C2, C3, ... Cn
第二步：先查C1, 如果C1在词典中；则查 C1C2，如果C1C2 在词典中，继续查C1C2C3, 其实就是找到以C1开头的最大的在词典中的词，分割出来，作为词。
其次接着前面的词，继续按照第二步的过程，循环查找；
最后完成切词；
复杂最大匹配算法
主要的规则是认为最可能的分割模式是分词的三个词的长度最大；
这也是MMSEG中比较核心的一个概念，这个最大匹配规则考虑问题比较全面，在对句子中的某个词进行切分时，如果有歧义拿不定主意，就再向后展望两个汉语词，并且找出所有可能的“三词语块”。例如，对于如下的“三词语块”，请注意括号中是注明的语块长度（以汉语单字为基本单位）：

   眼看 就要 来了
   眼看 就要 来
   眼看 就 要
   眼 看 就

上面中最大的就是长度的3个词组合是第一句，所以最前面的三个词会被分为第一句。

MMSEG分词系统

MMSEG分词系统分词系统将上面介绍的简单和复杂的最大匹配算法都实现了，并且，实现了三中消歧规则，用来解决最大匹配算法解决不了的歧义性问题。
下面主要来介绍MMSEG系统：

词表

词表的第一部分有124,499 个词条；词的长度范围是从二到八；这一部分的词不含任何的其它信息；
词表的二部分是由13,060个字和字频，字频用在最后一条消歧规则

匹配算法

简单算法，和复杂算法

消歧规则

最后三条规则只适合复杂匹配

规则1：最大匹配
(a) 简单匹配：找最长匹配的词；
(b) 复杂匹配：取最长的“三词语块”中的第一个词。如果有多个最长”三词语块“采用下面的几种规则
规则2：最长平均字长度：
顾名思义：就是找长的平均字长度；主要是为了解决分词中的空格符的问题；
规则3：最小方差字长度：
例如：下面的例子选第一种

   研究 生命 起源
   研究生 命 起源

规则4：最大单字词语语素自由度之和
例如：下面

   主要 是 因为
   主 要是 因为

这两个语块都包括了两个单字词语和一个两字词语，规则四主要关注其中的单字词语。直观来看，有些汉字很少作为词语出现，而另一些汉字则常常作为词语出现，从统计角度来看，在语料库中出现频率高的汉字就很可能是一个单字词语，反之可能性就小。计算单词词语语素自由度之和的公式是对“三词语块”中的单字词语频率取对数并求和规则四则选取其中和最大的语块，并将该语块的第一词语作为最佳的词语切分形式。

总结

总的来说MMSEG分词系统算是一种较简单基于查词典的分词算法，具有较好的性能和精度。是中文分词中一种重要的发展里程。

reference

http://technology.chtsai.org/mmseg/
http://www.52nlp.cn/%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D%E5%85%A5%E9%97%A8%E4%B9%8B%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8D%E6%B3%95%E6%89%A9%E5%B1%951