（计算机应用技术专业论文）基于词典的中文分词歧义算法研究.pdf

摘要 随着计算机网络的飞速普及，人们已经进入信息时代。在这个信息社会里，信息的 重要性与日俱增，无论是个人，企业，乃至政府都需要获取，掌握大量有用的信息。在 这种环境下，中文信息处理技术逐渐成为技术人员的开发热点，而其中最为重要的就是 中文分词技术。 中文分词技术，就是指将文本中每句话，利用分词算法拆分成词，以便于计算机对 文本信息进行处理和理解的过程。它应用广泛，主要应用于信息检索，信息抽取，机器 翻译等自然语言处理技术等。同时，它包括很多方面内容，例如中文分词技术中的分词 算法研究，未登录词识别技术，分词歧义处理技术等等。其中歧义处理技术和未登录词 识别技术是中文分词技术的两大难点。而本文则是重点对中文分词技术中的分词算法和 歧义处理技术进行了深入的研究和实践。 首先，本文采用了一种典型的基于词典的中文分词算法一正向最大匹配算法，它的 思想简单，并且易于实现，但是分词的精确度和速度并不理想。针对该问题，本文采用 了双层h a s h 结构的词典机制，来提升分词的速度，同时采用改进的正向最大匹配算法 来提高分词的精确度。 其次，由于歧义处理技术是中文分词技术中的重要组成部分，只有完成了对文本的 歧义处理，才能正确的对文本进行分词。所以本文在提出改进的正向最大匹配算法的基 础上，又提出了一种基于概率和规则想结合的歧义消解算法，完成了对文本的歧义处理。 最后，本文充分考虑分词系统准确率、速度及可实现性等因素，给出了一种中文自 动分词系统的设计方案。并对该分词系统进行了实现，取得一定的分词效果。 关键词：中文分词；分词算法；歧义处理；歧义消解算法 a b s t r a c t w 砧t h er a p i dp o p u l a r i z a t i o no fc o m p u t e rn e t w o r k s ，t h ep e o p l e 出e a d ye n t e r e dt h e i n f o r m a t i o na g e i nt h ei n f o r m a t i o ns o c i e t y ，t h ei m p o r t a n c eo fi n f o r m a t i o ni si n c r e a s i n g t h e n ag r e a td e a lo fu s e f u li n f o r m a t i o nw o u l db ea c q u i r e da n dm a s t e r e d , w h o e v e ri n d i v i d u a l s ， b u s i n e s s e s , a n de v e nt h eg o v e r n m e n t i nt h i sc i r e u r n s t a n c e ，c h i n e s ei n f o r m a t i o np r o c e s s i n g t e c h n o l o g yh a sg r a d u a l l yb e c o m eh o ts p o t sf o rd e v e l o p m e n tt e c h n o l o g y o n eo ft h em o s t i m p o r t a n tt e c h n o l o g y so fc h i n e s ei n f o r m a t i o np r o c e s s i n gt e c h n o l o g y i sc h i n e s ew o r d s e g m e n t a t i o n c h i n e s ew o r ds e g m e n t a t i o nt e c h n o l o g ym e a n sap r o c e s sw h i c hu s i n gt h ec o r r e s p o n d i n g w o r ds e g m e n t a t i o na l g o r i t h mt os e p a r a t et h et e x ta n de a s i l yt od e a lw i 也a n du n d e r s t a n dt h e i n f o r m a t i o nb yc o m p u t e r i t sr a n g eo fa p p l i c a t i o n si s 谢d e ，m a i n l yu s e di ni n f o r m a t i o n r e t r i e v a l ，i n f o r m a t i o ne x t r a c t i o n , m a c h i n et r a n s l a t i o n ，n a r l l 同l a n g u a g ep r o c e s s i n gt e c h n o l o g y a n ds oo n a tt h es a m et i m e ，i ti n c l u d e sm a n ya s p e c t s ，s u c ha sc h i n e s ew o r ds e g m e n t a t i o n a l g o r i t h m ，u n k n o w nw o r dr e c o g n i t i o nt e c h n o l o g y ，a m b i g u o u sw o r dp r o c e s s i n gt e c h n o l o g y ， a n ds oo n a m b i g u o u sp r o c e s s i n gt e c h n o l o g ya n db n k l l o w nw o r dr e c o g n i t i o nt e c h n o l o g yi s t w od i f f i c u l t i e so fc h i n e s ew o r ds e g m e n t a t i o nt e c h n o l o g y i nt h i sp a p e r ，i tw i l lm a i n l ys t u d y t h ew o r ds e g m e n t a t i o na l g o r i t h ma n da m b i g u i t yp r o c e s s i n gt e c h n i q u e so fc h i n e s ew o r d s e g m e n t a t i o n f i r s t l y ，h at h i sp a p e r i tu s e dat y p i c a lc h i n e s ew o r ds e g m e n t a t i o na l g o r i t h mb a s e do n d i c t i o n a r y t h el a r g e s tf o r w a r dm a t c h i n ga l g o r i t h m n l ei d e ao fi ti ss i m p l ea n de a s yt o i m p l e m e n t ，b u tt h er e s u l to ft h es e g m e n t a t i o na c e u r a c ya n dt h es e g m e n t a t i o ns p e e ds e e m st o b en o ti d e a l f o rt h ep r o b l e m , i nt h i sp a p e r , i tu s e st h ed o u b l e h a s hs t r u c t u r ed i c t i o n a r y m e c h a n i s mf o ri m p r o v i n gt h es p e e do fw o r ds e g m e n t a t i o n , a sw e l la si nt h i sp a p e rp r o p o s e d a ni m p r o v e dl a r g e s tf o r w a r dm a t c h i n g a l g o r i t h m f o ri m p r o v i n gt h ea c c u r a c yo f s e g m e n t a t i o n s e c o n d l y ，a m b i g u i t yp r o c e s s i n gt e c h n o l o g yi so d eo ft h ei m p o r t a n tc o m p o n e n t so f c h i n e s ew o r ds e g m e n t a t i o nt e c h n o l o g y o n l yd e a l 、航mt h ea m b i g u i t yf i e l dc o m p l e t e l y i t w o u l ds e g m e n tt h et e x tc o r r e c t l y t h e r e f o r e ，i tu s e ad i s a m b i g u a t i o na l g o r i t h mc o m b i n e 埘t h p r o b a b i l i t ya n dr u l e sb e h i n dp r o p o s e dt h ei m p r o v e dl a r g e s tf o r w a r dm a t t i n ga l g o r i t h mi n o r d e rt oa c h i e v eb e t t e rs e g m e n t a t i o nr e s u l t s f i n a l l y ，w ec o n c e r nt h es y s t e mp e r f o r m a n c em e a s u r e m e n tm e t r i c s ，s u c ha sp r e c i s i o n , s p e e d ，r e a l i z a b l ea n ds oo n t h e nad e s i g no f t h ec h i n e s ew o r ds e g m e n t a t i o ns y s t e mi sg i v e n a n dt h ec h i n e s ew o r ds e g m e n t a t i o ns y s t e mi sa c h i e v e d a tt h es a m et i m e ，t h ee x p e r i m e n t r e s u l t sp r o v et h a tt h i ss y s t e ma c h i e v e sac e r t a i l ld e g r e eo fs e g m e n t a t i o ne f f e c t k e yw o r d s ：c h i n e s ew o r ds e g m e n t a t i o n ；s e g m e n t a t i o na l g o r i t h m ；a m b i g u i t yp r o c e s s i n g ； u 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究 工作所取得的成果。据我所知，除了特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明的法律结果由本人 承担。 学位论文作者签名：主q 筵名日期：一罗l 宝刀 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：趣土丝盔 日期：迎2 ：皇! 兰； 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名；子芸毖到 日期：川舅岁 电话： 邮编： 东北师范大学硕士学位论文 第一章绪论 1 1 中文分词的研究意义 随着互联网的飞速发展及需求的不断增加，大量的信息涌入了人们的生活，语言信 息处理技术的社会需求越来越大，人们迫切需要用自动化的手段处理海量的语言信息。 分词技术属于自然语言处理技术的范畴，是语义理解的首要环节，它是能将语句中的词 语正确切分开的一种技术。它是文本分类，信息检索，机器翻译，自动标引，文本的 语音输入输出等研究领域的基础吲。而不同与英文单词之间用空格分割，在中文文本中， 词与词之间没有天然的分割符，所以中文文本在自动分析前，必须先进行中文自动分词。 目前无论在自然语言处理还是在搜索引擎技术中，中文自动分词都是个重要的环 节。而由于中文本身的复杂性及汉语语言的书写习惯，使中文自动分词存在着诸多困难。 其中歧义字段的大量出现，未登录词的难以识别是中文自动分词技术中一直没有完全突 破的两大难题，也是影响中文分词系统切分精度最困难的问题。 由于未登录词数量并没有歧义字段数量巨大，而且可以人工进行统计和扩充，所以 歧义字段切分才是中文自动分词研究中的一个“拦路虎 似3 ；才是影响分词系统切分精 度的最主要因素晦3 。只有自动实现对歧义字段的正确切分，才能实现对中文文本的自动 分词；只有准确，快速的完成对歧义字段的处理，才能设计和实现良好的中文分词系统。 所以歧义处理技术是中文自动分词技术的重要组成部分，有着重大的研究意义。 1 2 中文分词的研究背景 分词是指将文本拆分成词的一种技术，中文自动分词是中文信息处理的关键所在， 因为在中文信息处理中，凡是涉及句法、语义等的研究，如机器翻译、自然语言处理， 信息检索，搜索引擎等，都要以词为基本单位。 近年来，中文分词技术在信息检索、搜索引擎、信息抽取、机器翻译、汉字的智能 输入、中外文对译、中文校对、自动摘要、自动分类、文本的语音输入输出等很多方面 都有广泛应用。例如： 在信息检索方面，由于互联网的迅猛发展，网上的信息也在急剧膨胀，在这海量的 信息中，各类信息混杂在一起，要想充分利用这些信息资源就要对它们进行整理，人工 操作，已经是不可能的。而如果不采用中文分词技术，整理的结果又过于粗糙，导致资 源的不可用。所以只有采用好的中文分词技术，才能使机器对海量信息进行准确、合理 的整理。 而在搜索引擎方面，由于搜索引擎需要在最短的时间内处理数以亿计的网页，如果 分词速度太慢，分词耗用的时间过长，会严重影响搜索引擎的速度。而同时如果分词的 准确性很低，那么搜索引擎的搜索精度会大幅度降低，对于搜索引擎来说也是不可用的。 所以对于搜索引擎来说，好的分词精确度和快速的分词速度，是必不可少的要求。 l 东北师范大学硕士学位论文 1 3 中文分词的研究现状 最早的中文分词方法是由北京航天航空大学的梁南元教授提出的一种基于“查字 典”的分词办法。该方法的思想是把整个中文句子，读一遍，然后把字典里有的词都单 独标示出来，当遇到复合词的时候( 例如北京大学) ，就找到最长的词匹配；遇到不认 识的字符串就分割成单个文字。这种分词方法效率并不高，但它的提出为中文自动分词 技术奠定了基础。 n 8 0 年代，哈尔滨工业大学计算机博士生导师王晓龙博士把中文分词方法理论化， 提出了“最少词数的分词理论，即每一句话都应该采用词数最少的切分方式。这种分 词方法是对“查字典”分词方法的改进，为中文分词技术的发展起到了推动的作用。 九十年代以前，海内外不少学者试图用一些文法规则来解决分词的二义性问题，都 不是很成功。9 0 年后，清华大学的郭进博士用统计语言模型成功解决了分词二义性问题， 将汉语分词的错误率降低了一个数量级。促进了中文分词技术的发展，开辟了中文分词 技术的新思路。 近年来，许多研究者又实现了中文分词基于词典和基于概率统计的很多算法。例如 正向最大匹配算法，逆向最大匹配算法，许多词频统计算法，许多混合算法等等；如吴 建胜阳3 等提出的基于自动机的分词方法；赵伟口3 等提出的一种规则与统计相结合的汉语 分词方法；张长利随3 等提出的一种基于后缀数组的无词典分词算法等等。还有许多学者 提出了新型的词典机制，例如t r i e 树词典机制，p a t r i c i at r e e 树词典机制，整词二分 词典机制，h a s h 结构词典机制，双层h a s h 词典机制等等。 目前，国内已有许多分词系统相继开发完成。如s c w s ( s i m p l ec h i n e s ew o r d s s e g m e n t a t i o n ) 系统即简易中文分词系统，飞嘉华公司所研制的第三代智能分词系统 3 g w s3 0 系统以及由中科院的张华平、刘群等所开发的一套获得广泛好评的分词系统一 i c t c i a s 分词系统等。每种分词系统都有各自的分词算法和相应的优缺点。 随着中国上网人数的急速增加以及中文信息服务需求的进一步提高，中文分词技术 越来越受到人们的重视，而且朝着个性化的方向发展。所有这些都为中文分词技术提出 了更高更新的要求。 我国对于中文自动分词系统的研究还处在初级阶段，虽然研究人员也提出了一些中 文分词技术的重要方法和思想，但所开发的实验系统在不同领域所达到的分词精度也不 相同。所以如何更好地达到用户需求，提高中文自动分词系统的性能，是一个需要进一步 研究的重要课题。 1 4 本文的主要研究内容及论文结构 。本文研究的是中文分词技术中的分词歧义算法，主要设计和实现了一个完整的中文 分词系统。首先概述中文分词的研究背景和现状等，并从介绍中文分词相关算法和分词 歧义相关算法入手，阐明文本所要研究的基本问题。然后着重对中文分词中分词歧义发 现算法和分词歧义消解算法进行深入地分析和探讨，最后，对本文所实现的中文分词系 2 东北师范大学硕士学位论文 统做详细的介绍。 本文针对正向最大匹配算法的优点，提出了一种改进的正向最大匹配歧义发现算法 来实现分词系统对文本中歧义字段的发现；同时又根据概率统计方法的优点和规则方法 的优点，提出了一种新的规则和概率相结合的歧义消解算法来实现分词系统对歧义字段 的消解。 全文共分为五章，基本结构如下： 第一章：简要介绍中文分词技术的相关背景、研究现状、国内外的发展情况及其研 究意义。 第二章：介绍中文分词的些相关知识，主要包括中文分词的基本算法、几种常见 的词典机制、中文分词目前的研究困难、中文分词系统的评价指标等等。 第三章：对中文分词技术中的分词歧义处理方法进行深入的研究，其中包括歧义产 生的原因、歧义字段的分类、歧义处理中几种常见的歧义发现算法、歧义处理中几种常 见的歧义消解算法、歧义处理目前的困难等相关知识。 第四章：设计一个基于词典的中文分词系统，主要分为四个模块，分别为预处理模 块、分词模块、歧义发现模块和歧义消解模块，并对其主要实现方案进行详细的阐述， 最后进行系统实现及结果分析。 第五章：在论文的最后，对全文进行总结，并提出未来的研究工作方向。 3 东北师范大学硕士学位论文 第二章中文分词相关算法 2 1 中文分词算法概述 近年来人们对中文分词技术有了一定的研究，提出了多种多样的分词算法。目前的 中文分词算法主要分为三大类：基于词典的分词算法，基于统计的分词算法和基于规则 的分词算法。这三类算法分别代表了中文分词算法的三个发展方向。 2 1 1 基于词典的分词算法 基于词典的分词算法又叫做机械匹配算法，最早是在5 0 年代末提出来的，主要思 想是基于字符串匹配的机械分词，即按照一定的策略将待分词的汉字串与一个“充分大 的分词词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功，即识别出 一个词。 机械分词有三个基本要素：分词词典、文本扫描方向( 正向，逆向) 、匹配原则( 最 大匹配，最小匹配，逐词匹配等) 。因此根据文本扫描的方向和匹配原则，可以分为正 向最大匹配阳3 、逆向最大匹配n 们、逐词匹配n 、最少切分、全切分等匹配方法。而在实 际应用中，常常将上述方法结合起来。 ( 1 ) 正向最大匹配算法 正向最大匹配算法是最基本的机械匹配算法之一，它的基本思想是 a ) 从左往右取不超过词典最大长度的汉字作为匹配字段； b ) 查询词典并进行匹配，若能匹配，则将这个匹配字段作为一个词切分出来； c ) 若不能匹配，则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的 匹配字段，进行再次匹配； d ) 循环操作，直到匹配字段字数为零为止； e ) 重复正向最大匹配过程，直到切分出所有词为止。 ( 2 ) 逆向最大匹配算法 逆向最大匹配算法原理类似于正向最大匹配算法，它的具体原理是： a ) 从右往左取不超过词典最大长度的汉字作为匹配字段； b ) 查询词典并进行匹配，若能匹配，则将这个匹配字段作为一个词切分出来； c ) 若不能匹配，则将这个匹配字段的最前一个字去掉，剩下的字符串作为新的 匹配字段，进行再次匹配； d ) 循环操作，直到匹配字段字数为零为止； e ) 重复逆向最大匹配过程，直到切分出所有词为止。 - 正向最大匹配算法和逆向最大匹配算法的区别在于正向最大匹配算法是从左往右 依次取匹配字段，而逆向最大匹配算法则是从右往左依次取匹配字段；二者的匹配方法 相同，但方向不同。 4 东北师范大学硕士学位论文 机械匹配算法简洁，易于实现，在实际工程中应用较为广泛。但由于自然语言的复 杂性，该类分词算法存在分词歧义问题，影响分词的精度，并且难于实现词典的自动扩 充，单纯采用机械匹配进行分词难以满足信息处理中对中文分词的要求。 而在机械分词的基础上，利用各种语言信息进行歧义校正，是削弱机械切分局限性 的一种重要手段。目前实用的自动分词系统基本上都是以采用机械分词为主，辅以少量 的词法，语法和语义信息的分词系统。所以本文选择了正向最大匹配算法，并对其进行 了改进，加入了歧义处理方法。 2 1 2 基于统计的分词算法 基于统计的分词算法又叫无词典分词算法，主要利用词与词的联合出现概率作为分 词的信息。目前基于统计的分词算法有很多种，较为常见的算法是互信息的概率统计算 法，基于组合度算法，n - g r a m 算法等等。 ( 1 ) 互信息的概率统计算法n p l 3 3 互信息算法的主要思想是对于字符x 和字符y ，利用互信息公式计算出他们的互信 息值m i ( x ，y ) 。通过互信息值m i ( x ，y ) 的大小判断字符x 和字符y 之间的结合程度。 互信息计算公式如公式2 - 1 所示。 a ) 当互信息值m i ( x ，y ) o 时，则字符x 和字符y 之间具有可信的结合关系， 并且互信息值m i ( x ，y ) 越大，结合程度越强。 b ) 当互信息值m i ( x ，y ) = 0 时，则字符x ，字符y 之间的结合关系不明确。 c ) 当互信息值m i ( x ，y ) 0 时，则字符x 和字符y 之间基本没有结合关系，并 且互信息值m i ( x ，y ) 越小，结合程度越弱。 m i ( x ，y ) = l 0 9 2 磐 ( 2 一1 ) p t x ) p y ) 其中p ( x ，y ) 代表字符x 和字符y 共同出现的概率，p ( x ) ，p ( y ) 分别代表字符x 和字符y 分别出现的概率，m i ( x ，y ) 代表字符x 和字符y 的互信息值。 ( 2 ) 组合度算法n 町 组合度算法的主要思想是：由于中文的词语都是多个字符组合而成，所以在一篇文 章中，如果汉字b 紧跟在汉字a 的后面，我们就称a b 为一个组合运用组合度的计算 公式，计算出每个词组的组合度，组合度越高，说明它是词组的可能性越大，组合度越 低，说明它是词组的可能性越小。组合度计算公式如公式2 2 所示。 日肛：乩生掣 ( 2 2 ) 其中h 肺为a b 在文章中的组合度，n 为汉字个数，k 为a b 组合的个数，n ，是a 的个 数，n ：是b 的个数。 ( 3 ) n - g r a m 模型算法口钔 n - g r a m 模型算法的主要思想是：一个单词的出现与其上下文环境中出现的单词序列 密切相关，第n 个词的出现只与前面n 一1 个词相关，而与其它任何词都不相关，设w 。w ： 东北师范大学硕士学位论文 一唧。是长度为n 的字串，则字串w 的似然度用方程表示如公式2 - 3 所示。 p ( ) = 兀p ( w ，w i - n + ! w 嘲+ 2 一w i 1 ) ( 2 3 ) ，j ，例如预测词w 。的出现概率，必须知道它前面所有词的出现概率，太过复杂。为了简 化计算，规定任意词w ；只与其前两个相关，得到三元概率模型如公式2 - 4 所示。 p ( 形) p ( w 1 ) p ( w 2 w 1 ) 兀。：3 。p ( w ，w ，2 w ，1 ) ( 2 4 ) 以此类推，n 元模型就是假设当前词的出现概率只同它前面的n - 1 个词有关而得出 的。 基于统计的分词方法的优点在于不需人工建立规则库，所需数据由机器从语料库中 通过训练自动获得；能有效地自动排歧；识别未登录词：解决了机械分词算法的局限， 精度也更高。但同时它也存在一些缺点，如由于不使用分词词典，所以对常用词的识别 敏感度较低，经常会抽出一些无用词组；计算量大而且分词的精度与训练文本的选择有 关等等。 基于统计的分词方法由于具有良好的切分歧义处理能力和识别新词的能力，目前受 到越来越多的重视，发展较快。如何将该法与机械分词有机地结合起来，既发挥机械分 词速度快，效率高的特点，又利用无词典分词结合上下文自动消歧的优点，已成为该类 算法的下一步研究课题。 2 1 3 基于规则的分词算法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思 想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。 它通常包括三个部分： ( 1 ) 分词子系统； ( 2 ) 句法语义子系统； ( 3 ) 总控部分。 在总控部分的协调下，分词子系统可以获得有关词、句子的句法和语义信息来对分 词歧义进行判断，即它模拟了人对句子的理解过程。 基于规则的分词算法h 7 1 优点在于它可以由实例中进行自动推理和证明，可以自动 完成对未登录词的补充，但是它本身需要大量的汉语相关知识，使规则分词算法很难实 现。 本文主要采用的就是基于词典的正向最大匹配算法和基于概率统计相结合的分词 算法。综合了词典分词算法简洁，易于实现和概率统计算法识别精度高，能够处理歧义 的优点，设计实现了这个基于词典的分词系统。 2 2 分词中的词典机制 因为基于词典的分词系统的分词速度，主要取决与对分词词典机制的选择。所以要 研究基于词典的分词算法首先就要研究中文分词词典机制。最早的分词词典机制就是简 6 东北师范大学硕士学位论文 单的顺序排列，但是随着对分词词典机制的深入研究，人们发现顺序结构并不能得到良 好的分词效果。 所以近年来，通过无数研究者的共同努力，相继提出了多种典型的分词词典机制， 其中包括基于t r i e 树的词典机制，基于p a t r i c i at r e e 的词典机制，基于整词二分的分 词词典机制，双层h a s h 词典机制等多种词典机制。 2 2 1 基于t r i e 树的词典机制 t r i e 树n 8 矧是搜索树的种，它在本质上是一个确定的有限状态自动机，每个结点 代表一个状态，根据输入变量的不同，进行状态转移。可用于存储和查找字符串t r i e 树的每一条边都对应一个字符在t r i e 中查找字符串s 时，只需依次枚举字符串s 的每 个字符，同时从t r i e 的根节点开始选择相应的边往下走如果枚举完的同时到达t r i e 的 叶子节点，说明字符串s 存在于t r i e 中如果未到达叶子节点或者枚举中途发现没有任 何对应的边，说明字符串s 没有被包含在t r i e 树中。具体结构如图2 1 所示。 图2 1 基于t i l e 树的结构示意图 2 2 2 基于p a t r i c i at r e e 的词典机制 p a t r i c i at r e e 乜卜2 3 1 本质上是一种压缩的二叉查询树，它将关键词作为二进制位串记 录在树的结构中，从根结点到叶子结点的每一条路径都代表一个关键词位串。它有三个 基本的数据项分别： ( 1 ) 比较位： ( 2 ) 左指针： ( 3 ) 右指针。 其中，左指针和右指针分别指向该结点的左、右子树，比较位记录的是从根结点到 达该结点的所有位串中第一个不相同位的位置。由于比较位的存在，途经该结点的位串 将选择不同的后继路径，当比较位为0 时，位串转向左子树，当比较位为1 时，位串转 7 东北师范大学硕士学位论文 向右子树。具体结构如图2 2 所示。 关键词1 ：听众 关键词2 ：面的 关键词3 ：金 关键词4 ：金属 位串1 ：1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 位串2 ：1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 位串3 ：1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 位串4 ：1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 图2 2p a t r c i af r e e 数据结构图 这种词典机制其不足之处是需要较多的内存空间。因此，基于p a t r i c i at r e e 的分 词词典机制适用于实时性要求高的大规模汉语信息处理系统。 2 2 3 基于整词二分的词典机制 这种词典机制幢4 。别是一种曾经广泛使用的分词词典机制，它主要包括三个部分：首 字h a s h 表，词索引表和词典正文。其中首字h a s h 表就是找到一种数据内容和数据存放 地址之间的映射关系；词索引表的建立，实现了对词的随机访问；而字典正文实际上就 是以词为单位的有序表。其在内存中的形式如图2 3 所示。 首字散列表。 词索引表 词典正文 图2 3 整词二分的词典机制 2 2 4 双层h a s h 的词典机制 双层h a s h 词典机制陋制就是多次h a s h 结构循环，即不仅对首字进行h a s h 查找，对 于词次字仍然采用h a s h 查找的方式来确定。该词典是由首字h a s h 表、词次字h a s h 表、 词余字索引表、词余字词典正文等部分组成。该种词典机制和单层h a s h 词典机制相比， 能大大提高了系统的分词速度。目前该词典机制已经成为大多数机械分词算法的首选词 典机制。具体结构如图2 4 所示。 8 东北师范大学硕士学位论文 首字h a s h 表 是否为词 次字h a s h 表指针 次字h a s h 表一- 是否为词 剩余字串组指针一一 黧竺=j=：-孟i f ia i 亩一黧券j = j ：圈困一 ：答 i 案 ：要 ；案 j ， ；4 - ! ； ! 事； ；虫! ：一o ! 女! 、i i 自： i 鼠i ? 。：? _ ： ：鼾：，：鼾： ! 麦ji 壁j 图2 4 双字h a s h 索引分词词典机制 2 3 中文分词面临的主要困难 由于中文自动分词的困难及其在中文信息处理领域的重要地位，自2 0 世纪7 0 年代 末，许多人开始致力于中文自动分词的研究工作，出现许多具有应用前景的分词算法， 但分词仍然是中文信息处理的瓶颈问题。中文自动分词技术面临的主要困难如下： ( 1 ) “词 的概念不明确。1 9 9 2 年制定的国家标准信息处理用现代汉语分词规范 虽然给出了词和分词单位的非形式化定义，但语言学界对词还没有给出- 个为大家广泛 接受的、严格且统一的非形式定义。 ( 2 ) 未登录词的识别i 由于新词不断增加，而词典的容量有限，文本中必然会存 在词典中没有收录的词，如人名、地名、机构名等专有名词及新词语等( 统称为未登录 词) ，该问题的解决有赖于人们对汉语结构的进一步认识。 ( 3 ) 歧义切分字段的处理。中文分词还没有形成一个公认的分词标准，这是人和 计算机共同面临的困难，同一文本可能被不同的人划分为几种不同的分词结果。中文自 动分词的歧义问题将始终存在，并严重影响分词系统的精度，歧义切分字段的处理成为 中文自动分词技术的关键问题。 2 4 性能评价指标 常用的中文分词系统性能衡量指标常见的有：切分精度、切分速度、召回率、准确 率等铷。 ( 1 ) 切分精度 9 东北师范大学硕士学位论文 切分精度是中文分词系统的主要性能指标之一，其计算公式表示如公式2 5 所示。 切分精度= 篆磊黼1 。 ( 2 5 ) ( 2 ) 切分速度 切分速度也是中文分词系统的主要性能指标，其计算公式如公式2 - 6 所示。 切分速度= 切分结束时间一开始切分时间 ( 2 6 ) 切分精度表明分词系统的准确性，切分速度反映了系统的快慢性。这两个指标不是 独立的，其中一个指标的提高往往以另一个指标的降低为代价。一般而言，切分精度上 升，则切分速度会变慢，而切分速度变快，则切分精度会下降。 ( 3 ) 召回率 召回率是中文分词系统中未登录词识别性能评价指标之一，其计算公式如公式2 7 所示。 召回率= 焉菩誊署燃，。 q 7 ， ( 4 ) 准确率 准确率也是中文分词系统中未登录词识别性能指标之一，其计算公式如公式2 8 所 示。 准确率= 黑器1 0 似 ( 2 8 ) 召回率反映了未登录词识别的完整性，而准确率反映了未登录词识别的准确性。i 一 者相辅相成，相互依赖。 l o 东北师范大学硕士学位论文 第三章分词歧义相关技术 分词歧义技术是中文分词技术的重要组成成分，由于中文词与词之间不象西文那样 有明显的分隔符，同时中文中词的定义、词与词组划界标准和形式的缺乏都造成了歧义 字段的大量存在，从而使歧义字段的切分成为了影响中文分词系统切分精度的一个最困 难问题。本章的主要工作就是对分词歧义技术进行深入的研究。 3 1 歧义产生的原因 语言的准确性是语言表达的先决条件。它是语言的鲜明性、生动性的前提。人们无 论是说话或写文章，准确性是最重要的。只有正确地传达语意，才能给接受者以正确的 信息，在听或读的时候不至于造成误解。因而研究歧义产生的原因及消除的方法，就显 得致关重要。 汉语句子的表达形式相同，但意义不同，这种同形异义的句子称为歧义句。这里所 谓的“句子，实际上包含了若干个句子。它能作几种理解就能有几个句子。造成句子 歧义的因素很多，它包括词汇、语法、语义及语用等多方面。目前总体来看，歧义产生 的根源可以归结为以下三个方面： ( 1 ) 由自然语言的二义性所引起的歧义，我们称为第一类歧义。这类歧义字段的 特点是一般会有两到多种切分方式，同时这些切分方式无论在语法上还是语义上都是正 确的，人工分词也会产生歧义，只有结合上下文才能给出正确的切分。 ( 2 5 由机器自动分词产生的歧义，我们称为第二类歧义。这类歧义字段的特点是 由机器自动分词造成的，人工分词不会产生歧义。例如字符串“在这种环境下工作是太 可怕了”用机器切分可能会切分为“在这种环境下工作是太可怕 了 ，是错误的切分方式。而用人工分词就会得到“在这种环境下工作是 太可怕了 这种正确的切分方式。目前如何减少这种机器性歧义字段的产生，是中 文分词歧义处理技术的研究热点。 ( 3 ) 由分词词典的大小而引起的歧义，我们称为第三类歧义。这类歧义的特点是歧 义的产生是由词典大小决定。例如字符串“夏天空是一个农民 用机器切分，被分为 “夏天空是一个农民 ，这里“夏天空 是一个人名，在汉语中应是一个词， 如果词典中有该词，则“夏天空会被正确切分出来；但如果词典中没有该词，就会产 生了歧义，导致切分错误。又例如字符串“发展社会主义的新乡村”，如果词典中没有 “新乡 一词，则不会产生歧义；如果“新乡 是一个地名，在词典中有该词，则“新 乡村 就会成为了歧义字段。因此，不论词典的大与小都有可能产生歧义。 统计表明第一类歧义字段只占歧义字段总数的5 左右，而第二类歧义字段和第三 类歧义字段总数占歧义字段总数的9 5 左右。故中文自动分词阶段对歧义字段的研究主 要集中在对第二类、第三类歧义字段的研究。 l l 东北师范大学硕士学位论文 3 2 歧义字段的分类 歧义字段可分为三种类型：交集型歧义、组合型歧义和真歧义。下面分别介绍这三 种歧义字段的定义。 3 2 1 交集型歧义 定义1 ：在字段a b c 中，a b e w 并且b c e w ，a 、b 、c 为字串，w 为词表，则称a b c 为交集型歧义字段口2 制。其中交集型歧义字段中含有交集字段的个数，称为交集型歧义 的链长。交集字段中重复的汉字个数，称为交集型歧义的交集字段长度。例如： 交集型歧义字段“结合成可切分成( 1 ) “结合成和( 2 ) “结合成两种切分 方式，其中a = “结”，b = “合 ，c = “成”。这里该歧义字段的链长为1 ，交集字段长 度为1 。 交集型歧义字段。结合成分刀可切分成( 1 ) “结合成分”和( 2 ) “结合成分” 两种切分方式，其中“结合，“合成”，“成分都可单独成词，交集字段中的重复字数 都为1 ，所以交集字段长度仍然为1 。而由于它包括“结合成，“合成分 两个交集字 段，所以链长为2 。 因此根据交集字段长度和链长的变化，中文文本中会出现很多，形如a b c ，a b c d ， a b c d e ，a b c d e f 等等的交集型歧义字段，所以在汉语中交集型歧义字段的数量是比较庞 大的，但其处理方法相对简单，易于实现。 3 2 2 组合型歧义 定义2 ：在字段a b 中a b w ，a e w ，b w ，a 、b 、c 为字串，w 为词表，则称a b 为 组合型歧义字段啪1 。例如： 组合型歧义字段“将来可切分成( 1 ) “李教授将来香港讲学 和( 2 ) “香港 将来经济更繁荣 两种切分方式。 组合型歧义字段“起身”可切分成( 1 ) “他站起身来和( 2 ) “他明天起身 去北京两种切分方式。 这里组合型歧义字段除a b 型外，还可能有a b c 型或a b c 9 型等等。但由于中文语言 本身的习惯，a b 型组合型歧义的数量要超过其他类型的组合型歧义。所以目前很多学者 只侧重研究a b 型组合歧义。而虽然在汉语中组合型歧义字段数量相对较少，但是由于 中文语言本身的复杂性，却使组合型歧义处理起来相对比较困难。 3 2 3 真歧义 定义3 ：如果某一歧义字段，不结合其它信息，人也无法判断出其正确的切分方式， 那么这样的歧义字段就叫做真歧义字段。例如： 真歧义字段：“乒乓球拍卖完了竹可切分成( 1 ) “乒乓球拍卖完了 ( 2 ) “乒乓 球拍卖完了刀两种切分方式。这里如果没有上下文的相关信息，就无法判断出“乒 1 2 东北师范大学硕士学位论文 乓球拍卖歧义字段的正确切分方式。所以这样的字段就叫真歧义字段。 虽然歧义种类分为三种，但是由于真歧义字段是由于中文本身的二义性引起的，处 理起来难度很大并且数量相对稀少，所以目前歧义处理主要集中在对交集型歧义字段和 组合型歧义字段的处理上，本文所提出的算法主要实现了对交集型歧义字段的处理。 3 3 歧义的发现 目前常用的歧义字段发现算法包括双向最大匹配检索法，逐词扫描的最大匹配算法 以及最长词次长词算法，正向最大匹配+ 回退一字算法等等。每种发现算法都有其各自 的发现原理，对歧义字段的发现效果也不尽相同。 3 3 1 双向最大匹配检索法 其中双向最大匹配检索法h 是最简单的也是最基本的发现算法。它的原理是分别利 用正向最大匹配算法和逆向最大匹配算法，分别对字符串进行分词，得出不同的结果。 然后把两次得到的结果相比较，一样的字段就默认为非歧义字段，不一样字段就认为是 歧义字段。算法描述如下：假设待切分字符串为“独立自主和平等互利原则”则 ( 1 ) 用正向最大匹配切分，得到：“独立自主和平等互利原则”； ( 2 ) 用逆向最大匹配切分，得到：“独立自主和平等互利原则 ； ( 3 ) 把两次结果相比较，找到字段“和平等两次切分不一样； ( 4 ) 所以认为字段“和平等 就为歧义字段，然后在进行歧义处理。 这种发现算法虽然实现简单，但只能检测出交集型歧义字段，对组合型歧义字段却 难以识别j 3 3 2 逐词扫描的最大匹配法 其次逐词扫描的最大匹配法“2 1 是正向最大匹配检索与逐词扫描相结合的一种算法。 它的原理是从字符串中的起点取出不超过词典最大长度的汉字串，作为匹配字段；在词 典中查找该匹配字段，找到则切分出一条词，并与最近切分的词的做比较，根据歧义类 型做出标记；未找到则去除匹配字段的最后一个汉字，作为新的匹配字段重新匹配，以 此类推。直到匹配字段字数为零，才后移一个字作为下一次分词的起点，反复操作直 到字符串全部匹配完为止。算法描述如下：假设待切分字符串为“人民工努力工作，设 词典最长词为3 ，则 ( 1 ) 首先取“人民工 为匹配字段，在字典中查询，有该词； ( 2 ) 然后，去掉原匹配字段最右面的一个字，匹配字段变为“人民重新查询词 典，有该词，与“人民