中文分词入门之最大匹配法扩展1

　　这里曾写过《中文分词入门之最大匹配法》，并且获得了很高的关注度，不过现在回头来看，这个方法只是最初级的中文分词匹配方法。事实上，很多学者都基于简单的中文分词匹配法做了扩展，其中比较有名的就是台湾蔡志浩老师1996年写的“MMSEG: A Word Identification System for Mandarin Chinese Text Based on Two Variants of the Maximum Matching Algorithm”，在这篇文章的页面中，不仅介绍了相关的中文分词算法，并且提供了一个C版本的mmseg供研究使用，目前根据该文及其代码移植的mmseg程序版本包括C++版、Java版、Python版及Ruby版，影响甚广。
　　此文是英文版本，建议有条件的读者直接读原文。不过国内也有该文的简介文章：《MMSeg分词算法简述》，原文似乎出自“www.solol.org”，但是我一直没打开这个网站，因为Java版的mmesg也是其提供的，不知道是已经关闭了还是被“墙”了。另外，leeing也翻译了全文《MMSEG 中文分词算法》，我粗略的读了一下，感觉翻译的不错。以下我先从自己理解的角度介绍一下该算法，然后再运行一个C++版本的mmseg程序作为示例，大致需要两节。
　　MMSEG中文分词系统的可以由一句话总结：The system consisted of a lexicon, two matching algorithms, and four ambiguity resolution rules（该系统包括一个词典，两种匹配算法，以及四种歧义消解规则）：
1、 词典（The Lexicon）：
　　分两种形式，对于单个汉字的汉语词，除了汉字本身外，还包括其统计频率（这个频率属于先验知识，可以来自于已经人工分好词的训练语料库），而对于二字长及以上的汉语词，只要词条本身就可以了。
2、 匹配算法（Matching Algorithm）：
　a) 简单匹配:对于字符串中的汉字Cn，用词典匹配以Cn开头的子串并查找所有可能的匹配；
　b) 复杂匹配:对于字符串中的汉字Cn，查找所有可能以Cn开头的三词chunks，无论第一个汉语词是否有歧义。
3、歧义消解规则（Ambiguity Resolution Rules）：
规则一：最大匹配(Maximum matching)
　a) 简单最大匹配算法,也就是我们常说的最大匹配法，不过作者采取的是正向匹配，并且按长度从小到大搜索词典：假设C1,C2,….代表一个字符串中的汉字，首先搜索词典，看 _C1_是否为一个单字组成的词语，然后搜索 _C1C2_来看是否为两个汉字组成的词语，以此类推，直至找到字典中最长的匹配。
　b) 复杂最大匹配算法,由Chen 和Liu（1992）提出，其核心的假设是：The most plausible segmentation is the three-word chunk with maximum length. 请注意three-word chunk，可以将其翻译为“三词语块”，这也是MMSEG中比较核心的一个概念，这个最大匹配规则考虑问题比较全面，在对句子中的某个词进行切分时，如果有歧义拿不定主意，就再向后展望两个汉语词，并且找出所有可能的“三词语块”。例如，对于如下的“三词语块”，请注意括号中是注明的语块长度（以汉语单字为基本单位）：

1. _C1_ _C2_ _C3C4_（4）
2. _C1C2_ _C3C4_ _C5_（5）
3. _C1C2_ _C3C4_ _C5C6_（6）

　　最大长度的“三词语块”是第3个，所以其第一汉语词_C1C2_将被作为正确的分词形式。以此类推，接下来我们从C3开始，找出所有可能的“三词语块”，重复上述规则，直到句子的最后一个词被划分。直观一点，对于以“眼”开头的如下5个“三词语块”,利用该规则，则“眼看”是正确的词语划分：

1.眼看 就要 来了（6）
2.眼看 就要 来（5）
3.眼看 就 要(4)
4.眼 看 就要(4)
5.眼 看 就(3)

规则二：最大平均词长（Largest average word length）
　　在句子的末尾，很可能得到的“三词语块”只有一个或两个词（其他位置补空），例如，对于如下两个“三词语块”，他们拥有同样的长度：

1. _C1_ _C2_ _C3_（平均词长=1）
2. _C1C2C3_（平均词长=3）

　　这时规则1就无法解决其歧义消解问题，因此引入规则2：最大平均词长，也就是从这些语块中找出平均词长最大的语块，并选取其第一词语作为正确的词语切分形式。这个规则的前提假设是：It is more likely to encounter multi-character words than one-character words（在句子中遇到多字-词语的情况比单字-词语更有可能）. 因此，上述两个“三词语块”中第二个_C1C2C3_就是最佳候选。直观一点，对于如下位于句尾三种形式的“三词语块”：

1.国际化（平均词长=3）
2.国际 化（平均词长=1.5）
3.国 际 化（平均词长=1）

　　在规则1无法求解的情况下，根据规则2，则“国际化”为最佳候选语块，因此该语块的第一个词“国际化”就是最佳的分词形式。

规则三：最小词长方差（Smallest variance of word lengths）
　　还有一些歧义是规则一和规则二无法解决的，例如，如下的两个“三词语块”拥有同样的长度和同样的平均词长：

1. _C1C2_ _C3C4_ _C5C6_
2. _C1C2C3_ _C4_ _C5C6_

　　因此引入规则三：最小词长方差，也就是找出词长方差最小的语块，并选取其第一个词语作为正确的词语切分形式。在概率论和统计学中，一个随机变量的方差（Variance）描述的是它的离散程度，也就是该变量离其期望值的距离。因此该规则的前提假设是：Word lengths are usually evenly distributed（句子中的词语长度经常是均匀分布的）。直观来说，对于如下两个“三词语块”：

1.研究 生命 起源
2.研究生 命 起源

其长度为6，平均词长为2，规则一和规则二无能无力，利用规则三：
　语块1的方差 = ((2-2)^2+(2-2)^2+(2-2)^2)/3 = 0
　语块2的方差 = ((3-2)^2+(1-2)^2+(2-2)^2)/3 = 2/3
则语块1为最佳候选，因此该语块的第一个词“研究”为最佳的分词形式。

规则四：最大单字词语语素自由度之和（Largest sum of degree of morphemic freedom of one-character words）：
　　如下所示，例子中的两个“三词语块”拥有同样的长度、平均词长及方差，因此上述三个规则都无法解决其歧义消解问题：

1. _C1_ _C2_ _C3C4_
2. _C1_ _C2C3_ _C4_

　　这两个语块都包括了两个单字（one-character）词语和一个两字（two-character）词语，规则四主要关注其中的单字词语。直观来看，有些汉字很少作为词语出现，而另一些汉字则常常作为词语出现，从统计角度来看，在语料库中出现频率高的汉字就很可能是一个单字词语，反之可能性就小。计算单词词语语素自由度之和的公式是对“三词语块”中的单字词语频率取对数并求和（The formula used to calculate the sum of degree of morphemic freedom is to sum log(frequency) of all one-character word(s) in a chunk.）规则四则选取其中和最大的语块，并将该语块的第一词语作为最佳的词语切分形式。

　　关于MMSEG中文分词系统的框架就介绍到此，需要指出的是：

“It has to be noted that MMSEG was not designed to be a "professional level" system whose goal is 100% correct identification. Rather, MMSEG should be viewed as a general platform on which new ambiguity resolution algorithms can be tested.”

　　所以，不要认为有了MMSEG就可以解决中文分词的问题，更应该将MMSEG视为一个基本的平台，在该平台的基础上，有兴趣的读者可以尝试添加新的歧义消解算法以解决中文分词中的难点问题。

未完待续：最大匹配法扩展2

注：原创文章，转载请注明出处“我爱自然语言处理”：www.52nlp.cn

本文链接地址：https://www.52nlp.cn/中文分词入门之最大匹配法扩展1