（计算机应用技术专业论文）面向企业信息检索的中文分词系统的研究与实现.pdf

f j ：- - 、( l 0 ： o l u 、 at h e s i si nc o m p u t e r a p p l i c a t i o nt e c h n o l o g y r e s e a r c ha n d i m p l e m e n t a t i o no fc h i n e s ew o r d s e g m e n t a t i o ns y s t e m f o re n t e r p r i s e i n f o r m a t i o nr e t r i e v a l b yc h uj i n g n i a n s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rl i nh u i l i n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 【l ， j 一 i 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二屯 思o 学位论文作者签名：稻极年 日期：2 神亨7 牛 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年d一年口一年半口两年口 学位论文作者签名：镪铂导师签名：吾择青去_ 签字日期：加8 、1 争 签字日期：z 嘶。1 ，啤 0， 一 】1 一 ， l ， i - ， - 东北大学硕士学位论文摘要 面向企业信息检索的中文分词系统的研究与实现 摘要 随着企业信息的飞速增长，企业信息检索逐渐成为信息检索领域研究的热点，中文 分词作为信息检索的文本处理阶段一个重要步骤，直接影响着检索结果的准确性。学术 界关于分词技术的研究一直比较多，但是目前的研究大多是通用的分词算法，专门针对 企业检索应用的分词技术研究相对较少。因此，研究中文分词技术在企业信息检索中的 应用有重要的理论和现实意义。 本文研究了中文分词的关键技术及难点，分析了分词对大规模信息检索的影响，在 此基础上结合企业信息检索中分词技术的特点，设计了中文分词系统( e i r c w s ) 。由于 面向企业信息检索的分词算法对时间性能要求较高，本文设计了一种新的多字哈希结构 的词典，改善了词典查询算法，提高了分词效率。歧义消除和未登录词识别是分词的两 大技术难点。考虑到企业信息检索应用的特点，在歧义消除部分，本文重点解决交叉歧 义问题，利用双向匹配结果进行比较来检测歧义，采用自定义规则来消除歧义。在未登 录词识别部分，本文提出了一种新的未登录词识别方法，利用数量词识别规则和虚字辅 助切分分词碎片，通过局部词频统计结合单字非词概率，使得算法在不依赖大型语料库 的前提下可以有效地识别多个领域中各种类型的未登录词。 实验结果表明，本文设计的分词系统，分词速度快，准确率高，而且对未登录词具 有很强的识别能力，符合企业信息检索对中文自动分词的要求。 关键词：企业信息检索；中文分词； 歧义处理；未登录词识别 一i i ， ， 东北大学硕士学位论文 目录 r e s e a r c ha 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 mf o re n t e r p r i s ei n f o r m a t i o n r e t r i e v a l a b s t r a c t w i t ht h er a p i dg r o w t ho fe n t e r p r i s ei n f o r m a t i o n ，s t u d yi ne n t e r p r i s ei n f o r m a t i o nr e t r i e v a l i sb e c o m i n gah o tp o i n ti ni n f o r m a t i o nr e t r i e v a l a sa l li m p o r t a n tp r o c e d u r eo ft h et e x t o p e r a t i o ns t a g e ，c h i n e s ew o r ds e g r n e n t a t i o n ( c w s ) i n f l u e n c e st h ea c c u r a c yo f t h es e a r c h i n g r e s u l t sd i r e c t l y t h e r ea r em a n yr e s e a r c h e sw h i c hf o c u so nt h et e c h n o l o g yo fc w s h o w e v e r , m o s to ft h e ma r e a l w a y so nu n i v e r s a la l g o r i t h m s ，s e l d o ms p e c i a l i z e d f o re n t e r p r i s e i n f o r m a t i o nr e t r i e v a l t h e r e f o r e ，s t u d yo nc w si ne n t e r p r i s ei n f o r m a t i o nr e t r i e v a lh a s i m p o r t a n tt h e o r e t i c a la n d r e a ls i g n i f i c a n c e s i nt h i st h e s i s ，w es t u d yt h ek e yt e c h n o l o g ya n dd i f f i c u l t i e so fc w s ，a n a l y z et h ei m p a c t o ft h ec w so nl a r g es c a l ei n f o r m a t i o nr e t r i e v a l t h e na ne i r c w ss y s t e mi sd e s i g n e do nt h e b a s i so ft h i sa n dc h a r a c t e r i s t i c so fc w so ne n t e r p r i s ei n f o r m a t i o nr e t r i e v a l b e c a u s eo fh i 曲 d e m a n df o rs p e e do ns e g m e n t a t i o na l g o r i t h mo fe n t e r p r i s ei n f o r m a t i o nr e t r i e v a l ，w ed e s i g na n e wd i c t i o n a r ys t r u c t u r eo fm u l t i w o r d - h a s h - i n d e x i n g ，i m p r o v et h eq u e r ya l g o r i t h mo nt h e w o r dd i c t i o n a r ya n de f f i c i e n c yo nw o r ds e g m e n t a t i o n a m b i g u i t yr e s o l u t i o na n du n k n o w n w o r d si d e n t i f i c a t i o na r et w od i f f i c u l t i e si nc w s a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fe n t e r p r i s e i n f o r m a t i o nr e t r i e v a l ，w eo n l yr e s o l v eo v e r l a p p i n ga m b i g u i t yd u r i n gt h ed i s a m b i g u a t i o np h a s e b i d i r e c t i o nm a t c h i n gr e s u l t sa r ec o m p a r e dt od e t e c tt h ea m b i g u i t ya n ds e l f - d e f i n e dr o l e sa r e u s e dt or e s o l v et h e m i nt h eu n k n o w ni d e n t i f i c a t i o np h a s e ，an e wm e t h o di sp u tf o r w a r d i n t h i sm e t h o d ，q u a n t i f i e ri d e n t i f i c a t i o nr u l e s ，c l i p p i n gw o r ds e g m e n t a t i o nf r a g m e n ta s s o c i a t e w i t ht h ea u x i l i a r ye m p t yw o r d sa n dt h es t a t i s t i co ft h el o c a lw o r df r e q u e n c yc o m b i n i n gw i t h t h ep r o b a b i l i t yo ft h es i n g l ew o r da r eu s e dt om a k et h ea l g o r i t h me f f i c i e n t l yi d e n t i f yd i f f e r e n t t y p e so fu n k n o w nw o r d si nm a n ya r e a sw i t h o u tl a r g ec o r p u s o u re x p e r i m e n t ss h o wt h a tt h ee i r c w ss y s t e mn o to n l yh a st h eh i g hs p e e da n d a c c u r a c yo ft h ew o r ds e g m e n t a t i o n ，b u ta l s o h a sas t r o n gc a p a b i l i t yi ni d e n t i f y i n gt h e u n k n o w nw o r d s i tm e e t st h en e e d so ft h ec h i n e s ea u t o m a t i cw o r d ss e g m e n t a t i o no f e n t e r p r i s ei n f o r m a t i o n r e t r i e v a l k e y w o r d s ：e n t e r p r i s ei n f o r m a t i o nr e t r i e v a l ；c h i n e s 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 r e s o l u t i o n ；u n k n o w nw o r d si d e n t i f i c a t i o n i i i ， 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第l 章绪论一1 1 1 课题背景1 1 1 1 企业信息检索简介1 1 1 2 中文分词技术发展现状2 1 2 课题的提出及意义3 1 3 课题的研究内容3 1 4 本文的组织结构4 第2 章相关工作5 2 1 中文分词关键技术5 2 1 1 中文分词算法5 2 1 2 分词词典机制7 2 2 中文分词难点9 2 2 1 通用词表和切分规范9 2 2 2 切分歧义1 0 2 2 3 未登录词识别_ 1 l 2 3 分词和企业信息检索的关系1 2 2 3 1 分词对企业信息检索的影响1 2 2 3 2 分词精度与检索性能的关系1 3 2 4 本章小结1 4 第3 章中文分词系统的设计1 5 3 1 设计原则1 5 3 2 系统框架1 6 3 3 词典设计18 3 3 1 词典结构1 8 3 3 2 词典算法2 l 3 3 3 词典存储2 3 3 4 本章小结2 4 一一 东北大学硕士学位论文目录 第4 章中文分词系统的实现2 5 4 1 词典管理2 5 4 2 分词预处理2 6 4 2 1 文档抽取2 6 4 2 2 文本预切分。：2 8 4 3 乡词。2 9 4 4 歧义处理3 2 4 4 1 歧义字段检测3 2 4 4 2 交叉歧义消除3 4 4 5 未登录词识别二二3 7 4 5 1 分词碎片处理3 8 4 5 2 未登录词识别3 9 4 6 本章小结4 4 第5 章测试与分析4 5 5 1 系统功能测试4 5 5 2 词典性能测试4 6 5 2 1 评测指标4 6 5 2 2 测试结果与分析4 6 5 3 分词性能测试，4 7 5 3 1 评测指标4 8 5 3 2 测试结果与分析。4 8 5 4 本章小结5 4 第6 章总结与展望5 5 参考文献5 7 致谢6 1 一v 一 j _ 1 叫 东北大学硕士学位论文第1 章绪论 1 1 课题背景 第1 章绪论 随着互联网的迅速发展，网上信息量呈爆炸式增长，信息检索已经成了人们获取信 息的最主要方式。2 0 0 8 年1 月1 7 日，中国互联网络信息中心( c n n i c ) 在北京发布“第 2 1 次中国互联网络发展状况统计报告，报告显示6 6 6 的用户上网以获取信息为主要 目的，7 2 4 的用户把搜索引擎列为经常使用的网络服务，8 1 的用户利用搜索引擎寻 找信息。 在互联网上搜索服务热潮一浪高过一浪的同时，存在的另一现象是：组织机构内部 信息化浪潮，催生了大量的信息内容。据统计，企业数据每年以2 0 0 的速度增长，其 中8 0 的数据以文件、邮件、图片等非结构化数据形式存放在企业内计算机系统中的各 个角落，而这些数据总量远远超过了互联网信息的总量。有数字表明，企业发布到互联 网的信息只占到信息量的1 一2 ，而9 8 以上的信息是存储在企业内部，企业员工平 一 均每天花两个半小时进行信息的检索与查询工作。由于企业信息的特殊性，复杂性，以 及技术的发展水平等原因企业检索目前应用还不是很多，g o o g l e 、b a i d u 等搜索引擎在 公共信息领域取得的巨大成功使得人们对企业检索这个更加广阔的领域充满了遐想，企 一 业检索也逐渐成为信息检索领域研究的热点险。1 。中文分词是中文信息处理的基础，它作 为企业信息检索的文本处理阶段必不可少的一个环节，直接影响着检索结果的准确性。 ” 1 1 1 企业信息检索简介 信息检索( i n f o r m a t i o nr e t r i e v a l ) ，通常指文本信息检索，包括信息的存储、组织、 表现、查询、存取等各个方面，其核心为文本信息的索引和检索h 1 。从历史上看，信息 检索经历了手工检索、计算机检索到目前网络化、智能化检索等多个发展阶段。企业信 息检索是信息检索的延伸，可以理解为对“企业信息”的检索，也可以理解为“企业 使用的信息检索，前者强调数据的特殊性，后者强调服务对象的特殊性。 简单来说，企业信息检索是对企业内部的信息进行索引，在接收到用户提交的查询 请求以后在索引过的数据中进行查找，然后将查找到的相关结果信息返回给用户。典型 的企业信息检索系统如图1 1 所示。 东北大学硕士学位论文第1 章绪论 器 企业文档服务器 图1 1 企业信息检索系统的体系结构 f i g 1 1t h ea r c h i t e c t u r eo fe n t e r p r i s e i n f o n n a t i o nr e t r i e v a ls y s t e m 由图1 1 可以看到，用户通过查询服务器提交查询请求，然后从索引数据库检索出 相关的结果文档，按照相关度排序之后返回给用户。其中中文分词是企业信息检索系统 索引文档前的一个重要步骤，它不仅对索引效率有影响，对整个系统最终的评价指标一 一查准率和查全率，有着非常重要的影响。 t r e c ( t e x tr e t r i e v a lc o n f e r e n c e ) 2 0 0 5 首次将企业检索设定为一个专门任务，这 是企业信息检索第一次成为全球共同研究的课题，通过这次会议，信息检索技术开始为 企业需求服务，来自企业的课题也将促使信息检索的基础课题取得新的进展喳1 。 1 1 2 中文分词技术发展现状 中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、语音识别、文 本语音转换、自然语言理解等中文信息处理领域的基础研究课题陋1 。 简单地说，分词就是将连续的字序列按照一定的规范重新组合成词序列的过程盯1 。 在英语、德语、法语等欧美语言中，单词之间是以空格作为自然分界符的，而中文的基 本语义单位汉语词之间没有明显的间隔，汉语词的集合与汉字的集合构成一种交叉关 系，一个词可能就是一个字，也可能由两个或多个字组成陋1 。中文和西文的这种不同， 许多西文的处理方法中文不能直接采用，就是因为中文必需有分词这道工序。 目前研究中文分词的大多是科研院校和少数几家搜索引擎商业公司，东北大学、清 华、北大、中科院、北京语言学院、i b m 研究院、微软中国研究院等都有自己的研究队 伍，而真正专业研究中文分词的商业公司除了海量科技以外，几乎没有了。科研院校研 一2 一 东北大学硕士学位论文第l 章绪论 究的技术，大部分不能很快产品化，而一个专业公司的力量毕竟有限，中文分词技术要 想更好的服务于更多的产品，还有很长一段路。 1 2 课题的提出及意义 自从2 0 世纪8 0 年代初中文信息处理领域提出自动分词以来，众多专家和学者在这 一领域取得了令人可喜的进展，提出了许多分词方法。但是这些分词方法本身或多或少 的都存在着种种不足之处，而且随着近年来信息的多元化、复杂化，对信息处理技术的 研究和发展提出了新的挑战。要在浩瀚纷繁的信息海洋中快速而准确的获得自己想要的 信息，信息处理技术必须具备比以往更高的效率。 在当前的技术水准下，分词算法要想获得更好的切分精度，通常都需要利用更多的 语言资源，这样也必须耗费更多的时间去处理这些语言资源，因此一般切分精度比较高 的算法，切分的速度都比较慢；而一些切分速度快的算法，因为抛弃了一些繁琐的语言 处理，所以切分精度都不高。那些较高切分精度的分词算法，因为速度太慢不仅无法满 足实际应用的需求，有时甚至也无法满足其它自然语言处理研究的需要。目前的许多实 际应用产品中，为了保证速度都不得不牺牲部分准确度，采取了一些比较简单的切分算 法。 目前研究分词的团体和学者很多，但大多都集中于研究通用的分词算法，以提高分 词准确率为目的，学术界关于分词的评测也是以通用的分词精度为准绳阳3 。而鉴于分词 在切分标准和切分算法本身上存在困难，我们希望能够针对企业信息检索这一具体的上 层应用来研究相关的分词技术。因此本文的研究目的在于研究企业大规模信息检索中分 词技术的特点，找到一个适合于企业信息检索的，速度与精度相对平衡的，简单实用的 中文分词解决方案。 ， 1 3 课题的研究内容 本课题依托的项目背景源于建立面向冶金行业生产数据的搜索引擎项目。本文主要 针对企业信息检索中的中文信息处理问题进行探索和研究，通过研究传统的中文自动分 词技术，尝试对现有分词技术的切词速度与精度迸一步改进，开发适合于本项目要求的 的分词系统。本文主要研究内容如下： ( 1 ) 分析企业信息检索中分词技术的特点，设计开发适合于企业信息检索应用的 自适应中文分词系统e i r c w s ； 一3 一 东北大学硕士学位论文第1 章绪论 ( 2 ) 通过对传统的中文分词词典机制进行研究，设计系统所使用的分词词典，提 高词典查询效率； ( 3 ) 研究现有分词算法，重点研究机械分词算法，分析比较各种算法的优缺点， 对现有的分词算法进行改进，提高系统分词速度； ( 4 ) 研究分词过程中出现的歧义问题，分析歧义字段的特点和规律，对现有的基 于统计和规则的消歧方法进行改进，提高分词的准确率； ( 5 ) 研究分词过程中的未登录词识别问题，提出一种新的不依赖于大型语料库的 未登录词统一识别方法。 1 4 本文的组织结构 本文的主要内容安排如下： 第一章，论述了课题的研究背景，企业信息检索的概念和特点，中文分词技术的 研究现状，以及中文分词在企业信息检索中的重要性，并介绍了本文所要解决的主要 问题及论文的结构安排。 第二章，对企业信息检索中涉及的中文处理关键技术进行了研究，分析了中文分 词的相关技术及难点，介绍了几种常用的分词方法和分词词典机制，并且论述了分词 对企业信息检索系统的影响。 第三章，设计了中文分词系统的总体框架，介绍了系统各个模块的功能。设计了 一种新的多字哈希词典结构，设计了词典查找算法和词典存储结构。 第四章，详细论述了中文分词系统的实现方法，阐述了词典管理、分词预处理、 分词、歧义处理以及未登录词识别几个部分所涉及到的技术以及具体的实现流程。 第五章，对系统进行了功能和性能测试，根据测试结果对词典算法和分词算法进 行了比较分析。 第六章，对全文进行总结，概述了本文所做的工作以及对下一步研究工作的展望。 一4 一 东北大学硕士学位论文 第2 章相关工作 第2 章相关工作 中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、语音识别、文 本语音转换、自然语言理解等中文信息处理领域的基础研究课题。尽管已被研究了二十 多年，但分词仍然是中文信息处理的瓶颈问题。 2 1 中文分词关键技术 2 1 1 中文分词算法 现有的中文分词算法可分为三大类：基于规则的分词方法、基于理解的分词方法和 基于统计的分词方法n 。 2 1 1 1 基于规则的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一仓“充 分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功( 识别出 一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照 不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配；按照是否 与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。 常用的几种机械分词方法如下： ( 1 ) 正向最大匹配法( 由左到右的方向) ； ( 2 ) 逆向最大匹配法( 由右到左的方向) ) ； ( 3 ) 最少切分：使每一句中切出的词数最小。 目前机械式分词占主流地位的是正向最大匹配法和逆向最大匹配法。在匹配过程中， 又可分为增字和减字匹配两种。还可以将上述各种方法相互组合，例如，可以将正向最 大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点， 正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正 向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为 1 1 6 9 ，单纯使用逆向最大匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的需 要。 2 1 1 2 基于理解的分词方法 基于理解的中文分词又称为知识分词，这种分词方法是通过让计算机模拟人对句子 一5 一 东北大学硕士学位论文第2 章相关工作 的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用 句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子 系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和 语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要 使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息 组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 2 1 1 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越 多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的 可信度。基于统计的分词方法所应用的主要统计量或统计模型有：互信息、n 元语法模 型、神经网络模型、隐马尔科夫模型和最大熵模型等。这些统计模型主要是利用词与词 的联合概率作为分词的信息。可以对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的互现信息。定义两个字的互现信息，计算两个汉字x 、y 的相邻共现概率。 互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认 为此字组可能构成了一个词。这种方法只需对语料中的字组合频度进行统计，不需要切 分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会 经常抽出一些共现频度高、但并不是词的常用字组，例如“这一 、“之一、“有的 、 “我的 、“许多的等，并且对常用词的识别精度差，时空开销大。实际应用的统计 分词系统都要使用一部基本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计 方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快： 效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 2 1 1 4 三种分词方法比较 相比而言，基于词典的分词方法实现简单，较具体、实用，只需要分词词典，而无 需其它语料资源，分词速度快，但是处理歧义切分以及未登录词识别的能力很有限。基 于统计的分词方法不受待处理文本的领域限制，不需要一个机器可读词典，但是它需要 大量的训练文本来建立模型的参数，该方法的计算量比较大，同时它分词精度与训练文 本的选择有关。基于理解的分词方法算法复杂度高，其有效性与可行性尚需在实际工作 中进一步验证。因为汉语毕竟是缺乏词的标志和严格的构词规则。语言界现有的词法、 句法及组合规则仍然是十分笼统的和复杂的，能否有效的、系统地转换成为计算机采用 的形式恐怕难以定论。因此这种分词方法仪是处于研究阶段，距离实用化还有很大差距， 一6 一 东北大学硕士学位论文第2 章相关工作 一般不宜采用。 2 1 2 分词词典机制 分词词典是汉语自动分词系统的一个基本的组成部分。自动分词系统所需要的各类 信息( 知识) 都要从分词词典中获取，分词词典的查询速度直接影响到分词系统的整体 运行速度。而现实应用均对分词速度提出了迫切要求，因此建立高效快速的分词词典机 制势在必行n 1 3 1 。 目前用于组织词典的索引方法主要有两种，一种是t r i e 索引树，一种是散列( h a s h ) 表结构。t r i e 索引树是一种以树的多重链表形式表示的键树n 钔。基于t r i e 索引树的词典 机制一般是对词的首字计算h a s h 值，建立首字h a s h 表，然后建立t r i e 索引树。基于t r i e 索引树的词典结构如图2 1 所示。 图2 1 基于嘣e 索引树的词典结构 f i g 2 1t h ed i c t i o n a r ys t r u c t u r eb a s e do nt r i ei n d e xt r e e h a s h 表方法就是在表项的存储位置和关键码之间建立一个确定的对应函数关系， 使得每个关键码与结构中一个唯一的存储位置相对应。h a s h 函数一般都无法避免把不 同的关键码映像到同一个位置的情况发生，即会产生冲突，因此还通常需要处理冲突的 一7 一 东北大学硕士学位论文第2 章相关工作 方法。基于h a s h 索引的词典机制就是通过构造一种h a s h 函数来计算词语的h a s h 值， 将h a s h 值相同的词语放入一个通常称之为“桶”的集合内。检索时首先计算待查词的 h a s h 值，然后进入相应的h a s h 桶内进行二分查找。常用的有首字h a s h 和两字h a s h 法。 首字h a s h 是利用首字生成h a s h 值，将h a s h 值相同的词放在同一个h a s h 桶中，然 后在桶中进行二分查找。如图2 2 所示。 酋字h a s h 表 啊阿大鼾预 入口项个数 0 0 50 8 97 9 42o 第一项指针 ： ： 一 词索引表 词典正文指针 一 l o a d f a c t o r 时，此算法令l = 2 * l + i 并对哈希表进行重组，其中l o a d f a c t o r 是满 足0 l o a d f a c t o r 1 的常数。在本文中，我们令初始表长i n i t c p a c i t y 和装载因子上限 l o a d f a e t o r 均取缺省值，即令i n i t c a p a c i t y = 1 1 ，l o a c l f a c t o r = 0 7 5 。 词典索引的建立方法：对词典正文进行扫描，记录各个字段相应的信息，并填充到 对应的各个域中。在分词程序初始化的时候，初始化词典数据，由于h a s h 的查询速度 为d ，即能根据h a s h 值直接查找到存储位置，大大提高了数据查询的速度。 3 3 2 2 词典查找算法 在词典中查找一个词( s = c l c 2 c n ) ，词典查找算法如下。 ( 1 ) 初始化，i = l ，找到首字h a s h 索引i i ； ( 2 ) 如果h a s h ( c 1 ) 存在，在i l 中定位得到以首字c i 开头的索引项e l ，记录e l 中“是 否为词 的标志，否则，转i 占j ( 1 1 ) ； ( 3 ) 如果e l 有后续指针并且i + l n ，由e i 的“指针”项得到以“c l 字开头的所有 词的次字哈希索引i i + l ，否则转向( 1 0 ) ； ( 4 ) i + + ，如果h a s h ( c i ) 存在，在i i 定位得到c i 字的索引项e i ，记录e i 中“是否为词刀 的标志，否则转向( 1 1 ) ； ( 5 ) 如果e i 有后续指针并且i + l n ，转i f i j ( 6 ) ，否则转向( 1 0 ) ； ( 6 ) 判断e i 的后续词数是否大于阈值k ，如果大于阈值k ，转向( 7 ) ，否则转向( 8 ) ； ( 7 ) f l = le i 的“指针”项得到以“c 1 c i ”字开头的所有词的后续字哈希索引i i + l ，i + + ， 如果h a s h ( c i ) 存在，在i i 中定位得到c i 字的索引项e i ，记录e i 中“是否为词”的标志， 转向( 8 ) ，否则转i h j ( 1 1 ) ； ( 8 ) 由e i 中的“指针项得到以“c l c i 开头的所有词的剩余字串组w 。i + + ，在 范围w 中通过二分查找第一个字为“c i 的词，若找到，得到范围w l 的位置，记录 c i 的“是否为词”的标志，转向( 9 ) ，否则，转l h ( 1 1 ) ； ( 9 ) 如果+ h n ，在w l 中递归二分查找后续的字“c i ，“c i 十i 并缩小范围，若 找到最后一个词c i 的“是否为词”为“t 则转l f i ( 1 0 ) ，否则，转向( 1 1 ) ； ( 1 0 ) 如果i - - n 并且“成词标志为“t ，成功，返回该词，否则转向( 1 1 ) ； ( 1 1 ) 失败，报告无该词。 本文设计的多字h a s h 索引分词词典结构很适合正向最大匹配分词方法，查询词时 一2 2 东北大学硕士学位论文第3 章中文分词系统的设计 不用预知待查询词的长度，在从汉字串s = c 1 c 2 c n 的第i ( 1 i n ) 个汉字开始分词 时，首先逐字匹配c i ，c i + l ( 此步类似于“t r i e 索引树 的查询方式) ，然后再在c i ， c i + l 所指向的剩余字串中按照后续词数来决定是用h a s h 查找还是用二分查找逐字缩小 范围查询，这样就能仅通过一遍扫描而达到最大匹配的目的。例如：查询s = “老师教 学生们写阿拉伯数字 中从“阿 字开始的最长词。 ( 1 ) 首先在首字h a s h 索引口( 1 1 ) 中通过h a s h 定位得到以“阿 字开头的索引项e l ： ( 2 ) 因为e l 中的“是否为词”项值为“f ”，所以“阿 不是一个词。再由e l 的“指 针 项得到以“阿 字开头的所有词的次字哈希索引1 2 ； ( 3 ) 在1 2 中通过h a s h 定位得到“拉字的索引项e 2 。因e 2 中“是否为词项值为 “f ”，所以“阿拉”也不是一个词。再由e 2 中的“后续词数 项得到以“阿拉”开头 的所有词的剩余字串个数1 0 ，剩余字串数大于阈值k ( 比如8 ) ，继续h a s h 定位得到“伯 字开头的索引项e 3 ； ( 4 ) 因e 3 中“是否为词项值为“t ，所以“阿拉伯 是一个词。由e 3 中的“指针” 项得到以“阿拉伯 开头的所有词的剩余字串组w ； ( 5 ) 在w 中查找第一个字为“数”的词，得到范围w l ，w l 中仅包含一个字串“数 字，“数字对应的“是否为词”标示值为“f ，所以“阿拉伯数”不是一个词； ( 6 ) 在w 中逐字搜索后续的字“字”并缩小范围，最终得到语句s 中从“阿”字开 始的最长词为“阿拉伯数字。 己 3 3 3 词典存储 本文的目标是研究适用于的信息检索领域的中文分词系统。分词词典是系统的基 础，一个好的分词词典应该具有很高的覆盖率，词典中的词条既要具有通用性，又要具 有专业性。本文通过对1 9 9 8 年1 月人民日报语料库训练得到了语言规则词典以及概率 词典等相关语言规则词典。拥有的词典资源分为四部分：通用核心词典、专业词典，语 言规则词典和概率规则词典。核心词典来源北京大学计算机语言研究所的现代汉语语 法信息辞典，总共有1 3 4 2 2 7 个词条；专业词典有钢铁冶金专业词典，共有1 3 5 1 9 词条； 语言规则词典有虚字词典，停用字词典，数词词典，量词词典；概率词典有权重词典和 单字非成词词典。 初始的词典文件是文本文件，其中词的组织方法是：单个的字也算做一个词，每行 只有一个词，以回车键结束，词条按照字的内码顺序组织。词条部分显示如表3 3 所示。 一2 3 东北大学硕士学位论文第3 章中文分词系统的设计 表3 3 核心词典部分词条 t a b l e 3 3s o m ec o r ed i c t i o n a r ye n t r i e s 啊 阿坝 阿波罗 阿伯 阿布 由于本文设计的词典在内存中的数据结构较为复杂，对词典结构的加载以及存储则 至关重要。本文利用软件开发技术中的序列化技术来对词典结构进行保存。序列化是将 对象状态转换为可保持或传输的格式的过程。与序列化相对的是反序列化，它将流转换 为对象。这两个过程结合起来，就使得数据能够被轻松地存储和传输。 由于使用的开发环境是j a v a ，本文利用j a v a 的序列化技术将词典在内存中的状态 直接保存n - - 进制文件中，在每次加载词典的过程中，只需读取词典的序列化文件，直 接反序列化成内存中的词典状态，而不需要每次加载词典时都重新生成多字h a s h 结构， 能极大提高程序运行的速度。在j a v a 程序中，对象是存在于内存中的，实现j a v a 序列 化比较简单，通常不需要编写保存和恢复对象状态的定制代码。实现j a v a i o s e r i a l i z a b l e 接口的类对象可以转换成字节流或从字节流恢复，不需要在类中增加任何代码。利用序 列化技术使得词典的存储与传输变得简单而高效。同样的，系统中使用的其它辅助词典 也都是通过这种序列化技术实现其加载与保存。 3 4 本章小结 本章设计了面向企业信息检索的分词系统。首先根据企业信息检索的分词技术的特 点，设计了中文分词系统的总体框架。在研究现有分词词典技术的基础上，提出了一种 新的基于多字h a s h 的词典结构，并改进了词典查询算法和设计了词典的存储结构。 一2 4 东北大学硕士学位论文第4 章中文分词系统的实现 第4 章中文分词系统的实现 本文设计的中文分词系统主要由以下几个部分组成：词典管理模块，分词预处理模 块，分词模块，歧义处理模块，未登录词识别模块。 4 1 词典管理 一个实用的面向企业信息检索的中文分词系统不但要有快速简洁的分词算法来提 高检索效率以及识别未登录词及专用名词术语的能力，还要具备高质量的词典来适应用 户的多样化需求。词典管理就是提供用来操作词典的接口。词典管理模块主要包括词典 格式转换模块，词典维护模块和词典训练模块。 词典格式转换模块主要功能是转换词典格式。本文设计的分词系统可以适用于企业 多个领域的应用，系统在处理相关主题领域的文档时需要相关的专业词典来辅助切分， 所以系统需要支持用户自定义专业词典的加载。由于系统定义的词典格式与用户自定义 的词典格式不同，在词典加载时，需要对相关的自定义词典进行格式转化，将用户词典 的文本格式转化成系统词典中的二进制格式。本文主要是通过j a v a 对象序列化技术来实 现词典格式的转化。 词典维护模块主要是进行词条维护操作，包括词典的生成，加载，词条的插入、删 除和更新。词典的生成主要是最开始时由文本文件生成内存中的哈希结构