《毕业设计（论文）基于规则的分词算法研究与设计.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于规则的分词算法研究与设计.doc（40页珍藏版）》请在三一办公上搜索。
1、基于规则的分词算法研究与设计摘要：中文作为人类沟通交流、传递信息的主要语言工具之一，那么中文信息的处理在信息领域就显得非常重要。中文分词是中文信息处理的基本也是最重要的组成部分之一，它的成功与否直接关系到中文信息处理领域能否取得重大突破。中文分词是将中文的一段话或者一句话切分成一个一个单独的词，由于中文的词典没有明确规定词的定义，不像英文的单词之间有明确的分隔符，因此要实现中文的准确分词要比英文分词复杂得多也困难得多。目前，主要的分词算法有这么一些：正向最大匹配算法（MM）、逆向最大匹配算法（RMM）、最小切分算法、最佳匹配算法等。本文先对一些常用的经典算法进行了分析与研究，然后根据任务要求，
2、设计了一个简单的分词系统。系统主要分为三个部分：词典构造与载入、匹配词语、输出结果。本系统做出的改进有：减少了中文标点符号所引起的分词歧义；词典存储采用容器方式调入内存，提高分词效率。关键字：中文分词；词典；最大匹配Researching and Designing of Words Segmentation Algorithm based on RulesAbstract:Chinese as one of the main language tools for human communication and communicate information, so Chinese infor
3、mation processing in the information field is very important. The Chinese word segmentation is the basic and one of the most important part of Chinese information processing, the success directly related to Chinese information processing field can get significant breakthrough. The Chinese word segme
4、ntation is a passage into Chinese or words cut into a single word, since Chinese dictionary definition of the word did not make clear a regulation, dont like English words have clear between separator, so to achieve Chinese word segmentation of accurate than English word segmentation is much more co
5、mplex and much more difficult. At present, the main parting-words arithmetic has few:maximal matching algorithm, reverse maximal matching algorithm, minimum segmentation algorithm, optimal matching algorithm and so on. This paper first to some common classical algorithms are analyzed and studied, ac
6、cording to the mission requirements, design a simple word segmentation system. System can be divided into three parts: dictionary structure and load, matching words, output the results. This system has made improvements: reduce caused Chinese punctuation word segmentation ambiguity; dictionary by a
7、gelatinous memory storage containers way, improve efficiency .Keyword: Chinese word segmentation, dictionary, maximal matching algorithm目 录第1章 绪论11.1 课题背景11.2 研究目的与意义21.3 课题内容31.4 论文结构3第2章 中文分词概述42.1 中文分词的概念42.1.1 中文词的特点42.1.2 什么是中文分词42.1.3 为什么要进行中文分词52.2 中文分词技术发展现状52.2.1 主要分词技术52.2.2 分词难点研究62.2.3 目
8、前主要的分词系统82.2.4 常用分词算法的研究92.3 中文分词技术的应用112.3.1 在中文搜索引擎的应用112.3.2 在中文信息检索的应用122.3.3 在汉语拼音输入法中的应用122.3.4 在中外文对译中的应用122.3.5 在问题答疑系统中的应用12第3章 需求及功能分析133.1 需求分析133.1.1 词典组织模块133.1.2 切分词语模块133.1.3 反馈结果模块143.2 功能分析143.3 程序框架分析153.4 技术难点分析163.4.1 词典的组织与装载173.4.2 分词的效率与准确率173.4.3 区分英文字母和数字183.4.4 消除标点符号18第4章
9、系统设计与实现204.1 系统开发工具204.2 用户界面设计204.3 详细设计214.3.1 词典装载214.3.2 区分非汉字字符234.3.3 去除标点254.3.4 查找匹配分词27第5章 系统测试295.1 测试环境295.2 测试例子295.3 测试结论33结 论34致 谢35参考文献36第1章 绪论1.1 课题背景随着计算机技术的迅猛发展，计算机在数字处理和运算方面的成就都已有目共睹。相比这些领域的应用，在中文处理方面，无论发展程度还是实用程度都相对滞后。从研究现状来看，中文理解和处理的理论体系仍未在真正意义上建立，技术手段仍然比较单。中文作为人类思想感情最基本、最直接、最自然
10、的表达方式，是人类社会中最常用的交流工具。中文处理的研究范围极为广泛，是一门集认知科学、计算机科学、语言学、数学与逻辑学、心里学等众多科学于一身的交叉学科。不仅涉及语言学本身，而且包括了人脑对语言处理的机理，语言习得的过程，还包括了语言知识的表达方式与现实世界的关系等内容。所以，中文处理是计算机信息科学研究领域中的一项不可缺少的重要内容，它具有重大的科学意义和实用价值1。随着信息爆炸时代的到来，互联网上充斥大量各种各样的信息。可供用户检索的信息越来越多，用户在享受到大量信息资源的同时，也越来越被检索到的庞大信息所淹没，不能很快地找到自己所需要的信息，同时排除垃圾信息的工作也越来越复杂，导致人们
11、的工作效率低下。如何能在浩瀚的信息中快速准确地找到自己所需要的信息已成为当今信息处理领域的一个重大课题。这么庞大的信息用人工处理的方法现在肯定是行不通的，因此需要借助计算机高效的运算速度帮助人们实现自动化地处理这些信息。目前，出现了许多如中文文本自动摘要、自动分类、信息自动检索、自动提取等中文处理技术。这些技术中，提取关键词成为了它们的主要也是基础工作之一，而提取关键词就要涉及到把语句进行切分。切分语句即为分词，即把整句话分割成以字或者词为单位的语义单元2。但由于中文词语的多变性，与不确定性，所以中文语言不是计算机所能准确理解的。实际上，以目前的计算机水平来看，要百分之分准确理解中文词语那是不
12、现实的，但现在很多技术都需要用计算机来处理中文语句，这本来就相互矛盾的。一方面人们为了提高速度不得不采用计算机，另一方面由于计算机对中文处理的准确率不高，人们又要避免用计算机来处理信息。如何从这两者之间取得一个平衡点，值得人们去思考与研究。分词技术作为中文处理的基础环节，同时也是关键环节之一，它的质量好坏直接影响后续处理步骤的效果。其中，中文分词由于中文结构的特点，与西方国家文字相比更难于处理汉语的词汇与词汇之间没有明显的边界，汉语的分词需要通过计算机对汉语的音、形、义进行处理3，来达到切分词汇的目的。中文分词已成为计算机处理汉语面临的首要基础性工作。只有提高中文分词系统的准确率和工作效率，才
13、能使中文处理系统稳定高效地工作。中国五千年的文化积累，文字和词语经过这么多年的发展，早已经形成了一个庞大而复杂的体系。计算机在处理中文上与西方语言不同，总是会遇到很多困难：中文不像西方文字那样有空格这个明显的分隔符；中文的同义词、同音字、多音字非常多，所以中文一个词的用法非常多，在某一句话中它是一个词，但在另一句话中它就是两个分开的字，如“爱好”这个词，它在“我的爱好是看书”这句话中就是一个词，而在“我喜爱好的衣服”这句话中它根据人们的正常理解它就是两个单独的字，这就造成了计算机在识别词语上产生了重大分歧；由于中文有大量的虚词、助词的存在，造成了中文词语的可变性，如“快乐”可以变形成为“很快乐
14、”、“快快乐乐”，这样无形中更是加大了计算机对中文智能识别的困难。此外，不仅仅是中文，同样是亚洲语言的韩文、日文等这些用UNICODE编码的文字语言也存在着同样的问题4，所以分词技术作为一个具有普遍重大意义的课题，得到了越来也多学者的关注。1.2 研究目的与意义汉语语言理解有着极其广泛的应用价值，在人机接口、问答系统、机器翻译等众多的应用领域中，对输入文本进行句法分析是一项必不可少的处理任务。计算机从事句法分析所凭借的语法信息不外乎来自机器词典和句法规则库。机器词典收录了每个词条的语法、句法和语义知识，而句法规则一般来讲是在词类等知识基础上构造的。因此，对汉语句子必须先进行词语切分处理，才有可
15、能进行句法分析。如果对输入的源文件中的句子未经分词处理，仍然是一些字符串序列，就无法根据句子中出现的每个具体的词到机器词典中去查找相应的语言知识；而且如果不知道每个具体词的词性等词汇知识，也就不可能直接调用相关的句法规则来判断句子的句法结构。目前，许多分词方法已经得到实现，有些比较先进的方法还在进一步的研究与改善之中。中文信息处理在我国现代信息化建设中扮演的角色也越来越重要，经过几十年学者的不断探索与研究，取得了很显著的成果。不过，中文分词到现在任然制约着中文信息处理的发展。1.3 课题内容本课题针对现有分词系统的优缺点，即时准确的掌握分词系统的发展现状和工作原理，并在分析分词算法的基础上自主
16、地实现了一个初步的分词系统，通过实践来发现问题，优化系统。力图通过良好的数据存储与组织方式来实现一个词典比较全面，又比较快速的分词系统。1.4 论文结构论文主要研究了汉语自动分词系统的设计与实现，从目前中文搜索引擎的发展现状出发，引出中文搜索引擎的关键技术汉语自动分词系统的设计。第一章 绪论部分，介绍了该课题的研究背景与研究的目的与意义。第二章 中文分词概述部分，首先介绍了中文词组的特点；其次介绍了现在主要的分词技术与分词系统，并且对现有的常见分词算法进行了分析；最后介绍了分词技术的应用。第三章 需求及功能分析部分，首先从用户角度出发，分析了分词系统的结构与实现目标；然后从设计者的角度来看，对
17、分词系统的功能、框架以及设计技术难点进行了分析。第四章 系统设计与实现部分，对系统进行了详细的设计，提出先去标点再进行分词的办法，以及消除标点去掉后所引起的歧义问题的解决方案，实现人机交互界面。第五章 系统测试部分，选取中文语句对该系统进行测试，分析测试结果。第2章 中文分词概述2.1 中文分词的概念2.1.1 中文词的特点中文句子的基本单位是字而不是词，但理解一个句子的单位却是词。字组成了词，由词组成了句子才使得一个句子有意义。但分词中的词与语言学中说的词有一定的区别：分词中所说的词，是指一个分词单位。分词单位包含了语言学中的词。信息处理用现代汉语分词规范中，对词的定义是：最小的能独立运用的
18、语言单位。对分词单位的定义是：汉语信息处理使用的、具有确定的语义或语法功能的基本单位。它包括本规范的规则限定的词和词组。然而，并不是所有的研究人员都按照信息处理用现代汉语分词规范来进行中文分词。在词的问题上，没有一个统一的标准。中文词的最大特点是中文构成词的能力非常强大，中文词的集合是一个开放集。一个汉字可以和很多汉字组成词，比如“瓶”：有奶瓶、花瓶、醋瓶、酒瓶、啤酒瓶、酱油瓶、氧气瓶、液化气瓶、玻璃瓶、塑料瓶等等；又如“子”：有瓶子、袋子、盒子、叶子、绳子、牌子、桌子、椅子、窗子，儿子，老子，孔子，孙子等等。在GB2312汉字集的6763个汉字里，不能与其他字组成词的约有两千多，而其它的汉字
19、，有的汉字能与其他汉字组成几百个词。汉字词主要是二字词、三字词、四字词等组成，这三类词组成了汉字词的绝大部分，其中以二字词最为多。2.1.2 什么是中文分词简单地说，分词就是将连续的字（词）序列按照一定的规范重新组合成词序列的过程。信息处理用现代汉语分词规范中对分词的定义是：从信息处理需要出发，按照特定的规范，对汉语按分词单位进行划分的过程。对于英文分词，只要简单地以空格为分界符就能很好地把句子分析出来。这是由于英文是以词为单位的。不同于英文，计算机对中文分词时，由于中文句子中词与词之间是没有空格的，而且，两个字组合起来看似是一个词在句子中未必是一个词，所以计算机想要识别出中文句子中的词，就必
20、须采用不同于英文分词的新技术。例如，英文句子“I like football”，用中文则为：“我喜欢足球”。计算机可以很简单通过空格知道football是一个单词，但是不能很容易明白“足”、“球”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。我是一个学生，分词的结果是：我喜欢足球。2.1.3 为什么要进行中文分词由于中文文本的字与字之间的连续性，即汉语文本中词与词之间却没有明确的分隔标记，计算机无法识别出中文文本中哪些汉字串组合成词，导致处理中文信息无法直接理解中文的意义。所以，中文信息处理就必须比西文信息处理多了中文分词这一基本的步骤。汉语的中文
21、信息处理就是要“用计算机对汉语的音、形、义进行处理”。而“词是最小的能够独立活动的有意义的语言成分”。显而易见，自动识别词边界，将汉字符串切分为正确的词串的汉语分词问题无疑是实现中文信息处理的各项任务的首要问题。在自然语言处理领域，国外大大领先于我国，已经做出很多卓有成效的研究，但是那些研究大多基于西文，并不是以正确切分单词为前提的。如果不能很好地完成中文分词这道工序，就不能采用这些研究成果5。2.2 中文分词技术发展现状随着汉语自动分词系统的关注度不断提高，为克服中文词汇自动切分这一难题，近10年来，语言学界、人工智能领域和情报检索界的学者们，在汉语自动分词与自动标引的研究与实践上进行了大量
22、的研究，找到了许多解决汉语分词的方法。80年代以来见诸报端的中文自动分词方法归纳起来已有22种。同时，各种分词系统也不断建立，分词系统在运行速度、准确度等方面都已经具有了研究应用的价值。以目前应用最广的机械匹配分词法为例，其分词精度能达到90左右，一些经过长期研究具有一定规模的分词系统的精度达到了95以上，如今已得到广泛应用。2.2.1 主要分词技术我们可以将现有的分词算法分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。基于字符串匹配的分词方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，
23、则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法有：正向最大匹配、逆向最大匹配、最少切分（使每一句中切出的词数最小）。 基于理解的分词方法：通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则在后续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部分。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部
24、分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。基于统计的分词方法：从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。互现信息体现了汉字之间结合关系
25、的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。目前基于统计的分词方法最常用的有隐马尔科夫、最大熵和条件随机场，条件随机场克服了隐马尔科夫的独立性假设和最大熵的局部最优的缺点，因此条件随机场是目前最流行的一种基于统计的分词方法6。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来
26、，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。2.2.2 分词难点研究在过去的十几年里, 语自动分词工作虽然也取得了很大成绩,但无论按照人的智力标准，还是同实用的需要相比较，差距还很大。我们首先需要对这一困难的各个方面有充分的认识7。1. 分词规范问题分词结果是否正确需要有一个通用、权威的分词标准来衡量。分词标准的问题实际上是汉语词与语素、词与词组的界定问题，这是汉语语法的一个基本、长期的问题。它涉及到许多方面：（1）核心词表问题：分词需要有一个核心（通用、与领域无关的）词表，凡在该词表中的词，分词时就应该切分出来。对于哪些词应当收进核心词
27、表，已提出各种收词条件，但这些条件本身难以操作，目前尚无合理的可操作的理论和标准。（2）词的变形结构问题：汉语中的动词和形容词有些可以产生变形结构，如“打游戏”、“高兴”、“找到”、“信任”可能变形成“打打游戏”、“高高兴兴”、“找没找到”、“信不信任”等。可以切分出“打打/游戏”，但“高高/兴兴”就不合理。“找/没/找到”说得过去，“信/不/信任”就说不过去了。又如大量的离合词“看书”、“打牌”等可以合理地变形为“看了一本书”、“打了一场牌”。对这些变形结构的切分缺少可操作而又合理的规范。 2.分词算法面临问题要将汉语文本的字序列切分成词的序列,即使确定了一个合适的分词标准,要实现这个标准也
28、还存在算法方面的困难：（1）未登录词识别：登录词即未包括在分词词表中但必须切分出来的词,包括各类专名(人名、地名、企业字号、商标号等)和某些术语、缩略词、新词等等。（2）切分歧义：汉语文本中含有许多歧义切分字段，典型的歧义有交集型歧义（约占全部歧义的85%以上）和组合型歧义。只有向分词系统提供进一步的语法、语义知识才有可能作出正确的决策。排除歧义常常用词频、词长、词间关系等信息比如“真正在”中，“真”作为单字词的频率大大低于“在”作为单字词的频率，即“在”常常单独使用而“真”作为单字词使用的可能性较小，所以应切成“真正/在”。有时切分歧义发生在一小段文字中，但为了排除歧义，需要看较长的一段文字
29、。如“学生会”既可能是一个名词，指一种学生组织，也可能是“学生/会”，其中“会”为“可能”或“能够”的意思。在“学生会主席”中只能是前者,在“学生会去”中只能是后者,在“学生会组织义演活动”中歧义仍然排除不了，则需要看更多的语境信息。（3）分词与理解的先后：计算机无法像人在阅读汉语文章时那样边理解边分词，而只能是先分词后理解，因为计算机理解文本的前提是识别出词、获得词的各项信息。这就是逻辑上的两难：分词要以理解为前提，而理解又是以分词为前提。由于计算机只能在对输入文本尚无理解的条件下进行分词，则任何分词系统都不可能企求百分之百的切分正确率。2.2.3 目前主要的分词系统分词系统一般作为一些应用
30、程序的一个内部功能模块，比如在线翻译系统、搜索引擎，都具有自己的分词处理系统，该系统的运行准确率将直接影响这些应用程序的性能。现在比较优秀的分词系统有8： 1.清华大学SEG分词系统此系统提供了带回溯的正向、反向、双向最大匹配法和全切分-评价切分算法，由用户来选择合适的切分算法。其特点则是带修剪的全切分-评价算法。系统考虑到了切分盲点的问题（某些字串永远不会被某种分词法匹配出来），由此提出了全切分的概念，即找出输入字串的所有可能的子串，然后利用某种评价方法从所有这些可能的子串中选出最佳子串序列作为分词结果。 2.清华大学SEGTAG系统此系统着眼于将各种各类的信息进行综合，以便最大限度地利用这
31、些信息提高切分精度。系统使用有向图来集成各种各样的信息，这些信息包括切分标志、预切分模式、其他切分单位。为了实现有限的全切分，系统对词典中的每一个重要的词都加上了切分标志，即标志“ck”或“qk”。“qk”标志表示该词可进行绝对切分，不必理会它是否产生切分歧义；“ck”标志表示该词有组合歧义，系统将对其进行全切分，即保留其所有可能的切分方式。3.国家语委文字所应用句法分析技术的汉语自动分词此分词模型考虑了句法分析在自动分词系统中的作用，以更好地解决切分歧义。切词过程考虑到了所有的切分可能，并运用汉语句法等信息从各种切分可能中选择出合理的切分结果。其过程由两步构成：一、对输入字串进行处理，得到一
32、个所有可能的切分字串的集合，即进行（不受限的）全切分；二、利用句法分析从全切分集合中将某些词选出来，由它们构成合理的词序列，还原为原输入字串。 4.北大计算语言所分词系统本系统由北京大学计算语言学研究所研制开发，属于分词和词类标注相结合的分词系统。由于将分词和词类标注结合起来，系统可利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，同时将基于规则的标注排歧与基于语料库统计模型的排歧结合起来，使规则的普遍性与灵活性得到统一，而且对未登入词的估算到达了相当高的准确率。系统的处理过程包括了自动切分和初始词性标记、切分歧义字段识别、组词和标注预处理、词性标记排歧、
33、切分和词性标注后处理等过程，系统的算法综合了多种数据组织和搜索技术，以很低的时空开销实现了高速匹配和查找，同时采用了当代计算语言学的统计方法，运用隐Markov过程进行词类标注和排歧，对算法的效率和稳固性都作了尽可能的优化。2.2.4 常用分词算法的研究目前，基于规则分词比较常用的分词方法有这么几种：最大匹配算法、逐字匹配算法、神经网络分词算法、联想回溯法、N-最段路径分词算法9。下面将逐次介绍这几种算法。1.最大匹配算法基于字符串的最大匹配，这种方法现在仍比较常用。最大匹配(Maximum Matching)分为正向和逆向两种最大匹配，正向匹配的基本思想是：假设词典中最大词条所含的汉字个数为
34、n个，取待处理字符串的前n个字作为匹配字段，查找分词词典。若词典中含有该词，则匹配成功，分出该词，然后从被比较字符串的n+1处开始再取n个字组成的字段重新在词典中匹配；如果没有匹配成功，则将这n个字组成的字段的最后一位剔除，用剩下的n一1个字组成的字段在词典中进行匹配，如此进行下去，直到切分成功为止。例如，待处理字符串为“汉字多为表意文字”，取字符串“汉语多为表”(假设比较的步长为5，本文步长step都取5)与词典进行比较，没有与之对应的词，去除“表”字，用字段“汉语多为”进行匹配，直至匹配到“汉语”为至，再取字符串“多为表意”，循环到切分出“文字”一词。目前，正向最大匹配方法作为一种基本的方
35、法已被肯定下来，但是由于错误比较大，一般不单独使用。如字符串“处理机器发生的故障”，在正向最大匹配方法中会出现歧义切分，该字符串被分为：处理机、发生、故障，但是使用逆向匹配就能得到有效的切分。逆向最大匹配(Reverse Directional Maximum Matching Method，RMM)的分词原理和过程与正向最大匹配相似，区别在于前者从文章或者句子(字串)的末尾开始切分，若不成功则减去最前面的一个字。比如对于字符串“处理机器发生的故障”，第一步，从字串的右边取长度以步长为单位的字段“发生的故障”在词典中进行匹配，匹配不成功，再取字段“生的故障”进行匹配，依次匹配，直到分出“故障”
36、一词，最终使用RMM方法切分的结果为：故障、发生、机器、处理。该方法要求配备逆序词典。2.逐字匹配算法逐字匹配算法，基于TRIE索引树的逐字匹配算法,是建立在树型词典机制上，匹配的过程是从索引树的根结点依次同步匹配待查词中的每个字，可以看成是对树某一分枝的遍历。因此，采用该算法的分词速度较快，但树的构造和维护比较复杂。一种改进的算法是和最大匹配算法相结合，吸取最大匹配算法词典结构简单、TRIE索引树算法查询速度快的优点。因此词典结构和最大匹配词典构造机制相似，区别在于词典正文前增加了多级索引。匹配过程类似TRIE索引树进行逐字匹配，在性能上和TRIE索引树相近。3.神经网络分词算法神经网络分词
37、算法，尹峰等提出了以神经网络理论(BP模型)为基础的汉语分词模型,为汉语分词研究开辟了新途径。在实用中,BP算法存在收敛速度慢、易陷入局部最小等缺点,严重妨碍了分词速度。一种改进算法采用Levenbery2Marquart 算法来加速收敛速度,加快了收敛速度利用神经网络的基本原理进行分词。4.联想回溯法联想回溯法(AssociationBacktracking Method，AB )。这种方法要求建立三个知识库特征词词库、实词词库和规则库。首先将待切分的汉字字符串序列按特征词词库分割为若干子串，子串可以是词，也可以是由几个词组合而成的词群；然后，再利用实词词库和规则库将词群再细分为词。切词时，
38、要利用一定的语法知识，建立联想机制和回溯机制。联想机制由联想网络和联想推理构成，联想网络描述每个虚词的构词能力，联想推理利用相应的联想网络来判定所描述的虚词究竟是单独成词还是作为其他词中的构词成分。回溯机制主要用于处理歧义句子的切分。联想回溯法虽然增加了算法的时间复杂度和空间复杂度，但这种方法的切词正确率较高，是一种行之有效的方法。5.N-最段路径分词算法基于N-最短路径分词算法，其基本思想是根据词典，找出字串中所有可能的词，构造词语切分有向无环图。每个词对应图中的一条有向边，并赋给相应的边长(权值)。然后针对该切分图，在起点到终点的所有路径中，求出长度值按严格升序排列(任何两个不同位置上的值
39、一定不等，下同)依次为第1，第2，第i，第N的路径集合作为相应的粗分结果集。如果两条或两条以上路径长度相等，那么他们的长度并列第 i，都要列入粗分结果集，而且不影响其他路径的排列序号，最后的粗分结果集合大小大于或等于N。N一最短路径方法实际上是最短路径方法和全切分的有机结合。该方法的出发点是尽量减少切分出来的词数，这和最短路径分词方法是完全一致的；同时又要尽可能的包含最终结果，这和全切分的思想是共通的。通过这种综合，一方面避免了最短路径分词方法大量舍弃正确结果的可能，另一方面又大大解决了全切分搜索空间过大，运行效率差的弊端。N一最短路径方法相对的不足就是粗分结果不唯一，后续过程需要处理多个粗分
40、结果。但是，对于预处理过程来讲，粗分结果的高召回率至关重要。因为低召回率就意味着没有办法再作后续的补救措施。预处理一旦出错，后续处理只能是一错再错，基本上得不到正确的最终结果。而少量的粗分结果对后续过程的运行效率影响不会太大，后续处理可以进一步优选排错，如词性标注、句法分析等10。2.3 中文分词技术的应用2.3.1 在中文搜索引擎的应用在网络上，搜索引擎必不可少。对于搜索引擎来说，首先要找到搜索结果，然后看搜索结果是否是我们所需要的。也就是说，搜索的结果一定要把那些与我们所需要的结果最相关的排在最前面。如果在中文搜索引擎中没有中文分词，那么，很多结果肯定与我们需要的信息不相关。在搜索引擎中应
41、用中文分词技术，首先要求分词技术的速度快，其次要求准确性。现有比较著名的搜索引擎的速度都很快，但搜索结果很多与我们需要的信息不相关。故而改进现在的搜索引擎技术是非常有必要的。2.3.2 在中文信息检索的应用在信息检索系统中，用户是用自然语言输入查询内容的。系统检索用户查询内容时，将查询内容分解为索引项，进行信息检索。分词技术在信息检索系统的应用在于系统的索引项实现了按词索引，在系统与用户接口上，实现了自然语言的查询。建立一个应用分词技术的中文信息检索系统，要求建立一个对不同领域有不同专业词典的通用词典，收录了各个方面的专业术语、专用词和常用词。2.3.3 在汉语拼音输入法中的应用除了专业的打字
42、员，绝大部分人在计算机输入汉字基本都用拼音输入法。若按照字来输入，显然是不可取的。汉语单字同音现象是非常严重的。以6763个汉字为例，没有同音字的汉字只有16个。其它汉字都有同音字。其中最多的有116个同音字。而汉语词的同音现象则有很大的改善。以52505的词表为例，其中35942个词语没有同音词。因此，大多数同音字可以依靠词来确定。例如：“yi”对应的同音字“以，一，易，已，意”，分别可以在“以为，一定，容易，已经，意义”中来确定。对于词语（包括单字词）的同音现象，则需要运用词语之间的合理搭配以及词语在句子中的合法运用来确定。比如“一枝可爱的玫瑰花”，“zhi”的同音字有：“只，之，直，支，
43、枝”等。但是这里“枝”是和“花”的合理搭配。也就是说“一+枝+可爱的玫瑰花”是合理的搭配。由此不难看出，分词对于同音词自动辨识的作用。2.3.4 在中外文对译中的应用这里所说的中外文对译是指机器翻译，而不是人工翻译。将中文翻译成外文，首要的条件就是分词正确，才能理解中文句子，之后才可以做出正确的翻译。否则，一切都是空谈。词性对中外文对译也非常重要。2.3.5 在问题答疑系统中的应用 问题答疑系统中，回答一个问题首先要找出关键词，然后在问题中搜索关键词来回答问题。这需要系统对问题和答案都要做出正确的切分，才能做出正确的答疑。一个优秀的自动问题回答系统不要求用户输入关键词，用户只是用自然语言提问，
44、系统能给用户返回简单标准的答案，而不是返回模糊的回答甚至不相关的答案11。第3章 需求及功能分析3.1 需求分析本次设计主要是实现对中文语句进行切分，从而把分得的词语反馈给用户。该系统主要分为词典组织、切分词语、反馈结果这三个模块。词典组织是在用户输入带切分中文文字前就应该先组织并且存储，既是该系统的预处理部分；切分词语模块是在用户输入带切分词语后才运行的，是系统核心模块；反馈结果模块是在切分词语模块运行结束后，得到切分好的词组后才运行的，是系统最后一个模块。上述过程由流程图表示为： 反馈结果输入切分文字 切分组织词典图3-1 系统模块流程图3.1.1 词典组织模块该模块是系统预处理模块，既是
45、系统在正式运行前就应该准备好的模块。如果该模块发生了错误，那么整个系统就会无法正常运行，即使能勉强运行，但是得到的结果将会是严重不准确的，更甚至会出现乱码，所以该模块即使是程序的预处理模块，但是它在整个系统模块中所占分量是不容忽视的。词典对于用户来说要便于修改，随时需要删除、添加一些特定的词汇来保证用户需求，这样就要保证词典组织结构要尽量简单，所以本次设计选用顺序存储来建立组织词典。这样用户需要删除词汇的时候只需要找到这个词汇直接删除即可，不用考虑会不会影响其他词汇的存储，需要添加词汇的时候可以在词典任意位置添加，不用担心会破坏词汇与词汇之间的联系问题。但是需要注意的是，在词典调入内存并且正在
46、使用的过程中的时候，是不允许动态修改词典的，否则会引起内存泄露，甚至系统崩溃的结果。3.1.2 切分词语模块 该模块是系统核心模块，主要对待切分语句进行分割。用户对该功能模块要求要能尽量准确地切分出汉字词汇，并且要去除标点符号，并且运行速度要尽量快。排除词典组织对该模块分词效率的影响，那么决定该模块处理运行效率的就是分词的算法。算法上由于词典是顺序存储组织的，那么适合该词典组织结构的算法就是正向最大匹配算法。可是正向最大匹配算法对于很长的语句要遍历很多次词典，才能切分完成，这样势必会影响系统整体的运行速率。考虑到一段中文文字中基本上会出现一些数字、英文字母以及标点符号，由于数字与英文字母在内存
47、中存储是只占一个字节的，而单个汉字却是占两个字节的，如果直接用正向最大匹配算法来进行切分，那么它指针每次移动的距离将会难以确定，而且又要去除标点符号，所以可以考虑先对待切分语句进行断句。遇到数字或者英文字母后，就将前面的一段中文语句保存到一个数组中，数字或者英文字母接着保存在这句话后面，以此类推，一直到把待切分语句全部都保存到数组中。然后把数组中存放的单元内容取出来再来根据标点符号来进行断句处理。如果是标点符号就将前面的一段中文文字保存到另外一个数组中，标点符号后面的一段中文文字接着保存到这个数组中，直到第一个数组中的单元内容全部取出为止。最后再用这些非常短的句子来用正向最大匹配算法进行切分。
48、这样优化算法后，分词的速率和准确率都会得到很大的提高。3.1.3 反馈结果模块该模块是整个系统的最后一个功能模块，主要功能就是把切分词语模块中得到的分词结果反馈给用户。为了用户方便，分词结果与待切分语句在同一界面上显示，分词结果中词组与词组之间用“/”间隔区分开。3.2 功能分析为实现本设计中基于规则的中文分词系统，本次设计的大体思路和大体过程如下： 1.建立比较完善的中文词典，词典的组织方式主要有顺序存储，整词二分，TRIE树二分等几种方式。词典不但要收录常用语和成语，而且还要收录一些经常出现但严格来讲不能算做词的一些短语。同时，词典不能太大，也不能太小，太大使分词消耗的时间增多，降低效率，太小则影响分词的准确率。 2.选定一个数据结构来存储词典，好的数据结构能大大降低分词所花费的时间。本次设计采用STL中的set关联容器来实现词典的存储，由于set容器的高效存储结构，使得查找变得
