（计算机应用技术专业论文）综合字典和统计分析的中文分词系统的研究与实现.pdf

摘要 中文分词技术主要包含以下三个研究方向：理解分词，机械分词以及统计分 词。基于理解的分词方法研究尚未成熟，所以，绝大部分中文分词系统是应用机 械统计相结合的方法。在目前主流的词典和统计相结合的分词系统中，统计策略 和词典设计的关系往往是相互独立的，词典主要是作为机械分词的标准，而基于 统计的方法主要是为了解决歧义问题以及未登录词的识别问题。 本文所阐述的中文分词系统，将基于分词核心词典的机械分词和基于统计的 方法组成了一个有机的整体。系统将统计得出的结果作为分词核心词典的输入， 对于待切分文本来说，对于未登录词和词典词条，本文算法的本质均是先基于统 计的方法扩充核心词典，然后采用基于字符串匹配的分词方法切词。 总体上讲，本系统具有以下三方面的特点。专用性：适合计算机学科专业领 域的分词，这主要取决于训练文本的选择；分词效率高：算法核心是基于字符串 匹配的方法；分词精度较好：利用简单统计量模型与机械分词的有机结合解决了 部分歧义词和未登录词问题。 解决方案中涉及到的关键技术主要包括以下三个部分： 第一、分词词典的设计。在整体结构上，词典分成两级结构，临时词典和核 心词典。临时词典是通过统计方法将新词条向分词核心词典中输送的中间容器。 核心词典是分词系统中切分的唯一依据，为了提高查询速度，结合中文二字词比 例较大的特点，核心词典采用双层哈希结构。 第二、统计策略的制定。歧义词和新词的识别主要依靠基于统计的方法，本 文选择了基于互信息原理的方法进行词频统计。该统计模型，原理简单，实现方 便，有较强的实用价值。 第三、机械分词方法的应用。为了简化系统结构，提高算法效率，核心分词 模块中，根据汉语的后重心特点以及“长词优先”准侧，我们选择逆向最大匹配 算法。 总体上讲，系统在初始化后即能够满足一定程度的应用，准确率等分词精度 指标保持在9 7 以上：选择合适的训练语料，经过一定强度的统计学习后，分词 精度参数可以提高将近一个百分点左右；分词效率指标不会发生明显变化。 关键词：词典，统计，未登录词， 歧义词 a b s t r a c t t h et e c h n o l o g yo fc h i n e s e 肋r ds e g m e n t a t i o nc o n t a i n st h r e ed i r e c t i o n st h a tt h e c h i n e s ew b r ds e g m e n t a t i o nb a s eo nd i c t i o n a r y , t h ec h i n e s ew r o r ds e g m e n t a t i o nb a s e o ns t a t i s t i c sa n dt h ec h i n e s e 肋r ds e g m e n t a t i o nb a s eo nu n d e r s t a n d a b i l i t y b e c a u s e t h el a s td i r e c t i o ni sn o tm a t u r e ，m o s ts y s t e m sa d o p tt h es t r a t e g yw h i c hc o n t a i n s d i c t i o n a r ya n ds t a t i s t i c s h o w e v e ri nt h em o s ts y s t e m s t h ed i c t i o n a r ya n ds t a t i s t i c sa t e i s o l a t e d ，d i c t i o n a r yi st h eb a s i so fm e c h a n i c a lw o r ds e g m e n t a t i o n a n ds t a t i s t i c si s u s e df o rs o l v i n gt h ed i f f i c u l t i e so fd i f f e r e n tm e a n i n g sw o r d sa n du n r e g i s t e r e dw o r d s t h em e t h o di nt h i sa r t i c l ei st h a tt h ed i c t i o n a r ya n ds t a t i s t i c sa r ei n c o r p o r a t e t h e r e s u l t so fs t a t i s t i c sa r et h ei n p u t so fd i c t i o n a r y , a n dt ot h ed i f f e r e n tm e a n i n g sw o r d s a n du n r e g i s t e r e dw o r d s ，t h ee s s e n c eo ft h ea l g o r i t h mi st h a te x t e n d st h ed i c t i o n a r yb y t h em e t h o do fs t a t i s t i c sa tf i r s ta n dt h e nu s e st h em e t h o do fm e c h a n i c a lw o r d s e g m e n t a t i o n m ye n e r g ya n dl e v e l i sl i m i t e d ，w es e l e c tt h er e s e a r c ho fc h i n e s ew r o r d s e g m e n t a t i o nf o r t h ed o m a i no fc o m p u t e rs c i e n c e o v e r a l l ，t h i ss y s t e mh a st h ef o l l o w i n gt h r e ef e a t u r e s s p e c i f i c ，f o rt h ed o m a i no f c o m p u t e rs c i e n c e e f f i c i e n c y , a l g o r i t h mc o r ei sb a s e do ns t r i n gm a t c h i n gm e t h o d h i g l la c c u r a c y , w ec o m b i n es i m p l es t a t i s t i c a lm o d e la n dt h em e c h a n i c a ls u b w o r dt o s o l v et h ep r o b l e mo ft h ea m b i g u o u sw o r d sa n du n k n o w nw o r d s t h ek e yt e c h n o l o g i e si n c l u d et h ef o l l o w i n gt h r e ep a r t s f i r s t ，t h ed e s i g no fd i c t i o n a r y i nt h eo v e r a l ls t r u c t u r e ，d i c t i o n a r i e sa r ed i v i d e di n t o t w os t r u c t u r e s ，t h ec o r ed i c t i o n a r ya n dt h et e m p o r a r yd i c t i o n a r y t e m p o r a r yd i c t i o n a r y i st h ec o n t a i n e rf o rt r a n s p o r t i n gn e ww o r d sb e t w e e nc o r ed i c t i o n a r ya n dt e m p o r a r y d i c t i o n a r yb ys t a t i s t i c a lm e t h o d s t h ec o f ed i c t i o n a r yi st h eo n l ys t a n d a r df o rt h e s y s t e m ，s i n gd o u b l eh a s hs t r u c t u r eo ft h ec o r ed i c t i o n a r y s e c o n d t h es t a t i s t i c a ls t r a t e g y a m b i g u o u sw o r d sa n dn e ww o r di d e n t i f i c a t i o n r e l yo ns t a t i s t i c s - b a s e da p p r o a c h ，w es e l e c tt h ep r i n c i p l eo fm u t u a li n f o r m a t i o nt h e o r y t os t a t i s t i ct h ew o r df r e q u e n c y t h es t a t i s t i c a lm o d e li ss i m p l e ，e a s yt ob e i m p l e m e n t e d ，a n dh a v es t r o n gp r a c t i c a lv a l u e t h i r d ，t h ea p p l i c a t i o no fm e c h a n i c a lm e t h o d i no r d e rt os i m p l i f yt h es y s t e m s t r u c t u r c ，i m p r o v et h ee f f i c i e n c y , i nt h e c o r em o d u l e ，a c c o r d i n gt oc h i n e s e c h a r a c t e r i s t i e st h a tt h ef o c u si sb a c k w a r d sa n dt h er u l eo f ”l o n gw o r d sp r i o r i t y ”，w e h a v ec h o s e nt h ea l g o r i t h mo fc o n v e r s em a x i m u m m a t c h i n g o v e r a l l ，s c i e n c et h es y s t e mh a di n i t i a l i z e d ，t h ea c c u r a c yr e m a i n e da t9 7 ，a f t e ra c e r t a i ns t r e n g t hs t a t i s t i c a ls t u d y , t h ea c c u r a c yp a r a m e t e rc a ni m p r o v en e a r l y1 p e r c e n t a g ep o i n t ，a n dt h ee f f i c i e n c yh a d n o tc h a n g e ds i g n i f i c a n t l y k e y w o r d s ：d i c t i o n a r y , s t a t i s t i c ，u m e g i s t e r e dw o r d s ，a m b i g u o u sw o r d s i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生( 签名) ： 学位论文使用授权书 期： 1 蔓! 乏_ 孓? 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库进行检 索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时授权经武 汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论文，并向社会 公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：师( 签名) ：期：出砂 武汉理工大学硕十学位论文 1 1 引言 第1 章绪论 中文分词既是中文信息处理技术中的基础组成部分又是其领域中的前沿课 题。随着人们对汉语自然语言处理技术研究的逐渐深入，中文分词技术不断发展， 各种性能优良的中文分词系统层出不穷。其中绝大部分系统的使用范围广泛，有 较好的通用性。通用中文分词系统的设计要综合考虑各种情况，兼顾各种性能指 标，开发难度较大，开发周期长。目前针对专业领域【删【4 1 j 的中文分词系统并不 多见，并且自身的开发能力和研究时间都有限，本系统选择了计算机专业领域的 语料作为训练文本。计算机专业领域的知识更新很快，这有利于系统研究阶段学 习样本的收集，并且针对这一知识更新较快的专业领域做技术研究才是有价值 的，这样能够充分体现统计分词的优势。 在通用领域，中文分词技术目前的主要瓶颈是在处理未登录词和复杂多变的 歧义词识别，技术上很难再有更大的突破。因为在通用领域，随着网络信息量的 增长，时代的发展，新词出现的频度可想而知，甚至已经达到了不能完全收集的 程度。中文分词中的歧义词出现的形式多样、灵活。我们选择针对计算机专业领 域语料进行训练，从实际上减小了待分析的信息量，缩小了研究范围，本质上降 低了分词系统开发的难度，同时，该系统在专业领域又有着通用系统不能比拟的 优势。 总之，虽然综合性的分词系统功能非常强大齐全，但是用来分析某一特定领 域的信息就会力不从心，所以建立一个针对专业领域的中文分词系统是有必要 的。本论文，在中文分词的技术的基础之上，结合计算机专业领域的文本特点， 设计一套适用于计算机专业领域的中文分词解决方案。 1 2 中文分词发展现状及特点 中文分词系统解决方案中所包含的技术方向有【l j ：机械分词、统计分词、规 则分词以及理解分词。在这几种技术中基于字符串的匹配的方法是最基础的，也 是最根本的，是任何成熟分词系统中不可或缺的组成部分。基于统计的分词方法 适用于未登录词以及歧义词的分解，单纯的统计方法是构造不出完善的分词系统 的。基于理解的分词方法，现在仍然处于研究的起步阶段，尚未形成生产力。还 有基于规则的分词方法，该方法主要是建立一个能够准确反映自然语言中的规律 武汉理工大学硕十学位论文 的语言模型。但是由于语言规则是没有穷尽的，并且规则之间有时会存在矛盾， 所以该方法是有技术瓶颈的。目前比较成熟的系统，主要是基于统计以及机械分 词的结合，集成现有成熟的统计模型，例如隐马尔科夫、条件随机场等，主要是 解决未登录词和歧义问题，取得了比较理想的效果。尽管如此，如果以人工智能 甚至是实际需要的水平为参考，中文分词技术仍有待提高。 1 2 1 中文分词技术的发展 在二十世纪八十年代初期，自动分词技术成为中文信息处理领域中兴起的一 项研究。众多具有实用价值的分词系统相继问世，为以后的中文分词技术的发展 产生了较大的影响。下面列举几个有较强代表性的分词系统。 ( 一) c d w s 一书面汉语自动分词系统 书面汉语自动分词系统产生于1 9 8 3 年，是我国出现的第一个有实用价值的 中文分词解决方案。该系统有北京航空航天大学等十多个单位合作开发的。该系 统的核心分词算法为基于字符串匹配，并且结合了词尾字构词检索技术，配置了 核心知识库以及临时词典，此外还集成了一些有效的纠错知识。该系统有效降低 了分词过程中的错误切分率，在当时的硬件环境下，其分词速度达到了5 至1 0 字每秒钟，切分精度大约为1 6 2 5 。该系统的架构如图1 1 所示。 图1 1 书面汉语分词系统架构图 2 武汉理工大学硕士学位论文 ( 二) a b w s 一现代汉语书面语自动分词系统 该系统由山西大学设计并实现。由于汉字组词的灵活性、复杂性以及新生词 汇不断产生等众多原因，使得单纯基于词典的分词系统很难达到理想的切分效 果，本系统结合了基于统计以及规则的方法解决了部分歧义问题。本系统采用的 是a b 算法，系统本身并不过分依赖于核心分词词典，它利用构词法、构形法、 句法等汉语本身的知识，总结出一些歧义处理的适用的分词规则，以此来提高分 词精度和分词速度。其切分精度和c d w s 相比有显著提高，切分速度为4 8 词 分钟。该分词系统由知识库和选词机制两大部分构成的，系统结构如图1 2 所示。 图1 2 现代汉语书面语自动分词系统架构图 ( 三) 复旦大学中文分词系统 复旦中文分词系统主要由四个模块组成，分别是预处理模块，歧义识别模 块，歧义处理模块以及未登录词识别处理模块。在预处理模块中，除了用一些数 字，英文字母，标点符号，边缘信息等非汉字符号作为分隔符外，还引进了特征 词的概念，它是一些特殊的时间短语、货币符号等。为此系统额外增加了一次全 文扫描用以识别这些元素，当系统扫描之特征词后，采取一定的识别策略，确定 左右边界，实现币确切分。特征词的识别会引入新的问题，若处理不得当，会影 响后续分词流程的结果。歧义识别模块采取的策略是全文双向扫描，正向为最小 3 武汉理r 大学硕十学位论文 匹配，逆向为最大匹配。若两次分词结果有所不同，则说明存在歧义字段，将结 果送入下一环节进行处理。歧义处理模块所要处理的对象是歧义识别模块送入的 结果。该模块的核心思想是基于词频统计和基于构词规则方法结合排歧法。首先 使用构词规则，主要是一些自然语言语法规则，当基于规则的方法不能解决问题 时再采用基于统计的方法。最后是一个未登录词的处理模块。仍然运用的是统计 策略，该方法对识别人名未登录词有较为理想的效果，但是对于中文机构名的识 别仍然显得力不从心。实验结果表明，对中文人名的识别正确率达到7 0 左右。 该系统的主要结构模型如图1 3 所示。 预处理模块 土 歧义识别模块 1 l i 歧义处理模块 1 l 未登录词处理 图1 - 3 复旦大学分词系统主要功能核心架构图 ( 四) 杭州大学改进的正向最大匹配算法中文分词系统 和一般的j 下向匹配算法相比，该系统主要是加入了三条对歧义字段的规避规 则，从而是系统的切分精度有了很明显的提高。 第一，归右原则。通过大量的对交叉歧义的统计，作者发现8 0 以上的歧义 全不可采取归右原则进行处理，简言之就是遇到交叉歧义字段，就将该字段与右 侧的字段结合。 第二，左部结合。对于连续性交叉歧义，归右原则有时会发生错误判断，引 进左部结合规则进行处理。假设“1 2 3 4 ”为连续交叉性歧义，首先根据归右原则 将“3 4 ”合并，然后在根据左部结合原则将“1 2 ”合并，使得最后结果为“1 2 ” “3 4 ”。例如“今天气色不错啊”中的“今天气色”就可逐步分成：“今天气色 4 武汉理l 一大学硕十学位论文 “今天气色”一“今天气色”。 第三，跳跃匹配。在起义处理中有时两种方法的简单结合仍然会产生错误结 果，需要首先做跳跃判断将结果分解成较小的单元在做归右原则+ 左部结合的 处理，以此解决问题。 ( 五) 1 c t c l a s - - 中科院分词系统 中国科学院计算技术研究所经过多年的研究工作，丁= 发出一套性能优照，功 能齐全的中文分词系统- - 1 c t c l a s ，其主要功能包括中文分词、词性标注、命 名实体识别、新词识别同时支撑用户词典。五年内该系统内核升级六次，目前 版本为i c t c l a s 3 0 。该系统的分词速度达到9 9 6 k b 秒a p i 精致不超过2 0 0 k b ， 词典数据经过压缩在3 m 左右，是目前非常高端的中文分词工具。系统运行界面 如图1 - 4 所示。 图1 _ 4 中科院分词系统运行界面 此外，还有一些较有代表性的分词系统未作介绍。主要包括：c a s s 是由北 京航空航天大学没计实现的中文分词系统：清华大学s e g t a g 中立分词系统； 哈工大统计中文分词系统：北大计算语言所中文分词系统：m i c r o s o f tr e s e a r c h 汉 语句法分析器中的自动分词系统。 l - 2 2 中文分词系统的评价标准 一个中文分词系统的主要评价指标包括：切分精度，切分效率、适用范围等。 目前主要从以上特征来判断分词系统的好坏。 切分精度主要包括切分准确率以及切分分全率等指标。其中切分准确率是指 武汉理1 = 大学硕士学位论文 切分结果中包含的正确词汇数目与系统实际切分词汇数目的比率，该项参数越高 系统性能越优越：切分分全率指的是系统切分的词的数目和原文应有的词条数目 之间的比率，该项参数越高系统性能越优越。 切分效率指的是单位时间内分词系统所能够处理的信息量，该项参数越高系 统性能越优越。 目前分词系统有通用性的也有专用性的，所谓适用范围指的就是该系统的这 项指标。有一些专用分词系统知识和某一知识领域，例如化学化工领域；或者适 用某一方面的应用，例如适用于搜索引擎的中文分词系统。 1 3 论文的结构 第一章，绪论部分主要介绍了中文分词发展的现状及特点。 第二章，介绍中文分词系统中的三种常用算法，分别是机械分词、统计分词 和理解分词；简单列举的中文分词所面临的问题级解决方法。 第三章，阐述本论文所设计的分词系统的详细设计方案，详细分析主要技术， 主要包括字典的组织，统计策略的制定等。 第四章，整体介绍本论文所设计的分词算法的流程以及详细设计。 第五章，实验结果展示。主要包括系统评价标准的介绍，以及本论文所设计 的系统实验结果分析。 第六章，系统的总结和展望。 6 武汉理工大学硕士学位论文 第2 章中文分词基本算法研究 中文分词的算法多样，总结起来主要分为三大类，基于字符串匹配、基于统 计的分词算法以及基于理解的分词算法。 基于字符串匹配的分词算法也成为机械分词，该方法依赖于分词词典的建 立，分词的依据为词典中词条的覆盖率，分词效率较高。基于统计的分词主要原 理依据是，相邻单字的共现频率能够反映成词的概率，基于规则的方法本质上也 是一种基于统计的方法，该种方法计算量较大，分词效率相对低下。最后，基于 理解的分词方法，要求计算机能像人一样，分析语意句意，结合上下文环境，判 断成词情况，这种方法仍然处于研究阶段，目前没有成熟的分词系统的主体使用 了该方法。 2 1 中文分词的基本算法 每种分词算法包含若干中具体的方法【1 2 】【1 3 j 【1 4 】。机械分词算法就包含正向最 大匹配，反向最大匹配、全切分、邻接约束法等等：基于统计的方法有简单基于 词频统计的方法，基于现有成熟数学模型的统计方法；基于理解的包括基于规则， 人工智能，神经网络等等方向的研究。 2 1 1 机械分词算法 机械分词算法均是以机器可以识别的分词词典作为分词依据的，所以又称 为基于词典的分词。机械分词的具体算法分类很多，主要有以下三大类别。依据 不同长度词条有限匹配的方案可以分为最大匹配和最小匹配；依据待分词文本的 扫描方向区分，可以分为正向扫描、逆向扫描以及双向扫描；依据与词性标注过 程的结合情况，可以分为单纯分词算法和分词和词性标注一体化的分词算法。将 上述的单一方法结合在一起就能生成一种实用的分词算法，例如：基于字符串的 正向最大匹配分词算法、逆向最小匹配分词算法等等。 传统的机械分词主要是双向的最大匹配算法，随着中文分词技术研究的深 入，发现基本的方法是不能达到较为理想的效果的。机械分词的主要依据是分词 核心词典的建立，所以，绝大部分系统的优化均是围绕如何改进词典的结构展开 的。组织好词典结构后，应该设计与分词词典结构吻合的机械分词算法。机械分 词是依据既定的策略将待分词文本与一个足够大的机器可识别的词典中的词条 7 武汉理工人学硕士学位论文 进行匹配，如果在该词典文件中找到了某个字符串，表示匹配成功，分离出一个 词条。 正向最大匹配基于字符串匹配的算法【1 0 】【1 1 】，是基于词典分词基本方法的典 型代表。该算法的核心思想如下所述。假设核心词典中的词条最长的长度为n ， 从待分词文本的萨向扫描，先对该文本进行预处理，去除文本中的分汉字符号， 将整个文本分成较小的片段，简化后续处理，然后取出长度为n 的汉字串，与 词典中的词条进行匹配，如果找到对应的词条，就将该汉字串取出，该汉字串为 一词条，若词典中没有该词条，则将待匹配的词条长度减一，重复以上的过程， 直至单字词，重复以上的过程直至将待分词文本处理完毕。 典型的简化的基于字符串正向最大匹配的算法流程如图2 - 1 所示。 图2 - 1j 下向最大匹配算法流程图 传统的机械分词虽然在形式上能够解决字符串匹配的问题，但是由于算法过 8 武汉理t 大学硕十学位论文 程简单，控制不够严谨，使得分词效率比较低下。所以对机械分词算法的优化是 非常必要的。目前主要的优化方案主要有以下几种【3 5 l 。 一、字符串匹配长度的选择优化 传统机械分词的匹配方案是最大匹配递减匹配串或者是最小匹配增加匹配 串，但是汉语中，单字词或者多字词的数量是十分有限的，而主要是二字词。分 布图如表2 2 所示。 表2 2 汉语词语包含字数统计结果 词条字数 12 3 = 4 频率6 9 8 0 5 0 0 3 4 2 0 0 1 0 2 2 9 7 6 这样算法中对于字符串的匹配就会造成时间浪费，因为很多匹配都是可以忽 略的。此外，词条匹配长度可以从静态的向动态的转化，以减少匹配次数。从这 个角度出发，选择一个合适的匹配长度是很有必要的。选择一个合适的初始匹配 长度有利于分词效率的提高。 二、分词词典结构的优化 基于字符串匹配的算法性能的优劣主要决定与词典的构造。词典结构的改造 有多种方案主要包括：词条数据结构的变化，词典整体结构的调整。例如，可以 通过给词条加入词频信息用以作为分词的一个参数，弥补长词优先等基于规则的 分词方法的不足：可以将词典设计成多级哈希索引结构，充分发挥哈希查找的快 速性能，提高分词效率；可以将词典设计成多级结构，将分词词典分解成多个词 典，每个词典完成特定的功能，这是一种将复杂问题简单化的解决问题的方法； 扩大切分核心词典的词条规模等等。 经过众多学者多年的努力，实现了多种典型的分词词典机制。例如：基于t i l e 树的词典构造，基于整词二分法的词典构造。 ( 一) 基于t r i e 树的词典构造方法 t i l e 树【5 11 6 】f 7 l 还可称为字典树或者是单词查找树，本质上是一种树形数据结 构，可以用来存储大量字符串。假设t i l e 树的度为n ，则t r i e 树是一棵n = 2 的 树，每一层分支不靠整个关键码的值来确定，而由关键码中的某个分量来决定。 t i l e 树是比较简单的数据结构，其优点是可以利用字符串中的公共前缀来节省存 储空间，但是，由于其结构简单，t i l e 树的内存消耗很大。t i l e 树的基本性质可 总结为以下几点： ( 1 ) 根节点不包含字符，除根节点外每一个节点都只包含一个字符； ( 2 ) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字 符串； ( 3 ) 每个节点的所有子节点包含的字符都不相同。 9 武汉理1 大学硕士学位论文 将t r i c 树应用到词典查找中一次简单成功查找的过程如下描述： ( 1 ) 首先从根鲒点开始查找： ( 2 ) 确定要查找关键词的首关键字，根据泼关键字选择对应的子树，转到该 子树上进行查找： ( 3 ) 在相应的子树中，确定要查找关键词的第二个关键字，并进一步选择对应 的下一个子树进行检索； f 4 ) 进行选代： ( 5 ) 某个结点处，关键词的所有关键字都被确定，则读取该条边上的信息- 完成查找。 t d e 树的结构示例如图2 3 所示： l 鱼上盟l 生盟l 一 互卫皿叵卫覃 、压五丑 m t i l e 树示例图 ( 二) 基于整词二分法的诃典构造 基于整词_ 分法的词典机制，应用十分的广泛。一般情况下，其词典结构 分为三级，前两缎结构为索引，组后一级为词典诈文。其结构示例如图2 - 4 所示。 t$ 图2 - 4 整词二分词典结构示例 假设任意一个汉字字符串为w l w 2 w n ，w l 表示为该汉字字符串的首个宇 哥哥孵 鼍 武汉理工大学硕士学位论文 符，w n 表示为首字符后面的n 个汉字串。一个简单的整词二分查询过程描述如 下： 第一步，通过首字散列表获得该字符的入口指针以及在词索引表中以该字开 头的词条个数： 第二步，通过第一步中获得的信息，在词典正文表中对该汉字串做整词二分 查找，若查询成功则切分出该词条。 整词二分查询法，原理简单，查询效率不高。一次查询只能对所选词汇进行 成词与否判断，不能兼顾其他成词可能。例如：整词二分词串“中国家庭 ， 若检索“国家”词条，则只能切分出“国家”，不能在一次切词过程中切分出所 有成词可能，因此一般情况下整词二分法的效率较低。 2 1 2 基于统计的分词算法 中文自然语言中的词是单字的稳定组合，单字之间同时出现的频率我们称之 为字共现频率。字共现频率越大，那么成词的可能性就越大，这个参数能够较好 的反映上下文中相邻字成词的可信度1 2 通过计算字共现频率筛选词条，这就 是基于统计方法的最基本原理。目前，实际应用的统计方法主要可以分为两大块 内容。第一部分是应用统计量，如互信息原理、n 元统计模型、t 测试原理等。 第二部分就是应用成熟的统计模型，例如隐马尔科夫模型、条件随机场模型以及 最大熵模型等等f 2 2 】【矧。 基于统计的分词算法，本质上不依赖于分词词典，又称为无词典中文分词。 统计方法的优缺点可参考下表2 5 。 武汉理l ：人学硕十学位论文 表2 5 统计方法优缺点对比 统计分词优点 统计分词缺点 有数学理论依据，可以解决歧义和算法时间复杂度较高 未登录此问题 训练语料足够，可总结出语言规律需要大规模训练语料 服务于分词 算法健壮性、致性好分词效果与训练语料相关度较高 下面介绍几种基于统计的分词方法。 ( 一) 互信息原理【冽 互信息原理比较简单，主要是体现了单字之结合的紧密程度有多大，如 果紧密度达到某一个设定的阈值，则判断出该种组合构成一个词条。 定义：对有序汉字串a b 中汉字a b 之间的互信息定义如下面公式所示： 砌- l 0 9 2 高 公式中p 似b ) 表示汉字字符串a b 同时出现的概率，p ( 砷表示单独出现汉字 字符串a 的概率，p ( b ) 表示单独出现汉字字符串b 的概率。a 、b 、a b 在出现 的次数分别定义为n ( a ) ，n ( b ) ，n ( a b ) 。n 表示词频总数，我们可以推出如下公式。 p ( 爿) 。型； p ( 召) 。盟； p ( 爿，b ) ；n ( a b ) 互信息原理比较直接的反映汉字字符串之间的成词可信度，判断方法较为简 单。判断方法如表2 - 6 所示。 表2 - 6 互信息原理分析 条件结果 p ( a ，b ) p ( a ) p ( b ) ，即i ( a ，b ) oa b 之间正相关，a b 成词可能性较 大，当i ( a b ) 大于给定的一个阈值，则 认为a b 是一个词条 p ( 八b ) = p ( a ) p ( b ) ，即i ( 八b ) = 0 a b 之间不相关，成词可能性较小 p ( a b ) “篮球网”。由简单交叉性歧义可扩展至复杂交叉性歧义1 3 1 】，假设“w x y z ” 为字符串，w 、x 、y 、z 分别为单字，u 为词表集合，若( w x u ) n ( x y u ) n ( y z eu ) ，则称“w x y z ”为复杂交叉性歧义。例如：“武汉人民 一 “武汉人民”一 “武汉人民”一 “武汉人民”。 设“w x y z ”为一字符串，x 、y 、z 分别为单字，u 为词表集合，若( w x u ) n ( y z u ) n ( w x y z u ) ，则称“w x y z ”为组合性歧义字段。例如： “春分得意”一 “春分得意”一 “春分得意”。 中文分词中歧义问题的出现，总结起来主要有两种原因。其一是由于汉语的 语法复杂，句子组成会出现重复交叉的情况：其二就是主体的分词算法是基于词 典的，由于汉语中词语的数目是无限的，是不断发展的，不可能将所有的词语都 包含在词表当中，首先是不可能将无限的词条加载进有限的词表容器中，再次即 使将海量的词汇装入词典中，那势必使分词效率发生难以预料程度的下降，是整 个系统瘫痪。 中文分词领域中，目前主流的解决办法可以总结为两种方法。其一，基于规 则的方法，该方法会涉及到自然语言学的知识，需要多学科交叉，并且将规则抽 象成数据模型，并且将模型集成到分词系统中是难度较大的，效果的好坏与规则 1 7 武汉理工大学硕十学位论文 的制定密切相关。其二，基于统计的方法，该方法的中心思想是将所有字的组合 不分别处理，通过概率统计，将满足预先设定阈值的字的组合，看成是词。这种 方法，处理效率相对比较低，因为海量的词频统计是有很高的时间复杂度的，如 果算法处理不当，虽然能够在一定程度上能够解决一部分歧义的问题，但是系统 效率也会出现难以预料的低下。此外，基于理解的分词，理论上是可以在很大程 度上解决中文分词中的歧义问题，但是想让计算机按照人的思维去理解句子，目 前的研究还未完善，所以该方法的研究仍然处于起步阶段，并未形成现实生产力。 2 2 2 未登录词的处理 中文分词系统中，未登录词是指分词词典没有收录的词汇。未登录词种类繁 多，主要包括：中文姓名，中文机构名，专业术语，新生事物，网络流行语，中 文地名等等。由于未登录词问题难以解决，该项指标是评价一个分词系统好坏的 重要参数。 据统计，中文姓名、中文地名以及中文机构名占未登录词中的很大比例，所 以，着重研究这两方面的问题，是重中之重。 由于中文姓名的特殊性，姓和名字有很多规律可循，使得现在有一些比较成 熟的技术用于解决这一问题，例如：基于规则的方法，基于统计的方法，甚至是 基于角色标注的方法。规则和统计相结合的方法，能够很有效的解决中文姓名的 识别。 中文地名在未登录词中，是相对变化较小，发展较慢的组成部分。大部分地 名可以根据已有的权威的地名知识库构造词典，将地名词汇加载到词典中去，这 样就比较容易的解决了一部分问题。对于比较难以处理的部分，可以采用基于规 则的方法进行处理。目前有一些比较成熟的推理机制用以解决中文地名的识别。 图2 - 9 是一种中文地名识别的算法流程图。 1 8 武汉理工大学硕十学位论文 图2 - 9 未登录词一中文地名识别算法流程图 在未登录词的处理中，最棘手的问题便是中文机构名的识别。中文机构名， 种类繁多，变化很大，不断地增加或者减少。好在，从自然语言的角度考虑，中 文机构名的组成是有规律可循的，在机构名称中有很多的专有名词，比如；中央， 大学，办事处，公司，学院，研究院等等。我们整理这些规律，将其抽象成模型， 集成到中文分词系统中，就能够一定程度的解决中文机构名的识别。目前，机构 名识别的主流方法仍然是基于规则的方法。图2 1 0 表示的是一个抽象的中文机 构词条的处理流程图。 图2 1 0 中文机构名处理流程图 1 9 武汉理工大学硕十学位论文 第3 章基于字典与统计的分词算法的设计 本论文所阐述的系统是基于字典与统计策略相结合的分词方法。本章重点阐 述了本系统所要解决的问题以及系统的适用范围，并较为详细的介绍了系统三大 核心技术。第一，分词词典的设计，这是分词的基础：第二，统计策略的制定以 及设计，这是解决歧义和未登录词问题的关键；最后，详细介绍了机械分词的具 体方案，实现系统的设计。 3 1 本系统要解决的问题 机械分词算法简单，处理速度快，对于分词词典内包含的词汇会精确地切分 出来，但是不能处理新词，歧义词。统计分词，虽然，可以一定程度上处理歧义 问题和新词识别问题，但是，统计速度慢，尤其是对大信息量的数据进行处理， 分词效率会明显下降。 综上所述，纯粹的机械分词或统计分词都有其不能克服的缺点，均不能满足 实际分词系统的要求，目前的中文分词技术研究中，应力求一种将两种方法【1 6 1 结合起来的解决方案，以实现较好的分词效果。 本论文所阐述的系统主要完成以下工作： 第一、合理的组织分词词词典整体结构，采用二级词典结构，尽量减小核心 分词词典的规模。 第二、核心词典和临时词典的设计。核心词典采用二级哈希存储结构，提高 查找效率；临时词典采用单字哈希，简化词典结构。 第三、选择合理的统计策略来解决新词的识别，新词包括未登录词和歧义词。 统计策略采用类互信息原理的统计量策略，该方法简单实用，易于实现。 第四、分词算法核心模块，基于字符串匹配的的算法的选择。根据统计，逆 向最大匹配的性能略优于正向最大匹配的，所以我们选择逆向最大匹配算法。 第五、训练库的选择。 3 2 系统特点概述 本论文所阐述的系统主要具有以下几方面的特点。第一，专用性，适合计算 机学科专业领域的分词，这主要取决于学习语料的选择：第二，分词效率较高， 算法核为机械分词。 武汉理工大学硕士学位论文 3 2 1 专用性 通常情况下，一个分词系统都是与某一领域的应用或者某一种应用相匹配的。 例如，适用于化学专业的中文分词系统，适用于搜索引擎的中文分词系统，适用 于语音识别系统的中文分词系统等等。本论文选择的是适用于某一领域的中文分 词系统的研究，即计算机科学领域。本论文所讲述的分词系统，是词典和统计相 结合的分词策略，词典中收录的通用词汇，而解决歧义和未登录词识别的统计模 块主要是针对计算机科学领域的，系统的学习语料是使用武汉理工大学2 0 0 9 届 毕业生吴韦的自动文本分类的结果。系统初始化状态，分词词典中是不包含统计 新词的，随着对语料学习的不断增多，系统对计算机专业领域的分词精度会不断 提高。 3 2 2 精确性 分词精度是衡量中文分词系统的核心指标，本论文设计的系统初始化时，对 通用语料以及计算机科学专业类语料的分词精度值保持在9 7 3 左右，基本上能 够满足般的要求。对计算机科学类语料进行学习后，对通用领域分词精度基本 不产生影响，因为词典中并未更多加载更多通用词汇。但是对计算机科学领域的 文本重新分词，分词准确率明显提高，基本上能达到9 8 4 左右，原因在于系统 学习阶段加载了部分计算机科学专业的词汇。 3 2 3 分词效率 分词效率也是衡量一个中文分词系统的重要指标。统计分词的劣势就在于统 计信息量大，会对分词效率产生负面影响。但是本论文中对语料的学习阶段时才 会加载统计功能模块，学习之后，对新文档进行分词时，并没有加载统计模块， 算法的核心部分仍然是基于字符串匹配的方法，这样能够一定程度上规避统计策 略对算法效率的影响。该系统的分词效率能够达到2 3 0 0 0 词秒，经过笔者测试， 这一性能指标基本上和标准逆向最大匹配算法的分词效率保持一致。 3 3 分词词典的设计 机械分词与分词词典的有效结合才能使分词效率指标表现良好，所以分词词 典的设计非常重要。在中文分词技术发展之初，分词词典就是简单的顺序表，查 找速度比较慢，随着，中文分词技术研究的深入，对分词速度要求越来越高，词 2 1 武汉理1 ：人学硕士学位论文 典的设计也有了很大的发展。 3 3 1 基于哈希的分词词典机制 整词二分法，紧邻匹配法等都支持首字哈希查找，在定程度上加快了分词 速度，但是没有实现词的哈希查找。若能在整个分词过程中贯穿适用哈希查找法， 势必会使分词效率大幅提高，完全的哈希机制应运而生。哈希机制能够在算法时 间上有非常良好的表现，查找效率较高，虽然，哈希机制本身会增加空间的负荷， 但是，实验证明在中文分词系统中，该方法空间上的影响远远小于时间上的影响， 本文的系统设计，词典结构采用双字哈希机制，保障分词过程中关键词串的查找 效率。 3 3 1 1 分词词典的整体构造 一般情况下，传统的机械分词法只有一个分词词典，词典规模比较大，有十 几万到几十万的规模，这样会增大检索词典的复旦，本论文提出词典的分级构造， 分词词典集合由两部分组成，核心词典和临时词典，如图3 - 1 所示。 图3 - 1 分词词典结构图 系统初始化时，临时词典中的数据为空。临时词典中的数据是不断更新的， 但是，该词典中的词条并不作为分词系统的分词依据，系统将满足预设条件的词 条实时导入到核心词典中。核心词典中存储的词条是中文分词系统分词的唯一依 据，该词典的初始化词条包括常用的通用词汇，随着分词经验的增加，核心词典 中的词条会越来越完善，保证分词效果是动态的，并且使整个分词系统朝着更好 的方向发展。 3 3 1 2 核心词典的详细设计 在g b 2 3 1 2 编码中，共包括6 7 6 3 个汉字符号以及6 8 2 个其他符号。一个 g b 2 3 1 2 1 7 l 汉字码包含高低两个字节，高位字节称为汉字区码，范围是b ， 共占用7 2 个码位：低位字节称为汉字位码，范围是a 1 一f e ，共占用码位9 4 个。 武汉理i = 人学硕士学位论文 汉字的区位码能够唯一表示一个汉字。假设某一汉字的g b 2 3 1 2 码为高位h g b ， 低位为l g b ，这是建立哈希函数的依据。 根据对现代汉语构词特点的统计发现，单字词，二字词，三字词，多字词出 现的概率分别为：6 9 8 ，5 0 0 3 4 ，2 0