（计算机应用技术专业论文）基于k最短路径的中文分词算法研究与实现.pdf

哈尔滨丁程大学硕士学何论文 摘要 中文分词处于词法、句法、语义等语言层次的最底层。它是中文自然语 言处理的一项基础性工作，也是中文信息处理领域的一项基础性课题，它是 搜索引擎、自动翻译、语音识别、信息检索、自动分类、自动文摘、文本的 自动校对以及数据挖掘等技术的重要组成部分，是直接影响中文信息处理技 术发展的技术瓶颈。 本文首先阐述了中文分词的研究背景与意义，对中文分词的国内外研究 现状进行了分析，详细讲述了基于字符串匹配、统计和理解的三种典型中文 分词方法，并对每种方法的优缺点进行了简要的概括，分析了几种中文分词 相关的算法模型，并在分词规范、歧义识别、未登录词识别等方面总结了阻 碍中文分词发展的几种主要技术难题。 然后，本文对中科院汉语词法分析系统i c t c l a s 的n 最短路径粗分模 型算法进行了分析研究，并对该系统所生成的特殊有向图的特点和存储结构 进行了描述。本文基于该中文分词系统生成的有向图，提出了s e k 最短路 径算法模型，同时对该算法时间复杂度进行了分析。 本文最后对s - e k 最短路径算法与n 最短路径算法、d i j k s t r a 算法在时间 复杂度方面进行了对比分析，并给出了一个详细的s - e k 最短路径算法求解 实例。本算法采用通过局部求解重要节点集合而得到整个有向图的k 最短路 径的方案，降低了算法时间复杂度，并通过仿真实验进行了验证。 关键词：分词；歧义识别；未登录词识别；n 最短路径；s - e k 最短路径 哈尔滨j 厂程大学硕士学位论文 - - - - - - - m a b s t r a c t c h i n e s ew o r ds e g m e n t a t i o ni sa tt h el o w e s tl e v e lo fl a n g u a g el e v e l s i n c l u d i n gm o r p h o l o g y , s y n t a xa n ds e m a n t i c i ti saf o u n d a t i o n a lw o r ko fc h i n e s e n a t u r a l l a n g u a g ep r o c e s s i n g ，a n d ab a s i c s u b j e c t o fc 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 gf i e l d i ti sav e r yi m p o r t a n tc o m p o n e n to ft e c h n o l o g i e ss u c ha ss e a r c h e n g i n e ，a u t o m a t i ct r a n s l a t i o n ，s p e e c hr e c o g n i t i o n ，i n f o r m a t i o nr e t r i e v a l ，a u t o m a t i c c l a s s i f i c a t i o n ，a u t o m a t i ca b s t r a c t i n g ，t e x ta u t o m a t i cp r o o f r e a d i n g ，a n dd a t am i n i n g c h i n e s ew o r ds e g m e n t a t i o ni sag r e a tt e c h n i c a lb o t t l e n e c k ，w h i c hc a nd i r e c t l y a f f e c tt h ed e v e l o p m e n to 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 t h i st h e s i s m a i n l yd e s c r i b e dt h eb a c k g r o u n da n ds i g n i f i c a n c eo fc h i n e s e w o r ds e g m e n t a t i o n ，a n a l y z e dt h er e s e a r c hs t a t u sa th o m ea n da b r o a do fc h i n e s e w o r d s e g m e n t a t i o n ，e x p l a i n e d t h et h r e e t y p i c a l c h i n e s ew o r ds e g m e n t a t i o n m e t h o d s ，i n c l u d i n gs t r i n gm a t c h i n g ，s t a t i s t i c s ，a n dc o m p r e h e n s i o nb a s e do n c h a r a c t e r ，s u m a r i z e dt h ea d v a n t a g ea n dd i s a d v a n t a g eo fe v e r ym e t h o di nb r i e f , a n da n a l y z e dt h er e l a t e da l g o r i t h mm o d e lo fs e v e r a lc h i n e s ew o r ds e g m e n t a t i o n s a n dt h em a i nt e c h n i c a l p r o b l e m s ，w h i c h c o n t a i n e dt h ew o r ds e g m e n t a t i o n r e g u l a t i o n ，a m b i g u i t yr e c o g n i t i o n ，u n k n o w nw o r dr e c o g n i t i o no ft h ed e v e l o p m e n t o f c h i n e s ew o r ds e g m e n t a t i o n a f t e rt h a t ，t h i st h e s i sa n a l y z e da n dr e s e a r c h e dt h em o d e lo fc 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 do fi c t c l a s ( i n s t i t u t e o fc o m p u t i n g t 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 ) b yc h i n e s e a c a d e m yo fs c i e n c e s i td i s c r i b e dt h ef e a t u r ea n ds t o r a g es t r u c t u r eo ft h ed i r e c t e d g r a p hg e n e r a t e db yi c t c l a s o nt h i sb a s i s ，i tp u tf o r w a r ds - e ks h o r t e s tr o u t e a l g o r i t h m ，a n a l y z e di t st i m ec o m p l e x i t y ，a n do f f e r e das i m p l ee x a m p l e ，w h i c h i l l u s t r a t e dt h es p e c i f i cp r o c e s so fs o l v i n gks h o r t e s tr o u t eb ys - e ks h o r t e s tr o u t e a l g o r i t h m f i n a l l y , i tr e a l i z e dt h ee x p e r i m e n t a lr e s u l t sb ys - e ks h o r t e s tm u t ea l g o r i t h m ， d i jk s r aa i g o r i t h ma tt h ea s p e c t 。ft i m ec 。m p l e x i t y , a n dg a v et h es p e c i f i c s 。1 v i n g p r o c e s 8o fs e ks h o r t e s tr 。u t ea l g o r i t h m b yt h ee x a m p l e t h i sa l g o r i t l u l l g e t sa p l a no ft h eks h o r e s tr o u t eo ft h et h ew h o l ed i g r a p hb yt h e p a r t i a ls o l u t i o no ft h e i m p o r n a n tn o d es e t s i tr e d u c e dt h et i m e i tt h r o u g hs i m u l a t i o ne x p e r i m e n t s c o m p l e x i t yo ft h ea l g o r i t h m ，a n dv e r i f i e d k e y w o r d s ：w o r ds e g m e n t a t i o n ；a m b i g u i t yr e c o g n i t i o n ；n - s h o r t e s t r o u t e ：s - e k s h o r t e s tr o u t e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其它个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：役习跏 日期：谝c j f 年；月7 日 f f 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位12 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：翻台插 导师( 签字) ：莎匕侄甲 日期：2 弼7 年3 月7 日2 枷了年j 月 7 日 哈尔滨t 程大学硕士学位论文 1 1 研究背景与意义 第l 章绪论 1 1 1 研究背景 随着国内互联网的迅猛发展，网络信息量急剧膨胀，如果完全由人工来 整理如此繁多的信息，那是难以想象的工作量，同时也不现实的，如何有效、 快速、准确的从大量的信息中找到我们所需要的信息，是摆在我们面前的一 个重要和迫切的任务，为了解决这个难题，人们采用了中文分词技术，通过 雩| 入分词技术，就可以使得对海量信患的整理更准确更合理，使得检索结果 更准确，效率也会大幅度地提高。所谓中文分词，就是把一个汉语句子按照 其中词的含义进行切分。随羞人们更深入熬研究，中文信息处理技术得到了 广泛应用，并对中文分词技术的要求也越来越高。中文分词技术已经引起多 方藤的关注，并成为中文信息处理的一个前沿课题l 卜2 1 。 目前在自然语言处理技术中，中文处理技术远远落后于西文处理技术， 许多西文的处理方法中文不能直接采用，就是因为中文必须进行分词处理。 中文分词是其它中文信息处理的基础，搜索弓| 擎只是中文分词的一个应用， 其它应用比如机器翻译( m t ) 、语音合成、自动分类、自动摘要、自动校对、 中文文献瘁全文检索等翻，都需要焉到分词。分词准确性对搜索弓| 擎来说十 分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不 可用的，因为搜索弓l 擎需要处理数以亿诗的网页，如果分词耗用的时间过长， 会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说，分词的准确 性和速度，二者都需要达到很高的要求，中文分词技术要想更好的服务予更 多的产品，需要更多的专业队伍投入到研究中来，因此，中文分词的研究还 是一个相当长的探索过程。 目前中文分词得到了很多现实的应用，主要体现在在信息检索、同音字 和多音字方面的识别、文本校对、简体繁体的囱动转换、自动标引、自动文 撬、视器翻译、语言文字研究、搜索弓| 擎研究、自然语言理解和中文信息处 哈尔滨 二程大学硕七学位论文 理等方面m ，也是中文智能计算技术发展的前提和基础。随着对中文分词技 术关注度的不断提高，大量的学者都加入到了这一研究领域，使中文分词取 得了丰硕的研究成果。近1 0 年来，语言学界、人工智能领域和情报检索界的 学者们，在中文分词与自动标引的研究与实践上进行了大量的研究，找到了 许多解决中文分词的方法，目前关于中文分词研究方法主要有三个方面，即 基于字符串匹配的分词方法、基于统计的分词方法和基于理解的分词方法。 中文分词的研究，主要是从词层面进行的研究，这一问题很早就受到了 广泛的关注。目前，各种分词系统也不断建立，分词系统在运行速度、准确 度等方面已经具有了研究应用的价值( 8 - 1 0 ，但是在句子中词该如何被界定，仍 然是一个比较困难的问题，同时，在不同的应用领域由于应用需求的不同， 需要达到的分词效果有很大区别。词的确切概念难以标准化，词的应用领域 不同，使得分词规范难以统一，需要达到的分词效果也有很大区别。 在这一长期的研究和实践过程中，分词规范、歧义字段处理和未登录词 识别成为困扰我们的主要技术难题，随着计算机技术和汉语语言研究的发展， 中文分词技术将会有更大的突破。 1 1 2 研究意义 中文分词处于词法、句法、语义等语言层次的最底层，是中文信息处理 的基础。它是搜索引擎、自动翻译、语音识别、文本的自动校对以及数据挖 掘等技术的重要组成部分。中文分词技术是直接影响中文信息处理技术发展 的巨大技术瓶颈，由于汉语自身存在着诸多特性，这决定了在分词技术上中 文与其它分词技术的本质不同。众所周知，英文是以词为基本单位，词与词 之间是用空格隔开，检索起来很方便。相对来讲，中文是以字为基本的书写 单位1 1 1 ，是以连续的汉字字符串或序列形式出现的，词与词之间是没有分隔 符的，没有明显的分词区分标志。因此若想建立基于词的索引，就需要专门 的技术来将汉字字符串或序列按照一定规范切分为正确的词序列，这种技术 也就是中文分词技术。 中文分词使得计算机能够快速、准确、高效的处理中文信息。作为中文 信息处理的基础，在中文信息处理的广泛应用，许多中文信息处理项目中都 涉及到分词问题，如自动索引、自动分类、机器翻译、信息检索、自动文摘、 2 哈尔溱工程大学硕七学位论文 中文文献库全文检索等。中文自动分词也是中文搜索弓l 擎实现所必须的关键 技术之一，它直接影响着搜索引擎的性能。分词的重要性不言而喻，只有汉 语字符串转难确切分为词语时，中文才能像英文那样过渡到短语划分、概念 抽取以及主题分析，以至于自然语言理解。 1 2 中文分词的研究现状 中文分词技术是中文信息处理领域的一项基础性课题，也是智能化中文 信息处理的关键，中文分词系统的实现及效果依赖于分词理论与方法。1 9 9 2 年融国家技术监督局批准为国家标准( g b l 3 7 1 5 ) 的信息处理用现代中文 分词规范f 1 2 j 提出了切分单位的概念，为现代汉语信息处理提供一套实用、 使用、科学、系统的分词规则。 随着对中文分词方面的关注与研究，多种高效、准确的中文分词系统已 得到实现，并在不断完善中，在运行速度、准确度等方面都得到了很大程度 上的提高。露翦主要豹中文分谲系统主要有：早期8 0 年代北航的采用了羹三渤 或逆向最大匹配方法的c d w s t 1 系统和c w s s 、山西大学的a b w s 分词系统。 年代至今有：清华大学的一个基于评价的全切分中文分词系统s e g 、北师 大的自动分词专家系统、东北工学院的基于规则的中文分词系统、杭州电子 工业学院的h d c a w s 系统等，中国科学院计算技术研究所在多年研究工作 积累的基础上，研制出了汉语词法分析系统i c t c l a s ( i n s t i t u t eo f c o m p u t i n g t 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 2 0 0 8 ，i c t c l a s 2 0 0 8 分词速度单机9 9 6 k b s ，分词精度9 8 4 5 ， a p i 不超过2 0 0 k b ，各种词典数据压缩后不到3 m 。 汉语词法分析系统i c t c l a s ，采取的是基予类的隐马尔科夫模型【1 4 l ，在 这层隐马尔科夫模型中，未登录词和词典中收录的普通词一样处理。未登录 词识别引入了角色h m m ，识别出来登录词，并计算出真实的可信度。在切 分排歧方面，提出了一种基于n 最短路径i ”1 策略早期阶段召回n 个最佳结果 哈尔滨上- 仔l i 大学硕十学位论文 i i - _i,ti i i i i ；i i 作为候选集，目的是覆盖尽可能多的歧义字段，最终的结果会在未登录词识 别和词性标注之后，从n 个最有潜力的候选结果中选优得到。该系统在2 0 0 2 年的“九七三专家组评测中获得第1 名，在2 0 0 3 年汉语特别兴趣研究组( a 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 ) 组织的第1 届国际中文分词大赛中综合得分获得两项第1 名、一项第2 名。在i c t c l a s 中文分词系统中如图1 1 所示： i c t c l a s 分词系统 核心步骤 初步分词 7 1 初次n 最短路径粗分 l 未登录词识别 l 再次n 最短路径分词 优化分词结果 图1 1i c t c l a s 分词系统主要步骤 i c t c l a s 中文分词系统共分为以下五个部分： ( 1 ) 初步分词。在这一步骤中又详细划分为原子切分、找出原子之间所 有可能的组词方案等步骤。原子切分是词法分析的预处理过程，主要任务是 将原始字符串切分为分词原子序列，就是对输入的中文字符串拆分成为一个 个独立的中文字符和一些数字等字符，例如语句“教学科研”进行原子切分 后变成“始# # 始教学科研末# # 末”。 ( 2 ) n 最短路径算法求解初步分词结果，产生的粗切分结果是后续过 程的处理对象，粗分结果的准确性与包容性( 即必须涵盖正确结果) 直接影 响系统最终的准确率、召回率 1 6 】。 ( 3 ) 未登录词识别( 人名、地名识别) 。 ( 4 ) 再次使用n 最短路径算法求解最终分词结果。 ( 5 ) 对最终结果进行优化调整。 目前分词系统采用的分词方法主要有以下三种类型： 4 啥尔溱t 程大学硕士学位论文 ( 1 ) 基于字符串的分词方法 字符串的分词方法也称机械分词方法，是指按照一定的策略将待分析的 汉字串与一个已有机器词典中的词条进行模式匹配来进行切分。最基本的机 械切分方法有：正向匹配法( m m 法) 、逆向匹配法( r m m 法) 、逐词遍历 法、双向扫描法等。甚前以应用最为广泛的机械匹配分词法为例，其分词精 度能达到9 0 左右，一些经过长期研究具有一定规模的分词系统分词精度达 到t9 5 以上，已经广泛应瘸到汉字输入、计算机辅助文本校对、信息检索 等应用系统中。此种方法的优点是简单、易实现，分词效率较高，但汉语语 言现象复杂丰富，词典的完备性、规则的一致赣等闯题搜其难以适应开放的 大规模文本的分词处理，难以解决未登陆词和歧义字段等问题，机械切分的 分词精度受到了很大限制。 ( 2 ) 基于统计的分词方法 基于统计的方法撇开词典，是根据字串出现的概率，通过对语料库( 经 过处理的大量领域文本的集合) 中翡文本进行有益督或无监督的学习，可以 获取该类文本的某些整体特征或规律。该方法对于大的语料，分全率还可以， 但是对于小的语料分全率就比较低。实际应焉的统计分诞系统都要使用一部 基本的分词词典进行串匹配分词，同时使用统计方法识别一些新的词，即将 词频统计和审匹配结合起来，既发挥匹配分词切分速度快、效率离的特点， 又利用了无词典分词技术结合上下文识别生词、自动消除歧义的优点。 ( 3 ) 基于理解分词的方法 也称为知识分词方法，基本思想就是在分词的同时进行句法、语义分析， 利用句法信息和语义信息来处理歧义现象，是一种理想的分词方法。它通常 包括三个部分：分词子系统、句法语义子系统、总控部分。这种分词方法需 要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将 各季孛语言信息组织戒机器可直接读取的形式，这类分词方案的算法复杂度嵩， 其有效性与可行性尚需在实际工作中得到进一步的验证，因此目前基于理解 的分词系统还处在试验阶段。 应该说目前在分词领域的研究进展已经有了一定突破，但是这些分词方 法在面对语言现象不断变化时，显得适应性还很差，所以还需要继续对分词 方法作迸一步的研究，以期能形成更加完善的分词方法。 哙尔滚：l ：程大学硕士学位论文 1 3中文分词的应用 目前，中文分词圭主要应用于搜索弓| 擎、信息检索、同音字和多音字方 面的识别、文本校对、简体繁体的自动转换、自动标引、自动文摘、机器翻 译、语言文字研究、搜索弓| 擎研究、喜然语言理解和中文信息处理等方蚕， 根据在信息检索中应用阶段不同，将分词应用划分为以下几点：在索引项方 面，是实现按词索引的关键；在文档属性提取方蠢，是鱼动抽取关键谣的翁 提；在用户接口方面，是实现自然语言查询的基础1 1 7 】。随着中文分词技术的 进展，这一研究成果将会被应用到广泛的研究领域，如词频统计、惠容分析、 概念分析、认知心理学和汉语语言学等方面。 l 。4 论文研究内容与组织结构 本课题是在对i c t c l a s 中文分词系统进行研究与分析的基础上，提出 了s - e k 最短路径算法，对于i c t c l a s 中文分词系统中的原子切分、词性标 注、人名识别、地名识别等问题在本文中只做简单介绍，将不加赘述，重点 研究对特殊的有向图g 中求解k 最短路径算法。 1 4 1 论文的研究内容 本论文根据i c t c l a s 中文分词系统思想，提出了不同子n 最短路径算 法的一种求解算法，即s e k ( s t a r tn o d et oe n dn o d ek 最短路径) 最短路径 算法。i c t c l a s 中文分词系统总体流程包括初步分词、词性标注、人名与地 名识别、重新分词、重新词性标注共计五个部分。在初步分词部分又细分成 原子切分、找浅原子之间所有可能的组谰方案、n 最短路径中文词语粗分等 模块。本课题对i c t c l a s 中文分词系统进行了深入的研究与分析，把经过 系统初步分词而成的s - e k 图( 定义见3 1 节) 作为本文研究对象，重点放在 求解s - e k 图的k 最短路径问题。本文提出了一个求解k 最短路径的s - e k 最短路径算法，通过该算法求解i p s ( 重要节点集合，定义见3 2 1 节) ，在 很大程度上减少了算法遍历节点的循环次数，通过降低算法的时闻复杂度最 终达到提高中文分词的速率。 本文研究内容主要包括以下几个方瑟： 6 呤尔滨j f 翟大学硕七学位论文 ( 1 ) 详细介绍常用的三种中文分词方法，并对每种方法的优缺点迸行了 简要的说明，然后分析了几种中文分词相关的算法模型以及阻碍中文分词发 展的分词规范、歧义识别、来登录词识别三大技术瓶颈。 ( 2 ) 分析研究了i c t c l a s 中文分词系统中n 最短路径的中文分词粗分 模型算法，并在此基础上对i c t c l a s 中文分词系统所生成的有向图进行定 义与说明以及对该图的特点加以阐述，并提出了s - e k 最短路径算法，从时 闻复杂度方面对该算法进行了分析。 ( 3 ) 程序实现该s - e k 最短路径算法。通过详细的实验数据依据该算法 给如求解实例，并且与n 最缎路径算法进行了简要的对比分孝斤。 在s - e k 最短路径算法中侧重要解决的问题是： ( 1 ) 求解i p s ，找出s - e k 图中的重要节点集合。 ( 2 ) 求解重要节点集合i p s 中每个节点的a p p 与a n p 信息。 ( 3 ) 根据节点a p p 与a n p 信息，求解各个节点的a s p 信息。 ( 4 ) 最后求解k 最短路径。 1 4 2 论文的组织结构 本文内容共分为4 章，每章内容概要如下： 第l 章：绪论。主要阐述了研究中文分词的背景与意义，对中文分词的 磷究现状进行了分析与介绍，同时讲解了中文分词技术的几种典型应用。 第2 章：中文分词方法研究。在本章首先主要介绍了目前比较常见的三 种中文分词方法以及每种方法所存在的优缺点。然后在求解k 最短路径算法 模型上对d i j k s t r a 、f l o y d 、n 最短路径算法进行了介绍，本文是在i c t c l a s 中文分词系统基础上进行的研究，所以对n 最短路径算法以及如何实现做了 详细说明。最后介绍了中文分词研究存在的主要技术难点。 第3 章：s - e k 图模型与算法求解模型。在本章首先对s - e k 图进行了定 义，对该图的特点以及存储结构进行了描述。在此基础上提出了s - e k 最短 路径算法，从时间复杂度方面对该算法进行了分析，同时给出了利用该算法 的简单求解实铡。 第4 章：s - e k 最短路径算法实现及实验结果分析。首先简要地介绍了 s - e k 最短路径算法的实现，然后弓l 出个具体的实例，在该实例书给出了实 7 哙尔演i l 。：程大学硕士学位论文 验准备数据，根据该数据以及对应的变动后的数据由该算法计算求解而得出 的实验结果，最后与其它算法进行了简要的对比分析。 8 啥尔滨工程大学硕士学位论文 第2 章中文分词方法研究 2 1中文分词的主要方法 随着对中文分词技术关注度的不断提高，大量的学者都加入到了这一研 究领域，近l o 年来，语言学界、人工智能领域和情报检索界的学者们，在中 文分词与自动标引的研究与实践上迸行了大量的研究，找到了许多解决中文 分词的方法。吾前对中文分词方法的研究主要有基于字符串匹配的分词方法、 基于统计的分词方法和基于理解的分词方法。 2 。i 1基于字符串匹配的方法 基于字符串匹配的分词方法【1 8 l ，又叫做机械分词方法，是按照一定的策 略将待切分的字串与一个词的涵盖内容足够全面的词典中的词条进行匹配， 若在词典中找到某个字符串，则匹配成功，切分并识别出该词，否则不予切 分。常用的方法：最小匹配算法 计算它的出现概率，从结果中选取概率最大的一种。概率的计算方法依赖于 所建立的语言模型。随着大规模语料瘴的建立，这种方法得到越来越广泛的 使用。基于统计的分词方法所应用的主要的统计量或统计模型有：互信息、 n 元文法模型、神经网络模型、隐马尔可夫模型等，这些统计模型主要是利 用词与词的联合出现概率作为分词的信息。 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出 现次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能 够的反应成词的可信度。这种技术发展至今己经有许多不同的统计原理，这 种基于词频的统计分词的最大优点是不篙要词典直接利雳统计信息就可以分 啥尔濠丁程大学硕士学位论文 词，省去了词典的维护，无须人工介入；统计方法提供了良好的数学理论基 础，能够比较有效地实现上下文识别未登录词、囊动消除歧义等，处理自然 语言的健壮性好，能够覆盖的范围较大，解决了机械匹配分词算法的局限【2 3 】。 但这种方法也有一定的局限性，分词时会经常抽出一些共现频度高、但并不 是词的常用字组，并且对常用词的识翱精度差，时空开销大，基于语料库统 计学的方法虽然语言处理的覆盖面更广，但它仅仅考虑了语言的上下文关系， 忽略了语言现象的变化，会受到语料瘴规模的限制 凇s 】。实际应焉麴统计分 词系统都要使用一部基本的分词词典进行串匹配分词，同时使用统计方法识 别一些薪的诫，即将词频统计积睾匹配结合起来，既发挥匹配分词切分速度 快、效率高的特点，叉利用了无词典分词结合上下文识别生词、自动消除歧 义的优点。近几年来，基于统计的分词方法占了主要的地位。 2 1 3 基于理解分词的方法 基于理熊分词的方法，又蟮基于语法和规则的分词法，或者嚣堪专家系统 分词法，它将中文自动分词过程看作知识推理过程，通过计算机模拟人类对 句子的结构的理解，利用有关词、句子等的句法和语义信息或者从大量语料 中找出汉字组词的结合特点来进行评价，以期找到最贴近于原旬语义的分词 结果。该方法需要考虑知识表示、知识库的逻辑结构和知识库的维护，在实 际应用中工作量巨大，这类分词方案的算法复杂凄高，其有效性与可行性尚 需在实际工作中得到进一步的验证，因此目前尚处在实验阶段。 基于理解分词的基本愚想就是在分词的同时进行句法、语义分誊厅，利篇 句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、 句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有 关词、句子等句法和语义信息来对分词歧义进行判断，即它模拟了人对句子 的理解过程。该方法主要基于句法、语法分析，并结合语义分析，通过对上 下文内容所提供信息的分析对词进行定乔，这类方法试图让机器具有人类的 理解能力，需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复 杂性，难以将各种语言信息组织成机器可直接读取的形式，因此鼋前基于知 识的分词系统还处在试验阶段。中文分词算法有两个关键指标：速度和准确 率。不圆分词算法有不阕的侧重点。根据实际应用采用合适的算法十分重要。 1 2 哈尔滨j 【群大学碛七学位论文 另外，还有一些算法被提出来，例如基于标记的分词算法、基于特征词 的懿动分词等。 2 2 中文分词的路径算法模型 中文分词系统的总目标是建立一个开放的，具有较高通用性和实用性的 现代书面中文分词系统。衡量一个自动分词系统的标准主要在于分词的速度 及分词的精度( 即分 霹的正确率) ： 分词正确率瑾= 翥怒1 0 0 未登录词识别正确率b = 号篓警豢鬻1 0 0 未登录词识别召回率y = 旦篆筹翳筹1 0 0 其中分词的精度尤为重要，而影响分词精度的主要因素是歧义问题和未 登录词识别问题，因此选择一个恰当的分词算法模型来解决歧义切分问题和 未登录词的识别阐题是提高分词精度的关键。 目前几种常用的中文分词算法模型有基于类的三元语言模型f 2 6 】、隐马尔 科夫模型、最大麓望1 2 7 1 、信道噪声模型等等。在本文的磷究对象i c t c l a s 中文分词系统中采用了多层隐马尔可夫模型，同时利用n ，最短路径算法模型 字句的初次切分，为了与本课题研究的s - e k 最短路径算法模型进行对比分 析。下面将介绍其中的n 最短路径、d i j k s t r a 求解最短路径、f l o y d 求解最短 路径算法模型。 2 2 1 d i j k s t r a 算法模型 d i j k s t r a 算法焉来解决从单源点到有向匿其余各项点的最短距离。 d i j k s t r a 算法基本思想可以用递归的思想来理解，求一个节点到源节点的最短 距离，可以求其所有前驱节点到源点的最短距离，然后再与该节点的前驱节 点到该节点的权重求和取最小的一个即为该点到源点的最短距离，这样又转 化为求其前驱节点到源点的最短距离，直至取到源节点为止，用形式语言描 述如下： 哈尔滚j l ：程大学硕士学位论文 最= l m i n ( c 。s t ( a i ，a l p r i 。r ) 十s h 。r t ( a i p r i 。r ) ) ，i o 【o ，i = 0 d i j k s t r a 算法是按路径长度递增的次序来产生符最短路径的，具体算法描 述如下 2 s 1 ： ( 1 ) 设辅助向量d ，集合s ，定义若节点v ；与节点相邻则觚 ，) 为 其投重蓬，反之为，初始优d ： d i = a r c ( v o ，) ，v j 毯v ( 2 ) 宽度遍历节点，使得节点到节点m 距离最短，并把节点鼍加入 到s 中： d d 】= m i n d i 】l v s ) s = s u i ( 3 ) 宽度遍历节点集合v s 中节点到源点的最短路径值： 。c k ，_ 三翟】+ a r e 麓 磙三 叫j + + a a r r c c ( ( v j , ，逆；主三篱 ( 凄) 重复过程( 2 ) 、( 3 ) 蕤1 次，求得v 中各节点到源节点的最短路径 问题。 2 。2 2 f l o y d 算法模型 f l o y d 算法的基本思路是：从图的带权邻接矩阵a = 【a ( i ，j ) 】n n 开始，进 行1 1 次递归调用，即盘矩阵d ( 0 产a ，构造毫矩阵d ( 1 ) ，由d ( 1 ) 构造蠢 d ( 2 ) ，最后由d ( n - 1 ) 构造出矩阵d ( n ) 。矩阵d ( n ) 的第i 行第j 列元素 便是第i 号项点到第j 号顶点的最短路径长度，称d ( n ) 为图的距离矩阵，同 时还可引入个后继节点矩阵p a t h 来记录两点间的最短路径。 递推公式为： d ( 0 ) = a ； d ( 1 ) = 【d ( i ，j ) 1 】n n ，d ( i ，j ) 1 = m i n d ( i ，j ) o ，d ( i ，o ) o + d ( 0 ，j ) o ) ； d ( 2 ) = 【d ( i ，j ) 2 】舞狂，d j ) 2 = m i n d ( i ，j ) 1 ，d ( i ，1 ) l + d ( 1 ，j ) 王l ； 哙尔滨t 程大学硕士学位论文 矜( n ) = 【d ( i ， ) n 】n n ，d ( 毛j ) 魏= m i n d ( i ，j ) n - 1 , d ( i ，n 1 ) n 一王+ d ( n 一 1 ，jn - 1 】。 采焉循环迭代可以简便求出上述矩阵序到，p a t h ( i ，j ) 表示对应于d ( i ，j ) k 的 路径上节点i 的后继点，最终的取值为节点i 到节点j 的最短路径上节点i 的 居继点。具体算法如下： ( 1 ) 赋初值 d ( i ，j ) = a ( i ，j ) ，p a t h ( i ，j ) = ：a a ( ( i i ，, j j ) ) = o o ，k = 1 ； ( 2 ) 更新d ( i ，j ) ，p a t h ( i ，j ) 对于所有的i 和j ，若d k ) + d j ) d ( i ，j ) ，则转( 3 ) ；否则 d ( i ，j ) = d ( i ，k ) + d ( k ，j ) ，p a t h ( i ，j ) = p a t h ( i ，k ) ，k = k + 1 ，继续执行( 3 ) ： ( 3 ) 重复( 2 ) 蛊到k = n + l 。 2 2 3n 最短路径算法模型 n 最短路径算法模型是汉语词法分析系统i c t c l a s 所采取的一种处分 策略，可以快速产生n 个最好的粗切分结果，粗切分结果集能覆盖尽可能多 的歧义。在整个词法分析架构中，二元切分词匿是个关键的中间数据结构， 它将未登录词识别、排歧、分词等过程有机地进行了融合。 n 一最短路径方法基本思想是根据词典，顺序匹配出在中文字串中所有可 能的出现的词的集合，所有词语作为一个节点构造成为一个有向无环图，每 个节点记录k 个最短路径值，并记录相应路径上当前节点的前驱。如果同一 长度对应多条路径，必须同时记录这些路径上当翁节点的前驱。最后透过霾 溯求解n 类最短路径。词与词的逻辑关系在图中表现为节点与节点间的关系， 并赋予一定的权值，并对该有向无环图求解蘸k 最短路径。在该图中起点到 终点的所有路径中，递归调用求出每个节点的所有到源节点的路径值并按严 格递增顺序排列( 任何两个不同位置上豹路径值一定不等) ，每个路径值对应 哈尔滨t 程大学碛士学能论文 m i , i i i im li i l l li 1 1 1 1 1i lh l l li 篁赫眷薯 一个路径集合，每个集合中包含至少一个元素，依次为路径集合 & 、p z 、臻、矗，其路径值p a t h l p a t h 2 p a t h i p a t h n ，其中 p a t h i 代表第i 短路径的路径值，每个集合中包含的元素不唯一，作为相应的 粗分结果集。如果出现路径长度相等的路径集合，那么将其列入网一个粗分 结聚集，而且不影响其它路径的排列序号，最后的粗分结果集合大小大于或 等于n 。 n 最短路径算法也是采焉对d i j k s t r a 算法的改进算法，壶于n 最短路径 算法中的图是特殊的有向无环图( 在下章中对此图进行了定义，即为s - e k 图) ， 有其特有的藏性，求初始节点到终节点麴k 最短路径，需要求解其所有前驱 节点的k 最短路径，与对应的当前权值求和求取终节点的k 最短路径，这样 又转化为求取其前驱节点的k 最短路径，同理，求取其所有前驱节点的k 最 短路径又转化为求取其所有前驱节点的所有前驱节点的k 最短路径，依次类 推，需要求取始节点的k 最短路径，递归调用结束，求出k 集合的最短路 径，每个集合中包含至少一个路径元素，在4 。3 节实验对比分析中我们将会 给出利用n 最短路径算法求解的一个实例。 另乡 还有删除算法( d e l e t i o na l g o r i t h m ) 2 9 1 、最优化原理( p r i n c i p l eo f o p t i m a l i t y ) 、无环路算法( 1 0 0 p l e s sp a t h ) 3 q 、标签校正演算法( l a b e l c o r r e c t i n ga l g o r i t h m ) 3 2 - 3 3 等多种求解前k 条最短路径算法。 2 3中文分词的技术难点 现代中文分词虽然取得了很大成绩，但由予汉语本身的复杂性，无论按 照人的智力标准，还是同应用的需要相比较，中文分词技术需要更深一步的 研究和长远的发展。需要对自动分词的困难的各个方面有充分的认识，主要 体现在以下几个方面。 2 3 1分词规范 在中文分词中存在最大的问题就是词的概念不清。什么样的字组合在一 起被称之为词语，在句子中词该如何被界定，仍然是一个比较困难的问题。 虽然目前已经有了一些标准来进行衡量，但由于这些判断条件本身难以操作， 冒前尚无合理的可操作的理论和标准，再加上汉语本身的复杂性，如词的变 1 6 飧尔溟。 ：程大学璩卡学傅论文 形，词缀翔题，菲谰语蠢素阀瑟使得谰兹界定更为豳难。嗣对，在不同瓣应 用领域由于应用需求的不同，需要达到的分词效累也有很大区别。在绝大多 数表音文字中，词是豳传统确定的，一般来说不存在分词规范的问题。汉语 的书写则以汉字为单位，是一种缺少严格意义的形态变化的表意文字语言， 没有明显的形态界限可以作为分词标志，因而汉语存在特有的分词问题。e l l 于中文分词存在许多理论和技术阏题，语言学界最经数卡年努力，但至今仍 未制定出一套认识一致、完整和可行的分词标准。词麴确切概念难以标准化， 谣的应用领域不同，使褥分词规范难戳统一，需要达到的分词效梁也有缀大 区别。 2 3 2歧义识别 歧义是指对予同样个特定的甸子或字符察可能存在多种切分方法，不 同懿切分方法具有不同的含义，毽此会导致组合型鳢义和交叉型歧义。中文 分词的一个重要润题是如何从连续字睾的汉语句子对应的艨有合法可能词序 列中，选童一个正确的结果，霹歧义字段楚理。歧义切分字段在汉语书蘧文 本中所占的b 匕例并不大，一些可以通过字段内部的词法特征信息来唯一地判 定和币确地切分，另外些则需要用到词频、词长、词问关系等信息才能判 定和正确地切分m l 。分词歧义的产生主要有两种情况；组合型歧义和交叉型 歧义，二者如现比例约为2 2 ：l 。所谓组合型歧义是某个词的一部分也可能 是一个完整的词，倒如中文字符枣a b ( a 、b 为汉字宰) 中，a b 、a 、b 同 时都是一个标准