石家庄经济学院本科生毕业论文
2 中文分词简介
中文分词是中文信息处理的基础，也是中文信息处理的关键，中文分词，通俗的讲就是由机器在中文文本中词与词之间自动加上空格。一提到中文分词，就会有两类人对此产生质疑，一类人是外行，对此技术不是很了解，认为中文分词很简单，另一种来自圈内人，也可以讲是行家，虽然中文分词已经研究了将近三十年，可是到现在为止并没有退出一个很好的中文分词系统，中文分词这个难题到底还能不能解决。无论是哪一方面的质疑，中文分词的研究不能放弃，因为这是中国计算机发展的关键，是其它中文信息处理的瓶颈，本章主要对中文分词进行了介绍。
2.1 中文分词问题描述
在信息检索、语音识别、机器翻译等技术领域中通常需要理解中文的每一句话，也就是要理解每一句话里的每个词，从而来进行相应的操作，但这需要将每一个词从句子里单独切分出来，这就是中文分词技术。用一个专业性的描述就是中文分词系统的输入是连续的字符串（A1A2A3A4A5A6A7??）是由字组成的中文句子(其中An是字)，通过中文分词处理得到的字符串是B1B2B3B4??,其中Bi是由单个字或多个字组成的词。由于中文对于词的界限不是很清晰，如何分词，什么样的叫做词，都需要一个专业的词库来进行区分，可是遗憾的事到目前为止，并没有在这样一个词库，因此我们进行在这里进行的工作是尽可能的寻找一个标准化的词库，来帮助我们界定词的界限。
中文分词有两大基本问题，也是中文分词的难点，一是歧义识别问题，二是未登录词问题，本节简要介绍下这两类问题，有关这两类问题的详细介绍请参考2.2。
第一个问题是歧义识别的问题，由于中文自身的特点，对于中文中的一句话不同的划分可能有不同的意思，例如，“乒乓球拍卖完了”，这句话可以划分成“乒乓球/拍卖完了”，也可以划分成“乒乓球拍/卖完了”。虽然到现在为止没有出线一个百分百的消除歧义的算法，但是已经出现了许多比较好的，且具有实际应用价值的算法。
第二个是未登录词的问题，未登录词又称为新词，因为语言在不断的发展和变化导致新词的不断出现，同时词的衍生现象非常普遍，所以词表中不能囊括所有的词。最典型的是人名，例如在句子“李军虎去上海”中，人可以很容易理解“李军虎”作为一个人名是个词，但计算机识别就困难了。如果把“李军虎”作为一个词收录到字典中去，全世界有那么多名字，而且时时都有新增的人名，如此一项巨大的工程即使可以完成，问题仍旧存在。例如:在句子“李军虎背熊腰的”中，“李军虎”又算词吗?新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等这些人们经常使用的词都是很难处理的问题，因此在信息搜索中，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一[3]。
2.2 中文分词难点分析
中文分词研究了近三十年，虽然已经取得了一些成就，但是中文分词的基础性问题，也是关键性问题并没有解决即歧义识别问题和未登录词的识别问题。下面详细讲述这两大基本问题并讲述已有的解决办法。
- 4 -
石家庄经济学院本科生毕业论文
2.2.1 切分歧义及其处理方法
（1）常见歧义类型
在中文中存在着很多的歧义切分字段，典型的歧义有交集型歧义（约占全部歧义的85%以上）和组合型歧义[4]。交集型歧义是这样一种歧义：汉字串AJB被称作交集型切分歧义，如果满足AJ、JB同时为词（A、J、B分别为汉字串）。此时汉字串J被称作交集串[4]。 例如：高兴/奋 和高/兴奋，其中“兴”就是交集串。组合型歧义是这样一种歧义：汉字串AB被称作多义组合型切分歧义，如果满足A、B、AB同时为词[4]。 而在我们分词的过程中我们会遇到以下三种歧义的问题：
1）由自然语言的二义性产生的歧义是第一种歧义问题。例如：乒乓球拍卖完了，可以划分成“乒乓球/拍卖完了”，也可以划分成“乒乓球拍/卖完了”。这类歧义是自然语言的二义性而出现的，此类歧义问题无论如何划分都能够说的通，只有结合上下文才能得到正确的划分。 2）第二类歧义问题是由机器自动分词出现的，这类分词只有一种正确的分词方法，但因为分词采用的分词算法不同而出现不同的分词结果，例如对于这句话“这时候最热闹的”，如果采用最大正向匹配的算法就是“这时候/最热/闹/的”，而如果采用最大逆向匹配就是“这时候/最/热闹/的 ”。对于本句来说只有第二句才是正确的切分，如果对于人工分词来说这是不会出现的歧义。
3）第三类问题就是由于词典的大小，对于专业名词，人名地名等不包含出现的歧义，例如“张芳明是个好学生”，在这里“张芳明”是个人名，是一个词，但是如果在分词词典里不包含“张芳明”这个人名，那么就会出现“张/芳/明”这样错误的切分结果。对于这种歧义，只要字典足够大就可以解决，但是我们不可能也没有必要包含所有的人名地名，因此对词汇进行分类，从而对于某一行业的词用专业词典来切分是一个很好的解决方法。
（2）常见消除歧义算法[5]
不同的研究中它们的歧义消除方法也不同。一个经过表明简单有效的方法是最大匹配算法，最大匹配算法可以有多种形式。
1）简单最大匹配算法。其基本形式是解析单个单词的歧义性，例如，假设C1,C2,….代表一个字符串中的汉字。我们首先位于字符串的开头并想知道如何区分单词。我们首先搜索词典，看 _C1_是否为一个单个汉字组成的单词，然后搜索 _C1C2_来看是否为一个两个汉字组成的单词，以下类推。直至找到字典中最长的匹配。最可能的单词就是最长的匹配。我们取这个单词，然后继续这个过程直至字符串中的最后一个单词被识别出来。
2）复杂最大匹配算法。另一种最大匹配算法比基本的形式更为复杂。他们的最大匹配规则指出，最可能的分词方案是三个单词，再次，我们从一个字符串的头部开始，寻找分词的方案。如果存在有歧义的分词（例如，_C1_是一个单词，但是_C1C2_也是一个单词，等等），然后我们向前再看两个单词去寻找所有可能的以 _C1_ 或者 _C1C2_ 开头的三词chunks。例如,如果有一个可能的三词chunks： _C1_ _C2_ _C3C4_ _C1C2_ _C3C4_ _C5_ _C1C2_ _C3C4_ _C5C
最大长度的chunk是第三个。第一个单词，在第三个chunk中的_C1C2_，会被认为是正确的。我们接受这个词，并向前重复这个过程从汉字C3，直到字符串的最后一个词被识别。除了最
- 5 -
石家庄经济学院本科生毕业论文
大匹配算法，许多其它消除歧义的算法也已经被得出。在消除歧义的过程中使用了各种各样的信息，例如，概率和统计，语法，还有词语形态学，它们当中的大部份需要一个构建良好，拥有汉字和词组频率信息的字典，单词的语法分类，以及一个语法或形态学的集合（例如，汉语知识信息处理小组）。虽然有各种各样的消除歧义的算法，但是到目前为止并没有一种十分完美的消除歧义的算法。
2.2.2 未登录词及其处理方法
未登录词大致包含两大类：1）新涌现的通用词或专业术语等；2）专有名词，如中国人名、外国译名、地名、机构名（泛指机关、团体和其它企事业单位）等。前一种未登录词理论上是可预期的，能够人工预先添加到词表中（但这也只是理想状态，在真实环境下并不易做到）；后一种未登录词则完全不可预期，无论词表多么庞大，也无法囊括[4]。 未登录词的处理是中文分词的一大难题，对于歧义识别问题中出现的第一种，我们只有拥有庞大的上下文资料才能处理，而对于第二种歧义问题，目前已经出现了许多消除歧义的算法，第三种歧义问题实际上就是未登录词导致的歧义，对于现有的词典来说，所有不在词典里的词语可以说都是未登录词。对于未登录词，将未登录词进行分类，让用户自己选择自己需要的专业词汇，这是一种很人性化的解决办法。
2.3 主要的分词算法
从开始研究中文分词算法到现在，虽然没有出现非常完美的分词算法，但是也还是出现了许多比较好的分词算法，目前的分词算法主要包含基于字典的分词算法，基于统计的分词算法和基于理解的分词算法，下面简要介绍一下这些算法。 2.3.1 基于字典的分词算法
基于字典的分词算法又叫机械分词算法，这种方法按照一定策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功(识别出一个词)。根据扫描方向的不同分为正向匹配和逆向匹配;根据不同长度优先匹配的情况，分为最大(最长)匹配和最小(最短)匹配;根据与词性标注过程是否相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的方法如下[3]:
正向最大匹配法(Maximum Matching Method)通常简称为MM法。其基本思想为:设D为 词典，MAX表示D中的最大词长，string 为待切分的字串。MM法是每次从string中取长度为MAX的子串与D中的词进行匹配。若成功，则该子串为词，指针后移MAX个汉字后继续匹配，否则子串逐次减一进行匹配。
逆向最大匹配法(Reverse Maximum Matching Method)通常简称为RMM法。RMM法的 基本原理与MM法相同，不同的是分词的扫描方向，它是从右至左取子串进行匹配。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245，显然RMM法在切分的准确率上比MM法有很大提高。基于词典的分词算法，对于在词典中的词分词的精确度很高，但是不能很好的解决歧义问题，经常和其它分词算法结合在一起应用。 2.3.2 基于统计的分词算法[6]
该方法的主要思想：词是稳定的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻出现的概率或频率能较好反映成词的可信度。可以对训练文本中相邻出现的各个字的组合的频度进行统计，计算它们之间的互现信息。互现信
- 6 -
石家庄经济学院本科生毕业论文
息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可以认为此字组可能构成了一个词。该方法又称为无字典分词。
该方法所应用的主要的统计模型有：N元文法模型、隐Markov 模型和最大熵模型等。在实际应用中一般是将其与基于词典的分词方法结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。
2.3.3 基于理解的分词算法
该方法又称基于人工智能的分词方法，其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统和总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。目前基于理解的分词方法主要有专家系统分词法和神经网络分词法等。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 2.3.4 小结
无论是哪一种分词算法都不是完美的，都有各自的优缺点：基于词典的分词算法的优点是简单，易于实现，缺点是匹配速度慢，不能很好的解决歧义问题，并且也不能很好的解决未登录词的问题；基于统计的分词算法的优点是可以发现所有的歧义切分，缺点是统计语言的精度和决策算法在很大程度上决定了解决歧义的方法，并且速度较慢，需要一个长期的学习过程才能达到一定的程度；由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。
- 7 -
石家庄经济学院本科生毕业论文
3 双向匹配算法和子字典机制
通过第二章对中文分词的简介，我们知道在现有中文分词算法中，没有一个是百分之百完美的算法，本文主要是将基于字典的最大正向匹配算法和最大逆向匹配算法进行了结合，组成了双向匹配算法，本章主要是对双向匹配的算法思想和算法步骤流程进行了讲解，此外，本章还对基于词典的几种词典机制进行了讲解，比较了其优缺点，在此的基础上提出了本文采用的词典机制并且进行了详细的讲解。
3.1双向匹配算法
双向匹配算法简要说来就是对待切分的文字分别进行最大正向匹配和最大逆向匹配，然后在此基础上对切分结果进行比较，然后根据不同的结果采用不同的分词策略。首先，本小节先介绍最大正向匹配和最大逆向匹配，在两者的基础上介绍双向匹配算法。 3.11最大正向匹配算法（MM）
最大正向匹配算法的算法思想是：设D为词典，MAX表示算法采用的最大词长，string 为待切分的字串。MM法是每次从string中取长度为MAX的子串与D中的词进行匹配。若成功，则该子串为词，指针后移MAX个汉字后继续匹配，否则子串逐次减一进行匹配。我们在具体实现时提出了一种改进算法，经典的算法在实现的时候，最大长度词MAX是人工定的，这种方法由于不科学且因为个人的原因造成分词系统的不准确，我们在这里将最大长度词由程序自己获取，从子字典的最大长度来得到最大匹配的长度。根据算法的具体的思想，我们能够很清楚的得到MM算法的流程：
1）输入经过预处理后的待切分的句子,并初始化Index = 0； 2）获得字典数据库内各个子字典的长度；
3）获得分词单词的长度，并和字典数据库内最长的子字典比较，如果子字典的最大长度大于要分词的长度，则取剩于要分词的字符串为最大长度，否则则以最大长度切分；
4）用二分法查找与当前最大匹配长度相同的子字典，如果找到该字典则转5，否则最大长度减一转4；
5）取得要分词的字符串SubStr，在字典里找该字符串，如果找到则将该字符串添加到List内，如果没有找到则判断SubStr是否大于1，如果大于1，则删除SubStr最后一个字转5，否则置切分标志，转6；
6)判断Index是否小于STR，如果小于则转3否则保存List,退出。具体的算法流程如图3-1。
- 8 -