（计算机应用技术专业论文）基于蚁群算法的汉语自动分词的研究与实现.pdf

基于蚁群算法的汉语自动分词的研究与实现摘要 摘要 汉语自动分词是中文信息处理领域中的基础课题，其中，歧义切分的消除是 影响分词精度的关键问题。国内外很多学者在自动分词领域展开了富有成效的工 作，但在提高分词精度上，仍然存在着很大的困难。 我们研究发现，对于汉语自动分词，首先，必须对影响分词精度的语言。现象 作针对性的研究，做到对问题的实质从总体上把握；其次，必需考虑分词算法的 设计，建立分词模型，提高模型的计算能力；并研究在分词过程中提供更有效的 语言信息的度量。 本文在分词建模过程中，启发于蚁群算法在解决一系列复杂组合优化问题中 所表现出来的卓越性能，创造性地将蚁群算法模型运用到汉语自动分词问题中歧 义字段的识别和切分上面，通过汉语句子在内存中表示的数据结构的设计，构造 了我们的分词模型，以词频作为启发因子，巧妙的将纯粹分词问题转化为词的选 择问题，并从计算的角度，分别以绝对减值法和后备法给出我们相应方案的详细 设计。实验结果显示我们的基于蚁群算法的汉语自动分词方法是一个可行的解决 方案。 在统一的语料测试集上，我们就本文分词算法和中科院计算所的汉语词法分 析系统在歧义切分上做了一个全面的比较。并就分词知识从词频、语义信息层次 上展开了讨论，作出了展望。 关键字： 汉语分词；歧义切分；蚁群算法 作者：罗小虎 指导老师：吕强 r e s e a r c ha n d i m p l e m e n t a t i o n o ft h ec h i n e s ea u t o m a t i cw o r d s e g m e n t a t i o nb a s e d o nt h ea n t c o l o n ya l g o r i t h m 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 e i n f 0 1 t n a t i o np r o c e s s i n g t h ee l i m i n a t i o no ft h e s e g m e n t a t i o na r n b i g u i t yi st h ek e y f a c t o ra f f e c t i n gt h es e g m e n t a t i o np r e c i s i o n m a n yr e s e a r c h e r sh a v ep u tf o r w a r dm a n y m e t h o d so nt h i st o p i ci nt h ep a s ty e a r s b u ti nt h ei s s u eo f i m p r o v i n gt h ep e r f o r m a n c e o ft h ea m b i g u i t yr e c o g n i t i o na n d s e g m e n t a t i o n ，w es t i l lh a v em a n yh u g ep r o b l e m s a c c o r d i n g t oo u rr e s e a r c h w ef i r s t l y , b e l i e v et h ei m p o r t a n c e 血a tt h er e s e a r c h p e r t i n e n tt ot h el i n g u i s t i cp h e n o m e n o n sw h i c hw o r k so nt h es e g m e n t a t i o np r e c i s i o n ， s ot h a tw ec a nh a v ea g o o du n d e r s t a n d i n g o nt h ev e r ye s s e n c eo ft h ep r o b l e m w h o l l y s e c o n d l y , t h em o d e l i n go f t h es e g m e n t a t i o na n dt h ed e s i g no ft h ea l g o r i t h m ，w ef o c u s o nt h ee n h a n c i n go fc o m p u t i n g a b i l i t yo f t h es e g m e n t a t i o nm o d e l a n da l s ow eg i v e a ni n t e n s i v ec o n s i d e r a t i o no nh o wt om e a s u r et h e1 i n g u i s t i ci n f o r m a t i o nd u r i n gt h e p a r s i n g c o u r s e - a st h ea n tc o l o n ya l g o r i t h mw a sa p p l i e ds u c c e s s f u l l yt ot h ew e l l k n o w n t r a v e l i n g s a l e s m a n p r o b l e m ( t s p ) a n do t h e r h a r dc o m b i n a t i o n a l o p t i m i z a t i o n p r o b l e m s t h e a u t h o rt r i e st o a p p l y i tt os o l v et h ec h i n e s ea u t o m a t i cw o r d s e g m e n t a t i o nb yd e s i g n i n gt h ed a t as t r u c t u r eo ft h es e n t e n c e r e l i e do nt h ef r e q u e n c y o ft h ew o r da st h eh e u r i s t i cv a l u e t h i sp a p e rc o n v e r t st h ep u r es e g m e n t a t i o ni n t ot h e p r o b l e m o f t h es e l e c t i o no f t h ew o r d s m a r t l y a n dt w oc o m p u t a t i o n a lm e t h o d sa r ea l s o p r o p o s e di nd e t a i lt oa s s o c i a t et h eh e u r i s t i cv a l u ew i t ht h ep r o g r a mo f t h ea b s o l u t e d i s c o u n t i n ga n dt 1 1 eb a c k o f fa n d t h er e s u l t so ft h ee x p e r i m e n t ss h o wt h a to u r s o l u t i o ni sr i g h t o nt h et e s ts e to ft h eu n i f i e dl i n g u i s t i cr e s o u r c e s ，w eh a v em a d ea na l l a r o u n d c o m p a r i s o n b e t w e e nt l l er e s u l t so fo u rs o l u t i o na n d i c t c l a s s ( i n s t i t u t eo f c o m p u t i n gt e c h n o l o g y , c h i n e s e l e x i c a l a n a l y s i ss y s t e m ) o na m b i g u i t y s e g m e n t a t i o n a s 陆a st h es e g m e n t a t i o np r e c i s i o ni sc o n c e r n e d w ea l s og i v ea d i s c u s s i o no nt h e s e g m e n t a t i o nk n o w l e d g ea b o u tt h ef r e q u e n c ya n dt 1 1 e s e m a n t i c i n f o r m a t i o no f t h ew o r d k e y w o r d s ：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 n ；a m b i g u i t ys e g m e n t a t i o n ； a n t c o l o n ya l g o r i t h m ； 2 w r i t t e nb yl u ox i a o h u s u p e r v i s e db y l v q i a n g y 6 4 5 7 47 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：孥! 匿 日 学位论文使用授权声明 期：矿p v 。￥一巧矿 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏卅l 大学学位办办理。 研究生签名： 导师签名： 期：塑兰二z 二堡 期：型! 二! 二翌 基于蚁群算法的汉语自动分词的研究与实现第一章引言 第一章引言 汉字在计算机内部是以机内码的形式存储和传输的，中文信息处 理就是基于对汉字机内码的处理。处理的信息除了单个汉字外，词才 是自然语言中有意义的、可以独立运用的最小单位。汉语文本和西文 不同，词与词之间没有明显的分隔标记。而中文信息处理诸多重要的 应用领域：如汉字输入、语音合成、简繁转换、文本校对、文献检索、 机器翻译、篇章理解等都要求至少建立在词这一平面上。因此，汉语 自动分词是中文自然语言处理系统必须面对的第一道基本“工序”， 只有对汉语文本进行正确无误的分词，才有可能满足上述各应用领域 的要求。实践却表明，分词已成为中文信息处理的“瓶颈”，我们只 有逾越这个障碍，中文信息处理系统才称得上打上了“智能”的印记， 构建于词平面之上的各种后续语言分析手段才有展示身手的舞台。 1 1 研究背景 国内第一个实用性分词系统，是北京航空航天大学在1 9 8 3 年设 计的c d w s t ，采用无回溯最大匹配法，并辅以词尾字构词检错技术， 使用知识库纠错，这是汉语自动分词实践的首次尝试，具有很大的启 发作用和理论意义。该系统比较科学地阐述了汉语中的歧义切分字段 的类别、特征以及基本的对策。自此，科技工作者主要把精力集中在 下面两个方面：分词算法设计和汉语歧义字段的语言研究。 在分词算法设计上，大致可以分为以下两类。一类旨在提高分词 的切分精度。对于这个问题，研究人员几乎动用了人工智能领域所有 “时髦”的计算手段。文献 2 1 提出了一种改进的最大匹配分词方法： 正向扫描+ 增字最大匹配( 含跳跃匹配) + 词尾歧义检查+ 归右规则( 对 连续型交集，需左部结合) 。这种方法，对于某些类型的歧义，虽然 可以取得正确的切分结果，但势必又造成了其它类型歧义的切分错 误。如例句“原子结合成分子”，由上述算法可获得正确的切分结果； 对于“当原子结合成分子时”必须先把由介词或连词形成的“框型” 第一章引言基于蚁群算法的汉语自动分词的研究与实现 “当时”切分出来，才能获得正确的分词结果，而汉语是表意语 言，非常灵活，要正确无误地识别出这些“框型”，语言成分的基础 研究就不足：对于“原子结合成分子时，”，因无法识别“框型” 而得出了错误的分词结果。另一种方法是把正向最大匹配方法和逆向 最大匹配方法结合起来使用，称为双向最大匹配法。结果发现，9 0 左右的句子，正向最大匹配法和逆向最大匹配法切分重合且完全正 确；9 左右的句子，两者虽不同，但必有其一是正确的；只有不到 1 的句子，要么两者切分重合，却是错误的，要么两者切分虽不相 同，但没有一个是正确的。以上数据说明，双向最大匹配法具有较高 的歧义切分检测能力，这正是其在实用中文信息处理系统得以广泛使 用的原因。文献p 】对文本利用词库进行双向最大匹配分词，标出歧义 型字段，然后利用二元语法或三元语法对其进行处理，取得了良好的 效果。文献【4 】提出了一种汉语文本切分和词性标注相融合的一体化分 析的统计模型，由于词性标注等方面的基础研究工作不足，初步性开 放测试效果较好，而实用性有待验证。文献【5 】利用句子内部相邻字之 间的互信息及t 测试差这两个统计量来切分交集型歧义字段，缺点 是需要事先通过对语料的统计来获得任意两个汉字的同现概率，而这 些统计量的潜力有待进一步挖掘。文献1 6 n 尝试利用神经网络模拟人 脑思维来处理歧义切分问题，缺点是受训练语料选取的限制，离实际 应用还有很大的差距。此外，文献1 8 j 给出了汉语自动分词的专家系统 设计原理；文献1 9 j 提出了一种基于由极大似然原则构建的汉语自动分 词的零阶马尔可夫模型，并重点剖析了e m 算法；文献【10 】则根据汉 语歧义字段的长度的比例分布，有针对性的提出了一种消解中文三字 长交集型分词歧义的算法，回避了训练代价比较高昂的词性信息，仅 仅利用了词的概率信息及某些具有特定性质的常用字集合，取得了较 好的消解正确率。 另一类分词算法旨在提高切分的速度，从分词的实际应用出 发，着眼于如下两个角度：一是分词词表的构造，二是分词过程中的 匹配方法。文献【l l 】的词表结构为词首字h a s h 索引，同首字词条可顺 序查找，时间复杂度为2 8 9 。文献【1 2 】利用汉语中两字词占7 5 的统计 规律，提出了两字词根和两字词簇的概念，把三音节以上的词用两字 基于蚁群算法的汉语自动分词的研究与实现第一章引言 词簇来压缩处理，提高了分词的速度。文献1 13 j 在此基础上，设计出一 种高效的电子词表，支持首字h a s h 和标准的二分查找，进而提出一 种改进的快速分词算法，在快速查找两字词的基础上，利用近邻匹配 方法来查找多字词，该算法的时间复杂度理论上为1 6 6 。文献 1 4 1 则根 据多级内码的设计理论，提出了一种并行分词方法。 以上种种努力，从各个角度体现了人们对汉语自动分词的探索和 尝试的不同方面，在各自研究范围内取得了相应的效果，做出了应有 的贡献。在汉语歧义字段的语言研究方面，文献【lj 的作者粱南元最早 对这种语言现象进行了比较系统的考察和归纳。他定义了两种基本的 切分歧义类型。交集型切分歧义串：汉字串a s b ( a 、s 、b 为汉字 串) 中若a s 、s b 同时为词；组合型切分歧义串：汉字串a b ( a 、b 分别为汉字串) 中若a 、b 、a b 同时为词。文献l l5 j 中作者进一步指 出，切分歧义应区别“真歧义”和“伪歧义”并整理出一张歧义切分 类型表。同时，文献作者在考察了一个极大规模的汉语语料库的基础 上，提出了最大交集型歧义切分字段的概念并根据其频率分布的特 性，发现高频部分表现出相当强的覆盖能力及稳定性，给出了一种基 于记忆的，高频最大交际型歧义切分字段的处理策略。上述研究成果 加深了我们对歧义字段理解的深度，拓展了我们的视野，对歧义字段 的处理具有指导意义。 可以看出，自国内推出第一个分词系统以来，人们在这个研究领 域做出了巨大的努力，取得了可喜成绩。同时，在实践中，我们也深 刻地认识到，如果没有足够的语言知识作为支撑，汉语自动分词很难 有大的突破，这不仅体现在歧义切分上，而对于人名、地名、专业术 语等词表中未出现的词，其识别和切分就更加困难。1 9 9 5 年，国家 科委组织了8 6 3 智能机专题自动分词评测。开放测试条件下的评测结 剁1 6 】是：分词精度最高为8 9 4 ，交集型切分歧义处理的正确率最高 为7 8 0 ，组合型切分歧义则为5 9 o ，而未登陆词识别的正确率， 人名最高为5 8 o ，地名最高为6 5 o 。评测数据说明，面对分词这 第一道工序，距离真正意义的实际应用还有一段路，我们还需要付出 艰苦，细致的努力，在前人的基础上做进一步深入的研究。 第一章引言基于蚁群算法的汉语自动分词的研究与实现 1 1 1 本文研究的意义 利用计算机来处理自然语言是一门前景广阔的学科，如本文引 言中所述，应用领域更是遍布我们日常生活的各个角落。且当前的大 环境令人鼓舞：我国正在向信息化社会迅速前进，突出表现为国际互 联网上中文网页的急剧增加和中文电子出版物、中文数字图书馆的迅 速普及。如何从这些浩如烟海的信息资源中获得用户想耍的数据，如 何进行高效率人机交互，关键一点是计算机要能够正确处理人类语 言。在这一点上，中文信息处理的现状距离目标：大规模真实文本的 处理，还相距很远。 在字处理层面上，除了对其进行统计外，我们已不可能做得更 深入。不用说对句子的语言成分和结构进行分析，甚至是篇章一级。 而词语能够表达完整的语言成分的意义，所以说，我们必须把句子切 分为词的序列，除此之外，别无他途。且这个过程完成的好坏直接影 响到信息系统的质量。 从前面研究背景中可以看出，目前的汉语分词系统，从总体上 来看，还嫌粗糙，分词过程中提供的信息有限。有些系统，研究的比 较充分，但模型本身的计算能力偏弱，获得的计算机语言成分不够准 确和充分。而汉语自动分词在国内一直是研究的热点，对于中文信息 处理中词法分析后续的语法及句法分析、语义和语用分析等有决定性 的作用。 所以，我们需要在汉语分词模型的建立上作进一步深入的探索， 另外，句子的信息结构、数据的组织等也是我们今后的研究方向。例 如，分词的过程中，除词频、词性外，可以考虑综合运用词语的语音， 词语和词语的相关性等等。这方面，国内的研究和应用还不是很多， 目前主要是通过后续的语言成分的分析来纠错，这无疑增加了句法分 析的负担和工作量。如果能在分词的过程中更加充分地运用词语的语 义信息，那么对于分词的后续处理，将会产生积极的影响。 基于蚁群算法的汉语自动分词的研究与实现第一章引言 1 1 2 本文研究的难点 目前，绝大部分汉语自动分词系统【l 】【2 【1 2 】是基于分词词表的 形式分词。由于词概念的模糊对词的界定缺乏度量的标准，导致分词 结果同样缺乏可比性，其突出表现为下面几个问题。 ( 1 ) 词表的收词问题。我们认为，面向具体应用领域的分词系统的 词表应是：通用词表和由领域词汇组成的词表的集合。尤其对于通用 词表，需要充分考虑词和词组的收录，我 f l j g i w 道“中华人民共和国” 是专有名词，有特殊的意义，应该作为一个独立的词，像“中华人民 共和国公司法”、“中华人民共和国民法通则”等词组是否应该作为独 立的词条而收录词表则值得推敲。 ( 2 ) 词的变形结构问题。汉语中，词的变形结构现象让我们对词的 概念和界定更难把握，如“打牌”，我们经常说成“打打牌”，这种情 况很多，类似的例子还有“开开心”、“看没看见”、“相不相信”等。 ( 3 ) 词缀问题。语素“者”在现代汉语中单独使用是没有意义的， 因此，“马克思主义者”、“作者”、“开发者”、“成功者”录入词典的 话，毫无疑问“手工业者”也应录入词典。但语素词还有一个修饰范 围的问题，对于“作出重大贡献者”等短语或句子，语素词应和其直 接前趋的词作为整体来考虑，才符合语言规范，这样的语素词还有 “长”、“家”等。 ( 4 ) 形如“数词+ 量词”构成的词。对于这种类型的词，其完整的 组合才有意义，而把它们单独分开来是毫无意义的。且这种形式的词 是无穷尽的，词典也不可能完全收录。 ( 5 ) 对于由介词、助词、连词等构成的频率较小的词的收录问题。 这种词的引进很可能会增加以后歧义切分的负担。还有其它一些情 况，比如，多音字引起的歧义等，都需要我们给以充分的考虑。 若单独从机器的角度来看待汉语“词”的话，作为汉字串的词， 在文本中应不断的重复出现，若是很久都没出现的话，将之作为“词” 是没有意义的。文献【1 7 】基于这种思想提出了汉语语言的无词典分词模 型，该算法思想的一个优点是能发现文本中的“新”词，这对某些专 业应用领域是大有好处的，但其明显的不足是对词表中一些常用词， 第一章引言基于蚁群算法的汉语自动分词的研究与实现 切分精度低，算法复杂，时空开销大【l 7 1 ，加之该算法模型较粗糙，有 很多地方需要改进，基于词表的分词方法仍是大家的首选。 另一个突出的难点就是分词算法的设计，分词算法是建立在分 词模型基础上的。首要的是分词模型的建立，而在其可行性论证上， 目前我们还做不到；其次，在模型建立的探索过程中，我们需要综合 考虑上述提出的五个问题，对于( 3 ) 和( 4 ) ，需要有词的联想和推理的 机制；再次，着重考虑汉语歧义字段的识别和歧义切分的度量。 1 1 3 本文研究目标 双向最大匹配法以其算法简单，容易实现，成为一种通用的分词 方法。文献【1 8 1 提出了一种“全切分”的思想，穷举所有可能的切分， 消除了双向最大匹配法中歧义盲区检测的影响，但造成了可能切分词 组合数的爆炸，这个问题直到现在还未解决。上述两种情况，种最 简单，而另外一种最复杂。 鉴于双向最大匹配法和“全切分”模型的粗糙、计算能力比较弱、 提供的分词信息少等特点，以及“全切分”所导致可能切分个数的无 理膨胀等不足，本文作者在对利用蚂蚁算法1 19 j 求解组合优化难题做了 大量研究后，针对其在解决t s p t 2 0 】( t r a v e l i n gs a l e s m a np r o b l e m ) 问题 中表现出来的卓越性能，以及其后成功应用于一系列复杂的组合优化 难题，如：图着色问题1 、2 1 2 件排序问题、大规模电路设计问题 等。本文作者受到启发，对汉语分词重在进行计算模型的构造，在“全 切分”基础上，对数据进行有效地组织，实现无盲区的歧义切分的检 测，并提供一评价函数，用来度量汉语分词结果，并总结我们的研究， 提出改进目标。 基于蚁群算法的汉语自动分词的研究与实现第一章引言 1 2 本文综述 汉语自动分词是中文信息处理中的基础课题，在中文信息处理中 占据着相当重要的地位。国内同行在这个研究领域做了大量基础性工 作。由于汉语语言本身的复杂性；加上语言知识的基础研究不足；同 时，在利用计算机处理自然语言上，我们所能提供的手段有限等等， 导致在分词这个领域上，还存在着很多困难。 其中，对于汉语自动分词中歧义的识别和度量，本文作者利用大 自然生物世界中新兴的仿生类算法一蚂蚁算法进行语言模型的构造。 就词频启发因子从多个角度讨论了我们的设计思路，给出了实验的结 果，分析、比较并做出了展望。论文的结构安排如下： 第一章介绍汉语自动分词的背景，研究目标。主要内容是：从 不同的角度简介分词已有的研究，分析其中存在的困难，并提出了我 们的目标。 第二章汉语分词研究综述。主要内容是：从分词方法的角度介 绍各自优缺点和存在的问题。 第三章介绍蚁群算法模型。主要内容是：基本蚁群系统、蚁群 算法优缺点和应用及优化。 第四章介绍蚁群算法在汉语自动分词中的应用。主要内容是： 汉语分词模型的构造：数据结构的设计；并从多个角度给出我们的计 算方案。 第五章评价分词算法的结果。主要内容是：对同- - i i 试集上， 以中科院计算所汉语词法分析系统中的分词模块的切分结果为参照， 着重就分词切分的精度进行比较，分析存在的问题并做出改进。 第六章对论文的总结和展望。主要内容是：展望今后的工作和 研究方向。 第二章汉语分词概述基于蚁群算法的汉语自动分词的研究与实现 第二章汉语分词概述 汉语自动分词过程可描述为：输入含有若干个汉字的待处理字串 c ”= c l c 2 c ，c 。( c 。为汉字，ie 【1 ，”】) ，经过机器分析处理，输出词 串w “= w 1 w 2 w j w 。，( w 为汉语词语，j 1 ，m 】) 。考虑到汉语单 字词的特点，有m n 。其中，分词方法可概括为传统的机械式分词 方法；基于统计的分词方法和基于知识的分词方法。 我们的工作是建立在前人大量的研究基础之上的，在下文中，就 汉语分词的方法做简要回顾。 2 1 机械分词 机械分词又称为形式分词1 2 1 1 ，是指借助于分词词典，基于字符串 匹配的原理。分词过程中，按扫描的方向可分为正向扫描、反向扫描 和双向扫描三种；按匹配的原则可分为最大匹配法和最小匹配法；这 两种方法按匹配过程中增字和减字又可以分为下面两种类型。文献【2 2 】 中作者引用了揭春雨给出的机械分词方法形式化描述模型d a m ( d ， a ，m ) ，表述如下： d d = + l ，1 ) ，+ l 表示正向，一1 表示反向 a a = + 1 ，1 ) ，+ l 表示增字，1 表示减字 m m = + 1 ，1 ) ，+ 1 表示最大匹配，一l 表示最小匹配 对这个模型，一般来说，增字法和最小匹配法相结合，减字法和最大 匹配法相结合。 其中，d a m ( + l ，l ，+ 1 ) 的基本思想是：根据词典中词条的最 大长度，取汉字字符串的前若干个汉字作为匹配字段，查分词词典， 若能匹配，则将这个匹配字段切分出来：若不能匹配，就去掉该匹配 字段的最后一个汉字，得到颞的匹配字段，重复以上过程，直到匹配 为止。d a m ( - l ，- l ，+ 1 ) 和d a m ( + l ，一l ，+ 1 ) 类似，只是从字符 串的末端开始。实验表明，d a m ( - 1 ，- l ，+ 1 ) 的切分正确率高于 d a m ( + i ，一1 ，+ 1 ) ，为了便于发现歧义，常将两者结合起来使用， 基于蚁群算法的汉语自动分词的研究与实现第二章汉语分词概述 构成双向最大匹配法，由于它们对词库的组织有不同的要求，需要考 虑电子词表的构造。而不管哪种最大匹配法，由于是一种减字匹配过 程，它们的弱点有：( i ) 分词过程中可利用的信息少；( 2 ) 基于长词优 先，对词典中词条的收录有较高的要求，否则因分词的结果粒度太粗 而不符合应用需求。反之，对于d a m ( x ，+ 1 ，一1 ) ( x 一1 ，+ 1 ) ) ， 由于大多数汉字可以单独构成词，直接后果将导致分词结果中大量单 个汉字词的产生。由于分词粒度过细，这种方法不被采用。 机械分词中的最佳匹配法1 实际上可以归并到d a m ( x ，一1 ，+ 1 ) ( x 1 ，+ 1 ) ) 。其原理只是对分词词典中的词条按词频排序，缩 短对词典的检索时间，提高分词速度，是对最大匹配法的一种改进， 在算法本质上没有做多大的改动。 机械分词中的逐词遍历法1 ，其原理是将词典中的词，按由长到 短的顺序，逐个在待处理的文本中逐字搜索，直到字符串结束。也就 是说，不管待切分的字符串的长短，也不论词典容量的大小及词典中 词的长度的分布，都要将词典遍历一遍。显然，这种方法因时间响应 受到很多应用的限制。 实践中，有些学者从汉语中某些汉字构词能力的角度出发，将构 词能力差的一些汉字作为切分标记而首先分出来，这种方法称为切分 标记法或特征词库洲2 引。因其额外的搜索开销，不但无助于提高分 词的速度，对于切分精度更是适得其反，在文献【2 2 】中，作者同样引用 了揭春雨的证明结果。 其中，实用的方法是机械分词加歧义校正法，这是一种对机械分 词方法的改进，用来提高分词的精度。这里，用以歧义校正的方法有 多种。在文献 1 2 3 4 中，虽使用的方法各不相同，却也能在不 同程度上提高分词的精度。 值得一提的是，在机械分词中，有一种最短路径分词方法【”1 ，也 称为最少分词法【2 4 1 。它将分词问题归为图论中的最短路径问题，一个 词对应于图中的一条有向边。对于待切分的汉字串，分词闯题就是要 在这个串上找到一个对应词的序列。这样，图论中的有关算法为我们 提供了求解这个问题的有力手段。这种方法，分出的词最少，相对于 局部最优法一最大匹配法，它是一种全局最优法。 第二章汉语分词概述基于蚁群算法的汉语自动分词的研究与实现 以上我们详细回顾了机械分词原理和几种典型的基于机械分词 原理、从各个不同角度作出改进的分词方法。其中，有的已经广泛应 用于各种软件系统。还有其它一些方法，如单扫描分词方法【1 1 1 、约束 矩阵法2 3 1 等。对于机械分词，它们的一个共同特点就是只孤立考虑词 的形式，因而难免存在局限性。 2 2 统计分词 统计分词以概率论为理论基础，将汉语文本中汉字串的出现抽象 为一随机过程，其中，随机过程中的参数可以通过大规模的汉语语料 库来训练得出。其模型的形式化描述如下： p ( w ”i c “) 表示汉字串c “切分为w “的某种估计概率，t l ， t ：，t k 表示c “所有可能的切分方案。基于统计的分词方法就是 唯一的目的词串w “，满足下式： p ( w ”i c “) = m a x ( p ( t ii c “) ，p ( t 2 i c “) ，p ( t k i c o ) ) 即估计概率最大的词串，p ( w “i c “) 为评价函数。 根据贝叶斯公式有： p ( w “lc o ) = p ( w ”) p ( c “iw “) p ( c “) ，对一特定的汉 字串来说，p ( c “) 为常数，而p ( c “iw “) 表示在给定词串w 的 条件下字串c “的概率，是一必然事件，故p ( c “iw ) = l 。 上式可简化为：p ( w ic “) p ( w “) 。 对p ( w “) ，可如下展开： p ( w ) = 兀。p ( w ，1w ，w ：一w 。) 对于上式，不难看出，为了预测词w 。的出现概率，必须已知它前面 所有词w l ，w 2 ，w i ，w m - l ( j = l ，m 1 ) 的概率。在计 算上，这不仅太复杂，而且语料资源也极度贫乏。上述中，若规定任 意一个词的出现只和它前面出现的n 1 个词有关，我们把这种量化后 的语言模型称为n 元模型( n g r a m ) 。实际使用通常取n = 2 或n = 3 的二元模型( b i g r a m ) 或三元模型( t r i g r a m ) 。以二元模型为例，有： p ( w ”) = 兀，：h p ( w ，iw ，一) 即当前词的 出现仅和它的直接前趋词有关。 基于蚁群算法的汉语自动分词的研究与实现第二章汉语分词概述 即使经过这样的简化，若我们的词汇集的大小是三的话，当前词 的历史数据的大小也就为。在这种不同的历史情况下，模型中产 生当前词的自由参数就有个p ( w i i w ) ，我们的训练数据中根本 就没有这些参数。这种情况对于三元模型来说，更加突出。然而，n 越大，表示词之间关系越紧密，模型也越精细。在实际应用中，对于 工程性项目，我们一般采用一元模型或二元模型；对于研究型课题， 则使用三元模型。文献【2 5 】中，作者介绍了这种基于n 元语法的汉语 统计分词模型，以及该模型在不同资源要求下的实现方法。文章进一 步指出，利用n g r a m 直接估计p ( w ) 的方法，在目前是不可行的。 大多数基于统计的分词模型都是采用各种各样的估计方法，从不同的 角度，实现对p ( w “) 的近似。同时，文章也给出了利用词的等价 类：词性与词性的关系来近似词与词之间的关系的理论依据和数学推 导，把切分模型和标注模型结合起来，并给出了这些方法的切分速度、 切分精度、排歧能力和相应的实验结果。这种方法理论上值得借鉴， 但实现起来，具有很大的难度，而且是建立在熟语料库上的，训练代 价高昂，词性信息对解决分词歧义意义并不大【l0 1 。另外，许多学者就 n g r a m 中到底是基于汉字还是基于词分别展开了讨论，文献1 2 6 1 中作 者提出了一种基于字符的n g r a m 分词模型，同时结合机器学习的自 组词算法实现文本的切分，相对与词来说，g b 2 3 1 2 - 8 0 中汉字6 7 6 3 个，系统开销小，简单且容易实现。但在分词精度上，文献【2 “、文献 1 2 7 1 的分词结果说明，建立在丰富语料样本的情况下，基于词的分词精 度要优于基于字的n - g r a m 分词的精度。 上述的n g r a m 称为n 阶马尔可夫模型，描述了一类重要的随机 过程。其中，每一个状态代表了一个可观察的事件，这限制了模型的 适用性。如果观察到的事件是状态的随机函数的话，这中间就有一个 双重随机过程，其中模型的状态转换过程是隐蔽的。我们把这种状态 转换过程称为隐马尔可夫模型( h m m ) 。在计算语言学中，几乎所有 高性能的语音识别系统均采用h m m 来建模，其最成功的应用是用来 进行分词 9 1 甭1 1 词类标识，如中科院计算所的汉语词法分析系统。 第二章汉语分词概述基于蚁群算法的汉语自动分词的研究与实现 2 3 知识分词 知识分词与机械分词方法以及统计分词方法的根本区别在于它 不仅仅只是通过词典匹配，而且还要利用词法、句法甚至语义等方面 的知识。知识分词不但利用知识的范围更广，而且还利用人工智能技 术进行推理。并且将分词过程与“歧义校正”过程合二为一，而不是 像机械分词或者混合法分词那样先分词再校正。 文献【剐中介绍的书面汉语自动分词专家系统是一种典型的基于 知识的分词系统，主要分为两大模块：知识库的组织与实现、推理机 制与自动分词过程。系统力求从结构与功能上分离分词过程和实现分 词所依赖的汉语词法、句法以及部分语义知识。这样，更利于知识库 的管理与维护。 对于分词的知识，由于本身不完备；在组织上，只是对其简单的 罗列和叠加。这样就显得一方面在分词过程中缺乏知识：另一方面， 知识库又显得庞杂。在利用分词知识进行歧义切分的推理过程中，又 存在着分词知识的冲突和矛盾，缺乏有效的消解机制。所以，知识分 词往往在受限语言资源下能表现出较好的性能，对于开放的大规模真 实文本的处理，效果却不理想，达不到实用的水准。 2 4 小结 本章，作者对国内各种汉语自动分词系统做了深入研究后，结合 本人的工作，就分词方法在实现原理上，给出了系统的介绍。同时， 对每一种分词方法，作者例举了大量分词系统的实例，并对这些实例， 从实现及实用上作出了全面的分析和比较，阐述了各种分词方法应用 的场合和存在的问题。这说明，要提高汉语分词的精度，需要我们从 其它的角度，包括汉语分词模型，给出新的尝试和努力。 基于蚁群算法的汉语自动分词的研究与实现第三章蚁群系统模型 第三章蚁群系统模型 蚂蚁算法 1 9 1 ( a n ta l g o r i t h m ) 是一种源于大自然生物世界中新的 仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的 行为特性，通过其内在的搜索机制和蚂蚁间的协作机制，在一系列困 难的组合优化问题求解中取得了成效。由于模拟仿真中使用的是人工 蚂蚁的概念，因此，我们亦称之为蚂蚁系统，或蚁群系统。 3 1 基本蚁群算法 蚁群算法最早成功应用于t s p ( t r a v e l i n g s a l e s m a n p r o b l e m ) 问题。 其核心思想是蚂蚁在走过的路径上留下信息素，蚂蚁根据信息素的多 少来选择走哪一条路，而信息素的增多又增加了其选择该路径的概 率，这是一正反馈问题。 下面，我们以t s p 问题为例来说明基本蚁群算法的原理1 3 7 j ：设 共有n 个城市，蚁群中有m 个蚂蚁。一般将这m 个蚂蚁平均分布 到n 个城市上。d i i 表示城市i 和j 之间的距离，在本问题中，以i d i 作为各蚂蚁的启发因子。蚂蚁在连接两个城市之间的路径上留下了信 息素，我们以f 。( t ) 表示在t 时刻城市i 和城市j 之间残留的信息 素。设s 为全集，l s l = n 。在t 时刻我们得到第k 个蚂蚁的部分解集 c l o s e k ( t ) = y b y 2 ，y j ，最近加入到集合c l o s e ：k ( t ) 中的元素为y j ，我们 在寻找下一个元素y p 的过程中，主要是根据元素y 。和y p 之间概率p p ， p j p 。( t ) = r j p a ( t ) r j p 卢( t ) ，。即f ) v ( t ) 7 7j ，卢( t ) p o p e n k ( t ) ( 1 ) 0o t h e r w i s e( 2 ) 上式中，7 7j p ( t ) 为1 d j p 。把具有最大概率p j p 的元素y p 加入 到c l o s e k ( t ) 中，下一次，蚂蚁k 就以y j + l 为起点，在o p e n k ( t ) 表( 下 ，i，、，l 第三章蚁群系统模型基于蚁群算法的汉语自动分词的研究与实现 一步允许走过的城市的集合，在蚂蚁k 的行进过程中动态改变) 中继 续寻找使概率p j + 1 ，q 最大的元素y q 。行进过程可用下图来表示： ( ：i 滟 第j 时的 p e n k ( t ) 图3 1 其中，信息素彳i 。( t ) 随时间的推移会逐渐衰减，用p 表示信息 素的持久性( 1 p 0 ) 。依次类推，达到目标状态时有l c l o s e k ( t ) l = n 。 由此可以看出，蚂蚁不断地选择下一个城市的过程是一有序搜索的过 程，c l o s e k ( t ) t 9素的顺序体现了蚂蚁所走过的路径。第j 步状态如 下图1 所示： p c j + 1 ，j + 2 ，n ) ，q j + 2 ，j + 3 ，n 经过n 个时刻，蚂蚁可走完所有的城市，完成一次循环。此时， 需要根据下式对各路径上的信息素作更新： r 印( t + 1 ) = p r 庙( f ) + z - 扫 ( 3 ) 其中 晦= ：，a r p ( 4 ) f 加“表示蚂蚁k 在本次循环中，在城市j 和p 之间留下的信息素， 其计算方法根据具体的计算模型而定。在最常用的a n tc y c l es y s t e m 模 型中： “= m t ( 5 ) o 为一常数，厶为蚂蚁k 在本次循环中所走路径的长度。公式( 1 ) 中口和分别表示对不同因子的作用，对于参数0 5 、q 、p ， 可以用实验方法确定其最优组合。 这样，蚂蚁个体之间不断进行信息交流，有利于发现较好解。单 个个体容易收敛于局部最优，多个个体通过合作，很快收敛于解空间 的某一子集。 基于蚁群算法的汉语自动分词的研究与实现第三章蚁群系统模型 3 2 蚁群算法的应用和优化 自从蚂蚁算法在著名的旅行商问题( t s p ) 3 7 1 上取得成效以来， 已陆续渗透到其它问题领域中，如：通讯网络中的负载平衡问题【1 9 1 、 车辆调度问题 1 9 】、图着色问题【2 0 1 、工件排序问题2 0 1 等等，在许多 方面表现出相当好的性能。 国内对蚁群算法的研究和应用起步也比较早，有相当多的研究成 果发表在各种不同类型的期刊和杂志上。具有代表性的有：文献【2 蜘 中作者介绍了蚁群算法对于在各种限制条件下t s p 问题的应用，将 之嵌入到他们研制的运筹学、管理科学集成软件包中；文献 20 】中作者 在基本蚁群算法中引入变异机制，充分利用了2 交换法简洁高效的特 点，使得该方法带来较快的收敛速度；文献【2 9 】就t s p 问题在蚁群算 法的基础上提出了相遇算法，提高了算法中蚂蚁一次周游的质量，且 将相遇算法与采用并行策略的分段算法结合，取得了较好的实验结 果；文献1 3 0 提出根据优化过程中解的分布均匀度，自适应地调整路径 选择概率的确定策略和信息素更新策略，以求在加速收敛和防止早 熟、停滞现象间取得良好的平衡；文献【3 l 】则将蚁群算法扩展到连续空 间领域，通过将解空间划分为若干子域，在算法迭代过程中，通过求 出解所在的子域，然后由子域内已有的解确定，并以非线性规划问题 做了尝试。 3 3 小结 本章中，我们详细介绍了基本蚁群算法的原理及其一些成功应 用的范例，重点在于近年来国内在研究和应用蚁群算法上所作的贡 献，以及蚁群算法的应用领域和适用场合，好让我们对该算法模型有 一个比较全面的了解和掌握。 第四章基于蚁群算法的分词模型基于蚁群算法的汉语自动分词的研究与实现 第四章基于蚁群算法的分词模型 基本蚁群算法是一种新型的基于种群的模拟进化算法，属于随机 搜索算法，是人们对自然界中真实的蚁群集体行为的启发和提炼。单 个蚂蚁的行为很简单，能力也有限，由这样的单个简单的个体所组成 的蚁群群体却显现出惊人的寻优潜力，能够完成复杂的任务，而且还 能够适应环境的变化，不断的调整自己。其核心思想为：在搜索过程 中，通过个体之间的信息交流和相互协作，构成了一种学习信息的正 反馈机制。 从上一章的介绍中可以看出，蚁群算法对于求解组合优化等离散 型随机优化问题很适用，很容易在问题域和目标域之间就能找到映 射。而对于解决连续空