全文检索系统论文.docx

全文检索系统论文.docx

《全文检索系统论文.docx》由会员分享，可在线阅读，更多相关《全文检索系统论文.docx（49页珍藏版）》请在冰点文库上搜索。

全文检索系统论文

摘要

中文全文检索系统是信息产业中发展较快的一个领域，而一个中文检索系统的核心就是索引器，本文介绍了索引器构造的不同算法模型，对相关的技术进行了比较，分析了各自的优缺点和实现难点，提出了一种中文全文检索中索引实现的数据结构和新型的算法模型。

本文首先综述了中文全文检索中索引构造的相关技术，主要包括索引文件数据结构、索引单位选取和索引压缩算法。

在上述综述的基础上，本文采用了基于单字的倒排表文件格式和可变字节编码压缩技术实现了整个索引系统。

该系统包括三方面的功能分别是:

文本预处理、索引创建和索引更新。

在文本预处理部分实现了中文、外文和特殊字符的分离，同时实现了停止词（stopword）的删除。

在索引创建部分本文首先给出了一种基于传统倒排表的索引创建算法——合并排序式索引创建算法，该算法需要源文本10倍大小的临时空间。

为了解决合并排序式索引创建算法临时空间过大的问题，本文提出了一种新的索引创建方案，该方案采用分级的倒排表索引组织结构和链式顺序混合存储的方式。

它不仅不需要额外的临时空间，而且还提高了索引创建的效率。

在索引创建的过程中本系统采用了可变字节编码压缩技术对索引进行压缩，实验表明该压缩算法将索引文件大小减少了20-30%。

在索引更新部分本文提出了三种顺序存储方式下准动态的索引更新策略，一种链式存储格式下索引动态更新的算法。

该系统采用的链式存储结构下的索引更新算法复杂度达到了O（n）。

关键词：

中文全文检索；索引器；倒排表；索引压缩

ABSTRACTChineseFull-TextRetrievalSystemisoneofthefastdevelopingfieldsininformationindustry,andthecoreoftheChineseretrievalsystemistheIndexdevice.Thepaperanalyzesseveraldifferentalgorithmsofconstructingtheindexdevice,andcomparestherelatedtechniques,andthengivestheadvantagesanddisadvantagesofeachandthedifficultyofachieving.FniallythispapergivesthedatastructureandanewalgorithmmodelofTheindexinfull-textretrievalsystem..

ThispaperfirstsummarizestherelatedtechniquesofindexconstructinginChineseFull-TextRetrieval,mainlyincludesdatastructureofdocumentindexing,indexcompressionalgorithms.

Thefurtherway,thispaperimplementstheentireindexsystemusingthesetechniques,suchascharacterbased-onInvertedlistsandthevariablebytecodingcompressionalgorithm.Thissystemincludesthreefunctionsrespectivelyis:

Textpretreatment,indexfoundationandindexupdating.

Inthepartoftextpretreatment,hasrealizedseparationofChinese,foreignandtheSpecialcharacter,andhasrealizeddeletionof"stopword".

Inthepartofindexfoundation,producesonekindindexfoundationalgorithmbasedontraditionalInvertedLists——Sort-Mergemethod.Thisalgorithmneedsthe10timeofsizesfortemporaryspacesthanthesourcetext.Inordertosolvetheproblemofoversizedtemporaryspaceinabovealgorithms,thispaperproposedanewindexfoundationplan.TheindexorganizationalstructureofthisplanisimprovedInvertedlists,anditsmemorywayismixofchainandorder.Itnotonlydoesnotneedtheextratemporaryspace,butalsoenhancestheefficiencyofindexfounding.Intheprocessofindexfounding,usingtheinvariablebytecodecompressiontechnologytocarryontheCompressionofindex,theexperimenttindicatesthiscompressionalgorithmreducedthesizeofindexdocument20-30%.

Inthepartofindexrenewal,thispaperproposedthreedynamicindexupdatingstrategiesbasedonordermemory,andakindofindexdynamicupdatingalgorithmbasedonchainmemory.TheexperimentindicatesthatindexrenewalalgorithmcomplexhasachievesO（n）basedonchainmemory.

KEYWORDS：

ChineseFull-TextRetrieval；Indexdevice；InvertedLists；index

引言

1．1研究背景

在信息时代产生了大量数字信息，其中文本信息是最基本和常用的形式，为了能在海量的文本信息中找到自己的所需，人们迫切需要一个高效的检索工具。

怎样高效的存储和查询文本这种非结构数据，就是一个颇值得研究的问题。

这其中以全文检索技术成为国内外学者研究的热点。

全文检索（Full-textRetrieval）是以文本数据为主要处理对象，基于全文标引，使用自然语言进行检索的技术。

在信息检索领域，全文检索一直是一个比较复杂的问题.与普通数据库检索所设计的结构化数据查询不同，全文检索不仅要查询结构化数据，而且还要查询非结构化数据，比起标引检索来，全文检索提供了全新的，强大的检索功能，方便多角度、多侧面的综合利用信息资源。

当今以全文检索为核心技术的搜索引擎已成为网络时代的主流技术之一。

在文本检索中，为了满足一定的查询性能要求一响应时间（ResponseTime）和系统吞吐量（Throughput），词表和文档元数据的存储要有良好的设计，文献就检索效率问题作了详细的论述.文本检索有几种主要建索引的模型:

倒排表、正排表、后继数组模型、互关联后继数组模型等，其中倒排表是最常用的，它的存储设计也是文本检索中的基本问题之一。

目前很多主流的全文检索系统用自设计的文件来存储倒排文件，比如易宝北信TRS。

当倒排文件比较大时，就要考虑压缩。

压缩在大规模文本索引时尤其重要，目前比较流行的压缩算法有以下几种：

按位紧凑压缩法、可变字节编码、Eliasgammacoding、Golombcoding等。

压缩算法的好坏不能只用其压缩率来衡量，在考虑到压缩率的同时也要考虑到解压所用的时间。

国外的全文检索软件虽然较早地得到应用，但对中国用户有很多不适用的地方。

中文全文检索技术在原理上同西文全文检索是一致的，但汉语本身的特点使中文系统的实现比西文系统更为复杂。

全文检索的核心技术是将源文档中的所有的基本元素的出现信息记录到索引库中fill.在中文系统中，基本元素可以是单个汉字字符，也可以是词。

因此存在两种基本的索引库结构，即基于字表的索引库和基于词表的索引库。

字表法和词表法各有优缺点.国内学者对此都各有侧重研究，前者实用性很强，构建直观方便，纵观近几年单汉字标引和检索技术的发展，其发展趋势可归结到两点：

一是在单汉字标引和检索技术中引入受控标引和检索的技术和思想；二是引入人工智能技术。

检索方面，比较实用的是“首字直接匹配法”，词表法多集中在中文自动分词研究，自然语料统计分析等方面。

1．2索引在中文检索中的位置及研究现状全文检索是指计算机索引程序通过扫描文章中的每一个词，给每一个词建立一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。

这个过程类似于通过字典中的检索字表查字的过程。

在上段全文检索的叙述中提到了索引，为什么要建立索引?

索引对于全文检索到底意味这什么？

在OtisGospodnetic和ErikHatcher的luceneinaction一文中提到“在搜索引擎的所有概念中最为核心的概念就是索引，索引就是把原始的数据处理成一个有利于高效检索的数据形式。

”他们就为什么要进行索引给出了具体和形象的说明：

“假如你需要在很大量的文中进行某个特定信息的检索，并且你想在非常短的时间内找到含有需要信息的文件，你会怎样写程序实现这些？

最简单的方法是顺序扫描所有的文件寻找给定词和短语，但这种方式有一些缺点，其中最致命的是当文件很大时根本没有足够的空间来存储该文件，这就是为什么需要索引了，为了在大量文本中检索到所需要的信息，首先必须把源文本集转换成一另一格式的文件，这种格式的文件能够让你进行快速的检索，而不是只进行很慢的顺序扫描。

”这个转化的过程就是索引化，该过程输出的结果就是“索引气在上文中可以知道索引是全文检索的“心脏气下面的全文检索的模型结构图能够清晰的说明索引在全文检索中的地位。

下图即为全文检索的模型结构图:

图1-1全文检索结构模型图全文检索系统是按照全文检索理论建立起来的用来提供全文检索服务的软件系统，一般来说，全文检索要具有建立索引和提供查询的功能。

从上图中可以看出，全文检索系统中最为关键的部分是全文检索引擎，各种应用程序都需要建立在这个检索引擎之上。

在检索引擎中可以看出索引引擎占据了核心的位置，他是整个检索效率的重要决定因素，一个全文检索应用的优异程度，根本上由全文检索引擎来决定。

而全文检索的效率主要是由一个索引引擎所决定的。

1．3本文论文安排

鉴于上文的分析，知道一个优秀的索引引擎对于全文检索非常重要。

本文的主旨就是建立一个全文检索的索引系统。

本文主要的工作安排如下：

第二章主要阐述了基于中文全文检索索引器的功能。

同时给出了通用索引器的组织结构图：

一个索引器应该包文本预处理模块，创建索引模块以及索引维护模块。

第三章论述了中文全文检索索引所设计的主要技术问题。

主要有索引文件结构的选择，索引元的选取以及索引压缩算法的比较分析等。

同时给出了基于字和基于词的索引器优缺点的比较。

第四章中给出了基于单字的中文全文检索的索引器的设计方案和实现过程，其中包括索引文档的创建，索引文档的动态更新和删除以及索引压缩算法的实现。

第五章索引压缩算法测试结果以及索引创建效率分析。

第六章是小节篇，总结了本文所做的工作，找到了不足之处，给出了下一步工作的方向。

2中文全文检索中的索引器的结构和功能

2．1全文检索索引器的结构在下图中可以看出一个索引器有三部分组成，第一部分是文本预处理模块，在该模块中针对给出的待索引的文本进行预处理，然后对经过处理的文本进行索引的建立，在索引建立后由于待查文档的改变要对索引尽心维护。

索引维护主要涉及的问题是:

源文档增加时将新的索引附加到原来的索引上，当源文档改变时，将其相对应的索引文件更新，但某些文档不在需要时，也要将其相对应的索引文件删除。

具体的结构图见图2-1：

图2-1索引器结构图

2．2全文检索索引器的基本功能一个中文全文检索的索引器应该实现三部分的功能。

第一部分是文本预处理，一般需要检索的文档成分比较复杂，需要用文本预处理将文档中的中文，数字，符号，以及西文分开并归类然后分别对其建立索引。

由于中文语言的复杂性[（见3.3.3节分词技术说明）在预处理这部分需要包括中文索引单位的选取，目前主流的有两类：

一类是单字，一类是分词。

第二部分功能是创建索引，利用选定的索引数据结构对源文档遍历建立索引。

第三部分功能是实现索引的维护，包括索引删除，索引增加，索引更新。

3中文全文检索索引器构造相关技术综述

一个完整的中文全文检索的索引器的构造涉及到索引数据结构的选取，索引单位的选定，以及整个索引器的结构，索引采用的策略，以及有关索引压缩算法的研究。

在本章中介绍了索引数据结构以及其相关的工作原理，分析了一种基于单字的索引器的构造及工作原理以及基于分词技术的索引的构造方案，在最后的一小章中介绍了一些主流的压缩技术，并给出了这些技术与索引的结合应用。

3．1索引数据结构及其相关原理索引文件有多种组织形式，其中以正排表、到排表以及后继数组比较常用。

下面分别介绍正排表、倒排表以及后继数组的结构和工作原理。

3.1.1正排表的数据结构和其工作原理正排表是以文档的ID为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。

正排表结构如图3-1所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护;因为索引是基于文档建立的，若是有新的文档假如，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。

若是有文档删除，则直接找到该文档号文档对因的索引信息，将其直接删除。

但是在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。

由于正排表的工作原理非常的简单，但是由于其检索效率太低，几乎没有什么实用价值，所以在此不作详细介绍。

图3-1正排表结构图

3．1．2倒排表的数据结构和工作原理

倒排表以字或词为关键字进行索引，表中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的ID和字符在该文档中出现的位置情况。

由于每个字或词对应的文档数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排表。

在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，效率相对低一些，不会影响整个搜索引擎的效率。

倒排表的结构图如图3-2：

图3一倒排表结构图

倒排表的索引信息保存的是字或词条在文档内的位置，在同一篇文档内相邻的字或词条的前后关系没有被保存到索引文件内。

下面给出一个传统的基于单字的中文全文检索数据结构和算法模型进行分析说明。

全文检索方案是在执行检索操作时比较字或词条在同一文档内的位置是否相邻的算法方案。

在此为了说明倒排表的工作原理，采用一个全文检索方案加以说明。

倒排表实际上就是一个表结构，在对关键词进行检索时需要对关键词中每个字在倒排表中进行一次检索操作，假设我们要对key这个关键词进行全文检索，key如定义3-1所示:

定义3-1：

Key={Cl,C2,C3...Cn}n=123......Key是n个字符的集合，它们的前后位置关系是固定的，S（Ci）为包含字符Ci的索引信息二元组Duali的集合，二元组中第一个数字为文档标号，第二个数字为文字在文档内的位置。

S（Ci）可以描述为定义3-2：

定义3-2：

S（Ci）={（Axtldl,Posl）,（Artld2,Pos2）,...,（Artldm,Posm）}其中Artldm为包含字符Ci的文档的序号，Posm为字符Ci在文档Artldm中出现的位置，则一个key被检索到的条件数学描述。

从上面的条件公式可以看出，检索成功的条件就是对关键字中所有的字符Ci都可以找到同一篇文档，使该文档包含字符Ci而且这些字符在该文档中的字符位置的差值和它们在关键词中的位置的差值相同。

例如，搜索“中国气”假如索引库中“中”字的索引信息为二元组序列为

（2,5）（4,6）（5,9）（6,9）（7,10）“国”字的索引信息为二元组序列为：

（1,5）（2,6）（5,10）（7,34）则根据定义3-1和3-2:

Key={中，国}s（中）={（2,5）（4,6）（5,9）（6,9）（7,10）}S（国）={（1,5）（2,6）（5,10）（7,34）}根据式3-1定义的匹配成功条件，检索结果xi为2和5从上面检索的结果可以看出“中国”两个字在257号文档内都出现了，但是只有2和5号文档内“中国”两个字是相邻的，所以检索命中的文档为2和5号文档。

从上述的分析可以知道，倒排表检索效率的优势远远大于正排表。

3．1．3互关联后继树模型目前全文检索除了上述的正排表、倒排表模型外有人研究利用互关联后继树模型来实现全文检索。

与传统的倒排表的索引数据必须具有文档一索引项结构且只能实现简单的查询不同，互关联后继树模型不但能够处理具有文档索一引项结构的数据，同时也能够与Pat树一样处理无结构数据;具有创建速度快，查询速度快，空间效率高等特点。

在本小章中将简要的介绍互关联后继数组模型的基本构造及其工作原理。

设∑是构成文本的基本符号单元的集合是a1,a2,…，an。

中的一些基本符号，它们的有序组合便可构成一个文本。

我们在每个文本T的最后人为的添加一个不在∑中的符号，用来表示该文本的结束。

这个符号称为文本结束符，一般用ASCII为0的字符表示。

在本文中，为了阅读方便文本结束符使用“#”。

通常把加入某一个索引库的所有文本的集合叫做该索引库对应的全文。

定义3-3（前驱和后继）对任意文本T中的任意字符串a1,a2,a1，称为a2的前驱；a2称为a1的后继，文本最后一个字符的后继为文本结束符。

注记：

若组成文本T的字符串a1,a2,…，an中，出现了m个相同的字符，不妨记该字符为a。

那么a有m个后继，记为a[k],k=1,2,...,m。

a[k]表示a的第k个后继。

定义3-4（后继表达式与后继树）设全文I是由一字符串a1,a2,…，an,#组成的，若其中a;,=ai2=...=ain=a为相同的字符，an+1,ai2+1，…，an+1..,分别是其后继，an+1,ai2+1,…ain+1,的后继又分别{（an+1,tag1）,（ai2+1,tag2），…，（ain+1,tagn）那么我们称ai+1[tag1]，ai2+1[tag2],…，ain+n[tagn]为a的后继表达式，可以用一棵后继树来描述此表达式，如图3一所示，an+1,tag1是a的一个（后继，位置）对。

图3-3a的后继树形式倘若文本中有一段文字为…a,an+1,b，…，则a有（后继，位置）对（an+1,tag1），其中an+1是a的一个后继，而tag1是在以an+1,为根的树中b所在分支的序号。

这个序号实际上也就是b在an+1,树中的位置。

定义3-5（互关联后继树）由一个索引库对应的全文I的所有后继树组成的森林，叫做I的互关联后继树（IRSTInter-RelevantSuccessiveTrees）。

例1对于全文abcabaabc#，其中#为索引库的结束符，a的后继表达式为{（b,1）（b,2）,（a,4）,（b,3）}，其对应的后继树，全文IRST如图3-4所示。

abc

（b,1）（b,2）（a,4）（b,3）（c,1）（a,3）（c,2）（a,2）#

图3-4全文互关联后继树模型

创建该全文IRST的时候，我们为∑中的三个字符：

a,b,c分别建立三棵树，然后按照读取的字符依次为树添加树枝。

首先读入ab，将a的后继b填入树a的第一个分支处，由于此时还不知道该分支对应的位置信息，留空.而后，读入c,将c填入以其前驱b为根的树的第一个分支，此分支号即为前次留空的位置信息，将1回填到a树的第一个分支。

再读取a，在c树的第一个分支填写a，并且回添该分支号1到b树的第一个分支。

……。

当读入#后，在以其前驱c为根的后继树中增加第二个分支#，并将2回填。

此时，索引文件的结构如图3所示，将此索引文件结构表示成树的形式，即为图3一的IRST.a→b1b2a4b3

b→c1a3c2

c→a2#

图3一索引文件结构示例利用索引生成原文，我们需要记录加入索引库的文本的第一个字符A，和A的后继在树A中的存储位置P，本例中A=a,P=1。

取出a树的第1个分支，得到（b，1），即a的后继为b。

再取b树的第一个分支得到（c,1）,……依次，我们得到的分支序列为：

（a，0）→（b，0）→（c,0）→（a，1）→（b，1）→（a，2）→（a，3）→（b，2）→（c，1）→（#，FileNo）每一个分支中的字符的序列即为我们的原文件:

abcabaabc#。

如果查询字符串“abc”，我们在a树的分支中查找后继为b的，发现第1，2和4分支满足条件，再根据这三个分支的内容取其后继，仅1，4分支（b，1），（b，3）的后继为c，则“abc”在索引库中有两个匹配。

在处理索引文件结构时，有两种办法。

方法一：

为每个字符预留一定的空间（称为基础块），如果某一个字符的基本块用完，则在文件末尾为其分配一附加块，在每一块中添加指针，指向该字符的下一个块。

如图3-6，上面三行是基本块，当a的基本块满了，就为其在文件末尾分配一个附加块，指针由基本块指向附加块，再次满后，再次为其分配附加块。

如果此时c的基本块满了，则也为其分配一个附加块。

图3-6索引文件分块结构

但是该方法存在的缺点是在基本块没有写满的时候，仍需占用存储空间，而有些字符，如二级汉字，实际上很少会出现，所以如果基本块空间分配过大会浪费，而如果分配较小，一个字符后可能会出现很多个链接块，在文件中分散存储，将影响查询和原文生成的速度。

方法二：

在索引库中每加入一次文件，则为相应文本字符添加一块与该字符上一块连接。

方法二的不足是块的数目和大小完全由每次加入文本库的文本内容决定。

不同字符的块大小将极为不平衡。

如回车、换行或汉字“的”的索引块较大，而二级汉字的块将很小。

且这也将限制每次索引库中加入文件不能过小，否则将会出现繁多的小块，因而也会影响查询和原文生成的速度。

具体在处理索引文件结构时需要结合实际情况选择不同的索引创建方法，比如若是每个字符在所有文档中出现的概率相差不多，并且能够估计到文档的大小，则采用第一中预留的方案，能够快速的检索并且不会出现很多的