（计算机应用技术专业论文）基于多级hash分词的全文搜索引擎的研究.pdf

基于多级h a s h 分词的全文搜索引擎的研究 摘要 中文分词作为现代搜索引擎技术的重要基础，一直以来是人们研 究的热点和难点。l u c e n e 是一个成熟、开源的软件项目，是一个高 性能的信息检索和查询工具，通过对l u c e n e 源代码的分析和编程实 验，让我们领略到了l u c e n e 的精髓。由于其提供了一套简单却十分 强大的核心a p i ，使得我们可以快速得将它集成到我们自己应用程序 中。但是，l u c e n e 的核心包和扩展包对中文分词采取类似英文的机 械式切分方法。然而由于中英文之间在形式上存在着巨大的差异，这 种切分方法的分词效果是非常低效的。本文在通过对l u c e n e 分词的 结构的分析，设计出了一种基于h a s h 的l u c e n e 的高效机械分词方法。 目前信息处理用的词典机制主要有整词二分、t r i e 索引树、逐 字二分等几种方法，其中t r i e 索引树和逐字二分机制查询效率较高。 这几种词典机制都是以排序的线性表来提高查询效率，数据结构比较 复杂且查询速度较慢。本文主要工作是分析了几种常用词典构造方法 的优缺点，针对分词中特定的查询条件，设计并实现了基于h a s h 的 分词词典，同时分析了基于h a s h 的分词词典的性能。 本文在此研究基础上开发出了个人桌面搜索引擎系统，索引和搜 索部分利用l u c e n e 引擎架构，实现了比l u c e n e 自带的中文分词更有 效的中文分词。文章最后在系统设计和实现的基础上，对中文分词进 行了速度和准确率的测试，并在此基础上提出了今后努力的方向。 关键词搜索引擎中文分词l u c e n eh a s h t h er e s e a r c ho nf u l l t e x ts e a r c he n g i n e b a s e do nm u l t i l e v e lh a s hw o r d s e g m e n t a t i o n a b s t a c t a saf u n d a m e n t a le l e m e n to fm o d e mw e bs e a r c he n g i n e ，t h e t e c h n o l o g yo fc h i n e s ew o r ds e g m e n t a t i o nh a sb e e ns t u d i e da sah o t s p o t f o ral o n gt i m e l u c e n e ，a sam e m b e ro fo p e ns o u r c e ，i sam a t u r et o o l k i t w h i c hc a nb ee a s i l yu s e df o ri n f o r m a t i o ni n d e x i n ga n dr e t r i e v a l w ea l s o c o u l dm a s t e rt h ee s s e n t i a lo fl u c e n eb yt h ea n a l y s i so ft h es o u r c ec o d e a n dt h ee x p e r i m e n t a lp r o g r a m m i n g d u et ot h es i m p l ey e tp o w e r f u lc o r e a p i ，l u c e n ei sa b l et ob ei n t e g r a t e di n t oo u ra p p l i c a t i o nr a p i d l y h o w e v e r , t h ec o r ea n de x t e n d e dl i b r a r i e si nl u c e n eo n l ye n a b l ea u t o m a t i cc h i n e s e s e g m e n t a t i o ni nt h es a m ew a yt h a te n g l i s hw o r d sa r es e g m e n t e d t h eb i g g r a m m a rd i f f e r e n c eb e t w e e ne n g l i s ha n dc h i n e s em a d et h er e s u l t d i s s a t i s f i e d a f t e rt h ed e t a i l e ds t u d yo ff u l l t e x ti n d e x i n ga n dr e t r i e v a l a p p r o a c hw h i c hl u c e n eu s e st oi m p l e m e n tw o r ds e g m e n t a t i o n ，t h i st h e s i s d e v e l o p sah i g h l ye f f e c t i v em e c h a n i c a lc h i n e s ew o r ds e g m e n t a t i o nb a s e d o nh a s hs t r u c t u r e n o w a d a y s ，t h e r ea r es e v e r a ld i c t i o n a r ym e c h a n i s m sf o ri n f o r m a t i o n p r o c e s s ，a n dt h e y a r e b i n a r y - s e e k b y - w o r d ，t r i ei n d e x i n gt r e ea n d b i n a r y - s e e k - b y - c h a r a c t e r t h e l a s tt w om e t h o d sh a v eh i g h e ri n q u i r y e f f i c i e n c y a l l o ft h ea b o v et h r e em e t h o d s i m p r o v e t h e i r i n q u i r y e f f i c i e n c yu s i n gs o r t e dl i n e rt a b l ew i t hc o m p l e xd a t as t r u c t u r e sa n dp o o r i n q u i r ye f f i c i e n c y i n t h i s p a p e r , a d v a n t a g e sa n ds h o r t c o m i n g s a r e a n a l y z e d i no r d e rt os a t i s f yt h es p e c i a li n q u i r yi nc h i n e s es e g m e n t i o nw e d e s i g na n di m p l e m e n tas e g m e n td i c t i o n a r yb a s e do nh a s ha n da n a l y z e t h ep e r f o r m a n c e a d e s k t o ps e a r c he n g i n es y s t e mi sd e s i g n e do nt h eb a s i so ff o r m e r l i k e yw o r d ss e a r c he n g i n ew o r d s e g m e n t a t i o nl u c e n e h a s h l i i 以蚍 烹唧 辩山 晏黧il 吾拈肌 x 遗斌蛔m 呲缺锄m 托 证眦 怒一 砒莹却 远咖砌 出 眦刚 盏一 洲 蹦咖 嚣一 e 嘭 忙 n 粥出咄燃也 脓呈 k 陀m础“倒朗“ s 譬 s脚疵铽 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 盎壶 日期：塑叁! ；! 兰2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：年学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：塑! ：；：兰2 日期： 北京邮电大学硕士学位论文第一章绪论 1 1 课题背景和意义 第一章绪论 随着互联网的普及和信息技术的同新月异，网络信息不断膨胀，每个人的电 脑上的信息也可以说是迅速膨胀起来，同时人们对信息查询的要求越来越高。如 何给用户提供更好的信息检索机制，从用户本地电脑上的海量信息中检索出来用 户最需要的信息，全文搜索技术就是其中一项关键的实现技术。 全文搜索引擎的理论基础是信息检索技术。信息检索技术于2 0 世纪5 0 年代 被确立为一门独立的学科，这一时期计算机的应用和电子文本的大量出现成为传 统的数据检索向现代意义的信息检索过渡的主要推动力。2 0 世纪9 0 年代中期， 人们将已发展到一定程度的文本信息检索技术应用到i n t e m e t 上，网络的广泛应 用推动了信息检索技术的发展和应用，而搜索引擎的出现为信息检索开辟了一个 新的研究领域。l u c e n e 是a p a c h e 软件基金会j a k a r t a 项目组的一个子项目，是一 个开放源代码的全文检索引擎工具包，提供了完整的查询弓| 擎和索引引擎，部分 文本分析引擎。l u c e n e 的目的是为软件开发人员提供一个简单易用的工具包， 以方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起完整的全 文检索引擎。其基本搜索思想是对搜索内容进行全文匹配，向用户返回大于一定 相关度的内容。但是l u c e n e 对于中文分词支持并不是太好，只是简单的两字切 分，所以对于中文的词的切分并不是十分准确的，所以现在的一般的切词程序都 带有一个或多个词典，这时候就要考虑到切词速度的问题。 本课题正是在这样的背景下提出来的，我们希望通过对l u c e n e 的深入研究， 剖析其工作原理和运行机制，在保证其准确率的前提下，如何可以最大限度的提 高切词的速度，使得该分词程序可以满足搜索引擎的要求。 最后，希望我们的研究和实践可以为h a s h 分词后续研究，提供一些有价值 的技术准备，同时，在研究的基础上，创建一个基于该分词的一个桌面搜索引擎 的系统，为分词和桌面搜索技术的进一步发展贡献自己的一份力量。 北京邮电大学硕士学位论文第一章绪论 1 2 主要工作和贡献 本课题的目标是，在深入研究l u c e n e 的基础上，提出基于l u c e n e 的高效分 词算法，并在研究的基础上，开发一个桌面搜索系统。 本人负责并完成的工作主要包括： 1 对l u c e n e 的结构和工作原理进行了研究，对于l u c e n e 的分词模块进行了 深入了解； 2 根据l u c e n e 的结构编写了多级h a s h 的分词模块，并在此基础上对分词模 块进行了扩展和优化； 3 对分词模块进行了功能测试和对比测试； 4 开发基于l u c e n e 和分词模块的桌面搜索引擎系统。 1 3 本论文的组织 全文主要分为四部分： 第一部分由第二章构成，主要详细介绍了现阶段中文分词的发展的最新的情 况，并在此基础上提出了一种新的改进词典算法； 第二部分以第三章为主，介绍了全文搜索引擎l u c e n e 的历史和结构分析， 深入研究l u c e n e 的分词模块t o k e n i z e r ，并对其进行相应的扩展，完成新的算法； 第三部分由第四章构成，基于新算法和l u c e n e 完成了桌面搜索引擎c o s o u ， 并对分词的结果进行对比测试，然后对测试结果进行分析； 第四部分由第五章构成，对整个论文进行了总结。 2 北京邮电大学硕士学位论文第二章中文分词算法 第二章中文分词算法 2 1 中文分词的研究进展 自然语言和各种符号语言，是人类进行推理和交流的桥梁。随着计算机技术 和人工智能技术的发展，人们迫切希望计算机能够像人类那样对自然语言进行处 理，从而产生了人工智能技术的一个分支，其研究方向包括搜索引擎、问答系统、 机器翻译、文摘生成等等。随着研究的深入，人类对计算机语言处理的能力要求 越来越高，尤其是对本国语言的处理。计算机对于中文的处理相对于对于西文的 处理存在更大的难度。中文和西文截然不同，因此在处理技术上有很大的区别， 分词体现了中文与西文的显著的不同： ( 1 ) 西文文本是小字符集上的已充分分隔开的词串，而中文文本是大字符 集上的连续字串。词是最小的能够独立活动的有意义的语言成分。诸如英文、法 文、拉丁文等欧美语言在书写时，词与词之间都是用空格分开，因此词与词之间 的界限在书面上是泾渭分明的，而中文在书写时，词与词之间不留空白，一个句 子就是一系列前后连续的汉字组成的字符串，词与词之间没有明显的界限。 ( 2 ) 中文的形态没有西文丰富，书面上的单词基本上没有时态的变化。在 这种情况下，对中文文本进行单个词的自动切分，使词与词之间的界限暴露出来， 才可能对中文文本进行进一步的分析和处理。 ( 3 ) 中文尚未形成规范化的语法，人们习惯于非规范化的语法，所以语义 研究的重要性比西方语言重要得多。 所以，分词是汉语自然语言处理的第一步，也是最重要的基础环节。在中文 信息处理中，如信息检索、信息抽取、汉字的简体繁体转换、w e b 文本挖掘、 文本分类、文本校对以及图书情报关键词的建立等，都需要对文本信息进行分词 处理。 2 1 1 主要的几种分词方法 现有的分词算法主要分为三大类，机械分词方法、统计分词方法和基于理解 的分词方法。 1 机械分词方法 北京邮电大学硕士学位论文第二章中文分词算法 这是一种基于字符串匹配的分词方法，它是按照一定的策略将待分析的汉字 串与一个机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功 ( 识别出一个词) 。按照扫描方向的不同，机械分词方法可以分为正向匹配和逆向 匹配；按照不同长度优先匹配的情况，可以分为最大匹配( 简称m m 法) 和最小匹 配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相 结合的一体化方法。常用的几种机械分词方法如下： 1 ) 正向最大匹配法( 由左到右的方向，f m m 法) ； 2 ) 逆向最大匹配法( 由右到左的方向，b m m 法) ； 3 ) 最少切分( 使每句中切出的词数最小) ； 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最 大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配 和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配， 遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为 1 1 6 9 ，单纯使用逆向最大匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实 际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过 利用各种其它的语言信息来迸一步提高切分的准确率。 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其 基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处 理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。 在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来 对分词歧义进行判断，即它模拟人对句子的理解过程。这种分词方法需要使用大 量的语义知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息 组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 3 统计分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好 的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的互现信息。定义两个字的互现信息，计算两个汉字x 、y 的相邻共现 概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈 值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进 行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。 实际应用的统计分词系统都要使用一部基本的分词词典( 常用词词典) 进行 串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起 4 北京邮电大学硕士学位论文第二章中文分词算法 来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下 文识别生词、自动消除歧义的优点。 在实际应用中，往往采用的是以机械分词为主，统计分词为辅的分词方法， 统计分词只是对分词结果作一些微小的修正。 2 1 2 基于h a s h 的机械分词 基于h a s h 结构的机械统计分词方法主要分为三个步骤，即预处理阶段、机 械分词阶段、统计分词阶段。首先在预处理阶段去除原始语料中那些非汉字字符 ( 系统为汉语自动分词系统，对于非汉语字符如西文，阿拉伯数字，标点符号等 暂时不予以考虑，权且将之视为词与词之间的分隔符) ，并将原始语料中的句子 分割成一些短语，这些短语是相对于句子而一言单位较小的字符集合，预处理阶 段可谓是一个“粗加工过程。由于在机械分词阶段难免会遇到多次的匹配查找， 而匹配查找占据了分词处理绝大部分的系统开销，因此采用一种合理的匹配查找 方法将会大大减小系统开销。在众多的查找算法中，h a s h 算法查找匹配性能己 经得到绝大多数人的肯定，虽然采用h a s h 算法会产生一些系统空间上的冗余， 但是可以大大缩短时间上的开销，权衡其利弊，h a s h 算法无疑是最佳的选择。 在传统的最大匹配算法中最大匹配长度是一个固定值，这个值如果取得过大 势必会造成不必要的比较匹配，影响到分词的效率；而如果取得太小又无法识别 出更长的词语，则会影响到分词的精度。因此最大匹配长度值的确定无疑是很重 要的，但是无论如何都会造成一定的冗余。最理想的情况是动态地改变这个数值， 为每个首字都“度身分配一个最大匹配长度，这样就可以有效的消除不必要的 冗余。根据这个思想，系统在系统中添加了一个单字字典，在该字典中记录了每 个字的最大词长。当要对一个字符串进行分词时，首先取出字符串的第一字符， 在单字字典中查找出它的最大词长，将这个值作为最大匹配长度值，然后再根据 最大匹配算法思想进行分词。 机械分词方法顾名思义比较“机械化”，这种分词方法的好坏直接依赖于字 典的存储组织的方式，不论是哪种基于词典的分词方法，分词字典的查询速度是 匹配算法效率的直接决定因素，因而建立高效快速的分词词典机制势在必行。下 面就介绍几种比较常用的分词词典。 2 2 常用的三种分词词典 常用的分词词典机制有基于整词二分的词典机制、基于t r i e 索引树和基于 逐字二分的词典机制。 北京邮电大学硕士学位论文第二章中文分词算法 针对分词系统的特点，可以将分词词典的查询操作大致分为三种基本方式： 查询方式1 ：在分词词典中查找指定词w ( 词在分词词典中的定位) ，这是 一种最基本的查询方式。给定词w 并返回它在分词词典中的位置，以便得到它 的各类附属信息。此时词条是确定的，可以简单地给出结果。 查询方式2 ：根据分词词典，在汉字串s 中查找从某一指定位置i 开始的最 长词w i ，该方式( 对应最大匹配法) 有别于查询方式l ，这里最长词w i 和长度 无法预知，需要在查询过程中动态地确定。通常的做法是尝试始于位置i 的所有 可能长度的词，多次运用查询方式1 来完成查询。 查询方式3 ：根据分词词典，在汉字串s 中查找从某一指定位置i 开始的所 有的词w l ，w 2 ，w i ，m a x ( 对应全切分分词法) 类似查询方式2 ，但返回结果 通常不唯一。 2 2 1 整词二分的分词词典机制 这是一种广为使用的分词词典机制，其结构通常分为三级，前两级为索引( 见 图2 1 ) 。 ( 1 ) 首字散列表 首字散列表 入口项指针 第一项指针 词索引表 词典正文指针 词典正文 啊阿大鼾噗 0 0 50 8 97 9 40 0 20 0 0 | 川 l 啊啊哈阿呀啊呦阿吁阿 啊q 鼾睡 图2 1 整词二分的分词词典彩l 制 词首字散列函数根据汉字的国标区位码给出，通过一次哈希运算即可直接定 位汉字在首字散列表中的序号。 首字散列表的一个单元包括两项内容： 入口项个数( 4 字节) ：以该字为首字的词的个数； 第一入口项指针( 4 字节) ：指向第一入口项在词索引表中的位置。 ( 2 ) 词索引表 因为词的长度可变( 实际系统中还包括附属于该词的各类信息) ，故选择不 定长存储为宜，此外必须实现对词的随机访问，这两条决定了必须建立词索引表。 6 北京邮电大学硕士学位论文 第二章中文分词算法 词索引表的一个单元仅含一项内容； 词典正文指针( 4 字节) ：指向词在词典正文中的位置。 ( 3 ) 词典正文 以词为单位的有序表，通过词索引表和词典正文的配合，很容易实现指定词 在词典正文中的整词二分快速查找。 此种分词词典机制比较适合于查询方式1 ，而在查询方式2 和3 中，对于任 一位置i ，通常不得不预先主观设定一个词的可能最长长度l ( 一般取词典中最 长词的长度) ，然后截取子汉字串s i ，i + l 1 作为假想词，在词典中进行整词二 分查找。不成功则词长l 递减一并循环，直至匹配成功。由于一、二、三和四字 词分别占词典的3 6 、6 4 o 、1 6 o 和1 4 0 ，它们覆盖了真实文本绝大部分， 因此这种盲目尝试方法效率很低。 例如查询字串s “水怪大白天现形一个多小时这个令人惊异的消息不胫而 走 中从“大 字开始的最长词。 取“大 字开头的最长可能的汉字串w i ，m a x = “大白天现形一个多小时 这个令人惊异的”( 词典中最长词为1 7 个汉字) ； 用整词二分法在词典中查找候选词w i ，m a x 失败； 去掉w i ，m a x 减去最后一个字，重复步骤，失败； ； 经过1 4 次的错误尝试w i ，m a x 最终消减到“大白天”，查找成功，于是 返回w i ，m a x = “大白天。 2 2 2t r i f 索引树的分词词典机制 t r i e 索引树是一种以树的多重链表形式表示的键树。面向英文的t r i e 索 引树一般以2 6 个字母作为关键字，树结点包含个数相同的指针。汉字接近7 0 0 0 个，如果采用同样的策略构造中文词典，显然将造成指针的大量浪费，面向中文 的t r i e 索引树的结点应允许指针个数变化。 基于t r i e 树的分词词典由两部分组成( 见图2 2 ) ( 1 ) 首字散列表 同基于整词二分的分词词典机制，首字散列表的一个单元是所对应汉字的 t r i e 索引树的根结点。 ( 2 ) t r i e 索引树结点 t r i e 索引树结点是以下述结构为单元的、按关键字排序的数组：关键字( 2 字节) ，单一汉字；子树大小( 2 字节) ，以从根结点到当前单元的关键字组成的 子串为前缀的词的个数；子树指针( 4 字节) ，子树大小非0 时，指针指向子树， 北京邮电大学硕士学位论文 第二章中文分词算法 否则指向叶子。在t r i e 索引树上查询任意一个词w 1 ，n 的过程为： 首字散列表 入口项指针 第一项指针 关键字 子树大小 子树指针 夕 大 啊阿大 鼾 i 鼾 睡 大 坝 图2 - 2 基于t r e i 索引树的分词词典机制 根据首字散列表得到w 1 的t r i e 索引树，沿相应指针移动至目标结点 n o d e x ：i = 2 ； 在n o d e x 的关键字域中对汉字w i 进行二分查找。如果与n o d e x 的第 i 个单元的关键字匹配不成功，退出此过程；否则沿该单元的子树指针移至目标 结点，并令该结点为新的n o d e x ：i = i + l ；重复该步骤，直至n o d e x 为叶子结 点； 如果抵达叶子结点时i n ，则查询成功，w 1 ，n 】为分词词典中的一个词， 否则查询失败。 与整词二分法形成鲜明对照的是，基于t r i e 索引树的分词词典机制每次只 比较一个汉字，不需预知待查询词的长度，且在对汉字串s 的一遍扫描过程中， 就能得到查询方式2 和3 的结果。这种由短词及长词的确定性工作方式避免了整 词二分分词词典机制中不必要的多次试探性查询。 由于t r i e 索引树己蕴涵了词条信息，因此词典中不必再显式地罗列词条， 可直接存储词的附属信息，叶子指针直接指向这些信息。 例如查询字串s “水怪大白天现形一个多小时这个令人惊异的消息不胫而 走 中“大”字开始的最长词及所有词： 首先通过首字散列表得到以“大”字开头的词的t r i e 索引树结点t 。 北京邮电大学硕士学位论文第二章中文分词算法 由于结点t 中包含关键字“ ，( 表示空字符，下文同) ，因此“大 是一 个词。在结点t 中用二分法查找关键字“白”，其指针指向的目标结点设为t l ； 结点t l 中包含关键字“ ”，因此“大白”也是一个词。在结点t l 中继续 用二分法找关键字“天”，此时“天 的目标结点已是叶子结点，“大白天也是 一个词，查询结束。最后得到“大白天”为最长词，中间过程识别的“大”、“大 白 和“大白天 均为从“大”字开始的词。 t r i e 索引树分词词典机制的主要缺点是其构造及维护比整词二分复杂。 2 2 3 基于逐字二分的词典机制 针对整词二分和跟t r i e 索引树的不足，这里设计了一种改进方案：基于逐 字二分的分词词典机制( 见图2 3 ) ，逐字二分与整词二分在数据结构上完全一致， 不同的仅仅在于查询过程，不再将整个词作为关键字进行比较，而是类似t r i e 索引树的情形，每次仅仅比较单个的汉字。因而其效果同t r i e 索引树完全一样。 例如查询s “水怪大白天现形一个多小时这个令人惊异的消息不胫而走”中 “大”字开始的最长词及所有词： ( 1 ) 通过首字散列表可知：以“大”字开头的词位于索引表的第1 4 2 8 5 到 1 5 0 7 8 项范围内，并且其中的头一项“大”为一个单字词； ( 2 ) 通过二分法在第1 4 2 8 5 到1 5 0 7 8 项的范围内查找第二个字为“白 的词， 可知以“大白开头的词位于索引表的第1 4 2 9 2 到1 4 2 9 7 项范围内，并且其中的 头一项“大白”为一个二字词； ( 3 ) 通过二分法在第1 4 2 9 2 到1 4 2 9 7 项的范围内查找第三个字为“天”的词， 可知以“大白天”开头的词位于索引表的第1 4 2 9 6 到1 4 2 9 7 项范围内，并且其中 的头一项“大白天”为一个三字词； ( 4 ) 通过二分法在第1 4 2 9 6 到1 4 2 9 7 项的范围内查找第四个字为“现”的词， 此范围为空，查询结束。最后得到“大白天 为最长词，中间过程识别的“大 、 “大白”和“大白天 均为从“大”字开始的词。 2 2 4 三种分词词机制的实验结果 从时间和空间角度对第二节所述的分词词典机制进行了实验比较： 空间： ( 1 ) 词表( 仅含词条，不计词条所含的各类信息) 占用空间7 8 2 6 7 8 字节； ( 2 ) 首字散列表：每个单元占8 字节，共7 6 1 4 个单元( 包括一和二级汉字 及某些图形符号) ，故首字散列表占用空间7 6 1 4 3 8 = 6 0 9 1 2 字节； 9 北京邮电大学硕士学位论文 第二章中文分词算法 首字索引 词索引表 图2 - 3 基于逐字二分的分词词典机制 啊 大 大案 大白 大白菜 大白话 大白鼠 大白天 大白天说梦话 大鲵 ( 3 ) 词索引表：每个词占4 字节，共1 1 2 9 6 7 个词，故索引表占空间1 1 2 9 6 7 * 4 = 4 5 1 8 6 8 字节； ( 4 ) t r i e 索引树：每个t r i e 索引树结点单元占8 字节，共含1 2 9 5 8 8 个 索引项，故t r i e 索引树占用空间1 2 9 5 8 8 * 8 = 1 0 3 6 7 0 4 字节。 基于整词二分和逐字二分的分词词典机制包括( 1 ) 、( 2 ) 和( 3 ) 项开销。 而基于t r i e 索引树的分词词典机制包括项( 2 ) 和( 3 ) 项开销。 时间： 对每种分词词典机制，均设计了四个不同类型的测试： ( 1 ) 对字典的所有词依次查询1 次( 第一类查询) ； ( 2 ) 对字典的所有词依次查询，查询次数与词频成正比( 第一类查询，模拟 真实文本环境) ； ( 3 ) 从语料库中任意取段测试文本，用最大匹配分词法切分该文本( 第二 类查询) ； ( 4 ) 从语料库中任意取一段测试文本，用全切分分词法切分该文本( 第三类 查询) 。 针对( 3 ) 和( 4 ) ，从人民日报中随机选取了长度为3 0 6 6 k 字节的文本 作为测试文本。则关于空间、时间的实验结果总汇如下： l o 北京邮电大学硕士学位论文第二章中文分词算法 表2 - 1 空间时间的对比 查询方法词典空间测试l ( 单测试2 ( 单 测试3 ( 单位测试4 ( 单位 ( 字节) 位时间)位时间)时间)时间) 整词二分 1 2 9 5 4 5 85 0 03 9 5 01 0 5 4 6 01 6 8 9 5 0 t r i e 索引树 1 0 9 7 6 1 62 7 02 1 4 06 7 5 0 8 9 5 0 逐字二分 1 2 9 5 4 5 83 3 09 8 06 4 8 0 9 6 1 0 从实验结果来看，三种分词词典机制的空间效率差不多。而基于t r i e 索引 树和逐字二分的分词词典机制的时间效率大致相同，较基于整词二分的词典机制 均有大幅度的改善。由于基于逐字二分的词典机制的实现比t r i e 树简单，所以 认为就综合性能而言，前者较后者更为优越。由表中可见，对最大匹配分词法和 全切分分词法，基于逐字二分的分词词典机制的处理速度较基于整词二分的处理 速度分别提高了1 5 3 倍和1 6 6 倍，效果十分显著。 通过对目前常见词典机制的比较，可以得出这三种词典机制的优缺点： ( 1 ) 整词二分法 结构：首字散列表、词索引表、词典正文； 优点：数据结构简单、占用空间小； 缺点：全词匹配，效率相对来说不高。 ( 2 ) t r i e 索引树法 结构：首字散列表、t r i e 索引树结点； 优点：分词中，不需预知待查询词的长度，沿树链逐字匹配； 缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。 ( 3 ) 逐字二分法 结构：同整词二分法； 优点：查询采用逐字匹配，提高了一定的匹配效率； 缺点：由于词典结构未改变，效率的提高有限。 2 3 多级h a s h 的词典机制 为了最大限度的提高匹配的时间效率并兼顾空间利用率，提出了一种新的分 词词典机制一多级h a s h 的词典分词词典机制。我们吸纳了“整词二分 及 “t r i e 索引树 二者的优点，依次对每个字建立h a s h 索引，构成了多级t r i e 树，但是与t r i e 索引树不同的地方在于相当于t r i e 树的结点的地方里面存放 了是一系列的词，这些词共同点就在于他们的前n 个字是相同的，我们称这一 系列的词组成了一个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 桶，如此往复下去， 直到每个h a s h 桶里面的词的数量小于阈值。举例说明，如下图所示，假如设定 好阈值为6 ，以“一”为开头的词肯定超过了6 个，图片只截取了词典的片断， 这时要开始建立下一级的h a s h 桶，经过判断，以“一致”为开头的词在词典里 面有5 个，没有超过阈值，就把这5 个词放到一个h a s h 桶中。再接着判断，发 现以“一般”为开头的词超过了阈值，这个时候就要再建立下一级h a s h 桶，最 后建立的结果如图2 4 所示。 由此可以知道，这种分词词典的格式主要由以下几点控制： ( 1 ) 对于每级的h a s h 桶，都有一个标志为，h a s h l n d e x 来表明现在所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 l n d e x 这个标志位就可以知道查找的是那个h a s h 桶了。 ( 2 ) 控制每个h a s h 桶最多词个数的阈值。这个阈值的直接关系到建立h a s h 桶的个数，也就是内存消耗的多少，阈值越大，建立的h a s h 桶的个数越少，内 存消耗的越少，这时候消耗在二分查找上的时间就比较多，而阂值越小的话，建 立h a s h 桶的个数就越多，但是消耗在二分查找的时间就越少，当设定阈值为2 的时候，相当于每个词都是h a s h 索引的。 北京邮电大学硕十学位论文第二章中文分词算法 2 4 本章小结 图2 4 多级h a s h 原理图 本章中，主要是介绍了现在中文分词的现状，并着重的介绍了基于h a s h 的 机械分词方法，接着又介绍了机械分词常用的几种词典，并对这几种词典的特点 进行了相关的试验。并在此基础上提出了一种新的词典机制。 北京邮电大学硕士学位论文第三章基于l u c e n e 的分词技术研究 第三章基于l u c e n e 的分词技术研究 3 1l u c e n e 概述 l u c e n e 是a p a c h e 软件基金会j a k a r t a 项目组的一个子项目，是一个开放源代 码的全文检索引擎工具包，即它不是一个完整的全文检索引擎，而是一个全文检 索引擎的架构，提供了完整的查询引擎和索引引擎，部分文本分析引擎( 英文与 德文两种西方语言) 。l u c e n e 的目的是为软件开发人员提供一个简单易用的工具 包，以方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起完整 的全文检索引擎。目前已经有很多应用程序的搜索功能是基于l u c e n e 的，比如 e c l i p s e 的帮助系统的搜索功能。l u c e n e 能够为文本类型的数据建立索引，所以 只要能把要索引的数据格式转化为文本，l u c e n e 就能对该文档进行索引和搜索。 3 1 1 全文检索 全文检索是指计算机索引程序通过扫描文章中的每一个词，对每一个词建立 一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根 据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程 类似于通过字典中的检索字表查字的过程。 全文检索的方法主要分为按字检索和按词检索两种。按字检索是指对于文章 中的每一个字都建立索引，检索时将词分解为字的组合。对于各种不同的语言而 言，字有不同的含义，比如英文中字与词实际上是合一的，而中文中字与词有很 大分别。按词检索指对文章中的词，即语义单位建立索引，检索时按词检索，并 且可以处理同义项等。英文等西方文字由于按照空白切分词，因此实现上与按字 处理类似，添加同义处理也很容易。中文等东方文字则需要切分字词，以达到按 词索引的目的，关于这方面的问题，是当前全文检索技术尤其是中文全文检索技 术中的难点。 3 1 2l u c e n e 的特点 l u c e n e 作为一个全文检索引擎，其具有如下突出的优点： ( 1 ) 索引文件格式独立于应用平台。l u c e n e 定义了一套以8 位字节为基础 1 4 北京邮电大学硕士学位论文第三章基于l u c e n e 的分词技术研究 的索引文件格式，使得兼容系统或者不同平台的应用能够共享建立的索引文件。 ( 2 ) 在传统全文检索引擎的倒排索引的基础上，实现了分块索引，能够针 对新的文件建立小文件索引，提升索引速度。然后通过与原有索引的合并，达到 优化的目的。 ( 3 ) 优秀的面向对象的系统架构，使得对于l u c e n e 扩展的学习难度降低， 方便扩充新功能。 ( 4 ) 设计了独立于语言和文件格式的文本分析接口，索引器通过接受t o k e n 流完成索引文件的创立，用户扩展新的语言和文件格式，只需要实现文本分析的 接口。 ( 5 ) 已经默认实现了一套强大的查询引擎，用户无需自己编写代码即使系 统可获得强大的查询能力，l u c e n e 的查询实现中默认实现了布尔操作、模糊查 询、分组查询等等。 3 1 3l u c e n e 的结构 l u c e n e 作为一个优秀的全文检索引擎，其系统结构具有强烈的面向对象特 征。首先是定义了一个与平台无关的索引文件格式，其次通过抽象将系统的核心 图3 一ll u c e n e 的结构 组成部分设计为抽象类，具体的平台实现部分设计为抽象类的实现，此外与具体 平台相关的部分比如文件存储也封装为类，经过层层的面向对象式的处理，最终 达成了一个低耦合高效率，容易二次开发的检索引擎系统。 从图3 1 中我们清楚的看到，l u c e n e 的系统由基础结构封装、索引核心、对 外接口三大部分组成。其中直接操作索引文件的索引核心又是系统的重点。 l u c e n e 的将所有源码分为了7 个模块( 在j a v a 语言中以包即p a c k a g e 来表示) ， 各个模块所属的系统部分也如上图所示。需要说明的是 北京邮电大学硕士学位论文 第三章基于l u c e n e 的分词技术研究 o r g a p a c h e 1 u c e n e q u e r y p a s e r 是作为o r g a p a c h e 1 u c e n e s e a r c h 的语法解析器存在， 不被系统之外实际调用，因此这里没有当作对外接口看待，而是将之独立出来。 主要的模块作用如下： 1 ) o r g a p a c h e 1 u c e n e a n a l y s i s ，语言分析器，主要用于切词，本文所设计及 实现的中文字典分词模块就是扩展该类的基础上生成的。 2 1o r g a p a c h e 1 u c e n e d o c u m e n t ，索引存储时的文档结构管理，类似于关系 型数据库的表结构。 3 1 o r g a p a c h e 1 u c e n e i n d e x ，索引管理，包括索引建立、删除等。 4 ) o r g a p a c h e 1 u c e n e q u e r y p a r s e r ，查询分析器，实现查询关键词间的运算， 如与、或、非等。 5 、o r g a p a c h e 1 u c e n e s e a r c h ，检索管理，根据查询条件，检索得到结果。 6 1o r g a p a c h e 1 u c e n e s t o r e ，数据存储管理，主要包括一些底层的i o 操作。 3 1 4l u c e n e 的工作流程 l u c r e 功能强大，但从根本上说，主要包括两块： 1 建立索引库：根据已有的数据资料建立l u c e n e 索引文件。这一个部分是 搜索引擎的基础。 2 通过索引库搜索：有了索引后，即可使用标准的词法分析器或直接的词 法分析器实现进行全文检索。图3 2 是上述两大功能的逻辑图。 3 1 5l u c e n e 的与索引相关的类 1 i n d e x w r i t e r i n d e x w r i t e r 是在索引过程中的中心组件。这个类创建一个新的索引并且添加 文档到一个已有的索引中。可以把i n d e x w r i t e r 想象成让可以对索引进行写操作 的对象，但是不能读取或搜索。 2 d i r e c t o r y d i r e c t o r y 类代表一个l u c e n e 索引的位置。它是一个抽象类，允许它的子类( 其 中的两个包含在l u c e