（计算机应用技术专业论文）中文全文检索系统中索引的研究.pdf

中文摘要中文全文检索系统是信息产业中发展较快的一个领域，而一个中文检索系统的核心就是索引器，本文介绍了索引器构造的不同算法模型，对相关的技术进行了比较，分析了各自的优缺点和实现难点，提出了一种中文全文检索中索引实现的数据结构和新型的算法模型。本文首先综述了中文全文检索中索引构造的相关技术，主要包括索引文件数据结构、索引单位选取和索引压缩算法。在上述综述的基础上，本文采用了基于单字的倒排表文件格式和可变字节编码压缩技术实现了整个索引系统。该系统包括三方面的功能分别是：文本预处理、索引创建和索引更新。在文本预处理部分实现了中文、外文和特殊字符的分离，同时实现了停止词( s i o pw 讲d ) 的删除。在索引创建部分本文首先给出了一种基于传统倒排表的索引创建算法合并排序式索引创建算法，该算法需要源文本1 0 倍大小的临时空间。为了解决合并排序式索引创建算法临时空问过大的问题，本文提出了一种新的索引创建方案，该方案采用分级的倒排表索引组织结构和链式顺序混合存储的方式。它不仅不需要额外的i 临时空间，而且还提高了索引创建的效率。在索引创建的过程中本系统采用了可变字节编码压缩技术对索引进行压缩，实验表明该压缩算法将索引文件大小减少了2 0 一3 0 。在索引更新部分本文提出了三种顺序存储方式下准动态的索引更新策略，一种链式存储格式下索引动态更新的算法。该系统采用的链式存储结构下的索引更新算法复杂度达到了d 伽) 。关键词：中文全文检索；索引器；倒排表；索引压缩分类号： 3 9 1a b s t ra c tc h i n e s ef u l l t c x tr e t r i e v a ls y s t e mi s eo ft h e 正畦td c v e l 叩i n gf i e l d si ni n f b 肌a t i i n d u s t 啦姐dt h ec o o ft h ea l i i l 鹤er e t f i e v a ls y s t e mi st h eh d c xd c v i c c n ep a p e ra n a i y z e s 靶v e f a ld i f f e r e n ta l g o r i t l l m so fc 0 璐t m d i n gt h ei n d 懿d c v i c c ，柚do m n p a r c st h e l a t c dt c c i i i l i q u e s ，卸dt l i 西v e st h ca d v 柚t a g c sa l l dd i s a d v 柚t a g c so fe a c ha n dt h ed i f ! f i c i l l t yo fa c h i e v i l l 舀f i n a i l yt h i sp a p c r 爵v 鼯t h ed a t as t m c t u r ca n dan e wa l g o r i t l l l nm o d e lo ft h ei n d c xi nf i i l l t c x tr c t r i e v a ls y s t e m 1 1 i i sp a p c rf i 硌ts 蛐瑚a r i z c st h er e l a t c dt c c l l n i q u e so fi n d c x n s t n l c l i n gi nc h i n e f h l l t b x tr e t r i c v a l ，m a i l l l yi n c l u d 鼯d a t as m i d u 坤o fd o c i l m e n ti n d e x i l l g ，i l l d e x 埘面tl e c t i n 岛i n d e xc o m p r c s s i o na 1 9 0 r i t h l s t h ef i i n h e rw a y ，t h i sp a f 幔i m p l e m 锄t st h c 锄t i 豫i n d c xs y s t 锄u s i i l gt t i e t h n i q u e s ，踮c h 舔c h a m d e rb a s e 如ni n v c n e di j s t s 卸dt h ev a r i a b l eb y t e d i n g湖p r e 豁i a 1 9 0 r i t l i i n n i ss y s t e mi n c i u d e sl 慨f i l | 1 d i o 璐嘲梯d i v e l yi s ：t e x tp r e t m a t m e n t ，i n d e xf o u n d a t i o n 柚di n d e xu p d a t i i i 吕h it h ep a no ft e x tp r e t r e a t m e m ，h 勰r c a l i z e ds e p 盯a t i 伽o fc h i n e ，f o r c i 缈卸dt h e删a ld l a m c t e r ，a n dh 弱r c a l i z e dd e l e t i o no f“s t o pw o r d ”ht h ep a no fi n d e xf o 岫d a 曲n p m d u c 鹤彻ek i n di n d c xf o u n d a t i o na l g o r i t l l mb 勰c do nt 鞠d i t i o n a li n v e n e dl j s 忸- s o n m e r 窘em e t h o d 1 h i sa 1 9 0 r i t h mn d st h e1 0 血n eo fs i z c sf 研t 锄p o m r ys p a 0 瞄t h 锄t h e u f t e 】【t ho f d e rt os o i v et h ep m b l e mo fo v e 琏i z c dt e m p o r a r ys p a c ej na b w ea l g o r i t h m s t h i sp a p 盯p r o p 0 dan e wi n d 懿f o l m d a t i 彻p l 柚n ei l l d e xo 曙姐i z a t i o n a ls t n i 咖o ft h i sp l 觚i si 1 1 l p r o v c dl n v e n c dl 豳，柚d i t s m e m o r y w a y i s m i x0 f c h a i n 卸do f d e r nn o t o n l y d o 龉tn e c d t h ee x 仃at c l m p 0 忸r ys p a c e ，b ta l s oe i l l i 柚c c st h ee f f i c i e n c yo fi n d 懿f o u n d i i i g h it h ep m c e 鹞o fi n d c xf o 咖d i n 岛画n gt h ei n v 砌a b l eb ”ec o d cc o m p | e 龉i o nt c c h n o l o g yt oc a 】吖o nt h eo m n p r e 鹞i o fi l l d e x ，t l l ee x p e f i m e n ti n d i c a t 鼯t l l i s m p r c s s i 蛐a l 酬t h mr c d u c c dt h es i z eo fi n d e xd o c i i m e n t2 0 3 0 ht l l ep a no fi l l d c xr c n e w a l ，t h i sp a p c r 班叩o dt h r d y n 锄i ci n d e xu p d a t i n gs 妇t e 垂鼯b a s c d 衄o r d c fm 锄o r y ，柚da 虹n d0 fi n d e xd y n 锄i cu p d a t i l i ga l g o r i t h mb a d 伽c h a i nm e m o r y t h ee x p c r h n e n t 如d i c a t c st l l a ti n d e x 陀n 删a la l g o r i t l l l nm p l h 勰a c h i e v c so ( n ) b 獬d 彻c h a i nm e m o 珥k e y w o r d s ：c h i n e f u l l t c x tr e 埘c v a l ；h d 懿d c v i c c ；i n v e n c d “s t s ；i n d c xc o i n p r e s s i 伽致谢本论文的工作是在我的导师于剑教授和瞿有利副教授的悉心指导下完成的，于剑教授和瞿有利副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来于剑老师和瞿有利老师对我的关心和指导。于剑教授和瞿有利副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和帮助，在此向两位老师表示衷心的谢意。于剑教授和瞿有利副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢。在实验室工作及撰写论文期间，黄锋、张晓峰、李林立、马艳红等同学对我论文中的全文检索部分的研究工作给予了热情帮助，在此向他们表达我的感激之情。另外也感谢爸爸，妈妈和弟弟，他们的理解和支持使我能够在学校专心完成我的学业。韭塞窑壅盔堂亟堂焦监塞i l直1 1 研究背景1 引言在信息时代产生了大量数字信息，其中文本信息是最基本和常用的形式，为了能在海量的文本信息中找到自己的所需，人们迫切需要一个高效的检索工具。怎样高效的存储和查询文本这种非结构数据，就是一个颇值得研究的问题。这其中以全文检索技术成为国内外学者研究的热点。全文检索( 1 u 1 1 t e x tr c t r i c v a l ) 是以文本数据为主要处理对象，基于全文标引，使用自然语言进行检索的技术【在信息检索领域，全文检索一直是一个比较复杂的问题与普通数据库检索所设计的结构化数据查询不同，全文检索不仅要查询结构化数据，而且还要查询非结构化数据【2 】，比起标引检索来，全文检索提供了全新的，强大的检索功能，方便多角度、多侧面的综合利用信息资源。当今以全文检索为核心技术的搜索引擎己成为网络时代的主流技术之一。在文本检索中，为了满足一定的查询性能要求一响应时问限e s p o n s et i m e ) 和系统吞吐量m m u g l l p u o ，词表和文档元数据的存储要有良好的设计，文献【3 】就检索效率问题作了详细的论述。文本检索有几种主要建索引的模型：倒排表【4 】、正排表1 5 l 、后继数组模型1 6 】、互关联后继数组模型等，其中倒排表是最常用的，它的存储设计也是文本检索中的基本问题之一。目前很多主流的全文检索系统用自设计的文件来存储倒排文件，比如易宝北信t r s i _ ”。当倒排文件比较大时，就要考虑压缩。压缩在大规模文本索引时尤其重要，目前比较流行的压缩算法有以下几种：按位紧凑压缩法【8 j 、可变字节编码、e l i 舔g 锄m ac o d i n g 【蚋、g o l 劬bc d d i n 一1 0 j 等。压缩算法的好坏不能只用其压缩率来衡量，在考虑到压缩率的同时也要考虑到解压所用的时间。国外的全文检索软件虽然较早地得到应用，但对中国用户有很多不适用的地方。中文全文检索技术在原理上同西文全文检索是一致的，但汉语本身的特点使中文系统的实现比西文系统更为复杂。全文检索的核心技术是将源文档中的所有的基本元素的出现信息记录到索引库中f 1 1 l 。在中文系统中，基本元素可以是单个汉字字符，也可以是词。因此存在两种基本的索引库结构，即基于字表的索引库和基于词表的索引库1 1 2 。字表法和词表法各有优缺点国内学者对此都各有侧重研究，前者实用性很强，构建直观方便，纵观近几年单汉字标引和检索技术的发展，其发展趋势可归结到两点：一是在单汉字标引和检索技术中引入受控标引和检索的技术和思想；二是引入人工智能技术【1 3 i 。检索方面，比较实用的是“首字直接匹配法”f 1 4 1 。词表法多集中在中文自动分词研究，自然语料统计分析等方面。1 2索引在中文检索中的位置及研究现状全文检索是指计算机索引程序通过扫描文章中的每一个词，给每一个词建立一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表查字的过程。在上段全文检索的叙述中提到了索引，为什么要建立索引? 索引对于全文检索到底意味这什么? 在0 t i sg o s p o d n e t i c 和酬kh a t c h c r 的l u c c n ei na 咖n 1 1 习一文中提到“在搜索引擎的所有概念中最为核心的概念就是索弓l ，索引就是把原始的数据处理成一个有利于高效检索的数据形式。”他们就为什么要进行索引给出了具体和形象的说明：“假如你需要在很大量的文中进行某个特定信息的检索，并且你想在非常短的时间内找到含有需要信息的文件，你会怎样写程序实现这些? 最简单的方法是顺序扫描所有的文件寻找给定词和短语，但这种方式有一些缺点，其中最致命的是当文件很大时根本没有足够的空间来存储该文件，这就是为什么需要索引了，为了在大量文本中检索到所需要的信息，首先必须把源文本集转换成一另一格式的文件，这种格式的文件能够让你进行快速的检索，而不是只进行很慢的顺序扫描。”这个转化的过程就是索引化，该过程输出的结果就是“索引”在上文中可以知道索引是全文检索的“心脏匕下面的全文检索的模型结构图能够清晰的说明索引在全文检索中的地位。下图即为全文检索的模型结构图：r 1命令、一_i j一_一7 | 查询引擎r7 | 文本处理引擎部应陲引引擎( 索引器)用结果、t程弋j序、询结主处理索引文件叫匡本数据库二开发。图1 1 全文检索结构模型图2全文检索系统是按照全文检索理论建立起来的用来提供全文检索服务的软件系统，一般来说，全文检索要具有建立索引和提供查询的功能。从上图中可以看出，全文检索系统中最为关键的部分是全文检索引擎，各种应用程序都需要建立在这个检索引擎之上。在检索引擎中可以看出索引引擎占据了核心的位置，他是整个检索效率的重要决定因素，一个全文检索应用的优异程度，根本上由全文检索引擎来决定。而全文检索的效率主要是由一个索引引擎所决定的。1 3 本文论文安排鉴于上文的分析，知道一个优秀的索引引擎对于全文检索非常重要。本文的主旨就是建立一个全文检索的索引系统。本文主要的工作安排如下：第二章主要阐述了基于中文全文检索索引器的功能。同时给出了通用索引器的组织结构图：一个索引器应该包文本预处理模块，创建索引模块以及索引维护模块。第三章论述了中文全文检索索引所设计的主要技术问题。主要有索引文件结构的选择，索引元的选取以及索引压缩算法的比较分析等。同时给出了基于字和基于词的索引器优缺点的比较。第四章中给出了基于单字的中文全文检索的索引器的设计方案和实现过程，其中包括索引文档的创建，索引文档的动态更新和删除以及索引压缩算法的实现。第五章索引压缩算法测试结果以及索引创建效率分析。第六章是小节篇，总结了本文所做的工作，找到了不足之处，给出了下一步工作的方向。3韭豆至道去堂亟土堂焦i 金塞生塞全塞捡塞主的塞l 墨的绪捡塑功能2 中文全文检索中的索引器的结构和功能2 1全文检索索引器的结构在下图中可以看出一个索引器有三部分组成，第一部分是文本预处理模块，在该模块中针对给出的待索引的文本进行预处理，然后对经过处理的文本进行索引的建立，在索引建立后由于待查文档的改变要对索引尽心维护。索引维护主要涉及的问题是：源文档增加时将新的索引附加到原来的索引上，当源文档改变时，将其相对应的索引文件更新，但某些文档不在需要时，也要将其相对应的索引文件删除。具体的结构图见图2 - 1 ：图2 _ 1 索引器结构图f i g l l 2 1h d 懿d c v j s y s 蛔咀s 扛u c h l m2 2全文检索索引器的基本功能一个中文全文检索的索引器应该实现三部分的功能。第一部分是文本预处理，一般需要检索的文档成分比较复杂，需要用文本预处理将文档中的中文，数字，符号，以及西文分开并归类然后分别对其建立索引。由于中文语言的复杂性【1 q ( 见3 3 3 节分词技术说明) 在预处理这部分需要包括中文索引单位的选取，目前主流的有两类：一类是单字，一类是分词。第二部分功能是创建索引，利用选定的索引数据结构对源文档遍历建立索引。第三部分功能是实现索引的维护，包括索引删除，索引增加，索引更新。4韭复窑垣丕堂亟望僮途塞生塞全塞捡塞塞j i 墨控建担羞撞苤绽述3 中文全文检索索引器构造相关技术综述一个完整的中文全文检索的索引器的构造涉及到索引数据结构的选取，索引单位的选定，以及整个索引器的结构，索引采用的策略，以及有关索引压缩算法的研究。在本章中介绍了索引数据结构以及其相关的工作原理，分析了一种基于单字的索引器的构造及工作原理以及基于分词技术的索引的构造方案，在最后的一小章中介绍了一些主流的压缩技术，并给出了这些技术与索引的结合应用。3 1索引数据结构及其相关原理索引文件有多种组织形式，其中以正排表、到排表以及后继数组比较常用。下面分别介绍正排表、倒排表以及后继数组的结构和工作原理。3 1 1 正排表的数据结构和其工作原理正排表是以文档的l d 为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。正排表结构如图3 - l 所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护；因为索引是基于文档建立的，若是有新的文档假如，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。若是有文档删除，则直接找到该文档号文档对因的索引信息，将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。由于正排表的工作原理非常的简单，但是由于其检索效率太低，几乎没有什么实用价值，所以在此不作详细介绍。i 文档1 目 w o r d l 目 w o r d 2 吲il - - ，_ j1 。，。jt 一_ jl 。，。一jl匦蛩臣画，巨皿习j l匪图3 1 正排表结构图f i g i i r e 3 l 刑a f dl 缸s n 咖坤53 1 2 倒排表的数据结构和工作原理倒排表以字或词为关键字进行索引，表中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的i d 和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排表。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，效率相对低一些，不会影响整个搜索引擎的效率。倒排表的结构图如图3 2 ：巨画乎臣i 匦) 臣野日j l匝毋匝堑乎匝蛩圈jl曰图3 - 2 倒排表结构图f i g l i m3 - 21 n v e f t c dl 姗s 岫咖阳倒排表的索引信息保存的是字或词条在文档内的位置，在同一篇文档内相邻的字或词条的前后关系没有被保存到索引文件内。下面给出一个传统的基于单字的中文全文检索数据结构和算法模型进行分析说明。全文检索方案是在执行检索操作时比较字或词条在同一文档内的位置是否相邻的算法方案。在此为了说明倒排表的工作原理，采用一个全文检索方案加以说明。倒排表实际上就是一个表结构，在对关键词进行检索时需要对关键词中每个字在倒排表中进行一次检索操作，假设我们要对k c y 这个关键词进行全文检索，k c v 如定义3 1 所示：定义3 - 1 ：k y = c 1 ，c 2 ，c 3 c n n = 12 3 k e y 是n 个字符的集合，它们的前后位置关系是固定的，s ( c i ) 为包含字符c i的索引信息二元组d u a l i 的集合，二元组中第一个数字为文档标号，第二个数字为文字在文档内的位置。s 化i ) 可以描述为定义3 2 ：定义3 - 2 ：s ( a ) = ( a n l m ，p o s l ) ，( a n l d 2 ，p o s 2 ) ，( a n l d m ，p 嘴m ) 其中a r t l d m 为包含字符a 的文档的序号，p o 锄为字符a 在文档a n l d m 中出现的位置，则一个k c y 被检索到的条件数学描述如式3 1 所示：v c f 铆j 矗( a i d x i ，p o 镊i ) s ( c i ) a n d6韭夏銮适太堂亟堂焦途塞虫塞全塞捡塞塞l 墨掬适担羞挂苤绫述( a i d x i ) = aa n d( p o s x i p o 麟i 1 = 1 )式3 1从上面的条件公式可以看出，检索成功的条件就是对关键字中所有的字符a都可以找到同一篇文档，使该文档包含字符c i 而且这些字符在该文档中的字符位置的差值和它们在关键词中的位置的差值相同。例如，搜索“中国”：假如索引库中“中”字的索引信息为二元组序列为( 2 ，5 ) ( 4 ，6 ) ( 5 ，9 ) ( 6 ，9 ) ( 7 1 0 )“国”字的索引信息为二元组序列为：( 1 ，5 ) ( 2 ，6 ) ( 5 ，1 0 ) ( 7 ，3 4 )则根据定义3 一l 和3 2 ：k e y = 中，国)s ( 中) 2 ( 2 ，5 ) ( 4 ，6 ) ( 5 ，9 ) ( 6 ，9 ) ( 7 ，1 0 ) s ( 国) 2 ( 1 ，5 ) ( 2 ，6 ) ( 5 ，1 0 ) ( 7 ，3 4 ) 根据式3 - l 定义的匹配成功条件，检索结果五为2 和5从上面检索的结果可以看出“中国”两个字在2 5 7 号文档内都出现了，但是只有2 和5 号文档内“中国”两个字是相邻的，所以检索命中的文档为2 和5 号文档。从上述的分析可以知道，倒排表检索效率的优势远远大于正排表。3 1 3 互关联后继树模型目前全文检索除了上述的正排表、倒排表模型外有人研究利用互关联后继树模型来实现全文检索。与传统的倒排表的索引数据必须具有文档一索引项结构且只能实现简单的查询不刚切，互关联后继树模型【1 s 1 川不但能够处理具有文档索一引项结构的数据，同时也能够与p a t 树一样处理无结构数据【2 l l ；具有创建速度快，查询速度快，空间效率高等特点。在本小章中将简要的介绍互关联后继数组模型的基本构造及其工作原理【z 啦l 。设芑是构成文本的基本符号单元的集合是口。，4 ：，4 。中的一些基本符号，它们的有序组合便可构成一个文本。我们在每个文本t 的最后人为的添加一个不在中的符号，用来表示该文本的结束。这个符号称为文本结束符，一般用a s c i i为o 的字符表示。在本文中，为了阅读方便文本结束符使用“参”。通常把加入某一个索引库的所有文本的集合叫做该索引库对应的全文。定义3 3 ( 前驱和后继) 对任意文本t 中的任意字符串q 如，口，称为以的前驱；n ：称为n ，的后继，文本最后一个字符的后继为文本结束符。j e 基窑堕盔堂亟堂僮迨塞生塞全塞揎塞塞i 矍缒遣担羞莛苤绫签注记：若组成文本t 的字符串q ，如，4 。中，出现了m 个相同的字符，不妨记该字符为口。那么4 有m 个后继，记为口【k 】，k = 1 ，2 ，m 。口【k 】表示n 的第k 个后继。定义3 4 ( 后继表达式与后继树) 设全文1 是由一字符串口1 ，如，口。组成的，若其中口，= q ：= = 口。= 4 为相同的字符，q 。+ l ，哆：。，。分别是其后继，4 m ，口i m ，口如+ 1 的后继又分别4 n + l 【姐g l 】，q 2 “【女昭2 】，n 陋岛】那么我们称( ( 口，1 + 1 ，缸g 。) ，( 哆2 + i ，旭9 2 ) ，( 口h + l ，蛔晶) ) 为a 的后继表达式，可以用一棵后继树来描述此表达式，如图3 3 所示，( q ，。，细g 。) 是a 的一个( 后继，位置) 对。图3 - 3a 的后继树形式f i g i i m3 - 3s u 。e 路i h 般o f 丑倘若文本中有一段文字为4 ，q 。，6 ，则4 有( 后继，位置) 对( q 。，纫g 。) ，其中q 。+ 。是口的一个后继，而自昭，是在以q l + l 为根的树中b 所在分支的序号。这个序号实际上也就是b 在q 。树中的位置。定义3 5 ( 互关联后继树) 由一个索引库对应的全文l 的所有后继树组成的森林，叫做i 的互关联后继树( m s th t c r - r c l c 、r 锄ts u o o e 鲻i v c l r c 鼯) 。例1 对于全文口6 c 4 加口施弗，其中撑为索引库的结束符，口的后继表达式为( ( 6 ，1 ) ( 6 ，2 ) ，( 口，4 ) ，( 6 ，3 ) ) ，其对应的后继树，全文氓s t 如图3 4 所示。abc图3 4 全文互关联后继树模型f i g i l 聘3 4f h - t e x ti n k f 毗l e v 姐ts 州船 s s i v e 妇c e 器m o d e l创建该全文m s t 的时候，我们为中的三个字符：口，6 ，c 分别建立三棵树，然后按照读取的字符依次为树添加树枝。首先读入口6 ，将口的后继6 填入树口的第一个分支处，由于此时还不知道该分支对应的位置信息，留空。而后，读入c ，将c 填入以其前驱6 为根的树的第一个分支，此分支号即为前次留空的位置信息，8韭立至堕丕生亟主堂僮途塞生塞全毫捡塞塞i i 墨捡鲎担差蕴苤绽述将1 回填到4 树的第一个分支。再读取4 ，在c 树的第一个分支填写口，并且回添该分支号1 到6 树的第一个分支。当读入群后，在以其前驱c 为根的后继树中增加第二个分支撑，并将2 回填。此时，索引文件的结构如图3 所示，将此索引文件结构表示成树的形式，即为图3 4 的l r s t 口一6 16 2 口46 36 一c 1 口3c 2c ，4 2 静图3 - 5 索引文件结构示倒f i g u 坞3 5 i n d 能用es t n l c t i l l e利用索引生成原文，我们需要记录加入索引库的文本的第一个字符a ，和a的后继在树a 中的存储位置p ，本例中a = 口，p = 1 。取出口树的第1 个分支，得到( 6 ，1 ) ，即口的后继为6 。再取6 树的第一个分支得到( c ，1 ) ，依次，我们得到的分支序列为：( 口，0 ) 一( 6 ，o ) 一( c ，o ) 一( 口，1 ) 一( 6 ，1 ) 一( 4 ，2 )一( 口，3 ) 一( 6 ，2 ) 一( c ，1 ) 一( 群，f j l e )每一个分支中的字符的序列即为我们的原文件：口6 6 n 口6 c 撑。如果查询字符串“4 6 c ”，我们在4 树的分支中查找后继为6 的，发现第1 ，2和4 分支满足条件，再根据这三个分支的内容取其后继，仅1 ，4 分支( 6 ，1 ) ，( 6 ，3 ) 的后继为c ，则“口6 c ”在索引库中有两个匹配。在处理索引文件结构时，有两种办法。方法一：为每个字符预留一定的空间( 称为基础块) ，如果某一个字符的基本块用完，则在文件末尾为其分配一附加块，在每一块中添加指针，指向该字符的下一个块。如图3 6 ，上面三行是基本块，当口的基本块满了，就为其在文件末尾分配一个附加块，指针由基本块指向附加块，再次满后，再次为其分配附加块。如果此时c 的基本块满了，则也为其分配一个附加块。1bc 1量e 一图3 _ 6 索引文件分块结构f 硒雠3 石i n d e xf n eb 1 0 c k 咖d u 豫但是该方法存在的缺点是在基本块没有写满的时候，仍需占用存储空间，而9j e 塞銮逗太堂亟主堂僮途塞主室全塞捡塞塞l 墨控童塑羞拄丕绽述有些字符，如二级汉字，实际上很少会出现，所以如果基本块空间分配过大会浪费，而如果分配较小，一个字符后可能会出现很多个链接块，在文件中分散存储，将影响查询和原文生成的速度。方法二：在索引库中每加入一次文件，则为相应文本字符添加一块与该字符上一块连接。方法二的不足是块的数目和大小完全由每次加入文本库的文本内容决定。不同字符的块大小将极为不平衡。如回车、换行或汉字“的”的索引块较大，而二级汉字的块将很小。且这也将限制每次索引库中加入文件不能过小，否则将会出现繁多的小块，因而也会影响查询和原文生成的速度。具体在处理索引文件结构时需要结合实际情况选择不同的索引创建方法，比如若是每个字符在所有文档中出现的概率相差不多，并且能够估计到文档的大小，则采用第一中预留的方案，能够快速的检索并且不会出现很多的“碎片”若是文件的大小完全无法预料，则只能采用第二种。3 1 4 几种索引存储结构的比较在上面的三个小节中提到了三种索引存储结构分别是正排表、倒排表和互关联后继数组模型。下面给出三种索引结构的简要分析。由3 1 1 的分析可以知道，对正排表进行信息检索的时候，等于直接对源文件进行全文扫描，索引的建立并没有加快检索的速度，但是却在建立索引时耗费了空间和时间，这种方法没有实用的价值，一般不采用。相比来说倒排表就很是一种实用性很强的索引存储，倒排索引由于其组织结构的形式( 具体分析见3 1 2 ) ，对信息的检索能够变的非常快，所以倒排表成为了一种主流的索引文件格式，在大部分的全文检索系统中的都采用这种索引结构。互关联后继数组模型是一种新颖的全文检索的模型，他的特点：1 ) 能够处理无结构的数据( 这点与p a t 树有一样的功能) 。2 ) 创建的空间效率比较高。3 ) 可以通过索引生成原文。不足之处：4 ) 文件管理方面，由于所有的倒捧文件都是通过树或是森林来管理，所以系统要维持整个森林要花费很大的代价。5 ) 互关联后继数组在实现上的复杂度要远远大于倒排表。6 ) 在处理不相邻的检索关键字方面比较吃力。7 ) 在文本预处理时，互关联后继树模型对“s t o p w o r d ”就无能为力。1 0韭塞窑适盔堂亟堂焦i 金塞虫塞全塞捡塞塞i l 墨控适担苤撞苤绽述与之相比倒排表具有以下的优点：1 ) 倒排表技术是一种比较普遍通用的技术，针对倒排表的研究也比较多，所以相关的技术也比较容易实现。2 ) 经过改进倒排表结构形式也能够达到比较好的检索效率，以弥补检索效率的问题，在空间效率上可以利用索引压缩技术进行改进。3 ) 在网络上面，检索的返回结果只是一个链接，并不需要全文的还原，所以互关联后继树模型这方面的优势并没有很明显。综合比较起来，本文采用倒排表格式的索引存储格式。3 2基于单字的索引器构造全文检索的核心技术是将源文档中有的基本元素的出现信息记录到索引库中。在中文系统中，基本元素可以是单个汉字字符，也可以是词。因此，存在两种基本的索引库结构，即基于字表的索引库和基干词表的索引库。基于字表索引库的建造方法有很多种，不同的字表的构建方法会对应不同的检索策略。下面介绍其中一种字表法索引库的构造方法及检索策略【2 4 ，2 5 】。3 2 1 单字索引数据结构单字的索引库数据结构一般采用字表法，字表法索引库的主要部分是每个字的字表信息。字表结构如表3 1 所示，其中字符j 对应的字表记录了该字符在源文档中所出现的位置p i x 。该位置采用了字符相对于文档头的偏移字符数表示，而不按通常情况采用相对于文档头的偏移字节数，这样可以大大减小位置的数值大小，有利于进一步采用压缩技术。建立字表索引时，需要扫描整个源文档，对出现的每一个有效字符，计算其在文档中出现的位置，并将该位置的值加入到对应的字表中。表3 - l 字表结构t h b l e3 1c h 互哦虻把f 协b ks 咖咖啊p 1 1 ，p 1 2 ，p 1 3 阿p 2 1 ，p 2 2 ，p 2 3 的p i l ，p i 2 ，p i 3l l韭夏至塑盍堂亟堂焦途塞主塞全塞拴塞塞i i 墨捡选担羞撞苤绽述i中p j l ，p j 2 ，p j 3索引库中的一个字表记录了对应字符在源文档中的所有位置信息。考察一个字符串，如两个字的字符串x y ( 其中) ( ，y 表示任意的汉字字符) ，假设x 的位置为) p 】【，如果字符串x y 在源文档中出现，则y 的位置p y 必定等p x + 1 ，( 1 为两个汉字间的字符距离) 。在索引库中x 的字表中将包含p x ，而y 的字表中也必然包含p x + 1 。进行检索时，扫描x 和y 各自对应的字表，若文档中有该词出现，则必定有x 对应的字表中存在位置值p x ，y 对应的字表中存在位置值p y 使得p y =p 】【+ 1 成立，每查到一对这样的位置值，就是检索到字串x y 一次。扫描完两字的字表，就可检索出该字符串的所有出现。上面简要介绍了字表的用法，在具体实现的时候的数据结构要稍微复杂一些，因为某个字符的字表中不但要包含文档的信息还要有某字符在该文档中出现的位置信息，由于字符在每一个文档中出现的次数与位置都不一样，所以在实现的时候采用了一种比较复杂的数据结构，就是字表倒捧文档。字表倒排文档的数据结构是每个汉字字符对应的字表中，包含该字符出现在所有文档中的全部位置。为了区分每个位置公到属于哪个文档，每个字符的字表被分为多个字表段，每段对应一个文档，记录该字符在此文档中的出现位置。字表采用倒排文件结构，如表3 - 2 所示。表3 - 2 字表倒捧文档1 h b i e 王- 2c l l 砌锄：t 盯纽b i ei m 州e dl i 虹每个字表段起始部分记录当前文档的编号，随后是该字符在文档中的出现频率，最后是该字符在文档中的所有出现位置序列。每个字符的所有字表段按文档编号递增的顺序排列，如果该字符在文档k 中没有出现，则不存在文档k 对应的字表段。3 2 2 单字索引的创建方法上面简要介绍了基于字表的索引库的结构，下面给出基于单字索引的创建方韭塞变通态堂亟堂焦丝童主童全塞捡塞塞曼l 整控造担差撞盔绽违法。该索引创建方法不需要排序，分为如下两步：第一步分析源文档，产生l 晦时的中间文件，这个过程称为分析过程。当前只针对g b 码字符【捌进行处理，其中包含全部字符，既有汉字，又有一般的数字，标点符号等。g b 码第一个字节的范围是o x a l o x f 7 ，第二个字节的范围是0 x a l一o ) ( 1 琨。汉字从“啊”开始，首字节为1 7 6 - 2 4 7 ，第二个字节为1 6 1 2 5 4 。根据这种分布规律，可以方便地定位每个字符对应的字表信息。源文档经过处理，将其包含的每个字符的对应信息写到一个临时的中间文件中。对于每个字符，其在l 临时文件中的对应信息包括：该字所出现的当前文档编号、在该文档中的出现频率、出现的位置序列和该字符出现在下一个文档的数据的指针( 数据在文件中的偏移值1 。第二步处理临时文件，依次从临时文件中读取每个字符出现在每一篇文章中的数据信息，生成最终的倒排文件，在这里称为创建过程。生成的最终倒排文件中包含每个字符出现在所有文档中的信息。包含该字符出现的当前文档的编号、出现频率和相应的位置序列。处理过程如下图所示。分析图3 7 生成索引文件流程图f i g i l ”f l a w c h a no fc 陀a t i n gl n d 既3 2 3 优化的基于单字索引创建方法在上面所论述的基于单字的索引创建方法中，对于源文件的分析过程本身需要一定的时间，随着处理数据集规模的增大，相应的分析时间增大，第二步( 创建过程) 所需的时间相应的迅速增大。该过程需要大量的随机读取操作来遍历每个韭塞銮道太堂亟堂焦迨塞生塞全塞捡塞塞i i 墨翅造担羞撞苤绽述字符对应的所有信息。当数据的规模增大时，遍历每个字符的临时数据的操作变得很慢。这是由于字符对应的每个字表的数据在临时文件中有一定距离，遍历需要不断地移动文件指针来读取这些数据。利用操作系统提供的虚拟内存技术【2 7 j 可以优化索引的创建过程。w i n d o w s 操作系统用虚拟内存技术来动态管理运行时的交换文件。为了提供比实际物理内存还多的内存容量以供使用，w i n d o w s 操作系统占用了硬盘上的一部分空间作为虚拟内存。当c p u 有要求时，首先会读取内存中的资料。当内存容量不够用时，w 协d o w s 就会将需要暂时储存的数据写入硬盘。内存映射文件技术是w i n d o w sm提供的一种新的文件数据存取机制。利用内存映射文件技术，系统可以在2 g b 的地址空间中为文件保留一部分空问，并将文件映射到这块保留空间一旦文件被映射之后，w i n d o w sn t 将仔细管理页映射、缓冲以及高速缓冲等任务。通过把临时文件映射到虚拟内存中，可以大大加快对临时文件的访问速度。对于较小的源数据集，分析处理后生成的临时文件也较小，使用内存映射文件可以大大加快创建过程。但当数据规模增大时，该方法的性能迅速降低，甚至比没有使用内存映射文件都差。性能的降低一方面由于机器有限的内存，其小于临时文件的大小。另外一方面，同一个字符相邻的数据在临时文件中距离过大，导致大量的缺页中断，系统性能大大降低。解决该问题的有效方法是把原有的单个的大的中间文件分成多个小的临时文件，在分析过程中生成多个小的临时文件，创建过程依次处理每个临时文件，将其映射到虚拟内存中，可以充分利用直接内存访问的速度，并且减少缺页中断。在实际应用中，可以采用了统计的方法，通过对一个较大的数据集的分析，将原有的一个大的临时文件拆分成多个小的临时文件，每个字符的索引数据存放于其中的一个临时文件中。并且每个临时文件中存放的数据的大小相差很小。这样，每个小的临时文件的大小小于当前内存的大小，从而可以有效地使用虚拟内存技术加快存取。3 3基于词表的索引器构造由上文可以知道以中文的词组作为索引单元也是一种常用的索引文件构造方式f 2 8 j ，基于分词的中文全文检索索引器的构造l 魂蚓是以词为索引项的索引结构。3 3 1 词表索引数据结构1 4些塞銮道鑫堂爨堂焦逾塞生塞全塞捡塞塞! i 墨控造揠苤蕴苤绽述典型的基于词的倒排索引结构( 见图3 8 ) 包含两部分：1 ) 中文词组成向量( 称之为词汇表) ，它包含了词的基本信息和词索引在索引文件中的偏移量。2 )对于词汇表中的每一个词，都有一个它出现过的文档列表，它包含了出现文档编号，在此文档中该词的词频和出现位置序列。诃m索s i 指针一文献频率出现列表一一，、文档m字频位置序列w l 基本空间n 口w l 基本空间n e i 二 图3 8 词索引倒捧文档图3 - 9 临时文件结构f i 副3 - 8h v c r t e di n d e xb a d - 蚰w o f df i g u 3 9t 唧珂e 硼m c m ”词索引指针指向词的索引在索引文件中的偏移量，区域最开始保存的这个词出现过的文档数目( 文献频率) ，这是为了在检索过程中读取索引前能够合适地分配内存空间，文献频率后面是出现文档列表。在这个结构中，除了字频用单字节之外，其他都用4 个字节表示，而且出现在列表中的文档编号是升序排列的。3 3 2 一种词表索引创建流程要建立词索引，首先需要对文档进行自动分词。首先将文本中的中文词、西文词和连续数字组合分析出来，然后对分词结果进行排序，合并相同词的信息，这样就得到一张文档中出现词的列表以及它们的出现位置序列。对于每个词，可以根据它们的计算机编码( 中文g b 2 3 1 2 ，西文和数字a s c ) 映射到词表中的位置，更新词汇表及索引。下面是详细的流程描述：( 1 ) 对文档进行自动分词，对结果排序，合并相同词的信息。( 2 ) 定位词在词表中的位置，得到词索引区在临时文件中的偏移量，如果是以前未出现过的词，就在临时文件的末尾分配一个固定大小的基本空间，对于低频词来说太大的基本空间将造成浪费，所以需要分配合适大小的基本空间。在本系统中，基本空间大小正好能保存一个词出现一次的信息。( 3 ) 如果这个词以前出现过，将文档的读写指针定位到这个词的索引区的末尾。( 4 ) 写入每个词的索引信息到临时文件。如果此时分配给该词的空间用完，则在临时文件末尾给其分配新的溢出空问，出现次数越多的词分配的溢出空问也越大。索引写完后，将上一索引区的向前指针更新为新分配空间在临时文档中的偏移量。韭裹窑亟盔坐亟堂僮监塞生塞全塞捡塞蠢i i 墨翅造担羞莛鲞绽述( 5 ) 对于文档中的每个词，重复步骤( 2 ) 到( 4 ) ，对于每篇文档重复步骤( 1 ) 到( 5 ) 。( 6 ) 所有文档处理完后，对于每个词，我们将分散在临时文档中的索引信息合并在一起，然后按照图3 8 的格式写入最终的倒排文档。3 3 3 常用分词技术的研究以词为索引项的技术重点是词的切分问题。在本小节中对主流的一些分词技术1 3 1 j 枷l 进行了分析总结。目前采用的分词方法主要有：基于神经元网络和专家系统的算法、正向、逆向最大匹配法阴l 、逐词遍历法、最佳匹配法、词频统计法，此外还有穷多层次列举法、二次扫描法、基于期望的分词方法、双向扫描法、邻接约束方法、邻接知识约束方法、最少分词词频选择方法等。但归纳起来不外乎两类，第一类是在生成关键词时将语法、句法、语义结合起来，试图模仿人类的阅读过程。但有时语法、句法、语义连开发人员都不是很清楚，故一般情况下不采用。第二类由字典匹配法和基于频度方法组成，这些方法比起上一种来较具体实用。下面给出几种常用的分词方法：l 、逐词遍历法该方法是将词典中的所有词按由长到短的顺序在文章中逐个搜索匹配整个待处理材料，直到把所有的词都切分出来为止。也就是说，不管文章有多短，词典有多大，都要将词典遍历一遍。如“他睡觉打鼾”，利用该方法切分这一句话，不论分词词典多大，都得把整个分词词典匹配一遍。故这种方法的时间复杂度比较高，是一种不可使用的分词方法。2 、正向( m m ) 与逆向( r m m ) 最大匹配法正向最大匹配法是最早提出的自动分词方法，它的基本思想是先取一句话的前六个字查字典，若不是一个词，则删除六个字的最后一个字再查，这样一直下支，直到找到一个词为止，对句子剩余部分重复此操作，一直到把所有的词都分出来为止，逆向最大匹配法和m m 法一样，不同之处在于它是从句子的最后六个字开始的，每次匹配不成功时去掉汉字串中最前面的一个字。两种方法思路清晰，易于用计算机实现，但是由于试图用相对稳定的词表来代替灵活多变、充满活力的词汇，把词表作为判别词的唯一标准，因而，为了查询的方便，r m m 方法要求配备逆序的分词