中文分词毕业论文.doc

《中文分词毕业论文.doc》由会员分享，可在线阅读，更多相关《中文分词毕业论文.doc（18页珍藏版）》请在三一办公上搜索。

1、中文分词毕业论文 摘 要 中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、语音识别、文本语音转换、自然语言理解等中文信息处理领域的基础，虽然研究了很多年，但是中文分词依然是中文信息处理的瓶颈之一。 关键词：中文分词；双向匹配；子字典机制 ABSTRACT Chinese word segmentation is the basis of information extraction, information retrieval, machine translation, text categorization, automatic summarization, speech rec

2、ognition, 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 algorit

3、hm 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-wa

4、y 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引言.11.1 研究背景、目的及意义.1

5、1.2 中文分词的现状.11.3 1.4 课题任务和论文结构.32 中文分词简介.42.1 中文分词问题描述.42.2 中文分词难点分析.42.3 主要的分词算法.63 双向匹配算法和子字典机制.83.1双向匹配算法.83.2 基于词典的分词算法的词典机制.133.3 小结.164 中文分词系统的设计与实现.174.1 系统设计与原则.174.2 中文分词系统的设计.174.3 中文分词结果的实现.195 测试.245.1 测试环境和测试方案.245.2 中文分词系统评价标准.245.3 实验结果和结论.24结论.27致谢.28参考文献.29 基于双向匹配的中文分词算法的研究与实现1 引言1.

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

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

8、技术则是其中的关键，是其他中文处理技术的基础。在我国中文分词已经被研究了三十多年，但是这仍是制约中文信息助理的瓶颈之一，它主要存在语言学和计算机科学等两方面的困难1。对于语言学方面的内容1.2 中文分词的现状最早的中文分词方法是由北京航空航天大学的梁南元教授提出的一种基于“查字典”分词方法。该方法的思想事把整个中文句子，读一遍，然后把字典里有的词都单独标示出来，当遇到复合词的时候，（例如石家庄经济学院），就找到最长的词匹配，遇到不认识的字符串就分割成单个文字。这种分词方法效率并不高，但它的提出为中文分词技术奠定了基础。在接下来的近30年的研究中，许多研究者实现了中文分词基于词典和基于概率统计的

9、很多算法。现在中文分词的算法主要包括对于中文分词的研究主要有基于词典的分词方法，基于统计的分词方法，基于理解的分词方法等。其中基于词典的分词方法是当今的主流，可以说现在出现的分词系统，很多都是在基于词典的基础上再结合另外的一种或两种方法而成的。基于词典的分词方法又称机械分词方法，主要包括最大正向匹配，最大逆向匹配，最少切分法等。不仅对于算法的研究，目前国内已有许多分词系统相继开发完成。文2对现在的各个 - 1 -分词系统及其特点做了阐述如下：SCWSHightman开发的一套基于词频词典的机械中文分词引擎，它能将一整段的汉字基本正确的切分成词。采用的是采集的词频词典，并辅以一定的专有名称，人名

10、，地名，数字年代等规则识别来达到基本分词，经小范围测试大概准确率在 90% 95% 之间，已能基本满足一些小型搜索引擎、关键字提取等场合运用。45Kb左右的文本切词时间是0.026秒，大概是1.5MB文本/秒，支持PHP4和PHP 5。ICTCLAS这是最早的中文开源分词项目之一，ICTCLAS在国高效率：在PIII 1G采用基于 不限制个数 的词典文件对文章进行有效切分，使能够将对词汇分类定义。 能够对未知的词汇进行合理解析 仅支持Java语言。MMSEG4JMMSEG4J基于Java的开源中文分词组件，提供lucene和solr 接口 1、mmseg4j 用 Chih-Hao Tsai 的

11、 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 字符每秒

12、准确：盘古分词采用字典和统计结合的分词算法，分词准确率较高。 功能：盘古分词提供中文人名识别，简繁混合分词，多元分词，英文词根化，强制一元分词，词频优先分词，停用词过滤，英文专名提取等一系列功能。1.3 （1）对于词典在内存中的组织，（2）（3）1.4 课题任务和论文结构中文分词是自然语言信息处理的基础性课题之一。 - 3 -2 中文分词简介中文分词是中文信息处理的基础，也是中文信息处理的关键，中文分词，通俗的讲就是由机器在中文文本中词与词之间自动加上空格。一提到中文分词，就会有两类人对此产生质疑，一类人是外行，对此技术不是很了解，认为中文分词很简单，另一种来自圈内人，也可以讲是行家，虽然中文

13、分词已经研究了将近三十年，可是到现在为止并没有退出一个很好的中文分词系统，中文分词这个难题到底还能不能解决。无论是哪一方面的质疑，中文分词的研究不能放弃，因为这是中国计算机发展的关键，是其它中文信息处理的瓶颈，本章主要对中文分词进行了介绍。2.1 中文分词问题描述在信息检索、语音识别、机器翻译等技术领域中通常需要理解中文的每一句话，也就是要理解每一句话里的每个词，从而来进行相应的操作，但这需要将每一个词从句子里单独切分出来，这就是中文分词技术。用一个专业性的描述就是中文分词系统的输入是连续的字符串（A1A2A3A4A5A6A7）是由字组成的中文句子(其中An是字)，通过中文分词处理得到的字符串

14、是B1B2B3B4,其中Bi是由单个字或多个字组成的词。由于中文对于词的界限不是很清晰，如何分词，什么样的叫做词，都需要一个专业的词库来进行区分，可是遗憾的事到目前为止，并没有在这样一个词库，因此我们进行在这里进行的工作是尽可能的寻找一个标准化的词库，来帮助我们界定词的界限。中文分词有两大基本问题，也是中文分词的难点，一是歧义识别问题，二是未登录词问题，本节简要介绍下这两类问题，有关这两类问题的详细介绍请参考2.2。第一个问题是歧义识别的问题，由于中文自身的特点，对于中文中的一句话不同的划分可能有不同的意思，例如，“乒乓球拍卖完了”，这句话可以划分成“乒乓球/拍卖完了”，也可以划分成“乒乓球拍

15、/卖完了”。虽然到现在为止没有出线一个百分百的消除歧义的算法，但是已经出现了许多比较好的，且具有实际应用价值的算法。第二个是未登录词的问题，未登录词又称为新词，因为语言在不断的发展和变化导致新词的不断出现，同时词的衍生现象非常普遍，所以词表中不能囊括所有的词。最典型的是人名，例如在句子“李军虎去上海”中，人可以很容易理解“李军虎”作为一个人名是个词，但计算机识别就困难了。如果把“李军虎”作为一个词收录到字典中去，全世界有那么多名字，而且时时都有新增的人名，如此一项巨大的工程即使可以完成，问题仍旧存在。例如:在句子“李军虎背熊腰的”中，“李军虎”又算词吗?新词中除了人名以外，还有机构名、地名、产

16、品名、商标名、简称、省略语等这些人们经常使用的词都是很难处理的问题，因此在信息搜索中，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一3。2.2 中文分词难点分析中文分词研究了近三十年，虽然已经取得了一些成就，但是中文分词的基础性问题，也是关键性问题并没有解决即歧义识别问题和未登录词的识别问题。下面详细讲述这两大基本问题并讲述已有的解决办法。- 4 - 2.2.1 切分歧义及其处理方法（1）常见歧义类型在中文中存在着很多的歧义切分字段，典型的歧义有交集型歧义（约占全部歧义的85%以上）和组合型歧义4。交集型歧义是这样一种歧义：汉字串AJB被称作交集型切

17、分歧义，如果满足AJ、JB同时为词（A、J、B分别为汉字串）。此时汉字串J被称作交集串4。 例如：高兴/奋 和高/兴奋，其中“兴”就是交集串。组合型歧义是这样一种歧义：汉字串AB被称作多义组合型切分歧义，如果满足A、B、AB同时为词4。 而在我们分词的过程中我们会遇到以下三种歧义的问题：1）由自然语言的二义性产生的歧义是第一种歧义问题。例如：乒乓球拍卖完了，可以划分成“乒乓球/拍卖完了”，也可以划分成“乒乓球拍/卖完了”。这类歧义是自然语言的二义性而出现的，此类歧义问题无论如何划分都能够说的通，只有结合上下文才能得到正确的划分。2）第二类歧义问题是由机器自动分词出现的，这类分词只有一种正确的分

18、词方法，但因为分词采用的分词算法不同而出现不同的分词结果，例如对于这句话“这时候最热闹的”，如果采用最大正向匹配的算法就是“这时候/最热/闹/的”，而如果采用最大逆向匹配就是“这时候/最/热闹/的 ”。对于本句来说只有第二句才是正确的切分，如果对于人工分词来说这是不会出现的歧义。3）第三类问题就是由于词典的大小，对于专业名词，人名地名等不包含出现的歧义，例如“张芳明是个好学生”，在这里“张芳明”是个人名，是一个词，但是如果在分词词典里不包含“张芳明”这个人名，那么就会出现“张/芳/明”这样错误的切分结果。对于这种歧义，只要字典足够大就可以解决，但是我们不可能也没有必要包含所有的人名地名，因此对

19、词汇进行分类，从而对于某一行业的词用专业词典来切分是一个很好的解决方法。（2）常见消除歧义算法5不同的研究中它们的歧义消除方法也不同。一个经过表明简单有效的方法是最大匹配算法，最大匹配算法可以有多种形式。1）简单最大匹配算法。其基本形式是解析单个单词的歧义性，例如，假设C1,C2,.代表一个字符串中的汉字。我们首先位于字符串的开头并想知道如何区分单词。我们首先搜索词典，看 _C1_是否为一个单个汉字组成的单词，然后搜索 _C1C2_来看是否为一个两个汉字组成的单词，以下类推。直至找到字典中最长的匹配。最可能的单词就是最长的匹配。我们取这个单词，然后继续这个过程直至字符串中的最后一个单词被识别出

20、来。2）复杂最大匹配算法。另一种最大匹配算法比基本的形式更为复杂。他们的最大匹配规则指出，最可能的分词方案是三个单词，再次，我们从一个字符串的头部开始，寻找分词的方案。如果存在有歧义的分词（例如，_C1_是一个单词，但是_C1C2_也是一个单词，等等），然后我们向前再看两个单词去寻找所有可能的以 _C1_ 或者 _C1C2_ 开头的三词chunks。例如,如果有一个可能的三词chunks：_C1_ _C2_ _C3C4_C1C2_ _C3C4_ _C5_C1C2_ _C3C4_ _C5C最大长度的chunk是第三个。第一个单词，在第三个chunk中的_C1C2_，会被认为是正确的。我们接受这个

21、词，并向前重复这个过程从汉字C3，直到字符串的最后一个词被识别。除了最 - 5 -大匹配算法，许多其它消除歧义的算法也已经被得出。在消除歧义的过程中使用了各种各样的信息，例如，概率和统计，语法，还有词语形态学，它们当中的大部份需要一个构建良好，拥有汉字和词组频率信息的字典，单词的语法分类，以及一个语法或形态学的集合（例如，汉语知识信息处理小组）。虽然有各种各样的消除歧义的算法，但是到目前为止并没有一种十分完美的消除歧义的算法。2.2.2 未登录词及其处理方法未登录词大致包含两大类：1）新涌现的通用词或专业术语等；2）专有名词，如中国人名、外国译名、地名、机构名（泛指机关、团体和其它企事业单位）

22、等。前一种未登录词理论上是可预期的，能够人工预先添加到词表中（但这也只是理想状态，在真实环境下并不易做到）；后一种未登录词则完全不可预期，无论词表多么庞大，也无法囊括4。 未登录词的处理是中文分词的一大难题，对于歧义识别问题中出现的第一种，我们只有拥有庞大的上下文资料才能处理，而对于第二种歧义问题，目前已经出现了许多消除歧义的算法，第三种歧义问题实际上就是未登录词导致的歧义，对于现有的词典来说，所有不在词典里的词语可以说都是未登录词。对于未登录词，将未登录词进行分类，让用户自己选择自己需要的专业词汇，这是一种很人性化的解决办法。2.3 主要的分词算法从开始研究中文分词算法到现在，虽然没有出现非

23、常完美的分词算法，但是也还是出现了许多比较好的分词算法，目前的分词算法主要包含基于字典的分词算法，基于统计的分词算法和基于理解的分词算法，下面简要介绍一下这些算法。2.3.1 基于字典的分词算法基于字典的分词算法又叫机械分词算法，这种方法按照一定策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功(识别出一个词)。根据扫描方向的不同分为正向匹配和逆向匹配;根据不同长度优先匹配的情况，分为最大(最长)匹配和最小(最短)匹配;根据与词性标注过程是否相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的方法如下3:正向最大匹配法(Maxi

24、mum Matching Method)通常简称为MM法。其基本思想为:设D为 词典，MAX表示D中的最大词长，string 为待切分的字串。MM法是每次从string中取长度为MAX的子串与D中的词进行匹配。若成功，则该子串为词，指针后移MAX个汉字后继续匹配，否则子串逐次减一进行匹配。逆向最大匹配法(Reverse Maximum Matching Method)通常简称为RMM法。RMM法的 基本原理与MM法相同，不同的是分词的扫描方向，它是从右至左取子串进行匹配。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245，显然RMM法在切分的准确率

25、上比MM法有很大提高。基于词典的分词算法，对于在词典中的词分词的精确度很高，但是不能很好的解决歧义问题，经常和其它分词算法结合在一起应用。2.3.2 基于统计的分词算法6该方法的主要思想：词是稳定的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻出现的概率或频率能较好反映成词的可信度。可以对训练文本中相邻出现的各个字的组合的频度进行统计，计算它们之间的互现信息。互现信 - 6 -息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可以认为此字组可能构成了一个词。该方法又称为无字典分词。该方法所应用的主要的统计模型有：N元文法模型、隐Marko

26、v 模型和最大熵模型等。在实际应用中一般是将其与基于词典的分词方法结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。2.3.3 基于理解的分词算法该方法又称基于人工智能的分词方法，其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统和总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。目前基于理解的分词方法主要有专家系统分词法和神经网络分词法

27、等。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。2.3.4 小结无论是哪一种分词算法都不是完美的，都有各自的优缺点：基于词典的分词算法的优点是简单，易于实现，缺点是匹配速度慢，不能很好的解决歧义问题，并且也不能很好的解决未登录词的问题；基于统计的分词算法的优点是可以发现所有的歧义切分，缺点是统计语言的精度和决策算法在很大程度上决定了解决歧义的方法，并且速度较慢，需要一个长期的学习过程才能达到一定的程度；由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段

28、。 - 7 -3 双向匹配算法和子字典机制通过第二章对中文分词的简介，我们知道在现有中文分词算法中，没有一个是百分之百完美的算法，3.1双向匹配算法双向匹配算法简要说来就是对待切分的文字分别进行最大正向匹配和最大逆向匹配，然后在此基础上对切分结果进行比较，然后根据不同的结果采用不同的分词策略。首先，本小节先介绍最大正向匹配和最大逆向匹配，在两者的基础上介绍双向匹配算法。3.11最大正向匹配算法（MM）最大正向匹配算法的算法思想是：设D为词典，MAX表示算法采用的最大词长，string 为待切分的字串。MM法是每次从string中取长度为MAX的子串与D中的词进行匹配。若成功，则该子串为词，指针

29、后移MAX个汉字后继续匹配，否则子串逐次减一进行匹配。我们在具体实现时提出了一种改进算法，经典的算法在实现的时候，最大长度词MAX是人工定的，这种方法由于不科学且因为个人的原因造成分词系统的不准确，我们在这里将最大长度词由程序自己获取，从子字典的最大长度来得到最大匹配的长度。根据算法的具体的思想，我们能够很清楚的得到MM算法的流程：1）输入经过预处理后的待切分的句子,并初始化Index = 0；2）获得字典数据库内各个子字典的长度；3）获得分词单词的长度，并和字典数据库内最长的子字典比较，如果子字典的最大长度大于要分词的长度，则取剩于要分词的字符串为最大长度，否则则以最大长度切分；4）用二分法

30、查找与当前最大匹配长度相同的子字典，如果找到该字典则转5，否则最大长度减一转4；5）取得要分词的字符串SubStr，在字典里找该字符串，如果找到则将该字符串添加到List内，如果没有找到则判断SubStr是否大于1，如果大于1，则删除SubStr最后一个字转5，否则置切分标志，转6；6)判断Index是否小于STR，如果小于则转3否则保存List,退出。具体的算法流程如图3-1。 - 8 - 图3-1最大正向匹配算法 - 9 - 3.12 最大逆向匹配算法（RMM）最大逆向匹配算法的算法思想是：最大逆向匹配的算法跟最大正向匹配类似，不同的是扫描的方向，它是从右往左取子串进行匹配。根据算法的具体

31、的思想，我们能够很清楚的得到MM算法的流程：1)输入经过预处理后的待切分的句子STR,并初始化Index = STR.Length；2)获得字典数据库内各个子字典的长度；3)获得分词单词的长度，并和字典数据库内最长的子字典比较，如果子字典的最大长度大于要分词的长度，则取剩于要分词的字符串为最大长度，否则则以最大长度切分；4)用二分法查找与当前最大匹配长度相同的子字典，如果找到该字典则转5，否则最大长度减一转4；5)取得要分词的字符串SubStr，在字典里找该字符串，如果找到则将该字符串添加到List内，如果没有找到则判断SubStr是否大于1，如果大于1，则删除SubStr最后一个字转5，否则

32、置切分标志，转6；6)判断Index是否大于1，如果小于则转3否则保存List,退出。具体的算法流程如图3-2。 - 10 - 3.13 双向匹配算法（DMM）双向匹配算法的算法思想是：将正向匹配与逆向匹配算法相结合起来，对于待分字符串，首先分别用最大正向匹配和最大逆向匹配算法进行分词，对于分词结果进行比较， 比较正向和反向两个最大匹配，返回分词结果，当两个方向的分词结果一致，返回字符串，当不一致，返回长度小的，当长度一致，返回反向的。这是因为统计表明，统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245，显然RMM法在切分2的准确率上比MM法有很大

33、提高。同时本算法可以分别打出正向分词和逆向分词的结果供用户实验，还能够发现出现歧义的地方，从而为将来升级系统，消除歧义打下了良好的基础。 双向匹配算法的算法步骤如下：1）输入待切分的句子String；2）对String 进行预处理后分别用最大正向匹配算法和最大逆向匹配算法进行分词，对分词结果进行比较，如果分词结果完全相同则转3，如果分词结果不同则转4；3）任意选出一种分词结果，将分词结果输出算法结束；4）比较分词数目是否相同，如果相同则选取逆向分词结果，将分词结果输出，算法结束，否则选取分词数目较小的分词结果进行输出，算法结束。双向匹配的算法流程如图3-3。 - 12 - 图3-3双向匹配算法

34、3.2 基于词典的分词算法的词典机制基于词典的中文分词很大一部分上的效率取决于词典的选择，所以分词的词典设计是中文分词系统工程开发中一个重要基础部分。因为实际中文分词系统需要在词典中反复查找所需词汇，所以如何设计出高效、易于维护的词典存储，对整个分词系统的速度有很大影响。在实际工程中，时间和空间总是相互矛盾的，即很难找到一种既占用内存小同时速度很快的算法。经过30多年无数研究者的努力，提出了很多的中文词典机制。目前最常用的词典机制 - 13 -主要有：基于Trie索引树的词典、基于整词二分法的词典和逐字二分法的分词词典机制。下面首先介绍下着几类词典机制，然后再讲述本系统采用的词典机制。3.2.

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

36、维护也简单易行但由于采用全词匹配的查询过程效率较为较低。3.2.2 基于Trie 索引树的词典7 - 14 - 图3-5 基于TRIE索引树的词典机制如图3-5所示，基于TRIE索引树的分词词典机制由首字散列表和TRIE索引树结点两部分组成。TRIE索引树的优点是在对被切分语句的一次扫描过程中，不需预知待查询词的长度，沿着树链逐字匹配即可；缺点是它的构造和维护比较复杂，而且都是单词树枝(一条树枝仅代表个词)，浪费了一定的空间。3.2.3 基于逐字二分法的分词词典7这种词典机制是前两种机制的一种改进方案。逐字二分与整词二分的词典结构完全一 样，只是查询过程有所区别：逐字二分吸收了TRIE索引树的

37、查询优势，即采用的是“逐字匹 配”，而不是整词二分的“全词匹配”，这就一定程度地提高了匹配的效率。但由于采用的仍是整词二分的词典结构，使效率的提高受到很大的局限。 3.2.4 - 15 - n词长 图3-6 基于子字典的分词机制 单词 2词长 3词长 3.3 小结本章主要讲解了双向匹配的算法思想和算法流程，双向匹配是建立在传统的单向匹配的算法基础上，同时吸取了最大正向匹配和最大逆向匹配算法的优点，同时双向匹配对于发现歧义有一定的优势，对于将来研究消除歧义的算法打下了良好的基础。本章还讲解了基于词典的分词算法的分词机制，由于基于词典的分词机制是建立在“查字典”的基础上，因此，字典在内存中如何存储

38、，这在很大程度上影响了分词的效率， - 16 -4 中文分词系统的设计与实现在综合了上面讨论的中文分词技术和具体的算法思想的情况下，由于设计和实现是纯工程性问题，下面将详细讨论这个部分，并附带了字典在计算机内存中的存储数据结构，在第五章对该系统的分词进行了实验验证，实验显示该系统具有较高可行性。4.1 系统设计与原则中文分词系统的设计原则包含三个方面：精确性、高效性和可维护性，分别描述如下：1） 精确性：精确性是最能反映出中文分词系统好坏的核心标准。由于中文本身语言的复杂性，对于中文分词本身所遇到的切分歧义问题、未登录词做到没有错位完全实现几乎是不可能的。所以，如何在现有研究基础上，尽可能的提

39、高分词的精确度是至关重要的。2）高效性：高效性是反映中文分词系统性能的一项重要指标。由于大多数分词系统是基于词典的，在分词系统过程中需要对对中文语句进行反复的匹配，查找，对计算机而言时间消耗也是一个不小的问题。所以尽可能的提高分词的速度也是我们设计需要遵循的原则之一。3）可维护性：任何系统必须具有较好的可维护性，中文分词系统也是一样，由于是基于词典的中文分词系统，所以词典的选择应该具有灵活性，在用户想要更换词典的时候应该具有良好的接口，从而使分词系统更加完善，更加具有实用性8。4.2 中文分词系统的设计本中文分词系统分为四个功能模块：词典加载模块，预处理模块，中文分词模块和分词结果保存模块。其结构如图4-1所示。 - 17 - 图4-1 中文分词系统 1）词典加载模块：在进行分词时面对的是不同长度的词，2）预处理模块：这个功能模块的作用是对输入的待切分文档进行预处理，识别出明显的非中文字符，例如英文，数字等，从而消除了一部分歧义的产生。具体的流程是对输入的文本进行预处理，在进行分词前，先进行字符检查,检查是否是有效字符,比如是否是中文,英文字符等,包括全角和半角等