（计算机科学与技术专业论文）自适应歧义切分的汉语分词系统的设计与实现.pdf

自适成歧义切分的汉语分诃系统的设| 十号实现摘要 摘要 汉语自动分词是中文信息处理领域的基础课题，也是中文信息处理发展的瓶预 之，其中对歧义字段的处理是影响分词精度的关键，幽内外许多研究人员在这一 领域都进行了深入的研究，但就目自p 现状来看，仍不能满足实际应用的需要。 本文针对分词中的两个方面：切分速度和歧义处理，进行了深入的研究。在速 度方面，它首先对词典中的侧进行排序，并对首字索引，同时还利用字符串顺序排 列时的规律，大大提高了查找阋时的速度，同时还对n 一最短路径的粗分模型进行改 进，通过过滤无覆盖型歧义切分结果的切分方案，使得剩余粗分结果数量大大减少， 同时还使得在不考虑未登录词的情况下，粗分结果的召回率达到1 0 0 。最后通过 分析目前算法的缺陷，提出目前算法的最大不足是语料信息的不完备性，然后介绍 卜一种在利用词的多元信息进行分词的基础上，通过收集切分错误歧义句，经过人 工修正，由系统1 9 动调节多儿信息库，增强语料信息库的完备性，以此提高分词正 确率的方法。 在分析阶段，本文就分词系统的速度与精度，与中科院计算所的汉语分词方法 送行了全面的比较，在分析了本系统的优势的同时，也指出了本系统存在的一些不 足之处，并由此作出了展望。 关键词： 自适应、分词、歧义、多元关系 作者：温滔 指导老师：朱巧明 d e s i g n 。r i d i m p l e m e n t a t i o no f c h i n e s e w o r dsegmentatiens y s t e mofse)f-adaptweambiguouss e g m e n t a t i o n d e s i g na n di m p l e m e n t a t i o no fc h i n e s ew o r ds e g m e n t a t i o n s y s t e mo fs e l f - a d a p t i v ea m b i g u o u ss e g m e n t a t i o n a b s t r a c t c h i n e s ea u t o m a t i cw o r ds e g m e n t a t i o ni st h ef u n d a m e n t a lt a s ko ft h ec h i n e s ei n f o r m a t i o n p r o c e s s i n g i tb e c o m e so n eo ft h eb o t t l e n e c k si nc 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 h ec h i n e s ew o r d d i s - a m b i g u i t yi st h ek e yf a c t o ro fp r e c i s i o no fc h i n e s ew o r ds e g m e n t a t i o n m a n yr e s e a r c h e r sh a v e s t u d i e di nt h i sf i e l d b u tc o m et ot h ep r e s e n tc o n d i t i o n ，i tc a n ts a t i s f yt h ed e m a n do f a p p l i c a t i o n t h i sa r t i c l eh a sd o n ed e e p l yr e s e a r c hi nt w oa s p e c t so f 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 ns p e e da n dd i s a m b i g u i t y a tt h es p e e da s p e c t ，t h r o u g ha r r a y i n gt h ew o r d i nt h e d i c t i o n a r ya n dg e t t i n gt h ei n d e xo f t h ef i r s tw o r d ，a n dt h e nu s i n gt h er e g u l a r i t yo f t h ea r r a yo f w o r d ，i t r a i s e st h es p e e do f w o r d s e e k i n g a tt h es a l l l et i m e ，t h ea r t i c l ei m p r o v e st h em o d e lo f c h i n e s ew o r d s r o u g hs e g m e n t a t i o nb a s e do nn s h o r t e s t - p a t h sm e t h o db yd e l e t i n gt h er e s u l to fw o r ds e g m e n t a t i o n w h i c hc o n t a i n st h eu n c o v e r da m b i g u i t y ，i tr e d u c e st h er o u g hr e s u l t s u n d e rt h ec o n d i t i o no f t a k i n gn o a c c o u n to ft h eu n d e f i n e dw o r d ，t h er e c a l l i n gr a t ec a nb e1 0 0 a tl a s t ，t h r o u g ht h ea n a l y s i so ft h e e x i s t i n ga l g o r i t h m so fc h i n e s ew o r ds e g m e n t a t i o n ，t h ea r t i c l ep o i n t so u tt h a tt h ec u r r e n ta l g o r i t h m s f l a wi si n f o r m a t i o n si n c o m p l e t e n e s so nc h i n e s ec o r p u s ，a n dt h e ni ti n t r o d u c e sa l la l g o r i t h mt h a t b a s e do nt h ei n f o r m a t i o no fm u l t i g r a m i tc a r lc o l l e c tt h ea m b i g u o u ss e n t e n c e si ns e g m e n t i n ge r r o r t h e nt h r o u g hm a n u a li n t e r f e r e n c et h es y s t e mc a na d j u s tt h em u l t i g r a mi n f o r m a t i o na u t o m a t i c a l l y ，i t c a ns t r e n g t h e nt h em a t u r i t yo ft h ei n f o r m a t i o no fm u l t i g r a mm a de r t h a n c et h ea c c u r a c yo fc h i n e s e 、w ) r ds e g m e n t a t i o n a tl a s t ，t h ea r t i c l eh a sm a d ea na l l - a r o u n dc o m p a r i s o nb e t w e e nt h es y s t e ma n di c t c l a s s ( i n s t i t u t eo fc o m p u t i n gt e c h n o l o g y ，c h i n e s el e x i c a la n a l y s i ss y s t e m ) o ns p e e da n da c c u r a c y t nt h e e n di td i s c u s s e st h ea d v a n t a g ea n ds h o r t a g eo f t h i ss y s t e ma n dg i v e ss o m ep r o s p e c t sf o rt h ef u t u r e k e y w o r d ：s e l f - a d a p t i v e ，w o r ds e g m e n t a t i o n ，a m b i g u i t y , m u l t i g r a m i i w r i t t e nb yw e nt a o s u p e r v i s e db yz h uq i a o m i n g 自适应歧义切分的汉语分词系统的设计与实现 第一章序言 第一章序言 1 1 论文背景 自1 9 8 3 年国内第一个分词系统_ c d w s 实现以来，国内许多科 学工作者都对分词进行了更深入的研究，其主要研究方向集中于以下两 个方面：分词的算法设计和汉语歧义字段的研究。 在分词算法设计上，大致可分为以下两个方面，一类旨在提高分词 的切分精度的算法。另一类主要在提高算法速度方面上下工夫。对于提 高分词切分精度的算法，可以说动用了几乎所有可能的方法。文献【2 】中， 提出了正向扫描+ 增字最大匹配+ 词尾歧义检查+ 归右原则的方法。这种 方法对某些类型的歧义可以得到正确的切分结果，但又势必造成其他类 型的切分错误。另一种方法是将正向最大匹配法和反向最大匹配法结合 起来使用的双向最大匹配法。结果发现，9 0 左右的句子，这两种算法 的切分结果重合且完全正确；9 左右的句子，两者虽不同，但必有其 一是正确的；只有l 的甸子，不论两者切分是否重合，都无法得到正 确的结果。以上数据说明，此方法有较强的歧义切分检测能力。文献【3 1 就是利用双向匹配法标出歧义字段，然后利用二元或三元方法进行处 理，取得了良好的效果。文献 4 1 提出了一种汉语文本切分和词性标注相 融合的一体化分析的统计模型，由于词性标注等方面的基础研究工作不 足，初步性开放测试效果较好，而实用性有待验证。文献翻利用句子内 部相邻字之间的互信息及t 测试差这两个统计量来切分交集型歧义字 段，缺点是需要事先通过对语料的统计来获得任意两个汉字的同现概 率，而这些统计量的潜力还有待进一步挖掘。文献 6 1 1 7 1 尝试利用神经网 络来模拟人脑思维处理歧义切分问题，缺点是受训练语料选取的限制， 离实际应用还有很大差距。此外，文献 8 1 给出了汉语自动分词的专家系 统设计原理，文献1 9 】提出了一种基于极大似然估计原则构建的汉语自动 分词的零阶马尔可夫模型，并重点剖析了e m 算法：文献【旧1 根据汉语歧 义字段的长度的比例分布，有针对性的提出了一种消解中文三字长交集 型歧义的算法，回避了训练代价比较高昂的词性信息，仅仅利用了词的 l 第一章序吉自适应歧义切分的汉语分词系统的设计b 实现 概率信息及某些具有特定性质的常用字集合，取得了较好的效果。 对提高分词速度方面的算法，主要通过改进分词词表的速度以及分 词过程中的匹配方法来实现的。文献j 的词表结构为词首字h a s h 索引， 同首字词条可顺序查找，时间复杂度为2 8 9 。文献l l2 j 利用汉语中两字词 占7 5 的统计规律，提出了两字词根和两字词簇的概念，把三音节以上 的词用两字词簇来压缩处理，提高了分词的速度。文献i l3 j 在此基础上设 计出种高效的电子词表，支持首字h a s h 和标准的二分查找，进而提 出一种改进的快速分词算法，在快速查找两字词的基础上，利用邻近匹 配方法来查找多字词，该算法的时间复杂度理论上为1 6 6 。文献【1 4 】贝q 根 据多级内码的设计理论，提出了一种并行分词方法。 在汉语歧义字段的语言研究方面，文献【l 】的作者梁南元最早对这种语 言现象进行了比较系统的考察和归纳。他定义了两种基本的切分歧义类 型：交集型歧义字段：汉字串a s b ( a 、s 、b 为汉字串) 中若a s 、s b 同 时为词；组合型歧义字段：汉字串a a ( a 、b 为汉字串) 中若a 、b 、a b 同时为词。文献【1 5 】中作者进一步指出，切分歧义应区别“真歧义”和“伪 歧义”并整理出一张歧义切分类型表。同时，文献作者在考察了一个极 大规模汉语语料库的基础上，提出了最大交集型歧义切分字段的概念并 根据其频率分布的特点，发现高频部分表现出相当强的覆盖能力和稳定 性，给出了一种基于记忆的，高频最大交集型歧义切分字段的处理策略。 上述研究成果加深了我们对歧义字段理解的深度，拓展了我们的视野， 对歧义字段的处理具有指导意义。 虽然前入在分词这一领域上花费了极大的精力并取得了一定的成 效，但就其实用性而言还远没有达到人们所希望的程度。1 9 9 5 年，国家 科委组织了8 6 3 智能机专题自动分词评测。开放测试条件下的评测结果 6 】是：分词精度最高为8 9 4 ，交集型切分歧义处理的正确率最高为 7 8 o ，组合型切分歧义则为5 9 o ，而未登录词识别的正确率，人名 最高为5 8 ，地名最高为6 5 o 。评测数据说明，面对分词这第一道工 序，距离真正意义的实际应用还有段路，我们还需要付出更多的努力 ， 白适腕歧义切分的汉语分诃系统的设计与实现 和艰苦，在这一领域上作出更深入的探索。 1 2 本文研究的意义 所谓分词( t e x ts e g m e n t a t i o n ，w o r ds e g m e n t a t i o n ) 就是将连续的字序列 按照一定的规范重新组合成词序列的过程。与英文不同，汉语中最小的 单位不是词，而是字，但具有一定语义的最小单位却是词。而中文文本 在计算机内部表示时，词与词之间并没有明显的切分标志。但是中文信 息处理的诸多重要领域如篇章理解、机器翻译、文本检索、文本的语音 输入输出、文本校对、自动标引等都要求在词这一平面上来进行，因而 汉语分词已成为中文信息处理中的基础课题之一，在中文信息处理中占 据着相当重要的地位。 为什么要分词? 首先我们谈一下智能计算技术。智能计算技术涉及 的学科包括物理学、数学、计算机科学、电子机械、通讯、生理学、进 化理论和心理学等等。简单的说，智能计算就是让机器“能看会想，能 听会讲”。而词是最小的、能独立活动的、有意义的语言成分。计算机 的所有语言知识都来自机器词典( 给出词的各项信息) 、句法规则( 以 词类的各种组合方式来描述词的聚合现象) 以及有关词和句子的语义、 语境、语用知识库。汉语信息处理系统只要涉及句法、语义( 如检索、 翻译、文摘、校对等应用) ，就需要以词为基本单位。只有当汉字由句 转化为词之后，中文才能象英文那样过渡到短语划分、概念抽取以及主 题分析，以至于自然语言理解，最终达到智能计算的最高境界。 从现阶段的实际情况来看，英文已经跨越了分词这一步，也就是说 在词的利用上已经先一步，并且已经展现了良好的应用前景，无论是信 息检索还是主题分析的研究都要强于汉语，究其根本原因就是汉语要通 过分词这道难关。只有攻破了这道难关，我们才有希望赶上并超过英文 在信息领域的发展，所以汉语分词对我们来说意义重大，可以说直接影 响到使用汉语的每一个人的方方面面。 但从分词研究的现状来看，目前的分词系统仍然不尽完善，其实用 性还远远一i 能满足实际应用的需要，因此我们需要在汉语分词模型上作 3 笙二：量生童 鱼垩! 翌堕墨塑坌塑翌堕坌塑至笙堕丝生要塞墨 _ 进一步的探索。另外，还需要在句子的信息结构及数据组织等方面加 强研究，如分词过程中除词频及词性外，还可以考虑词语音，词与词之 间的相关性等。分词过程的好坏直接影响到了整个信息系统的质量。 1 3 本文的主要工作 在汉语分词的研究上有多个难点，本文主要研究的是汉语歧义切分 这1 方向。由于汉语分词过程中的主要问题就是存在歧义字段，如何解 决歧义字段的排歧问题就成为分词过程中一个极为重要的方面。 本文首先着眼于算法速度，对已有词表进行改进，根据字符串按序 排列时的规律，提出了一种快速汉语分词算法。理论分析表明，这种算 法即使在大词库下也能有很好的表现。然后对n - 最短路径的粗分模型 进行改进，提出了一种在不考虑未登录词的情况下，可使分词粗分结果 的召回率达到1 0 0 的歧义粗分方法。最后，本文考虑到由于汉语使用 的广泛性和复杂性，导致语料信息的完备性无法得到保障，由此提出了 一种在利用词的多元信息进行分词的基础上，通过收集切分错误歧义 句，经过人工修正，由系统自动调节多元信息库，增强语料信息库的完 备性，以此提高分词正确率的高效的分词系统，并对该系统进行了分析、 评价及展望。 1 4 章节安排 本文的主要章节安排如下： 第一章主要介绍本文的背景、研究意义及所做的主要工作。 第二章主要介绍汉语分词的背景，以及一些常见的歧义切分的算 法，并提出了他们的不足。 第三章提出了一1 种快速汉语分词算法，使得在分词速度方面有了 很大的提高。 第四章通过改进n 最短路径的粗分模型，提出了一种在不考虑未 登录词的前提下可使召回率达到1 0 0 的歧义粗分方法。 4 自适麻歧义切分的汉语分浏系统的设计与实现第一章序苦 登录词的前提下可使召回率达到1 0 0 的歧义粗分方法。 第五章通过对自适应歧义切分的汉语分词系统的介绍，提出了利 用人工干预完善语料信息的方案，通过实验及与其他方法的对比，证明 r 此方案的有效性。 第六章主要内容为将本文介绍的分词系统与中科院计算所汉语词 法分析系统中的分词模块进行了对比，并对该系统的优缺点进行了总 结。 第七章对将来的分词研究工作进行了展望。 第一錾汉语分词概述 自适应歧义切分的汉语分词系统的设计与实现 第二章汉语分词概述 2 1 汉语分词的概念 什么是分词? 分词就是将连续的字序列按照一定的规范重新组合成 词序列的过程。在英文的行文中，单词之间是以空格作为自然分界符的， 因此，在词理解上就比较直观。而汉语只有在旬与句之间才通过标点或 段落来简单划界，词与词之间则没有这样的分界符。例如，英文一句子 ia mas t u d e n t ，译为汉语则为“我是一名学生”，计算机可以通过“s t u d e n t 分词，但同样是“我是一名学生”，让计算机理解“学”和“生”是一 个词就不太容易。汉语分词就是要把汉语的这种序列切分成有意义的 词，以便机器理解。虽然英文也同样存在短语的划分问题，但是在词这 一层面上，中文的处理就要比英文复杂的多。 2 2 汉语分词的难点 2 2 1 分词规范问题 在汉语分词中最大的困难就是词的概念不清。什么样的组合称之为 词，词该如何界定，这是一项比较困难的事。虽然已经有了一些标准来 判断，但由于这些判断条件本身难以操作，目前尚无合理的可操作的理 论和标准。再加上汉语本身的复杂性，如词的变形( 相信相不相信、 睡觉睡了一个觉) ，词缀问题( “x x 者”等的划分问题) ，非词语素 问题等使得词的界定尤为困难。 同时，在不同的应用领域，由于应用需求的不同，需要达到的分词 效果也有很大区别。例如在以词为单位的键盘输入系统中，为了提高输 入速度，将一些出现率高的相互邻接的几个字也作为输入的单位，如“这 时”、“每一”、“x x 的”、“不多”，“不在”等，甚至一些较长的句子也 作为一。个切分单位。而在检索系统中，词库的建立则倾向于术语和专名， 有的检索系统更将分词单位较小化，如将“并行计算机”切成“并行 计算机”，“计算语言学”应切成“计算语言学”，使得无论用“并行计 算机”还是用“计算机”、“计算语言学”或是“语言学”检索，都能查 旦适生些塞塑坌塑堡曼坌塑墨堑塑丝生兰薹型 到。 2 2 2 歧义切分 所谓歧义( a m b i g u i t y ) 就是指对一句句子( 或一个字串) ，可以有多 种理解方式。例如：“表面的”，既可以理解为“表面”，“的”，又可以 理解为“表”，“面的”；又如“机器翻译程序”，可以切分为“机器”，“翻 泽”，“程序”，又可以分为“机器”，“翻译程序”，或“机器翻译”，“程 序”。梁南元( 1 9 8 7 ) 最早对这种语言体系进行考察，并归纳出了歧义 的两种类型，分别称为交集型歧义( o v e r l a p p i n ga m b i g u i t y ) 和组合型歧 义( c o m b i n a t i o na m b i g u i t y ) 。所谓交集型歧义就是指字串a b c ( a ，b ，c 为汉字串) 中，若存在a b ，b c 同时为词，则称此切分为交集型歧义切分。 组合型歧义就是指字符串a b ( a ，b 为汉字串) 中，若a b ，a ，b 同时为词， 则称此切分为组合型歧义切分。为了消除歧义，除了词库外，我们通常 需要一些附加的信息，如词频、词长、词间关系等等。如“在世界”， 由于“在”以单字出现的频率远高于“界”的出现频率，因此应被切分 为“在世界”，而不是“在世界”。有时还需要通过上下文来判断词的 切分情况，如“学生会”一词，既可能是一个名词，指一种学生组织， 也可能是“学生会”。在“学生会主席”中只能是前者，在“学生会去” 中只能是后者。 2 2 3 未登录词识别 所谓未登录词( u n k n o w nw o r d ) 就是指分词词表中不存在的未知词， 如人名、地名、企业字号、商标号等，以及各类术语、缩略词、新词。 未登录词的识别对于汉语处理系统不仅有直接的实用意义，而且起到基 础性的作用。如果没有对未登录词的处理，在我们利用分词进行词频统 计时就会产生较大误差。例如，“分析也是需要权衡的问题”一句中，“分 析”和“也是”在词类中不存在，则切分为“分析也是需要权衡 的”，如何发现“分析”、“也是”这些词呢? 同样，在文本中，若存在 笙= 三垦堡墨坌塑塑垄 ! 垩壁些墨塑坌塑堡堕坌塑墨堕塑堡盐皇壅翌 大量的人名、地名，则让机器去识别就更为困难。 2 2 4 分词理解的先与后 由于计算机需要靠词的信息来理解文本，因此它只能采用先分词，后 理解的方法，这样就产生逻辑问题：分词需要以理解为基础，而理解则 必须先分词。因此，不可能有百分之百正确的分词方法。 2 3 汉语分词现有方法介绍 汉语自动分词过程可描述为：输入含有若干个汉字的待处理字符串 c “= c 1 c 2 c j c 。( c i 为汉字，l 【1 ，n 】) 经过机器处理分析，输出 词串w = w 1 w 2 w i w 。，( w i 为词j e l l ，m 1 ) 。现有的分词算法可 分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于 统计的分词方法。 2 3 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法【l9 】，它是按照一定的策略将待分析的 汉字串与一个“充分大的”机器词典中的词条进行匹配。若在词典中找 到某个字符串，则匹配成功( 识别出一个词) 。按照扫描方向的不同， 字符串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先 匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配；按照是 否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结 合的一体化方法。常用的几种机械分词方法如下： 1 ) 正向最大匹配法( 由左到右的方向) ； 2 ) 逆向最大匹配法( 由右到左的方向) ； 3 ) 最少切分( 使每一句中切出的词数最小) 。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和 逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特 8 自适应歧义切分的汉语分词系统的设计与实现 点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配 的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明， 单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向最大匹配的错 误率为1 2 4 5 。但这种精度还远远不能满足实际的需要。其主要缺点是 ( 1 ) 分词中的可利用信息较少；( 2 ) 基于长词优先，对词典中的词条 的收录有较高要求，否则因分词的结果粒度太粗而不符合应用需求。此 外还有最小匹配的方法，但由于大多数汉字都可以单独成词，直接后果 将导致分词结果中大量单个汉字的产生。由于分词粒度过细，这种方法 不被采用。 另外还有一些方法是对上述方法的改进：如最佳匹配法1 ，其原理 只是对分词词典中的词条按词频排序，缩短对词典的检索时间，提高分 词速度，在算法本质上与最大匹配法没有什么太大的改动。 还有逐词遍历法i l ，其原理是将词典中的词，按由长到短的顺序， 逐个在待处理的文本中逐字搜索，直到字符串结束。也就是说，不管待 切分的字符串的长短，也不论词典容量的大小及词典中词的长度分布， 都要将词典遍历一遍。显然这种方法因时间响应受到很多应用的限制。 还有些研究人员，将构词能力差的一些汉字作为切分标记而首先分 出来，这种方法称为切分标记法1 2 0 或特征词库法f 2 1 1 。因其额外的搜索开 销，不但分词速度毫无改善，切分精度也有所下降。 还有一种最短路径法【2 1 1 ，也称为最少分词法f 2 2 1 。它将分词问题归为 图论中的最短路径问题，一个词对应于图上的一条有向边。对于待切分 的字符串，分词问题就是要在这个串上找到一个对应词的序列。这样图 论中的有关算法就为我们提供了求解这个问题的有力手段。这种方法， 分出的词最少，相对于最大匹配法，它是一种全局最优法。 由于机械分词只孤立考虑词的形式，因此，实际使用的分词系统， 都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息 来进一步提高切分的准确率。 自适应歧义切分的汉语分词系统的设计与实现 2 3 2 基于理解的分词方法 这种分词方法是让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语 义信息来处理歧义现象。它通常包括三个部分：分词予系统、句法语义 子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、 句等的句法和语义信息，来对分词歧义进行判断，即它模拟了人对句子 的理解过程。 文献1 8 中介绍的书面汉语自动分词专家系统是一种典型的基于知识 的分词系统，主要分为两大模块：知识库的组织与实现、推理机制与自 动分词过程。系统力求从结构与功能上分离分词过程和实现分词所依赖 的汉语词法、句法以及部分语义知识。这样，更利于知识库的管理与维 护。 这类分词方法需要使用大量的语言知识和信息。由于汉语语言知识 的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式， 另外，在利用分词知识进行歧义切分的推理过程中，又存在着分词知识 的冲突和矛盾，缺乏有效的消解机制。因此目前基于理解的分词系统还 处在试验阶段。 2 。3 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时 出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率 或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字 的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息， 计算两个汉字x 、y 的相邻共现概率。互现信息体现了汉字之间结合关 系的紧密程度。当紧密程度高于某一个闽值时，便可认为此字组可能构 成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分 词典，因而又叫做无词典分词法【l7 j 或统计取词方法。但这种方法也有一 定的局限性，会经常抽出些共现频度高、但并不是词的常用字组，例 臼适应蛟义切分的汉语分词系统的设计与实现 如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的 识别精度差，时空开销大【1 7 】。实际应用的统计分词系统都要使用一部基 本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计方法识别 一一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速 度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动 消除歧义的优点。 统计分词以概率论为理论基础，将汉语文本中汉字串的出现抽象为 一随机过程，其中，随机过程中的参数可以通过大规模的汉语语料库来 训练得出。其模型的形式化描述如下： p ( w “t c “) 表示汉字串c “切分为w “的某种估计概率，t 1 ，t 2 ，t k 表示c “所有可能的切分方案。基于统计的分词方法就是唯一的目的词 串w m ，满足下式： p ( w m i c “) - - - r n a x ( p ( t 1 c “) ，p ( t 2 f c “) ，p ( t k i c n ) ) 即估计概率最大的词串，p ( w “i c “) 为评价函数。 根据贝叶斯公式有： p ( w m | c n 户p ( w m ) p ( c n l w 。) p ( c n ) ，对一特定的汉字串来说，p ( c n ) 为 常数，而p ( c “i w m ) 表示在给定词串w o 的条件下字串c “的概率，是一 必然事件，估p ( c “i w “) p ( w ”) 。 对p ( w 。) ，可展开如下： v ( w m ) = 1 - l 乩。p ( w ，1w ，w 2 w i 一) 对于上式，不难看出，为了预测词w 的出现概率，必须己知它前 面所有词w l ，w 2 ，w i ，w 。1 0 = 1 ，i n 1 ) 的概率。在计算上，这 不仅太复杂，而且语料资源也极度贫乏。上述中，若规定任意一个词的 出现只和它前面出现的n - 1 个词有关，我们把这种量化后的语言模型称 为n 元模型( n g r a m ) 。实际使用通常使用n = 2 或n = 3 的二元模型或三 元模型。以二元模型为例，此时当前词的出现仅与它的直接前驱词有关。 即使经过这样的简化，若我们的词汇集的大小是l 的话，当前词的 历史数据的大小也就为l 。在这l 种不同的历史情况下，模型中产生当 第一章汉语分词概述 白适应歧义切分的汉语分词系统的设计与实现 前词的自由参数就有l 2 个v ( w ；1 w ) ，我们训练数据中根本就没有这些 参数。这种情况对于三元模型来说更加突出。然而，n 越大，表示词之 问关系越紧密，模型也越精细。在实际应用中，对于工程项目，我们一 般采用一元模型或二元模型：对于研究课题，则使用三元模型。文献1 2 驯 中，作者介绍了这种基于n 元语法的汉语统计分词模型，以及该模型在 不同资源要求下的实现方法。文章中进一步指出，利用n g r a m 直接估 计p ( w ”) 的算法，在目前是不可行的。大多数基于统计的分词模型都是 采用各种各样的估计方法，从不同的角度，实现对p ( w “) 的近似。另外， 许多学者就n g r a m 中到底是基于汉字还是基于词分别展开了讨论，文 献【2 4 】中作者提出了一种基于字符的n g r a m 分词模型，同时结合机器学 习的自组词算法实现文本的切分，相对与词来说，g b 2 31 2 8 0 中汉字 6 7 6 3 个，系统开销小，简单且容易实现。但在分词精度上，文献【1 9 1 、 文献【2 习的分词结果说明，建立在丰富语料样本的情况下，基于词的分词 精度要优于基于字的n - g r a m 分词的精度。 上述的n - g r a m 称为n 阶马尔可夫模型，描述了一类重要的随机过程。 其中，每一个状态代表了一个可观察的事件，这限制了模型的适用性。 如果观察到的事件是状态的随机函数的话，这中间就有一个双重随机过 程，其中模型的状态转换过程是隐蔽的。我们把这种状态转换称为隐马 尔可夫模型( 删) 。在计算语言学中，几乎所有高性能的语音识别系 统均采用h l v l m 来建模，其中最成功的应用是用来进行分词【9 】和词类标 识，如中科院计算所的汉语词法分析系统。 2 3 4 小结 本章介绍了目前流行的几类分词方法，对每一类方法都介绍了其原 理，同时例举了大量分词系统的实例，并对这些实例从实现上及实用上 做出r 全面的分柝和比较，阐述了各种分词方法应用的场合和存在的问 题。通过了解目前的分词算法，我们更清楚地认识到，要提高汉语分词 的精度，必须更为努力，在各方面做新的尝试才行。 白适应歧义切分的汉语分词系统的设计与实现釜三望二壁选鎏塑堡堡坌型笺鲨 第三章一种快速的汉语分词算法 3 1 引言 在实现分词算法的过程中，有两方面必须考虑：分词的正确率和分 词的速度。由于无论哪种分词方法都需要将大量的时间用于计算出待切 分语句的可能词，然后通过对切分出的这些词依据统计或语法方面的规 则，得到一种最有可能的正确切分结果，来提高分词的正确率。因此， 如果能加快初始切分的速度，对于提高整个分词算法的速度也会有很大 帮助。 许多人对分词的问题已经进行了深入的研究，并提出了一些提高分 词效率的方法，如改进的m m ( 最大匹配法) ，主要提高了切分时对歧 义的处理【2 】：基于神经网络的分词算法【6 】：基于两字簇的汉语快速分词 算法【3 3 】等。其中在分词速度方面比较有优势的有陈桂林，王永成等所 著的一种改进的快速分词算法【i 孙。该文是在一种高效词表的基础上， 提出了一种快速算法：邻近匹配算法。它利用词表中同一首字下的词条 按升序排列这一条件，在找到某个字符串后，在其后增加一个字得一新 字串，如果新字串在词典中出现，则新字串一定在原字串的后面，且相 隔位置不会太远，在匹配时，首先查找二字词c c o c c l ，得到索引i n d e x ， ( 如果不存在此二字词，则查找最接近c c o c c l 且排在其前的索引号) ， 然后在i n d e x 之后寻找最长且完全匹配的词条。终止这一寻找过程的条 件有两个：或者当前匹配长度小于最大匹配长度，或者词表中的词条比 字符串大。然后用相同的方法匹配下一词条。如在切分“中国人民解放 军成功守住了大堤“时，词表中以“中”开头的词有i 0 0 多个，以“中 国”开头的词有“中国青年”、“中国人民”、“中国银行”、“中国政府”， 找到“中国”后，在其后找“中国人民”只需两次词条匹配操作即可。 这种算法在小词库状态下，效率是比较高的，但在大词库状态下的效果 就未必很好了。比如，在1 0 万词的大词库中，以“中国”开头的词就 比较多，大概有1 2 0 个，要找到“中国人民”也要匹配大约6 0 多次。 在这样的情况下，再利用这种算法，效率就不会太高了。为此，在这种 1 1 笙三里：盐堡堕竺堡堡坌塑蔓垄一 ! 望坐堕墨型坌塑竖曼坌塑墨竺塑丝生皇壅型 算法的词表基础上，本文提出了一种在大词库状态下也能降低匹配次数 的高效分词算法。 3 2 算法介绍 我们先证明一+ 个定理。 定理：对一组已经排好序的词k 。k 。，设p 为待搜索字符串， r e s u l t 为p 首字开头的最大词，m 为这样一个位置，使得k 。p k 。+ 1 ( 对不存在这样位置的字符串暂不考虑) ，则有如下结论：k m 的前几 位必然是r e s u l t 。 证明：如果k 。= p ，那么显然有这个结论。 如果k 。 p k m + 1 ，则e h = r t t s u l t 属于k n 显然有r e s u l t p ，矛盾。证毕。 有了这样一个结论后，我们可以按照如下方法计算： ( 1 ) 、如果p 长度为1 ，则退出，否则，利用二分法计算出位置m ( m 定义如定理所示) 。 ( 2 ) 、将p 缩短至k 。的长度再进行比较，如果p 爿。则搜索成功，否 则，根据定理，最长词必定包含在k 。中，则将p 继续缩减，直到p k m ， 再返回步骤1 。( 其中可以改变二分范围为0 m ) 如对“中国人民解放中国”，假设首先找到“中国人民解放军”为位 置m 的词，则将字符串缩至与“中国人民解放军”同长，变为“中国 人民解放中”，比较后发现其不同，再将其缩至“中国人民解放”，此时 该字符串比m 位置词小，再对该词进行二分搜索( 范围为0 m ) ，找到 位置i l l ( “中国人民”) ，将“中国人民解放”缩至与“中国人民”同长， 再比较发现相同，于是“中国人民”就是最长词了。 臼适成歧义切分的汉语分词系统的设计与实现第三章二壁堡蕉塑堡量坌型笺堕 这种方法对于长字词来说比较好的。但这样会有缺陷，如果待搜索 的词比较短而找到的i t i 位置的词比较长，则需要比较的次数就会很多， 为了解决这个问题，我们采用这样的方法。 对每个词记录下它所包含的最大词( 不包括其自身) 的具体位置。 例如对于“中华人民共和国”，则记录下“中华人民”这个词的具体位 置，而“中华人民”则记录“中华”的具体位置。对于没有包含最大词 的词则记录一个负数。 对词做了如上处理以后，我们可以将步骤2 改进为：如果p 长度为 l 则退出，否则若p = k 。，则搜索成功，反之当p ! = k 。时，此时若p 为 二字词，则退出，否则设k 。处所记录的位置上的词为k 。，则将p 缩至 与k x 同长，再进行步骤2 即可。如此一来，只需进行一次二分搜索和 若干次缩词工作就可以找到最大词了。此外，对于其他可能存在词，也 只需要从最大词所记录的位置中就可以得到了，大大加快了搜索速度。 但这样做的坏处是，每次都至少经过一次二分搜索，对于二字词或 三字词的搜索效率就明显不如逐个增字搜索来的好。因此我们将增字法 融合到了搜索中来。 为了更好的应用增字法，我们对词的信息进行再加工，首先对每个 词，记录下其是否为2 字词，对于二字词，则再记录下以这个二字词为 开头的所有词的数目。这样就完成了信息的改造。 在具体实现中我们采用如下的方法，首先对待搜索字符串p 的前两 个字单独保存下来，记为q ，在二分搜索过程中，如果待比较的词是二 字词，则用q 比，否则用p 。在二字词的比较过程中，当q 是词的时候， 则通过以这个词开头的所有词的数目重新定位二分范围，如果数目为l ， 则该词就是最大词。否则继续进行二分搜索，并在此后运用之前所介绍 的减字法，就可以很快得到需要搜索的词了。 3 3 算法实现 3 3 1 索引的建立 第三章一种快速的汉语分词算法自适应歧义切分的汉语分词系统的设计与实现 首先利用字的内码的唯一性建立一一个h a s h 表，在表中记录如f 信息 ( 1 ) 、是否存在以此字开头的词 ( 2 ) 、以此字开头的词的首位置 ( 3 ) 、以此字开头的词的数目 具体建立方法参考文献吲。 3 3 2 信息记录 每个词利用一个8 位二进制来记录信息： ( 1 ) 、第8 位记录该词是否为二字词 ( 2 ) 、若为二字词，则显然其不包含最大词，不用记录最大词的位 置，则用1 7 位记录以该词为首的词的数目 ( 3 ) 、如果不是二字词，则1 7 位记录此词包含的最大词( 不包括 自身) 的位置与自身位置的距离，如果不包含最大词，则全为0 。 3 3 3 信息具体记录方法 ( 1 ) 、设p _ 为待操作词，首先判断p 是否为二字词，如果是，则将第 8 位置为1 ，否则为0 。 ( 2 ) 、如果p 是二字词，则继续向下搜索，判断有多少以p 为首的词， 并将此数据记录在p 信息的前7 位上。 ( 3 ) 、如果p 不是二字词，则p 所包含的最大词或者不存在，或者包 含于p 的前一个词中。则首先判断p 前一个字是否为p 的最大词，如果 是，则记录其间隔1 ，否则只需对p 的前一个词内所包含的词与p 比较 即可知道p 包含的最大词的位置。将他们之间的距离记录于p 的前7 位 中。如果p 不存在最大词，则将p 的前7 位置为0 。 举例说明： ( 1 ) 、c i c 2 0 ( 2 ) 、c l c 2 0 c 3 l c 4 l ( 3 ) 、c i c 2 0 c s i c 4 2 c 5 2 c 6 2 0 0 0 1 0 0 1 l 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 旦垩堕些兰塑坌墼堡堕坌塑墨篓塑丝生兰壅塑 釜兰童二墼堡垂塑堡堡竺型塞垄 ( 4 ) 、c l c 2 0 c 3 3 0 0 0 0 0 11 0 ( 5 ) 、c l c 2 0 c 3 3 c 4 4 0 0 0 0 0 0 1 0 ( 6 ) 、c l c 2 0 c 3 3 c 4 5 0 0 0 0 0 1 0 0 ( 7 ) 、c i c 2 。c 3 4 c 4 6 c 5 6 0 0 0 0 11 0 0 ( 8 ) 、c l c 2 0 c 3 4 c 4 7 c 5 7 c 6 7 0 0 0 0 1 l l o ( 9 ) 、c l c 2 0 c 3 4 c 4 7 c 5 7 c 6 s 0 0 0 1 0 0 0 0 3 3 4 算法具体实现 ( 1 ) 、将所有信息都调入内存，加快搜索速度。 ( 2 ) 、根据待搜索字符串p 的首字，通过首字索引得到它的可能范围， 如果这个字不能成词，则退出。否则，确定二分法的搜索范围，并令 q 为其前两个字。 ( 3 ) 、利用二分法，如果待比较的词为二字词，则用q 进行比较，否 则用p 比较。 ( 4 ) 、在二字词比较过程中，如果q 为词，则首先判断包含此词的词 的数目是否为0 ，若为0 ，则q 就为最大词，退出搜索。否则根据这 个数目重新确定二分范围，继续搜索。 ( 5 ) 在其余情况下均可以寻找到位置m ，使得k m = p k 。+ 1 如果不 存在这样的m ，则说明不包含以此字开头的词，退出搜索；否则，将