译者原文地址： http://leeing.org/2009/11/01/mmseg-chinese-segmentation-algorithm/
论文原文地址： http://technology.chtsai.org/mmseg/
MMSEG ：一个基于最大匹配算法的两种变体的中文单词识别系统
发表日期: 1996-04-29
更新日期: 1998-03-06
文档更新: 2000-03-12
许可: 非商业使用情况下免费
Copyright © 1996-2006 Chih-Hao Tsai (Email: hao520@yahoo.com)
摘要
中文文本在计算分析中一个问题是中文文本在印刷时缺少单词的边界，由于单词是一个基本的语义单元，因此有必要识别中文文本的单词以让进一步的处理可以进行。这份论文的目的是开发一个基于最大匹配算法的两种变体的中文单词识别系统，这个系统由一个词典，两种匹配算法，以及四种歧义消解规则组成。在一个由1013个单词组成的样本中，这个系统的正确识别率达到98.41%，本文也会对这个系统可能潜在的应用加以讨论。
介绍
正如Hung and Tzeng (1981) 和 DeFrancis (1984) 指出，中文书写系统同时以语素和音节来映射到口语中，因此，汉字在书面语中是区分的，从另一个方面来说，按照惯例，单词的边界在中文的印刷和书写中是缺失的。
单词识别过程中的难点
由于单词是一个基本的语言单位，因而有必要对中文文本的单词进行区分以让计算分析和处理中文文本能够进行。然而，在单词识别过程中有一些难点：
首先，几乎所有的汉字都可能是一个单字的单词。进一步地，它们能与其它汉字组成多字的单词，这就导致了大量的分词歧义。其次，在现代中文中，合成词是一种居主导地位的造词方案。经常很难区分一个低频率的合成词是一个单词还是一个短语；区分固有单词也会为一个问题。最后， 一些特定的形态结构例如重复和 ” A 不 A ” 也需要加以考虑。
若不是一些例外情况（例如e.g. Huang, Ahrens, & Chen, 1993; Sproat and Shih, 1990），大部份的单词识别方法共享一种常见的算法（例如，Chen & Liu, 1992; Fan & Tsai, 1988; Yeh & Lee, 1991），这种基本的策略是使用存储在一个预编译的词典中的大量词条集来匹配输入的汉字以找到所有（或部份）可能的分词方式，由于通常仅有一种正确的分词方法，歧义应当被消除。
最大匹配算法及它的变体
不同的研究中它们的歧义消除方法也不同。一个经过表明简单有效的方法是最大匹配算法（Chen & Liu, 1992），最大匹配算法可以有多种形式。
简单最大匹配算法。其基本形式是解析单个单词的歧义性（Yi-Ru Li, personal communication, January 14, 1995），例如，假设C1,C2,….代表一个字符串中的汉字。我们首先位于字符串的开头并想知道如何区分单词。我们首先搜索词典，看 _C1_是否为一个单个汉字组成的单词，然后搜索 _C1C2_来看是否为一个两个汉字组成的单词，以下类推。直至找到字典中最长的匹配。最可能的单词就是最长的匹配。我们取这个单词，然后继续这个过程直至字符串中的最后一个单词被识别出来。
复杂最大匹配算法。另一种最大匹配算法是由Chen 和Liu（1992）提出的，它比基本的形式更为复杂。他们的最大匹配规则指出，最可能的分词方案是三个单词。。。再次，我们从一个字符串的头部开始，寻找分词的方案。如果存在有歧义的分词（例如，_C1_是一个单词，但是_C1C2_也是一个单词，等等），然后我们向前再看两个单词去寻找所有可能的以 _C1_ 或者 _C1C2_ 开头的三词 chunks 。例如,如果有一个可能的三词chunks：
1. _C1_ _C2_ _C3C4_
2. _C1C2_ _C3C4_ _C5_
3. _C1C2_ _C3C4_ _C5C6_
最大长度的chunk是第三个。第一个单词，在第三个chunk中的_C1C2_，会被认为是正确的。我们接受这个词，并向前重复这个过程从汉字C3，直到字符串的最后一个词被识别。Chen 和 Liu（1992）声称这个规则达到了99.69%的准确率并且93.21%的歧义能被这个规则消除。
其它消除歧义的算法
除了最大匹配算法，许多其它消除歧义的算法也已经被得出。在消除歧义的过程中使用了各种各样的信息，例如，概率和统计（Chen & Liu, 1992; Fan & Tsai, 1988），语法（Yeh & Lee, 1991），还有词语形态学（Chen & Liu, 1992），它们当中的大部份需要一个构建良好，拥有汉字和词组频率信息的字典，单词的语法分类，以及一个语法或形态学的集合（例如，汉语知识信息处理小组[CKIP], 1993a, 1993b, 1993c）。
MMSEG 系统概述
MMSEG系统实现了前面讨论的最大匹配算法的简单和复杂形式。更进一步来说，为了消除未被复杂最大匹配算法所消除的歧义，又实现了三个消除歧义的规则。
其中一个是由Chen 和Liu（1992）提出的，剩下的两个则是新做法。这些规则会在后面加以讨论。这个系统没有特殊规则来处理固有名称和特殊的形态结构例如重复和“A不A”结构。
并不是说MMSEG不是设计目标为100%正确识别率的专业级别系统，在一定程度上，应当 将 MMSEG 看作是一个通用平台，用来测试新的消除歧义的算法。然而，我们能看到即使是当前版本的MMSEG也达到了非常高的准确率，与一些在学术性期刊上发表的算法相当。
字典
字典的第一部份由124499个多字词条组成，字典词条的长度从两个汉字到八个汉字，可以从附录A来查看单词长度的分布。字典是一个简单的汉字字符串的有组织的列表，每个字符串没有附加额外的信息。字典的基础是一个由作者维护的拥有137450个中文单词列表（Tsai,1996c），这个列表是通过将一些能在 Internet 上获得的中文单词列表归并而创建的 (Tsai, 1996a)。
字典的第二部份由13060个汉字及它们的使用频率组成（Tsai,1996b），汉字的频率在最后一个歧义消除规则之中使用。
匹配算法
简单匹配：对于字符串中的汉字Cn，用字典匹配以Cn开头的子串并查找所有可能的匹配。
复杂匹配：对于字符串中的汉字Cn，查找所以可能以Cn开头的三字chunks，不管是否与第一个单词有歧义。三字chunks仅在第一个单词有歧义时形成。
歧义消除规则
四种歧义消除规则被使用。在简单和复杂的匹配算法中都使用了最大匹配规则来消除分词的歧义。剩下的三个规则没有（而且不能）应用于简单匹配算法。
规则 1：最大匹配（Chen & Liu 1992）。
a) 简单最大匹配：取最大长度的单词。
b) 复杂最大匹配：从Chunk中以最大长度取第一个单词，如果有多于一个chunk最大长度，应用下一个规则。
规则 2：最大平均单词长度（Chen & Liu,1992）。在每一个字符串的结尾，很可能得到只有一个或者两个单词的chunk，例如，下面的 chunks 拥有相等的长度且单词长度的方差也相等。
1. _C1_ _C2_ _C3_
2. _C1C2C3_
规则2 以最大平均单词长度从chunk中取得第一个单词。在上面的例子中，它从第二个chunk中选择_C1C2C3_。这个规则是假设更可以遇到多字的单词而不是单字的单词。
这个规则在chunk中一个或多个单词为空的条件下才有用。当chunks是一个真正的三词chunks，这个规则并没有用。因为拥有相同总长度的三词 chunks 拥有同样的平均长度，所以我们需要其它的解决方案。
规则 3：单词长度的最小方差（Chen & Liu 1992）。规则1和规则2不能解析的歧义条件很少，例如，这两个chunks拥有相同的长度：
1. _C1C2_ _C3C4_ _C5C6_
2. _C1C2C3_ _C4_ _C5C6_
规则3取chunk中拥有单词长度最小方差的作为单词，在上面的例子中，它从第一个chunk中取_C1C2_。 这个规则和Chen & Liu（1992）提出的规则完全相同。(然而，他们在规则1之后立即应用这个规则)。 这个规则假设单词的长度通常是均匀分布的。如果存在多于一个chunks拥有最小的单词长度方差，则 应用下一个规则。
规则 4：单字单词的语素*度的最大和。这个例子展示了两个拥有相同长度，方差和平均单词长度的chunks。
1. _C1_ _C2_ _C3C4_
2. _C1_ _C2C3_ _C4_
两个chunks都有一个单字单词和一个双字单词。哪一个更像是正确的呢？在这里我们会关注于单字单词。中国汉字的语素*度不同，一些很少使用的汉字被用作 free morhemes，但其它则拥有较大的*度。一个汉字的出现频率可以作为它的语素*度的索引。一个高频率的汉字更可能是一个单字单词，反之亦然。
用来计算语素*度的和的公式是计算一个chunk中所以单字单词的频率。这个算法转换的原理是相同数量的频率区别并不对所有的频率范围起到一个一致性的影响。
规则4选取chunk中拥有最大频率的第一个词。由于很有可能两个汉字拥有相同的频率值，在这个规则应用之后应当没有歧义性。
虽然年份久远，对于NPL的CaiDiao而言，真的相当有启发性。