（计算机软件与理论专业论文）基于后缀数组salm模型的中文分词研究.pdf

摘要 摘要 自然语言处t 里( n l p ) 是语言学和人工智能的一个交叉域，它研究人类自然语 言的自动化产生和理解的问题，对于汉语来说，它涉及自动分词、词法分析、 语法分析和语义分析等。其中，自动分词是语言处理其它方面的关键和前提。 特别是随着中国计算机科学的发展，中文自动分词已经成为一项基础性课题。 很多机构如公司、院校都成立了专门的研究部门，希望在中文自动分词技术有 所突破。目前分词算法大概有几十种，可以归纳为三类：基于字符串匹配的机 械分词、基于概率论和信息论的统计分词和基于理解的分词方法。由于中文自 身的复杂性，中文自动分词有两个难点很难解决一一歧义识别和未登录词识别。 解决某一个难点已经成为评价一个分词系统好坏的重要标志之一。其它重要标 志还包括分词准确率、召回率、分词速度等。 本文开始介绍了机械分词技术、统计分词技术。然后，提出并实现了一个基 于后缀数组和句子字词表的分词方法。后缀数组是信息检索领域的通用高效技 术，本文系统利用s a l m 模型得到高频词条，经减枝后，用b e r k e l e yd b 把它 们组织成一个分词词典。分词算法在利用句子字词表进行分词的同时，还能发 现歧义，歧义句子采用最大句频原则进行切分。实验结果表明，本文系统的分 词速度能达到5 0 k b s ，分词准确率达到9 0 ，值得进一步的研究。 本文最后总结了全文内容，并分析了本文系统存在的问题，提出了改进方法。 关键字 自然语言处理中文分词s a l m 模型 b e r k e l e yd b字词表歧 义切分 a b s t r a c t a b s t r a c t n a t u r a ll a n g u a g ep r o c e s s i n g ( n l p ) i sac r o s s d o m a i no fl i n g u i s t i c sa n da r t i f i c i a l i n t e l l i g e n c e i t i sa b o u tt h ep r o b l e m st h a th o wt oa u t o m a t ea n du n d e r s t a n d h u m a n b e i n g s n a t u r a ll a n g u a g e e s p e c i a l l y t oc h i n e s e l a n g u a g e ，n l p i n v o l v e s a u t o m a t i cw o r d s e g m e n t a t i o n ，l e x i c a la n a l y s i s ，g r a m m a ra n a l y s i s ，a n d s e m a n t i c a n a l y s i s a n d ，w o r ds e g m e n t a t i o n i st h ek e ya n dp r e r e q u i s i t eo fo t h e ra s p e c t si n c h i n e s el a n g u a g ep r o c e s s i n g p a r t i c u l a r l yw i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e i nc h i n a ，c h i n e s ea u t o m a t i cs e g m e n t a t i o nb e c o m e sab a s i ci s s u e m a n yo r g a n i z a t i o n s s u c ha sc o m p a n i e s ，i n s t i t u t i o n sh a v es e tu pas p e c i a lr e s e a r c hd e p a r t m e n t ，h o p i n gt o b r e a kt h r o u g ho nc h i n e s ea u t o m a t i cs e g m e n t a t i o n a tp r e s e n tt h e r ea r ed o z e n so f a l g o r i t h m su s e df o rs e g m e n t a t i o n t h e yc a nb es u m m a r i z e di nt h r e ec a t e g o r i e s ： m a c h i n e r ys e g m e n t a t i o nb a s e do ns t r i n gm a t c h i n g ；s t a t i s t i c ss e g m e n t a t i o nb a s e do n i n f o r m a t i o n t h e o r y a n d p r o b a b i l i t y t h e o r y ；a n ds e g m e n t a t i o n b a s e d o n u n d e r s t a n d i n g a st h ec o m p l e x i t yo fc h i n e s e ，t h e r e a r et w om a i nd i f f i c u l t i e so n c h i n e s ea u t o m a t i cs e g m e n t a t i o n ，o n ei sa m b i g u o u sr e c o g n i t i o na n dt h eo t h e ri s u n k n o w nw o r dr e c o g n i t i o n t os o l v eap a r t i c u l a rd i f f i c u l t yb e c o m e sa ni m p o r t a n t i n d i c a t o ro fas e g m e n t a t i o ns y s t e mt oj u d g eag o o do n eo rab a do n e o t h e ri n d i c a t o r s i n c l u d e sa c c u r a c y , r e c a l la n ds e g m e n t i n gs p e e d t h eb e g i n n i n go ft h i sa r t i c l ei n t r o d u c e dt h em a c h i n e r ys e g m e n t a t i o n t e c h n o l o g y , s t a t i s t i c ss e g m e n t a t i o nt e c h n o l o g y t h e n ，ac 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 m ，w h i c h b a s e do ns u f f i x a r r a y a n dw o r d s t a b l e ，i s p r o p o s e d a n d i m p l e m e n t e d s u f f i xa r r a yi s at e c h n o l o g yi nt h ei n f o r m a t i o nr e t r i e v a lf i e l d t h e s y s t e mu s e ds a l m t o o l k i tt og e tal e x i c o ni n c l u d i n gh i g h - f r e q u e n c yw o r d sf r o mt h e c o r p u s a f t e ras i m p l el e x i c o np r u n i n gs c h e m e ，w ee m p l o y e db e r k e l e yd b t oo r g a n i z e t h el e x i c o ni n t oad i c t i o n a r y i nt h es e g m e n t a t i o np a r t ，w ef i r s tg o taw o r d st a b l eo f e a c hs e n t e n c e t h e nw ec o u l ds e g m e n tt h es e n t e n c e sa n dr e c o g n i z e dt h ea m b u g u i t i e s a c c o r d i n gt ot h et a b l e e x p e r i m e n tr e s u l t ss h o w e dt h a tt h es e g m e n t a t i o ns p e e dc o u l d a c h i e v e5 0 k b s ，a n dt h es e g m e n t a t i o na c c u r a c yc o u l da c h i e v ea b o u t9 0p e r c e n t s ot h e a b s t r a c t s y s t e mi sw o r t hf u r t h e rr e s e a r c h e do n f i n a l l y , w es u m m e du pb yt h ec o n t e n to ft h i sa r t i c l ea n da n a l y z e dt h ee x i s t i n g p r o b l e m si nt h es y s t e m ，a n dp r o p o s e dw a y st oi m p r o v e k e y w o r d n l p ， c h i n e s ew o r ds e g m e n t a t i o n ，s a l mt o o l k i t ， b e r k e l e yd b ， w o r d st a b l e ，w o r ds e g m e n t a t i o na m b i g u i t y i i i 目录 图目录 图2 1 切分词图。1 4 图3 - 1 分词系统设计图1 8 图3 - 2b e r k e l e yd b 子系统关系图。2 1 图3 - 3生成词典的流程图2 4 图3 - 4 后缀树示例2 5 图3 - 5 预处理流程3 2 图3 - 6 生成字词表3 6 图3 - 7 分词和歧义发现。3 7 图3 - 8 歧义解决流程。3 8 图3 - 9 系统框架图4 0 图4 - 1页尺寸大小与数据库大小的关系4 2 图4 - 2 缓存大小与数据库大小的关系。4 3 v i 目录 表目录 表3 - 1 “计算机软件专业和计算机应用专业”各字符的u n ic o d e2 7 表3 - 2 “计算机软件专业和计算机应用专业”的后缀数组s a 和l c p 数组2 7 表3 - 2 续“计算机软件专业和计算机应用专业刀的后缀数组s a 和 l c p 数组2 8 表4 - 1 页尺寸大小对读写性能的影响4 2 表4 - 2 缓存大小对读写性能的影响。4 3 表4 3 配置文件f r e q _ i c f g ( i = l ，2 ，8 ) 4 5 表4 4 配置文件f r e q _ i c f g ( i = l ，2 ，8 ) 对应的粗词典4 5 表4 - 5 过滤上限q 和下限b 对词典的影响。4 6 v i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：影易脚嘭 砂，舻年f 月7 r 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：渤谗左 莎年，月7 日 第一章绪论 第一章绪论 第一节论文背景的介绍与问题提出 1 1 1 自然语言处理 自然语言是世界人民长期智慧的结晶，而自然语言处理m l p ，n a t u r a l l a n g u a g ep r o c e s s i n g ) 是人工智能中最为困难的问题之一，对自然语言处理的研究 也是充满魅力和挑战的。自然语言是研究如何能让电子计算机理解并生成人们 日常所使用的语言( 如汉语、英语、同语) ，目的在于建立起一种人与机器之间 的密切而友好的关系，使之能进行高度的信息传递与认知活动。 就自然语言处理的形态来说，大概可以分为以下三类：分析、转换及生成。 1 分析( a n a l y s i s ) ：就是通过统计概率模型( s t a t i s t i c a lm o d e l s ) 、模式识别( p a t t e r n r e c o g n i t i o n ) ，机器学习( m a c h i n el e a r n i n g ) 等功能，去“分析”文字的内涵、 结构，理解一个文件的意思。 2 转换( t r a n s f e r ) ：分析之后，可以将它“转换”成另一种形式的有用信息， 作进一步的应用，比如转换成另一种评议的深层结构( 如机器翻译) ，或者 资料库。 3 生成( g e n a r a t i o n ) ：有时候，我们也会把某些有用的，但是比较抽象的信息， 用文字写出来，或者用语音说出来，这个过程就叫作“生成”或“合成”。 自然语言处理的研究可以回溯到电子计算机问世之初，并且在上世纪五十年 代初就开始了机器翻译的试验。当时的研究方法还不能称作带有“智能”。到了 上世纪六十年代，乔姆斯基的转换生成语法得到广泛的认可，生成语法的核心 是短语结构规则，分析句子结构的过程就是利用规则自顶向下或自底向上的句 法树生成过程。 由于认识到生成语法缺少表示语义知识的手段，在上世纪7 0 年代随着认知 科学的兴盛，研究者又相继提出了语义网络、c d 理论、格框架等语义表示理论。 这些语法和语义理论经过各自的发展，逐渐开始趋于相互结合。到上世纪8 0 年 代一批新的语法理论脱颖而出，具有代表性的有词汇功能语法( l f g ) 、功能合一 语法( f u g ) 和广义短语结构语法( g p s g ) 等。这些基于规则的分析方法可以称之 第1 页 第一章绪论 为自然语言处理中的“理性主义 。现有的手段虽然基本上掌握了单个句子的分 析技术，但是还很难覆盖全面的语言现象，特别是对于整个段落或篇章的理解 还无从下手。到了上世纪9 0 年代，随着互联网的发展，互联网为n l p 提供了市 场需求和试验数据，n l p 的研究方法转为统计方法并流行至今。 下面举一个n l p 的实例一一机器翻译： 1 输入的英文句子：m rs m i t hp u tt h r e ea p p l e so nt h i sd i n i n gt a b l e 2 形态分析( m o r p h o l o g i c a la n a l y s i s ) m r s m i t h p u t ( + e d ) t h r e e a p p l e + s o n t h i s d i n i n gt a b l e 3 句法分析( s y n t a c t i ca n a l y s i s ) s n pv p vn pp p m rs m i t hp u tt h r e ea p p l e so nt h i sd i n i n gt a b l e 4 词汇转换 先生m r 史密斯s m i t h 放p u t ( + e d ) 三t h r e e 书a p p l e + s 在上面o n 这t h i s 餐桌d i n i n gt a b l e 5 短语转换 一先生史密斯放三苹果在上面这餐桌 第2 页 第一章绪论 一史密斯先生放三苹果在这餐桌上面 6 生成 一史密斯先生放三苹果在这餐桌上面 一史密斯先生( 把) 三( 个) 苹果放在这( 张) 餐桌上面 7 最终翻译结果 一英文：m rs m i t hp u tt h r e ea p p l e so nt h i sd i n i n gt a b l e 一中文：史密斯先生把三个苹果放在这张餐桌上面 1 1 2 中文分词的提出 随着计算机和互联网的广泛应用，计算机可处理的自然语言文本数量空前 增长，面向海量信息的文本挖掘、信息检索、跨语言信息处理、人机交互等应 用需求急速增长，自然语言处理研究必将对我们的生活产生深远的影响。中文 是我们的母语。中文信息处理是我国实现二十一世纪信息化和现代化的必经之 路。目前，中文信息处理在字处理的层次上已经得到较好的解决，而词语、短 语、句子一级的处理能力仍然非常弱。于是，中文分词被提上了中国计算机信 息研究的同程中。分词就是将连续的字序列按照一定的规范重新组合成词序列 的过程。 举个例子看： 句子：我是一个中国人。 分词结果是：我是一个中国人。 我们知道，在英文的行文中，单词之间是以空格作为自然分界符的，而中 文只是字、句和段可以通过明显的分界符来简单划界，唯独词没有一个形式上 的分界符，虽然英文也同样存在短语的划分问题，但是在词这一层上，中文比 之英文要复杂的多、困难的多。 1 2 3 4 中文处理与英文处理的区别： 字集非常大，字码不统一。 同音字很多，注音或拼音输入有很大的歧义性。 字的排序没有一定标准( 通常依照笔画或部首顺序) 。 词的界线不明显，没有空格把词分开，多数应用需要先作分词( w o r d s e g m e n t a t i o n ) 。 第3 页 第一苹绪论 5 句子的界线也不明显，标点符号没有统一的标准，不像英文一样，一个句子 只有一个主要动词。 6 缩写词产生方式非常自由，具有相当程序的歧义性。 7 中文词序非常自由，同一个句子部分用词位置调动后，意思还是不变。 第二节中文分词的意义与应用 词是最小的能够独立活动的有意义的语言成分【l 】，所以对于中文来讲，将词 确定下来是理解自然语言的第一步，只有跨越了这一步，中文才能象英文那样 过渡到短语划分、概念抽取以及主题分析，以至于自然语言理解，最终达到智 能计算的最高境界，实现人类的梦想。中文分词对我们来说意义重大，可以沈 直接影响到使用中文的每一个人的方方面面。 中文分词主要应用于信息检索、汉字的智能输入、中外文对译、中文校对、 自动摘要、自动分类等很多方面。下面就以信息检索为例来说明中文分词的应 用。 通过近几年的发展，互联网已经离我们不再遥远。互联网上的信息也在急 剧膨胀，在这海量的信息中，各类信息混杂在一起，要想充分利用这些信息资 源就要对它们进行整理，如果由人来做这项工作，已经是不可能的，而如果面 对中文信息不采用分词技术，那么整理的结果就过于粗糙，而导致资源的不可 用，例如：“制造业和服务业是两个不同的行业”和“我们出口日本的和服比去 年有所增长”中都有“和服 ，而被当作同一类来处理，结果是检索“和服 的 相关信息，会将他们都检索到，在信息量少的情况下，似乎还能够忍受，如果 是海量信息，这样的结果就会令人讨厌了。通过引入分词技术，就可以使机器 对海量信息的整理更准确更合理，在“制造业和服务业是两个不同的行业”中 “和服”不会被当做一个词来处理，那么检索“和服当然不会将它检索到， 使得检索结果更准确，效率也会大幅度的提高。所以中文分词的应用会改善我 们的生活，使人们真正体会到科技为我所用。 第4 页 第一章绪论 第三节论文的主要内容 全文共分五章： 第一章介绍了中文分词的背景、意义和应用； 第二章先总结了中文分词算法的发展，比较详细地说明了机械分词和统计分 词，然后介绍了国内外在中文分词方面的研究成果，最后分析了中文分词存在 的难点； 第三章提出并实现了基于s a l m 模型、混合处理歧义的中文分词系统，具体 分析了词典模块和分词模块。尝试性地用后缀数组提取经过预处理后的生语料 库的高频词形成一个粗词典，再用词频信息裁减粗词典，去掉不当词语，生成 一个有效词成分较大的分词词典；分词模块对每个句子生成一个字词表，利用 字词表进行歧义发现和句子切分，对有歧义的句子采用最大句频原则切分。 第四章对系统进行实验，实验表明系统达到了预期目标。 第五章对本文进行总结和展望。 第5 页 第二章中文分词研究基础理论 第二章中文分词研究基础理论 从上世纪八十年代初北京航空学院实现了我国第一个自动分词系统 c d w s 1 】以来，各领域的众多专家、学者对中文文档的分词工作开展了大量研究。 经过不懈的努力，他们提出了许多自动分词方法【2 】【3 1 ，推动了中文分词研究迅速 发展，这是对研究初期对中文分词这一陌生领域持怀疑态度的人的回应。本章 重点介绍了中文分词算法的发展，以及目前国内外这方面的研究成果；另外， 还总结了中文分词系统的疑难杂症和评价标准。 第一节中文分词算法的发展 在过去近三十年的研究中，人们不断地提出各种理论和分词方法，使得中 文信息处理领域得以不断前进。目前的分词方法可以归纳为三种：基于词典的 机械分词、基于信息论和概率论的统计分词，以及基于理解的分词方法。第三 种分词方法由于汉语语言知识的笼统、复杂性，目前还处于试验阶段。所以下 文主要讨论前两种分词方法。 2 1 1 基于词典的机械分词 由于自然语言的计算机形式化工作非常困难，而且汉语的语法更为灵活、 复杂而不具规则性，使得目前比较实用和普通的分词方法都是属于基于词典的 机械分词。 1 机械分词的类别 机械分词方法又叫基于字符串匹配的分词方法，因为它是用字符串匹配的 原理，按照一定的策略将待分析的汉字串与一个“充分大的机器词典中的词 条进行匹配，若在词典中找到某个字符串，则匹配成功( 识别出一个词) 。 机械分词方法的要素是分词词典、扫描字符串的方向和字符串匹配的原则 岔筮 号手。 按照扫描字符串的方向的不同，机械分词方法可以分为正向匹配、逆向匹配 和双向匹配。所谓正向匹配，就是从待切分字符串的开头开始扫描，将之与分 第6 页 第二苹中文分词矽f 究基础理论 词词典的词条进行匹配。而逆向扫描就是从待切分字符串的末尾开始扫描。双 向扫描是把正向扫描与逆向扫描相结合，一般来说，先正向扫描再逆向扫描。 另外有研究表明，逆向扫描的切分准确率略高于正向扫描。因此，双向扫描的 歧义识别率较高。 字符串匹配的原则是指按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配、最小( 最短) 匹配和最佳匹配。最大( 最长) 匹配是一种局部最优法， 指每次匹配时，优先考虑较长的词；而最小( 最短) 匹配的目标是为了使待切 分字符串分词后得到的词数最少；最佳匹配是在分词词典中加入词条的词频信 息，词条按照词频大小排列，切分时选中词频最大的候选词。 按照匹配不成功时再次匹配的策略，机械分词方法又分为增字法和减字法， 其中增字法一般与最小匹配法相结合，减字法一般与最大匹配法相结合。 按照是否与词性标过程相结合，又可分为单纯分词方法和分词与标注相结合 的一体化方法。 2 有了上面的分类，我们现在来看看其中最为基础也最为常用的双向匹配 法( d o u b l ed i r e c t i o n a lm a t c h i n gm e t h o d ，d m m ) d m m 方法是正向最大匹配法( f o r w a r dd i r e c t i o n a lm a x i m u mm a t c h i n g m e t h o d f m m ) 和逆向最大匹配法( r e v e r s ed i r e c t i o n a lm a x i m u mm a t c h i n g m e t h o d 。r m m ) 的组合。 为了能清楚的描述问题，我们假设分词词典为d i c ，待切分语句为s t r , 它的长 度为s t r l e n ( 以汉字为单位) ，d i c 中最长词条的长度为m a x l e n ( 注：我们把分 词问题简单化处理，假设待切分的语句只包含中文字符) 其中f m m 的基本思想如下： 1 1 从s t r 中按正向( 即从第一个字符开始) 取长度为m a x l e n 的字串s u b s t r ， 所以有s u b s t r 的长度l e n = m a x l e n ，如果s t r l e n 等于0 ，则结束程序； 2 ) 在d i c 中匹配s u b s t r ，查找有没有与s u b s t r 匹配的词条； 3 1 若匹配成功，则s u b s t r 作为一个词被切分出来，即s t r 去掉s u b s t r 后， 然后返回步骤1 ) ； 4 ) 若匹配不成功，则把s u b s t r 去掉最后一个字后，即l e n = l e n 一1 ，然后返 回步骤2 ) ； r m m 方法的基本思想与f m m 相类似，具体如下： 1 ) 从s t r 中按逆向( 即从最后一个字符开始) 取长度为m a x l e n 的字串s u b s t r ， 第7 页 第二章中文分词研究基础理论 所以有s u b s t r 的长度l e n - - m a x l e n ，如果s t r l c n 等于0 ，则结束程序； 2 ) 在d i c 中匹配s u b s t r ，查找有没有与s u b s t r 匹配的词条： 3 ) 若匹配成功，则s u b s t r 作为一个词被切分出来，即s t r 去掉s u b s t r 后， 然后返回步骤l 、) ； 4 ) 若匹配不成功，则把s u b s t r 去掉第一个字后，即l e n = l e n 一1 ，然后返回 步骤2 ) ； 有统计表明，r m m 方法的精度要高一些，大概的错误切分率为1 2 4 5 ；而 f m m 的切分错误率大概为1 1 6 9 。因此聪明的人们把这两种方法结合在一起， 处理流程为：对待切分语句分别进行f m m 和r m m 处理，对得到的结果我们有 如下处理： 1 ) 如果f m m 和r m m 的切分结果相同，则它们的切分结果就是最后的结 果，因为我们没有其它选择； 2 ) 如果f m m 和r m m 的切分结果不相同，则我们要采取某些策略来选择 其中一种结果，作为最终的结果。常用的策略有人工干预、统计概率最 大等等。 下面我们举两个例子，更直观的理解这种方法： 1 ) f m m 和r m m 切分结果相同 待切分语名：今天早上我们去学校了 f m m 结果：今天早上我们去学校了 r m m 结果：今天早上我们去学校了 2 ) f m m 和r m m 切分结果不同 待切分语句：中国是世界上人口最多的国家 f m m 结果：中国是世界上人口最多的国家 r m m 结果：中国是世界上人口最多的国家 f m m 和r m m 的原理简单，易于实现，复杂度也比较低，但是它们受词条 的最大长度影响很大。汉语词语长度范围比较大，无法用一个确定的数表示， 但为了程序顺利运行，在程序中一般把长度设定为常数，若这个常数定大了， 程序的时间复杂度明显提高：如果定小了，不能切分长度超过它的词语，导致 切分正确率下降。 3 在这次完成论文的过程中，我特别注意了中文分词在搜索引擎中的作 用。在信息爆炸，互联网飞速发展的今天，人们查找信息的首选工具一定是搜 第8 页 第二章中文分词研究基础理论 索引擎，像谷歌( g o o g l e ) 、百度( b a i d u ) ，、中国搜索、y a h o o 等大型搜索引擎一直 是人们讨论的话题。目前搜索市场价值不断增加，越来越多的公司开发出了自 己的搜索引擎，如阿里巴巴的商机搜索、酷讯k o o x o o 的生活搜索等。 对搜索引擎来说，最重要的不是搜索到所有的结果，因为在上百亿个网页 中找到所有结果没有太大的意义，没有人能看得完所有的结果，其实最重要的 是把相关的、人们最想看到的结果放在最前面，这就是相关度排序。中文分词 的准确与否，常常直接影响到搜索引擎对结果的相关度排序。不过我们还是挺 好奇百度( b a i d u ) 和谷歌( g o o g l e ) 两大搜索引擎是用什么方法来分词的。中科院软 件所张俊林在( ( b a i d u 分词算法分析一文中提到，百度的分词系统首先用专有 词典采用j 下向最大匹配分词，切分出部分结果，剩余没有切分交给普通词典，同样 采取正向最大匹配分词，最后输出结果；而谷歌也是是采用正向最大匹配分词算 法，不过没有百度那样的专用词典，所以很多专有名词都被切分开了。 2 1 2 基于信息论和概率论的统计分词 机械分词方法虽然准确率比较高，但是需要一个大而全的词典作为保证。 一个词语其实是字与字之间稳定的一种结合，在一个中文文档样本( 可以称之 为语料库) 中，如果两个或几个相邻的字同时出现的次数越多，那么它们结合 成一个词语的可能性就越大。因此，字与字相邻共现的频率能够较好地反映它 们成词的可信度。随着科学技术的进步，人类拥有的语料库资料越来越多。在 十几年前，一百万的b r o w n 语料库，还被认为是巨大的；此后，更大的语料库 出现了，如拥有二千万词的b i r m i n g h a l n 语料库【4 1 ；而现在，谷歌研究院公布了 一个超大规模的5 g r a m 的语料库，它包含了从多达l ，0 1 1 5 ，8 2 4 5 ，3 2 1 3 个词 的语料中整理出的1 1 ，4 6 5 8 ，0 6 6 4 个出现过4 0 次以上的长度为5 的词，每个完 整的语料库要占用6 张d v d 5 1 。人类利用这些信息，加以挖掘，希望发现这些 数据内部隐藏的特有的规律，来支持人类的决策。 语料库分为生语料库和熟语料库。基于生语料库的统计方法有更强的适应 性。基于信息论和概率论的统计分词方法在这种背景下应运而生并逐步完善了。 s p r o a t 最早提出了通过使用信息论中互信息( m u t u a li n f o r m a t i o n ，m i ) 的概念来 实现分词【6 】。具体做法是计算相邻字符对的互信息，度量它们之间的相关性，然 后将互信息值最高的二字模型对从句中依次提取出来，直到所有的二字模型对 第9 页 第二章中文分词研究基础理论 抽取完毕。这种方法后来被c h e n 证明效果好于最大匹配法，并且所有互信息参 数是从生语料库训练得到的，不需要过多的人工干预。然而这种方法受字长限 制，没有统计三字及三字以上的关系。s u n 在此基础上引入了t - s c o r e 插值的统 计分词算法，找到多种情况下最可能的切分结果【刀。后来，r i ek u b o t aa u d o 提 出t a n g o 算法用于解决日文分词问题，该算法实现了二字模型到六字模型的统 计，取得了不错的效果。 统计分词的方法是使用e m ( e x p e c t a i o nm a x i m u m ) 算法【8 】训练语言模型，然 后使用v i t e r b i 动态规划算法【9 】【1 0 】查找最佳路径实现切分文本，反复迭代训练， 直到模型的参数收敛。 统计语言模型的优势就在于利用数学之美把一些复杂的问题变得简单。李 开复的成功之处就是在上世纪八十年代用统计语言模型把9 9 7 词语音识别的 问题简化成了一个2 0 词的识别问题，实现了有史以来第一次大词汇量非特定 人连续语音的识别系统s p h i n x 。 统计语言模型建立在概率统计和信息论的基础上，对大量语料进行统计， 揭示出语言内部特有的统计规律。常用语言模型有n g r a m 模型】、n m u l t i g r a m 模型1 2 】和隐马尔科夫模型等。 1 n g r a m 模型 n g r a m 语言模型是将语言中的字串( 词或者字) 的出现概率近似为( n 一1 ) 阶 马尔科夫模型。设有一个字串s 是w l ，w 2 ，w 3 ，w l ，那么w i 出现的概率只跟 它前面n - 1 个字有关，即： p r ( w iiw l w 2 w 3 m 1 ) p r ( w iiw l 一一+ 1 一w i i ) ( 2 1 ) 因此n g r a m 模型的数学定义如下： p “s ) = iip r ( w , 1w l w 2 w 3 w l 一- ) 兀p r ( w , lw l - n + 1 w i 一- ) ( 2 2 ) f = li = l 为了化简n g r a m 模型计算的复杂度，我们常常用字串在语料库出现的频率 来估计n g r a m 模型的参数，得到： p r ( w fm一。+lm1)freq(m-,+1a,w-1wi) ( 2 3 ) 。 f r e q ( w i 月+ 1 w i 1 ) 其中，f r e q ( * ) 表示字串幸在语料库中的频率。 例如，若s = a b c d e f , 则s 的概率为 p r ( s ) = p r ( fa b c d e ) p r ( ea b c d ) p r ( dla b c ) p r ( ca b ) p r ( ba ) p r ( a )( 2 4 ) 第l o 页 第二章中文分词研究基础理论 若n = 2 ，即为二元模型( b i g r a m ) 时，( 2 1 4 ) 式可简化为： p r ( s ) = p “厂id e ) p r ( ec d ) p r ( db c ) p r ( ca b ) p r ( ba ) p r ( a ) ( 2 5 ) 2 n m u l t i g r a m 模型 n g r a m 模型假设一个句子中固定长度为n 的各子串之问的某种统计依赖性， 后来人们提出另一个模型一一n m u l t i g r a m 模型，则假设一个句子中变长各子串 之间是独立存在的，于是，一个句子的概率就等于各个可能切分结果的概率之 和。 假设句子s - - - w ( 1 ) w ( 2 ) w ( t ) ，w ( 木) 表示一个字。l = s ( 1 ) s ( q ) 是s 的一个可 能切分，s ( 宰) 表示一个字串。那么，n m u l t i g r a m 模型认为，句子s 和切分l 的 联合概率等于切分l 中各子串( 最大长度为n ) 的概率的乘积，即 p r ( s ，三) ：n p “j ( f ) ) ( 2 6 ) = f 我们用 l 表示句子s 的所有切分的集合，那么整个句子s 的概率为： p r ( s ) = p r ( s ，l )( 2 7 ) 在n m u l t i g r a m 面向决策时，可以近似地把概率最大的那个切分作为s 的概 率，即 p r ( s ) _ m a x ( p r ( s ，三) )( 2 8 ) ，# ，i 、7 3 隐马尔科夫模型( h i d d e nm a r k o vm o d e l ，h m m ) 前面我们提到由于现实中问题的复杂性，我们往往很难把问题直接转换成 马尔科夫链来处理，于是马尔科夫模型被提出来。当马尔科夫模型的“状态 对外界不可见的时候，也就是说，我们所观测到的结果不是序列的状态值时， 马尔科夫模型就转换成了隐马尔科夫模型。隐马尔科夫模型在语音识别、词性 标注等领域有非常广泛的应用。它用来解决三个基本问题： 1 ) 对于给定的观察序列，它出现的概率是多大。 2 ) 对于给定的观察序列，在状态序列未知的情况下，根据现有的隐马尔科 夫模型，它最有可能的隐含状态序列是什么。 3 ) 怎样调整现有的模型参数，使得能最好的描述给定观察序列。 基于语料库的统计语言模型常用最大似然估计( m a x i m u ml i k e l i h o o d e s t i m a t i o n ，m l e ) t 1 3 1 和最大熵模型( m a xe n t r o p ym o d e l ，m e m ) j 吐, j t 模型求解。 语言模型虽然能很好的刻画语言的结构，但是一个给定的语料库所能给予 我们的数据信息毕竟是有限的，这就造成很多字串在语料库中出现的次数少， 第1 1 页 第二章中文分词研究基础理论 甚至根本没有出现，使得模型求解的参数可信度不高。这就是所谓的数据稀疏 问题【1 4 】。这种现象在语料库规模不大的时候，更为明显。例如，词性标注问题 中，共有1 4 0 个可能的标记，考虑当前词前后两个词的影响的3 - g r a m 模型时， 词性标注位置可能取到的值的个数为k = 1 4 0 1 4 0 1 4 0 = 2 ，7 4 4 ，0 0 0 ；给定一个 1 0 万词左右的人工标注训练集，即n = 1 0 0 ，0 0 0 。l n ，可见训练数据显得非 常不足。 解决数据稀疏问题的一个方法就是扩大语料库的规模，但是这种做法的效 果是有限的，因为语料库的规模到一定大小时，解决数据稀疏的能力就相对越 来越小了。因此，专家们采用某种方式对统计结果和概率估计进行必要的调整， 来降低数据稀疏问题带来的统计误差。常见的数据平滑方法有t u f i n g g o o d 估计 法、折扣模型、删除插值法等。 2 2 1 国内研究成果 第二节国内外分词研究成果 随着国内计算机科学的发展，人们越来越感受到中文自然语言处理的重要 性。因此，越来越多的科研机构增加了这方面的研究所。因为自然语言处理的 难度，再加上科研成果转化成生产力、创造财富的周期比较长，所以加入自然 语言处理的科研机构大部分是高校和巨头公司，其中高校包括中国航空航天大 学、重庆大学、东北大学、哈尔滨工业大学、中科院计算所等，公司包括微软 亚洲研究院等。目前国内比较成功的成果有： 1 中科院计算所i c t c l a s 1 5 】 中国科学院计算技术研究所在多年研究基础上，耗时一年研制出了基于多 层隐马模型的汉语词法分析系统i c t c l a 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 ) ，该系统的功能有：中文分词；词性标注；未登 录词识别。最新版本i c t c l a s 3 0 分词速度单机9 9 6 k b s ，分词精度为9 8 4 5 ， a p i 不超过2 0 0 k b ，各种词典数据压缩后不到3 m b ，是当前世界上最好的汉语词 法分析器。 汉语分词牵涉到汉语分词、未定义词识别、词性标注以及语言特例等多个 因素，大多数系统缺乏统一的处理方法，往往采用松散耦合的模块组合方式， 第1 2 页 第二章中文分词研究基础理论 最终模型并不能准确有效地表达千差万别的语言现象，而i c t c l a s 采用了层叠 隐马尔可夫模型( h i e r a r c h i c a lh i d d e nm a r k o vm o d e l ) ，将汉语词法分析的所有环 节都统一到了一个完整的理论框架中，获得最好的总体效果，相关理论研究发 表在顶级国际会议和杂志上，从理论上和实践上都证实了该模型的先进性。第 四十一届国际计算语言联合会( 4 1 s ta n n u a lm e e t i n go ft h ea s s o c i a t i o n f o r c o m p u t a t i o n a ll i n g u i s t i c s ，4 1 t ha c l ) 下设的汉语特别兴趣研究组( t h ea c l s p e c i a li n t e r e s tg r o u p o nc h i n e s el a n g u a g ep r o c e s s i n g ，s i g h a n ；w w w s i g h a n o r g ) 于2 0 0 3 年4 月2 2 同至2 5 日举办了第一届国际汉语分词评测大赛( f i r s t i