中文分词毕业论文

石家庄经济学院本科生毕业论文

摘 要

中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、语音识别、文本语音转换、自然语言理解等中文信息处理领域的基础，虽然研究了很多年，但是中文分词依然是中文信息处理的瓶颈之一。

本文首先将已有的分词算法进行了分析、总结和归纳，讨论了中文识别一直难以很好解决的两大问题：歧义识别和未登录词。接着在基于词典的基础上将最大正向匹配和最大逆向匹配结合起来，得到了双向匹配分词算法，并且使用了自己提出的字典机制（子字典机制）实现了一个基于双向匹配算法的中文分词系统。

关键词：中文分词；双向匹配；子字典机制

ABSTRACT

Chinese word segmentation is the basis of information extraction, information retrieval, machine translation, text categorization, automatic summarization, speech recognition, text-speech, natural language understanding and other Chinese information processing , although Chinese word segmentation has been studied for many years, the Chinese word is one of the Bottleneck of Chinese information processing .

Firstly, this paper is to present the segmentation algorithm which has been analyzed, summarized, discussed the implementation of the Chinese has not been identified two major problems: ambiguous word recognition and not landing. Then, the basis of the dictionary will be based on maximum matching and maximum reverse positive match together to form a two-way matching word segmentation algorithm, and uses its own dictionary mechanism proposed by (a dictionary mechanism.) to achieve a two-way matching algorithm based on Chinese word segmentation system.

Key words: Chinese word; two-way match; Sub-dictionary mechanism

Ⅰ

石家庄经济学院本科生毕业论文

目 录

摘要.............................................................................................................................Ⅰ ABSTRACT.................................................................................................................Ⅰ 1引言.............................................................................................................................1 1.1 研究背景、目的及意义...........................................................................................1 1.2 中文分词的现状....................................................................................................1 1.3 本文的主要创新点................................................................................................3 1.4 课题任务和论文结构............................................................................................3 2 中文分词简介...........................................................................................................4 2.1 中文分词问题描述.................................................................................................4 2.2 中文分词难点分析................................................................................................4 2.3 主要的分词算法....................................................................................................6 3 双向匹配算法和子字典机制...................................................................................8 3.1双向匹配算法.........................................................................................................8 3.2 基于词典的分词算法的词典机制......................................................................13 3.3 小结......................................................................................................................16 4 中文分词系统的设计与实现.................................................................................17 4.1 系统设计与原则..................................................................................................17 4.2 中文分词系统的设计..........................................................................................17 4.3 中文分词结果的实现..........................................................................................19 5 测试.........................................................................................................................24 5.1 测试环境和测试方案..........................................................................................24 5.2 中文分词系统评价标准......................................................................................24 5.3 实验结果和结论..................................................................................................24 结论.............................................................................................................................27 致谢.............................................................................................................................28 参考文献.....................................................................................................................29

Ⅱ

石家庄经济学院本科生毕业论文

基于双向匹配的中文分词算法的研究与实现

1 引言

1.1 研究背景、目的及意义

随着信息时代的到来，可供人们查阅和检索的中文信息越来越多，如何在浩如烟海的中文信息世界里找到自己需要的资料成为一个越来越重要需要研究的课题。在当今时代，要处理迅猛增长的信息，手工处理已经变得不太现实。因此出现了自动化出来方法，自动化处理方法帮助人们检索、管理信息，来解决现在社会信息丰富而知识贫乏的现状。目前已经出现了很多自动化的工具诸如自动摘要、自动文件检索等语言处理技术，在这些技术内的一个核心关键是主题词，对于主题词的提取有助于简化此类工作，而如何找到主题词是需要中文分词技术的。此外中文分词也是搜索引擎，翻译等技术的基础。

中文分词，顾名思义，就是借助计算机自动给中文断句，使其能够正确表达所要表达的意思。中文不同于西文，没有空格这个分隔符，同时在中文中充满了大量的同义词，相近词，如何给中文断句是个非常复杂的问题，即使是手工操作也会出现问题。中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、语音识别、文本语音转换、自然语言理解等中文信息处理领域的基础研究课题[1]。对于中文分词的研究对于这些方面的发展有着至关重要的作用。可以这样说，只要是与中文理解相关的领域，都是需要用到中文分词技术的。因此对于中文分词技术的研究，对于我国计算机的发展有着至关重要的作用。

计算机对中文和西文的处理技术原理基本相同，但是由于中文本身的特点，我们必须引入中文处理技术，而中文分词技术则是其中的关键，是其他中文处理技术的基础。在我国中文分词已经被研究了三十多年，但是这仍是制约中文信息助理的瓶颈之一，它主要存在语言学和计算机科学等两方面的困难[1]。对于语言学方面的内容本文不再赘述，本文主要讲解计算机科学方面的内容。在计算机科学，仍有两大难题未能很好的解决，一是歧义识别问题，二是未登录词的处理问题。这两类问题解决不好，那么中文分词就无法解决，本文系统的讲解了这两类问题，以及遇到的困难等。

1.2 中文分词的现状

最早的中文分词方法是由北京航空航天大学的梁南元教授提出的一种基于“查字典”分词方法。该方法的思想事把整个中文句子，读一遍，然后把字典里有的词都单独标示出来，当遇到复合词的时候，（例如石家庄经济学院），就找到最长的词匹配，遇到不认识的字符串就分割成单个文字。这种分词方法效率并不高，但它的提出为中文分词技术奠定了基础。

在接下来的近30年的研究中，许多研究者实现了中文分词基于词典和基于概率统计的很多算法。现在中文分词的算法主要包括对于中文分词的研究主要有基于词典的分词方法，基于统计的分词方法，基于理解的分词方法等。其中基于词典的分词方法是当今的主流，可以说现在出现的分词系统，很多都是在基于词典的基础上再结合另外的一种或两种方法而成的。基于词典的分词方法又称机械分词方法，主要包括最大正向匹配，最大逆向匹配，最少切分法等。不仅对于算法的研究，目前国内已有许多分词系统相继开发完成。文[2]对现在的各个

- 1 -

石家庄经济学院本科生毕业论文

分词系统及其特点做了阐述如下：

SCWS

Hightman开发的一套基于词频词典的机械中文分词引擎，它能将一整段的汉字基本正确的切分成词。采用的是采集的词频词典，并辅以一定的专有名称，人名，地名，数字年代等规则识别来达到基本分词，经小范围测试大概准确率在 90% ~ 95% 之间，已能基本满足一些小型搜索引擎、关键字提取等场合运用。45Kb左右的文本切词时间是0.026秒，大概是1.5MB文本/秒，支持PHP4和PHP 5。 ICTCLAS

这是最早的中文开源分词项目之一，ICTCLAS在国内973专家组组织的评测中活动获得了第一名，在第一届国际中文处理研究机构SigHan组织的评测中都获得了多项第一名。ICTCLAS3.0分词速度单机996KB/s，分词精度98.45%，API不超过200KB，各种词典数据压缩后不到3M.ICTCLAS全部采用C/C++编写，支持Linux、FreeBSD及Windows系列操作系统，支持C/C++、C#、Delphi、Java等主流的开发语言。 HTTPCWS

HTTPCWS 是一款基于HTTP协议的开源中文分词系统，目前仅支持Linux系统。HTTPCWS 使用“ICTCLAS 3.0 2009共享版中文分词算法”的API进行分词处理，得出分词结果。HTTPCWS 将取代之前的 PHPCWS 中文分词扩展 CC-CEDICT

一个中文词典开源项目，提供一份以汉语拼音为中文辅助的汉英辞典，截至2009年2月8日，已收录82712个单词。其词典可以用于中文分词使用，而且不存在版权问题。Chrome中文版就是使用的这个词典进行中文分词的。

IK

IKAnalyzer是一个开源的，基于java语言开发的轻量级的中文分词工具包。从2006年12月推出1.0版开始，IKAnalyzer已经推出了3个大版本。最初，它是以开源项目Luence为应用主体的，结合词典分词和文法分析算法的中文分词组件。新版本的IKAnalyzer3.0则发展为面向Java的公用分词组件，独立于Lucene项目，同时提供了对Lucene的默认优化实现。Paoding

Paoding（庖丁解牛分词）基于Java的开源中文分词组件，提供lucene和solr 接口，具有极 高效率 和 高扩展性 。引入隐喻，采用完全的面向对象设计，构思先进。 高效率：在PIII 1G内存个人机器上，1秒 可准确分词 100万 汉字。 采用基于 不限制个数 的词典文件对文章进行有效切分，使能够将对词汇分类定义。 能够对未知的词汇进行合理解析 仅支持Java语言。 MMSEG4J

MMSEG4J基于Java的开源中文分词组件，提供lucene和solr 接口 1、mmseg4j 用 Chih-Hao Tsai 的 MMSeg 算法实现的中文分词器，并实现 lucene 的 analyzer 和 solr 的TokenizerFactory 以方便在Lucene和Solr中使用。 2、MMSeg 算法有两种分词方法：Simple和Complex，都是基于正向最大匹配。Complex 加了四个规则过虑。官方说：词语的正确识别率达到了 98.41%。mmseg4j 已经实现了这两种分词算法 盘古分词

- 2 -

石家庄经济学院本科生毕业论文

盘古分词是一个基于.net 平台的开源中文分词组件，提供lucene(.net 版本) 和HubbleDotNet的接口 高效：Core Duo 1.8 GHz 下单线程 分词速度为 390K 字符每秒 准确：盘古分词采用字典和统计结合的分词算法，分词准确率较高。 功能：盘古分词提供中文人名识别，简繁混合分词，多元分词，英文词根化，强制一元分词，词频优先分词，停用词过滤，英文专名提取等一系列功能。

本文认为，虽然我国对于中文分词的研究有了一定的成绩，但是我国对于中文分词的研究还处于初级阶段，虽然研究人员也提出了一些中文分词技术的重要思想和方法，但是对于中文分词的两大基本问题（歧义识别问题和未登录词问题）还没有很好的解决，所研发的中文分词系统在不同领域所达到的分词精度也不尽相同。这些都是我们将来对中文分词的研究方向。

1.3 本文的主要创新点

（1）对于词典在内存中的组织，本文主要讲解了现有的词典机制，并提出了子字典的概念：将字数相同的词语组织在一起，从而提高了词典的匹配速度；

（2）本文采用双向匹配的分词算法，双向匹配的分词算法主要是将最大正向匹配和最大逆向匹配相结合的分词方法，这对于歧义词语的发现和解决提出了一个很好的方法；

（3）本文支持词典的新增，这很好的解决了未登录词的问题，并支持专业词汇的载入，从而提高了分词的精准度。

1.4 课题任务和论文结构

本文针对现有的分词系统的优缺点，及时准确的掌握分词系统的发展现状和工作原理，并在分析现有系统的基础上自主实现了一个初步的分词系统，通过实践来发现问题，优化系统。在经典的分词算法的基础上进行了改进，希望通过良好的数据存储与组织方式来实现一个比较快速，词典比较全面，分词结果比较精确的分词系统。本文对于深入的研究中文分词，打下了良好的基础，试图为今后的的研究工作提出一个比较系统的研究方案。

中文分词是自然语言信息处理的基础性课题之一。本文首先从目前语言信息处理的瓶颈入手，提出了自然语言信息处理的关键技术——中文分词。接下来第一章阐述了中文分词机制和中文分词的研究背景、意义，和中文分词的现状。第二章主要是对中文分词进行了介绍，主要包括中文分词的问题描述，中文分词的难点，中文分词的两大基本问题，中文分词现有的算法思想和优缺点等内容。第三章主要讲解本文自己的分词算法和词典机制，第四章主要讲解了本文系统设计的主要思想和步骤，对于算法的思想，词典数据结构的设计和实现，和算法的主要步骤进行了讲解。第五章主要是对系统进行了测试 ，提出了三种不同的测试方案，来从不同角度对系统进行了测试，从分词速度和分词精确度对系统进行了评价，提出了本文词典机制和算法的优缺点。最后对本文进行了总结，对下一步的工作进行了展望。

- 3 -

石家庄经济学院本科生毕业论文

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 -

石家庄经济学院本科生毕业论文

开始 获得预处理的待分句子( STR)初始化Index=0 获得子字典最大长度并将其设为最大长度MaxLength 否 比较STR长度是否大于MaxLength 是 取STR为字符串SubStr Index位取MaxLength 长字符串（SubStr） 将SubStr在字典库中按最大长度搜索 是 是否搜索成功 切分位置加SubStr 删除SubStr最后一个字 否 是 是否SubStr大于1 否 切分标志加1(Index+1) 将str在标志位Index切分，保存分词结果到list 是 判断Index是否小于STR的长度 否 返回结果集List 结束 图3-1最大正向匹配算法

- 9 -

石家庄经济学院本科生毕业论文

3.12 最大逆向匹配算法（RMM）

最大逆向匹配算法的算法思想是：最大逆向匹配的算法跟最大正向匹配类似，不同的是扫描的方向，它是从右往左取子串进行匹配。根据算法的具体的思想，我们能够很清楚的得到MM算法的流程：

1)输入经过预处理后的待切分的句子STR,并初始化Index = STR.Length； 2)获得字典数据库内各个子字典的长度；

3)获得分词单词的长度，并和字典数据库内最长的子字典比较，如果子字典的最大长度大于要分词的长度，则取剩于要分词的字符串为最大长度，否则则以最大长度切分；

4)用二分法查找与当前最大匹配长度相同的子字典，如果找到该字典则转5，否则最大长度减一转4；

5)取得要分词的字符串SubStr，在字典里找该字符串，如果找到则将该字符串添加到List内，如果没有找到则判断SubStr是否大于1，如果大于1，则删除SubStr最后一个字转5，否则置切分标志，转6；

6)判断Index是否大于1，如果小于则转3否则保存List,退出。具体的算法流程如图3-2。

- 10 -

石家庄经济学院本科生毕业论文

开始 处理的待分句子( STR)初始化Index=STR.length 获得子字典最大长度并将其设为最大长度MaxLength 否 比较STR长度是否大于MaxLength 是 取STR为字符串SubStr Index位取MaxLength 长字符串（SubStr） 将SubStr在字典库中按最大长度搜索 是 是否搜索成功 切分位置加SubStr 删除SubStr最前一个字 否 是 是否SubStr大于1 否 切分标志加1(Index-1) 将str在标志位Index切分，保存分词结果到list 是 判断Index是否大于1 否 返回结果集List 结束 图3-2最大逆向匹配算法 - 11 -

石家庄经济学院本科生毕业论文

3.13 双向匹配算法（DMM）

双向匹配算法的算法思想是：将正向匹配与逆向匹配算法相结合起来，对于待分字符串，首先分别用最大正向匹配和最大逆向匹配算法进行分词，对于分词结果进行比较， 比较正向和反向两个最大匹配，返回分词结果，当两个方向的分词结果一致，返回字符串，当不一致，返回长度小的，当长度一致，返回反向的。这是因为统计表明，统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245，显然RMM法在切分

[2]

的准确率上比MM法有很大提高。同时本算法可以分别打出正向分词和逆向分词的结果供用户实验，还能够发现出现歧义的地方，从而为将来升级系统，消除歧义打下了良好的基础。 双向匹配算法的算法步骤如下：

1）输入待切分的句子String；

2）对String 进行预处理后分别用最大正向匹配算法和最大逆向匹配算法进行分词，对分词结果进行比较，如果分词结果完全相同则转3，如果分词结果不同则转4；

3）任意选出一种分词结果，将分词结果输出算法结束；

4）比较分词数目是否相同，如果相同则选取逆向分词结果，将分词结果输出，算法结束，否则选取分词数目较小的分词结果进行输出，算法结束。双向匹配的算法流程如图3-3。

- 12 -

石家庄经济学院本科生毕业论文

开始 输入待切分的句子String 对String 进行预处理 对预处理后的String分别进行MM和RMM得到切分结果MMResult和RMMResult 是 比较分词结果是否相同 否 比较分词数目是否相同 否 任意选择一种分词结果 是 选择分词数目较小的结果 选择RMM的分词结果

将分词结果输出 结束 图3-3双向匹配算法

3.2 基于词典的分词算法的词典机制

基于词典的中文分词很大一部分上的效率取决于词典的选择，所以分词的词典设计是中文分词系统工程开发中一个重要基础部分。因为实际中文分词系统需要在词典中反复查找所需词汇，所以如何设计出高效、易于维护的词典存储，对整个分词系统的速度有很大影响。在实际工程中，时间和空间总是相互矛盾的，即很难找到一种既占用内存小同时速度很快的算法。经过30多年无数研究者的努力，提出了很多的中文词典机制。目前最常用的词典机制

- 13 -

石家庄经济学院本科生毕业论文

主要有：基于Trie索引树的词典、基于整词二分法的词典和逐字二分法的分词词典机制。 下面首先介绍下着几类词典机制，然后再讲述本系统采用的词典机制。 3.2.1 基于整词二分法的词典[7]

首字HASH表

入口项个数

第一项指针

词索引表

词典正文指针

啊 阿 ?? 大 ?? 鼾 顸 005 089 ?? 794 ?? 002 000 . . ?? . ?? . ^ . . . . . . ?? . . . ?? .

词典正文 啊 啊哈 啊呀 啊哟 啊唷 阿 阿Q ?? 鼾声

图3-4基于整词二分法的词典机制

如图3-4 ，基于整词二分法的词典机制包括首字散列表、词索引表、和词典正文三部分。其中，首字散列表是根据所有的首字确定一个影射,由该字可以直接定位到该字对应的入口该入口包括以下部分:数组长度(以该字开始的词的个数)和 数组首指针(该字开始的词列表的开始位置)；词索引表包括词典指针，因为词典长度可以变化，所以需要选择不定长存储；词典正文是以词为单位的有序表,可以实现二分查找 ，当我们获得首字后，可以进行多次试探，来检索所需要的词语。这种算法的数据结构简单占用空间小构建及维护也简单易行但由于采用全词匹配的查询过程效率较为较低。 3.2.2 基于Trie 索引树的词典[7]

- 14 -

石家庄经济学院本科生毕业论文

首字Hash表 入口项个数 子树指针 啊 阿 ?? 大 ?? 鼾 顸 005 089 ?? 794 ?? 002 000 . . ?? . ?? . ^ 大字的TRIE索引树 关键字 子树大小 子树指针 ^ 案 把 坝 白 ?? 0 2 2 0 5 ?? . . . . . ?? ^ 要 0 1 . . ^ 菜 话 鼠 天 0 0 0 0 0 . . . . . 大 案 案 0 . 大 白 大 白 菜 大 白 话 大 白鼠 大 白天 大案要案 图3-5 基于TRIE索引树的词典机制

如图3-5所示，基于TRIE索引树的分词词典机制由首字散列表和TRIE索引树结点两部分组成。

TRIE索引树的优点是在对被切分语句的一次扫描过程中，不需预知待查询词的长度，沿着树链逐字匹配即可；缺点是它的构造和维护比较复杂，而且都是单词树枝(一条树枝仅代表—个词)，浪费了一定的空间。

3.2.3 基于逐字二分法的分词词典[7]

这种词典机制是前两种机制的一种改进方案。逐字二分与整词二分的词典结构完全一 样，只是查询过程有所区别：逐字二分吸收了TRIE索引树的查询优势，即采用的是“逐字匹 配”，而不是整词二分的“全词匹配”，这就一定程度地提高了匹配的效率。但由于采用的仍是整词二分的词典结构，使效率的提高受到很大的局限。 3.2.4 本文的分词词典机制———子字典机制

本文在吸取了以上词典的基础上，通过对汉字编码体系和中文分词特点的分析，采用了一种新的词典机制：子字典机制，这种词典是由一个链表实现的词典，在词典里每一项都是一个子词典的数据结构，以便在词典库中快速查找词。其数据结构如3-6图。

- 15 -

石家庄经济学院本科生毕业论文

字典首项，每项指 向一个子字典

?? ?? n词长

图3-6 基于子字典的分词机制

单词 2词长 3词长

3.3 小结

本章主要讲解了双向匹配的算法思想和算法流程，双向匹配是建立在传统的单向匹配的算法基础上，同时吸取了最大正向匹配和最大逆向匹配算法的优点，同时双向匹配对于发现歧义有一定的优势，对于将来研究消除歧义的算法打下了良好的基础。本章还讲解了基于词典的分词算法的分词机制，由于基于词典的分词机制是建立在“查字典”的基础上，因此，字典在内存中如何存储，这在很大程度上影响了分词的效率，本文提出的子字典机制，将字数相同的词放在一起存储，能够提高分词的效率。

- 16 -

石家庄经济学院本科生毕业论文

4 中文分词系统的设计与实现

在综合了上面讨论的中文分词技术和具体的算法思想的情况下，本文实现了一个可以进行中文分词的系统。编程语言为JAVA，开发环境为Windows 7,编译环境为eclipse。输入为GB2313格式的中文，输出为经过分词的中文。所用训练语料库为来自经典文章和网络新闻，本系统的分词算法采用了基于词典的分词算法，本系统很好的将最大正向匹配算法和最大逆向进行了结合，实现了双向匹配的算法。

由于设计和实现是纯工程性问题，下面将详细讨论这个部分，并附带了字典在计算机内存中的存储数据结构，在第五章对该系统的分词进行了实验验证，实验显示该系统具有较高可行性。

4.1 系统设计与原则

中文分词系统的设计原则包含三个方面：精确性、高效性和可维护性，分别描述如下：

1） 精确性：精确性是最能反映出中文分词系统好坏的核心标准。由于中文本身语言的复杂性，对于中文分词本身所遇到的切分歧义问题、未登录词做到没有错位完全实现几乎是不可能的。所以，如何在现有研究基础上，尽可能的提高分词的精确度是至关重要的。

2）高效性：高效性是反映中文分词系统性能的一项重要指标。由于大多数分词系统是基于词典的，在分词系统过程中需要对对中文语句进行反复的匹配，查找，对计算机而言时间消耗也是一个不小的问题。所以尽可能的提高分词的速度也是我们设计需要遵循的原则之一。

3）可维护性：任何系统必须具有较好的可维护性，中文分词系统也是一样，由于是基于词典的中文分词系统，所以词典的选择应该具有灵活性，在用户想要更换词典的时候应该具有良好的接口，从而使分词系统更加完善，更加具有实用性[8]。

4.2 中文分词系统的设计

本中文分词系统分为四个功能模块：词典加载模块，预处理模块，中文分词模块和分词结果保存模块。其结构如图4-1所示。

- 17 -

石家庄经济学院本科生毕业论文

开始 打开系统 词否 典

加是否添加字典 载模 是 块

选择词典并加载

选择带切分文档 预 处理文本预处理，断句

模 块预处理输出结果

最大正向匹配算法 中文

分 最大逆向匹配算法 词模

块 双向匹配算法 保输出分词结果 存

模 块保存分词结果

结束 图4-1 中文分词系统

1）词典加载模块：在进行分词时面对的是不同长度的词，本文将同一首字下不同长度的词放入不同的子字典，每个子字典的长度是相同的，形成了2字词表、3字词表??等，以链表方式存储。这样我们在进行匹配的时候，对于不同长度的词可以直接定位到以该词的首字为索引的相同长度的子字典，提高了查询速度。另外本系统为了达到系统设计的可维护性，支持字典的选择性加载，用户在进行分词前可以选择加载专业词典或者是用分词自带的字典进行分词，词典的加载需要一定的时间，但是加载词典只需要一次，以后用户就可以直接使用加载过的词典。

2）预处理模块：这个功能模块的作用是对输入的待切分文档进行预处理，识别出明显的非中文字符，例如英文，数字等，从而消除了一部分歧义的产生。具体的流程是对输入的文本进行预处理，在进行分词前，先进行字符检查,检查是否是有效字符,比如是否是中文,英文字符等,包括全角和半角等，如果判断的字符与上一个字符是同一类字符的话则进行下一个判断，如果是不同的字符的话则在两者之间加入空格，例如对于“你的编号是12345，Welcome!”

- 18 -

石家庄经济学院本科生毕业论文

经过预处理后应该变成“你的编号是 12345 ，Welcome”。在进行预处理过程中，“你的编号是”这几个字符同属于中文字符，故不进行处理，而“1”与“是”分属于不同的的字符，则在两者之间由中文分词系统自动添加上空格，从而减少了歧义的产生。

3）中文分词模块：在经过预处理后得到的应该是连续的单个中文字组成的中文词串，在这部分用双向匹配来进行中文分词，这是整个中文分词的核心，也是设计的关键部分。对于中文分词系统来说，采取什么样的分词算法，分词算法的效率如何是评价一个系统好坏的决定因素。本系统在吸收了最大正向匹配和最大正向匹配的基础上，采用了双向匹配的分词策略，该算法的具体思想上是首先分别用最大正向匹配和最大逆向匹配进行分词，然后根据分词的结果来进行判断采取用何种分词结果。在这个模块，本系统用户可以在看到最大正向匹配和最大逆向匹配的分词结果不同时的地方，从而对分词以后进行消除歧义打下了良好的基础。

4）分词结果保存模块：本功能模块的主要功能是允许用户将分词结果以文本形式保存起来，此模块的功能相对简单，不涉及什么算法，只是为用户提供了保存结果的一个接口，在该模块用户可以自己定义要保存的文件的名称和保存路径。

4.3 中文分词结果的实现

本系统的实现环境是Eclipse，它是IBM公司出品的开源的java语言运行环境，开发语言是java，java是纯面向对象的语言，是一门很优秀的编程语言。

首先在Eclipse内新建java工程，命名为WordAutoSegment,来管理整个工程项目。

接下来我们将实现词典库的设计，在WordAutoSegment项目中添加一个新类Dictionary,用它来全面封装词典数据库中的数据和相关词典库存储的操作。根据上文3.2.1阐述的词典机制，来逐步实现词典类。

（1）在类Dictionary中有一个属性是词典的名称，对于中文分词系统来说，我们不能加载任何词典，这不可能也不现实，我们只是加载经过用户自己同意加载的词典，这类词典都有特殊的名称，这就是类Dictionary内的属性。

（2）在上文中提到，我们将词典分为不同的子字典，每一个子字典的长度是相同的，因此对于一个完整的中文分词系统来说，我们只有一个具体的大的词典的数据库，在数据库里面存在着很多的子词典，这就要求我们提过了两个方面的要求：首先，我们需要一个用来盛放子字典的容器，我们用链表来实现；其次，根据面向对象的思想，我们需要抽象出一个类来表示子字典，因此我们在工程中再添加一个新的类，名称为SubDictionary,根据上文中提到的词典机制，我们的SubDictionary分别有长度，内容等属性。无论是Dictionary还是SubDictionary当中与词典的相关操作（查询、插入等）与链表的查询、删除、插入等一致，本文不在赘述，有感兴趣的读者可查阅与链表相关的资料。 在词典简历完成后我们就可以很好的实现最大正向匹配（MM）和最大逆向匹配（RMM），在此基础上实现双向匹配。我们新建一个类命名为MaxMatchSegment，用来封装中文分词系统中出现的分词算法，在4.2中我们提到本中文分词系统有预处理模块，因此我们又创建了字符检查类CharTest，用来进行完成预处理模块所要求的功能，然后为了完成接下来我们的核心算法，我们又创建了实现了工具类Search 和Sort来对所要进行的字符串进行搜索和排序。通过以上的工作，接下来实现核心算法：

- 19 -

石家庄经济学院本科生毕业论文

（1）正向最大匹配的函数名称是segmentChnLToR，该函数接受一个参数String source，即要分词的源文件，返回结果是一个分好词的链表。具体代码实现如下： private List segmentChnLToR(String source){ String temp = \ List list = new ArrayList();//新建一个链表用来存储分词结果 int[] wordLen = dictionary.getDBWordLen();//获得字典数据库内单词长度的个数，即字典数据库内有几个子字典 int start = 0; int length = source.length();//获得分词的单词长度 int minReadLen = 0; if (wordLen.length == 0) return null;//如果没有子字典，则返回空 minReadLen = wordLen[0]; while (start < length){ minReadLen = wordLen[wordLen.length - 1]; if (minReadLen > (length - start)){ minReadLen = length - start;//如果子字典的最大长度大于要分词的长度，则取剩余的要分词的字符串为最大的长度 } while(minReadLen > 1){//用二分法查找与当前最大匹配长度相同的子字典 if (!Search.binarySearch(wordLen, minReadLen)){ minReadLen--; continue; } temp = source.substring(start, start + minReadLen);//取得要分词的字符串 if (dictionary.find(temp)){//如果找到该字符串则退出 break; }else{//如果找不到则最大长度减一 minReadLen--; } } temp = source.substring(start, start + minReadLen);//取得匹配成功后的字符串 list.add(temp);//将匹配成功的字符串添加到List start += minReadLen; } return list;//返回List }

（2）逆向最大匹配的函数名称是segmentChnRToL，该函数接受一个参数String source，即要分词的源文件，返回结果是一个分好词的链表。具体代码实现如下： private List segmentChnRToL(String source){ String temp = \ List list = new ArrayList() ; List list1 = new ArrayList();//新建两个链表，一个用来存储中间的保存结果，一个用来存放最后 的结果 int[] wordLen = dictionary.getDBWordLen();//获得字典数据库内单词长度的个数，即字

- 20 -

石家庄经济学院本科生毕业论文

典数据库内有几个子字典 int start = 0; int length = source.length(); int minReadLen = 0; if (wordLen.length == 0) return null;//说明没有字典 minReadLen = wordLen[0]; while (start < length){ minReadLen = wordLen[wordLen.length - 1];//最长的子字典 if (minReadLen > (length - start)){//如果子字典的最大长度大于要分词的长度，则取剩余的要分词的字符串为最大的长度 minReadLen = length - start; } while(minReadLen > 1){//用二分法查找与当前最大匹配长度相同的子字典 if (!Search.binarySearch(wordLen, minReadLen)){ minReadLen--; continue; } temp = source.substring(length - start - minReadLen, length - start);//取得要分词的字符串 if (dictionary.find(temp)){//如果找到该字符串则退出循环 break; }else{//找不到该字符串最大匹配长度减一 minReadLen--; } } temp = source.substring(length - start - minReadLen, length - start);//取得反向匹配的字符串 list.add(temp);//将匹配的字符串保存到临时的链表内 start += minReadLen; } for (int i = list.size() - 1; i >= 0; i--){//按分词源文件的方向将分词结果保存到链表内 temp = (String)list.get(i); list1.add(temp); } return list1;

}

（3）在实现了最大正向匹配和最大逆向匹配后我们来实现双向匹配算法：双向匹配算法的思想上文已经提到，具体代码实现如下： private String operate(TextBlock block){ String result = \ List list1 = null;//得到最大正向匹配的结果 List list2 = null;//得到最大逆向匹配的结果 //判断是否是中文字符，如果不是中文字符，则添加“/” if (block.getProperty() != CharTest.CHINESE){ result = block.getText() + \ - 21 -

石家庄经济学院本科生毕业论文

}else{ list1 = segmentChnLToR(block.getText());//从左至右拆分 list2 = segmentChnRToL(block.getText());//从右至左拆分 //比较正向和反向两个最大匹配，返回分词结果，当两个方向的分词结果一致，返回字符串， //当不一致，返回长度小的，当长度一致，返回反向的 result = compare(list1, list2); } return result;

}

在最大双向匹配的的函数实现中调用了compare()这个函数是比较最大正向和最大逆向的匹配结果，然后选择最优的，这个函数就是单纯的链表比较，因为这个比较不是本算法的重点，具体实现不在赘述。

在实现了核心算法以后，为了使用户更舒适、更方便、更人性化，我们设计了UI图形界面，如图4-2所示：

① ⑧

③

②

④

⑤

⑥

图 4-2 中文分词系统界面

UI图形界面说明：①----用户可以选择载入字典，也可以使用现有的字典； ②、③--用户选择输入方式，当用户点击手动输入时，③区域变为可 编辑的，用户可以在里面输入自想要分词的内容，当点击文 件输入时，会弹出对话框，当用户选择文件点击确认后，会 将文本打开显示在③区域当中；

④、⑤--当用户点击分词后，会将显示在③区域内容的文字按双向 匹配分词，分词结果会显示在区域⑤内，⑤显示分词的结果；

- 22 -

石家庄经济学院本科生毕业论文

⑥----状态显示栏，会将系统当前运行的状态显示出来；

⑦----当用户点击是的时候回弹出文件保存对话框，将用户需要保存 的内容保存起来；

⑧----当用户点击退出按钮时，系统退出。

- 23 -

石家庄经济学院本科生毕业论文

5 测试

5.1 测试环境和测试方案

（1）测试环境： 实验平台：Eclipse

操作平台：Windows7 32位操作系统

CPU： Intel(R) Core(TM)2 Duo CPU T5670@1.80GHZ 内存： 2.00GB 硬盘： 120GB （2）测试方案：

方案一：本文按照3种常见的歧义类型，分别对常见的三种歧义分词采用正向最大正向匹配，最大逆向匹配，和双向匹配算法来进行切分，并对切分结果进行对比分析：

第一类歧义（中文自身的二义性引起的歧义）：“乒乓球拍卖完了”； 第二类歧义（由于分词算法引起的歧义）：“这时候最热闹的 ”； 第三类歧义（由于未登陆词引起的歧义）：“淘宝网上竟然能搜索到”；

方案二：为了充分的对中文分词系统进行测试，本文分别摘取了计算机、科学和计算机三个方向的文章来进行测试。

方案三：为了测试本系统的分词词典机制，本文提出了方案三，方案三是将本系统与基于整词二分法的分词系统进行了测试对比，在硬件环境和分词词典等都相同的情况下测试其运行速度和空间消耗。

5.2 中文分词系统评价标准

中文分词很难有统一的评价标准，因为现在还很难定义词的界限，因此我们采用以下两个标准来评判分词系统的性能：

标准一：分词精度是指切分的正确率。它是自动分词系统的一个重要技术指标。分词的精度的计算机公式是：

分词的精度 = 正确切分成的词语数/切分出的词语数*100%

标准二：、分词速度，分词速度是指单位时间内所处理的汉字个数。在分词正确率基本满足要求的情况下，切分速度是另一个很重要的指标，本系统切分速度采用的单位是毫秒。

5.3 实验结果和结论

对于方案一中的实验，因为分词时间较短，因此我们只采用评判其是否正确来进行评测。表显示了其分词的结果：

- 24 -

石家庄经济学院本科生毕业论文

歧义类别 第一类歧义 第二类歧义 第三类歧义 表5-1 对于方案一的切分结果对比分析 句子切分 是否正确 原句子 乒乓球拍卖完了 MM 乒乓球/拍卖/完了 正确 RMM 乒乓球拍/卖完/了/ 正确 双MM 乒乓球拍/卖完/了/ 正确 原句子 这时候最热闹的 MM 这时候/最热/闹/的 错误 RMM 这时候/最/热闹/的/ 正确 双MM 这时候/最/热闹/的/ 正确 原句子 淘宝网上竟然能搜索到 MM 淘宝网/上/竟然/能/搜索/到 正确 RMM 错误 淘宝/网上/竟然/能/搜索/到 双MM 淘宝网/上/竟然/能/搜索/到 正确 从上表的切分对比我们看出，由于中文歧义的特殊性，单纯的使用MM或RMM并不能很好的解决歧义的问题，可用双向匹配来说就能够在一定范围内解决歧义问题。

按照第二种实验方案进行实验，得到了以下的结果，如表5-2。

表5-2 对于方案二的测试结果 序号 文章类型 文章分词精度 时间（ms） 大小 1 计算机 29k 97.25% 229ms 2 体育 18k 93.26% 146ms 3 科学 22k 93.57% 198ms 按照方案三，本文从时间和空间上测试本系统采用的新的分词机制，首先我们先给出理

论上的分析：对于基于词典的分词算法，给定文档D，其长度为N，给定词典Z，字典的词条数目为T，在词典中查找某一字串的复杂度为f(T),在本文使用的是二分查找来在词典内查找给的的词语，则查找单个词语的时间复杂度是O（Log2T）并且使用双向匹配算法分词需要进行O（N）次的词典查找，故其时间复杂度为O（N*Log2T），设计一个好的分词词典机制就是要降低T和N的大小，因为本文是将字数相同的词语放在一起组织，因此与整词二分法的时间相比，T小了很多，故用本算法实现的系统理论上应比基于整词二分词典机制的快。在空间上整词二分法的空间复杂度是O（N）,而基于子字典的空间复杂度也是O（N+n）,其中N指的是词典的单词数目，n指的是我们在组织子字典的时候产生的额外存储指针的开销，因此理论上基于子字典的词典机制所用空间会比基于整词二分的词典机制较大些。

下面本文将本系统和经典的基于整词二分法词典机制进行了对比。并且都使用本文中采用的最大双向匹配算法分别对一段文本进行了切分，比较其分词速度。两个分词程序系统都使用了java实现，运行环境一致，保证了实验的公平性。

对两个分词词典机制，我们任取一段文本（大小4M字节左右）进行切分，测定其分词速度和词典的空间。实验进行了多次，取平均值。实验结果如表5-3所示。

- 25 -

石家庄经济学院本科生毕业论文

表5-3方案三的测试结果 词典机制 词典空间（字节） 所用时间（单位ms） 整词二分 2237344 23450 子词典（本文词典） 3547300 5390 由上表可以表明，两种词典机制的词典空间大小为本文词典>整词二分的词典.

本文词典比整词二分词典的空间大了大概1.5M左右，对于现代计算机来说，1.5M的内存

空间对系统运行可以忽略不计。而时间上本分词系统的词典机制比整词二分法时间快了很多。这与我们理论上的判断结果一致。 通过上文的三个测试方案，单纯的最大正向匹配和最大逆向匹配并不能很好的解决歧义的问题，在我们使用双向匹配的分词算法后，我们能够很好的吸取最大正向匹配和最大逆向匹配的优点，对于歧义的解决有了一定的提高，对于本中文分词系统，用户可以自己选择建立新的词，然后自动的加入到分词系统去，从而提高了分词的准确率。通过方案三与传统的分词词典机制即整词二分法的对比，从而证明了在现代这个时间越来越珍贵的时代，本系统有着巨大的优势。

中文语言的复杂性，给中文分词系统带来了很大的困难，任何一个分词系统都不能够百分之百的解决分词，本系统通过对分词词典机制的探索和对分词算法的改进使得本系统有了较高的效率，实验结果表明，本系统完成了中文分词系统的功能。

- 26 -

石家庄经济学院本科生毕业论文

结论

在中文信息处理中，中文分词一直是基础的研究课题，可是这也是中文信息处理的关键，处理不好中文分词，中文信息处理就无法突破，其研究的好坏对于以中文分词的基础的课题比如语音识别，在线翻译等课题有着决定作用。但是因为中文分词的复杂性，中文分词研究了很长时间至今还没有非常完美的分词系统问世。本文针对现有的分词系统的优缺点，及时准确的掌握分词系统的发展现状和工作原理，并在分析分析系统的基础上自主实现一个初步的分词系统，通过实践来发现问题，优化系统。在经典的分词算法的基础上进行了改进，通过良好的数据存储与组织方式来实现一个比较快速，词典比较全面，分词结果比较精确的分词系统。本文的主要工作如下：

（1）系统的介绍了中文分词的研究背景、研究意义，分析了中文分词的现状，对于中文分词的两大基本问题进行了阐述。

（2）本文对于中文分词的经典算法，比如基于词典的中文分词算法，基于统计的分词算法，基于理解的分词算法等进行了详细的讲解，并总结了其优缺点。另外，本文还对现存的词典机制进行了阐述，再此基础上我提出了自己的一种词典机制，并对其进行了详细的讲解。 （3）在前文的基础上，我实现了一个中文分词系统，本系统是基于词典的中文分词系统，词典机制采用的是子字典机制，分词算法是在最大正向匹配和最大逆向匹配的基础上实现的双向匹配算法。

（4）本文还对实现的中文分词系统进行了测试，实验表明，本中文分词系统能够很好的解决中文分词的问题，分词结果基本上正确。

由于时间有限，水平有限，词典等的来源等问题，本系统无论是精确度还是分词效率上都有待提高，另外本系统虽说采用了双向匹配的分词算法，这能够消解一部分的歧义，但是并没有真正的提出歧义的消除算法，因此接下来的工作展望如下： （1）尽可能的收集各种专业词典，从而提高本系统词汇量，从根本上进一步提高分词精确度； （2）进一步学习各种消除歧义的算法，尽可能的提出自己的消除歧义算法，并对本系统进行实现，提高分词的精确度；

（3）中文分词只是中文信息处理的基础，在完善系统后，本文作者打算学习新的知识，从而将中文分词学以致用，间接推动中文分词的发展。

- 27 -

石家庄经济学院本科生毕业论文

致 谢

在这里衷心地感谢孟永刚老师及同组的同学在毕业设计过程中给予我的帮助和支持。孟老师给我提出了许多合理性的建议，在孟老师的帮助下，我解决了一个个自己难以解决的问题。这对我能够顺利的完成本次设计是至关重要的。老师认真负责的工作态度、严谨的治学风格，使我深受启发，我会谨记孟老师的谆谆教导，这对我今后的工作会有很大的帮助。

同时，我也感谢计算机教研室的其他老师，他们同样也帮助我解决了不少毕业设计中的疑难问题，提出了宝贵的建议。

在此次设计过程中，考验了我们大学所学知识的综合应用以及在此基础上付诸实践，将理论与实践有机的结合起来，使自己的对知识的运用水平得以提高，在与同学的共同设计中，更是深刻体会到了团队精神的重要性，他们同样给予了我很多帮助。在此我也感谢在设计中对我帮助、支持和鼓励的同学们。

最后，在此对曾经帮助过我的朋友、老师表示致谢。也衷心的感谢在百忙之中评阅论文和参加答辩的各位专家、教授！

- 28 -

石家庄经济学院本科生毕业论文

参考文献

[1] 张春霞,郝天永.汉语自动分词的研究现状与困难[J].系统仿真学报.2005.(17）.138-147. [2] 百度百科 中文分词[EB/OL].http://baike.http://www.wodefanwen.com//view/19109.htm

[3] 余占秋.中文分词技术及其应用初探[J].电脑知识与技术：认证考试.2004.( 11).81-83. [4] 孙茂松,邹嘉彦.汉语自动分词研究评述[J].当代语言学.

[5] _Amo.Jry,ZZMMSEG 中文分词算法[EB/OL]. http://archive.cnblogs.com/a/1795908/ [6] 龙树全,赵正文,唐华.中文分词算法概述[A].电脑知识与技术.2009.5.

[7] 李庆虎,陈玉健,孙家广. 一种中文分词词典新机制——双字哈希机制[A].中文信息学报 ,2003(17),13-18.

[8]丁承，邵志清.基于字表的中文搜索引擎分词系统的设计与实现[J]计算机工程.2001,27(2)191-193.

[9] 马玉春,宋涛瀚.web中中文文本分词技术研究[J].计算机应用,2004,24(4):134-136.

[10]-Jing Wang, Wen Liu, Yong Qin, A Search-based Chinese Word Segmentation Method[A], Poster Paper 2007 1129-1130.

[11] 黄昌宁,赵海中文分词十年回顾[J] 中文信息学报2007,21(3),8-18.

- 29 -

石家庄经济学院本科生毕业论文

参考文献

[1] 张春霞,郝天永.汉语自动分词的研究现状与困难[J].系统仿真学报.2005.(17）.138-147. [2] 百度百科 中文分词[EB/OL].http://baike.http://m.wodefanwen.com//view/19109.htm

[3] 余占秋.中文分词技术及其应用初探[J].电脑知识与技术：认证考试.2004.( 11).81-83. [4] 孙茂松,邹嘉彦.汉语自动分词研究评述[J].当代语言学.

[5] _Amo.Jry,ZZMMSEG 中文分词算法[EB/OL]. http://archive.cnblogs.com/a/1795908/ [6] 龙树全,赵正文,唐华.中文分词算法概述[A].电脑知识与技术.2009.5.

[7] 李庆虎,陈玉健,孙家广. 一种中文分词词典新机制——双字哈希机制[A].中文信息学报 ,2003(17),13-18.

[8]丁承，邵志清.基于字表的中文搜索引擎分词系统的设计与实现[J]计算机工程.2001,27(2)191-193.

[9] 马玉春,宋涛瀚.web中中文文本分词技术研究[J].计算机应用,2004,24(4):134-136.

[10]-Jing Wang, Wen Liu, Yong Qin, A Search-based Chinese Word Segmentation Method[A], Poster Paper 2007 1129-1130.

[11] 黄昌宁,赵海中文分词十年回顾[J] 中文信息学报2007,21(3),8-18.

- 29 -

本文来源：https://www.bwwdw.com/article/nbb7.html