毕业设计（论文）基于传统倒排表的索引创建算法合并排序式索引创建算法.doc

《毕业设计（论文）基于传统倒排表的索引创建算法合并排序式索引创建算法.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于传统倒排表的索引创建算法合并排序式索引创建算法.doc（38页珍藏版）》请在三一办公上搜索。

1、摘要 中文全文检索系统是信息产业中发展较快的一个领域，而一个中文检索系统的核心就是索引器，本文介绍了索引器构造的不同算法模型，对相关的技术进行了比较，分析了各自的优缺点和实现难点，提出了一种中文全文检索中索引实现的数据结构和新型的算法模型。本文首先综述了中文全文检索中索引构造的相关技术，主要包括索引文件数据结构、索引单位选取和索引压缩算法。 在上述综述的基础上，本文采用了基于单字的倒排表文件格式和可变字节编码压缩技术实现了整个索引系统。该系统包括三方面的功能分别是:文本预处理、索引创建和索引更新。 在文本预处理部分实现了中文、外文和特殊字符的分离，同时实现了停止词 (stopword)的删除。

2、 在索引创建部分本文首先给出了一种基于传统倒排表的索引创建算法合并排序式索引创建算法，该算法需要源文本10倍大小的临时空间。为了解决合并排序式索引创建算法临时空间过大的问题，本文提出了一种新的索引创建方案，该方案采用分级的倒排表索引组织结构和链式顺序混合存储的方式。它不仅不需要额外的临时空间，而且还提高了索引创建的效率。在索引创建的过程中本系统采用了可变字节编码压缩技术对索引进行压缩，实验表明该压缩算法将索引文件大小减少了20-30%。 在索引更新部分本文提出了三种顺序存储方式下准动态的索引更新策略，一种链式存储格式下索引动态更新的算法。该系统采用的链式存储结构下的索引更新算法复杂度达到了O(

3、n)。 关键词：中文全文检索；索引器；倒排表；索引压缩 ABSTRACT Chinese Full-Text Retrieval System is one of the fast developing fields in information industry , and the core of the Chinese retrieval system is the Index device. The paper analyzes several different algorithms of constructing the index device, and compares the

4、related techniques, and then gives the advantages and disadvantages of each and the difficulty of achieving. Fnially this paper gives the data structure and a new algorithm model of The index in full-text retrieval system.This paper first summarizes the related techniques of index constructing in Ch

5、inese Full-Text Retrieval, mainly includes data structure of document indexing, index compression algorithms. The further way, this paper implements the entire index system using the setechniques, such as character based-on Inverted lists and the variable byte coding compression algorithm. This syst

6、em includes three functions respectively is:Text pretreatment, index foundation and index up dating. In the part of text pretreatment, has realized separation of Chinese, foreign and the Special character, and has realized deletion of stopword.In the part of index foundation, produces one kind index

7、 foundation algorithm based on traditional Inverted ListsSort-Merge method. This algorithm needs the 10 time of sizes for temporary spaces than the source text. Inorder to solve the problem of oversized temporary space in above algorithms, this paper proposed a new index foundation plan. The index o

8、rganizational structure of this plan is improved Inverted lists, and its memory way is mix of chain ando rder. It not only does not need the extra temporary space, but also enhances the efficiency of index founding. In the process of index founding, using the invariable byte code compression technol

9、ogy to carry on the Compression of index, the experiment tindicates this compression algorithm reduced the size of index document 20-30%. In the part of index renewal,this paper proposed three dynamic index updating strategies based on order memory, and a kind of index dynamic updating algorithm bas

10、ed on chain memory. The experiment indicates that index renewal algorithm complex has achieves O(n) based on chain memory. KEYWORDS：Chinese Full-Text Retrieval；Index device；Inverted Lists；index 引言11研究背景在信息时代产生了大量数字信息，其中文本信息是最基本和常用的形式，为了能在海量的文本信息中找到自己的所需，人们迫切需要一个高效的检索工具。怎样高效的存储和查询文本这种非结构数据，就是一个颇值得研究的

11、问题。这其中以全文检索技术成为国内外学者研究的热点。 全文检索(Full-text Retrieval)是以文本数据为主要处理对象，基于全文标引，使用自然语言进行检索的技术。在信息检索领域，全文检索一直是一个比较复杂的问题.与普通数据库检索所设计的结构化数据查询不同，全文检索不仅要查询结构化数据，而且还要查询非结构化数据，比起标引检索来，全文检索提供了全新的，强大的检索功能，方便多角度、多侧面的综合利用信息资源。当今以全文检索为核心技术的搜索引擎已成为网络时代的主流技术之一。 在文本检索中，为了满足一定的查询性能要求一响应时间(Response Time)和系统吞吐量(Throughput)，

12、词表和文档元数据的存储要有良好的设计，文献就检索效率问题作了详细的论述.文本检索有几种主要建索引的模型:倒排表、正排表、后继数组模型、互关联后继数组模型等，其中倒排表是最常用的，它的存储设计也是文本检索中的基本问题之一。目前很多主流的全文检索系统用自设计的文件来存储倒排文件，比如易宝北信TRS。当倒排文件比较大时，就要考虑压缩。压缩在大规模文本索引时尤其重要，目前比较流行的压缩算法有以下几种：按位紧凑压缩法、可变字节编码、Elias gamma coding、Golomb coding等。压缩算法的好坏不能只用其压缩率来衡量，在考虑到压缩率的同时也要考虑到解压所用的时间。 国外的全文检索软件虽

13、然较早地得到应用，但对中国用户有很多不适用的地方。中文全文检索技术在原理上同西文全文检索是一致的，但汉语本身的特点使中文系统的实现比西文系统更为复杂。全文检索的核心技术是将源文档中的所有的基本元素的出现信息记录到索引库中fill.在中文系统中，基本元素可以是单个汉字字符，也可以是词。因此存在两种基本的索引库结构，即基于字表的索引库和基于词表的索引库。字表法和词表法各有优缺点.国内学者对此都各有侧重研究，前者实用性很强，构建直观方便，纵观近几年单汉字标引和检索技术的发展，其发展趋势可归结到两点：一是在单汉字标引和检索技术中引入受控标引和检索的技术和思想；二是引入人工智能技术。检索方面，比较实用的

14、是 “首字直接匹配法”，词表法多集中在中文自动分词研究，自然语料统计分析等方面。 12 索引在中文检索中的位置及研究现状 全文检索是指计算机索引程序通过扫描文章中的每一个词，给每一个词建立一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表查字的过程。 在上段全文检索的叙述中提到了索引，为什么要建立索引?索引对于全文检索到底意味这什么？在Otis Gospodnetic和Erik Hatcher的lucene in action一文中提到 “在搜索引擎的所有概念中最为核心的概念就是

15、索引，索引就是把原始的数据处理成一个有利于高效检索的数据形式。”他们就为什么要进行索引给出了具体和形象的说明：“假如你需要在很大量的文中进行某个特定信息的检索，并且你想在非常短的时间内找到含有需要信息的文件，你会怎样写程序实现这些？最简单的方法是顺序扫描所有的文件寻找给定词和短语，但这种方式有一些缺点，其中最致命的是当文件很大时根本没有足够的空间来存储该文件，这就是为什么需要索引了，为了在大量文本中检索到所需要的信息，首先必须把源文本集转换成一另一格式的文件，这种格式的文件能够让你进行快速的检索，而不是只进行很慢的顺序扫描。”这个转化的过程就是索引化，该过程输出的结果就是 “索引气在上文中可以

16、知道索引是全文检索的 “心脏气下面的全文检索的模型结构图能够清晰的说明索引在全文检索中的地位。 下图即为全文检索的模型结构图: 应用程序开发搜索命令查询引擎文本处理引擎索引引擎（索引器）查询结果查询结果处理索引文件文本数据库 图1-1全文检索结构模型图 全文检索系统是按照全文检索理论建立起来的用来提供全文检索服务的软件系统，一般来说，全文检索要具有建立索引和提供查询的功能。从上图中可以看 出，全文检索系统中最为关键的部分是全文检索引擎，各种应用程序都需要建立在这个检索引擎之上。在检索引擎中可以看出索引引擎占据了核心的位置，他是整个检索效率的重要决定因素，一个全文检索应用的优异程度，根本上由全文

17、检索引擎来决定。而全文检索的效率主要是由一个索引引擎所决定的。13本文论文安排 鉴于上文的分析，知道一个优秀的索引引擎对于全文检索非常重要。本文的主旨就是建立一个全文检索的索引系统。本文主要的工作安排如下： 第二章主要阐述了基于中文全文检索索引器的功能。同时给出了通用索引器的组织结构图：一个索引器应该包文本预处理模块，创建索引模块以及索引维护模块。 第三章论述了中文全文检索索引所设计的主要技术问题。主要有索引文件结构的选择，索引元的选取以及索引压缩算法的比较分析等。同时给出了基于字和基于词的索引器优缺点的比较。 第四章中给出了基于单字的中文全文检索的索引器的设计方案和实现过程，其中包括索引文档

18、的创建，索引文档的动态更新和删除以及索引压缩算法的实现。 第五章索引压缩算法测试结果以及索引创建效率分析。 第六章是小节篇，总结了本文所做的工作，找到了不足之处，给出了下一步工作的方向。 2中文全文检索中的索引器的结构和功能 21全文检索索引器的结构 在下图中可以看出一个索引器有三部分组成，第一部分是文本预处理模块，在该模块中针对给出的待索引的文本进行预处理，然后对经过处理的文本进行索引的建立，在索引建立后由于待查文档的改变要对索引尽心维护。索引维护主要涉及的问题是:源文档增加时将新的索引附加到原来的索引上，当源文档改变时，将其相对应的索引文件更新，但某些文档不在需要时，也要将其相对应的索引文

19、件删除。 具体的结构图见图2-1：外部接口索引器文本预处理索引维护外部接口建立索引文本数据库索引数据库图2-1索引器结构图22 全文检索索引器的基本功能 一个中文全文检索的索引器应该实现三部分的功能。第一部分是文本预处理，一般需要检索的文档成分比较复杂，需要用文本预处理将文档中的中文，数字，符号，以及西文分开并归类然后分别对其建立索引。由于中文语言的复杂性 (见 3.3.3节分词技术说明)在预处理这部分需要包括中文索引单位的选取，目前主流的有两类：一类是单字，一类是分词。 第二部分功能是创建索引，利用选定的索引数据结构对源文档遍历建立索引。 第三部分功能是实现索引的维护，包括索引删除，索引增加

20、，索引更新。 3中文全文检索索引器构造相关技术综述一个完整的中文全文检索的索引器的构造涉及到索引数据结构的选取，索引单位的选定，以及整个索引器的结构，索引采用的策略，以及有关索引压缩算法的研究。在本章中介绍了索引数据结构以及其相关的工作原理，分析了一种基于单字的索引器的构造及工作原理以及基于分词技术的索引的构造方案，在最后的一小章中介绍了一些主流的压缩技术，并给出了这些技术与索引的结合应用。 31索引数据结构及其相关原理 索引文件有多种组织形式，其中以正排表、到排表以及后继数组比较常用。下面分别介绍正排表、倒排表以及后继数组的结构和工作原理。 3.1.1正排表的数据结构和其工作原理 正排表是以

21、文档的ID为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。正排表结构如图3-1所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护;因为索引是基于文档建立的，若是有新的文档假如，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。若是有文档删除，则直接找到该文档号文档对因的索引信息，将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。 由于正排表的工作原理非常的简单，但是由于其检索效率太低，几乎没有什么实用价值，所以在此不作详细介绍。 Word1文档1W

22、ord2文档1Word1Word2 图3-1正排表结构图 312倒排表的数据结构和工作原理 倒排表以字或词为关键字进行索引，表中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的ID和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排表。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，效率相对低一些，不会影响整个搜索引擎的效率。倒排表的结构图如图3-2： Word1文档2Word1文档1文档2文档

23、1 图3一倒排表结构图 倒排表的索引信息保存的是字或词条在文档内的位置，在同一篇文档内相邻的字或词条的前后关系没有被保存到索引文件内。下面给出一个传统的基于单字的中文全文检索数据结构和算法模型进行分析说明。 全文检索方案是在执行检索操作时比较字或词条在同一文档内的位置是否相邻的算法方案。在此为了说明倒排表的工作原理，采用一个全文检索方案加以说明。 倒排表实际上就是一个表结构，在对关键词进行检索时需要对关键词中每个字在倒排表中进行一次检索操作，假设我们要对key这个关键词进行全文检索，key如定义3-1所示: 定义3-1：Key=Cl,C2,C3.Cnn=123. Key是n个字符的集合，它们的

24、前后位置关系是固定的，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而且这些字符在该文档中的字符位置的差值和它们在关键词中的位置的差值

25、相同。 例如，搜索 “中国气” 假如索引库中 “中”字的索引信息为二元组序列为 (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号文档。 从上述的分析可以知道

26、，倒排表检索效率的优势远远大于正排表。313互关联后继树模型 目前全文检索除了上述的正排表、倒排表模型外有人研究利用互关联后继树模型来实现全文检索。与传统的倒排表的索引数据必须具有文档一索引项结构且只能实现简单的查询不同，互关联后继树模型不但能够处理具有文档索一引项结构的数据，同时也能够与Pat树一样处理无结构数据;具有创建速度快，查询速度快，空间效率高等特点。在本小章中将简要的介绍互关联后继数组模型的基本构造及其工作原理。设是构成文本的基本符号单元的集合是a1,a2,，an。中的一些基本符号，它们的有序组合便可构成一个文本。我们在每个文本T的最后人为的添加一个不在中的符号，用来表示该文本的结

27、束。这个符号称为文本结束符，一般用ASCII 为0的字符表示。在本文中，为了阅读方便文本结束符使用 “#”。通常把加入某一个索引库的所有文本的集合叫做该索引库对应的全文。 定义3-3（前驱和后继）对任意文本T中的任意字符串a1,a2,a1，称为a2的前驱；a2称为a1的后继，文本最后一个字符的后继为文本结束符。 注记：若组成文本T的字符串a1,a2,，an中，出现了m个相同的字符，不妨记该字符为a。那么a有m个后继，记为ak,k=1,2,.,m。ak表示a的第k个后继。 定义3-4（后继表达式与后继树）设全文I是由一字符串a1,a2,，an,#组成的，若其中a;,=ai2=.=ain=a为相同

28、的字符，an+1,ai2+1，an+1.,分别是其后继，an+1, ai2+1,ain+1,的后继又分别(an+1,tag1), (ai2+1,tag2)，(ain+1,tagn)那么我们称ai+1tag1，ai2+1tag2,，ain+ntagn为a的后继表达式，可以用一棵后继树来描述此表达式，如图3一所示，an+1,tag1是a的一个（后继，位置）对。 aai+1tag1ai2+1tag2ain+ntagn 图3-3a的后继树形式 倘若文本中有一段文字为a,an+1,b，则a有(后继，位置)对(an+1,tag1)，其中an+1是a的一个后继，而tag1是在以an+1,为根的树中b所在分支

29、的序号。这个序号实际上也就是b在an+1,树中的位置。 定义3-5（互关联后继树）由一个索引库对应的全文I的所有后继树组成的森林，叫做I的互关联后继树 (IRST Inter-Relevant Successive Trees)。 例1对于全文abcabaabc#，其中#为索引库的结束符，a的后继表达式为 (b,1)(b,2),(a,4),(b,3)，其对应的后继树，全文IRST如图3-4所示。 a b c (b,1) (b,2) (a,4) (b,3) (c,1) (a,3) (c,2) (a,2) # 图3-4全文互关联后继树模型 创建该全文IRST的时候，我们为中的三个字符：a,b,c分

30、别建立三棵树，然后按照读取的字符依次为树添加树枝。首先读入ab，将a的后继b填入树a的第一个分支处，由于此时还不知道该分支对应的位置信息，留空.而后，读入c, 将c填入以其前驱b为根的树的第一个分支，此分支号即为前次留空的位置信息，将1回填到a树的第一个分支。再读取a，在c树的第一个分支填写a，并且回添该分支号1到b树的第一个分支。当读入#后，在以其前驱c为根的后继树中增加第二个分支#，并将2回填。此时，索引文件的结构如图3所示，将此索引文件结构表示成树的形式，即为图3一的IRST. a b1 b2 a4 b3 b c1 a3 c2c a2# 图3一索引文件结构示例 利用索引生成原文，我们需要

31、记录加入索引库的文本的第一个字符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”在

32、索引库中有两个匹配。 在处理索引文件结构时，有两种办法。 方法一：为每个字符预留一定的空间(称为基础块)，如果某一个字符的基本块用完，则在文件末尾为其分配一附加块，在每一块中添加指针，指向该字符的下一个块。如图3-6，上面三行是基本块，当a的基本块满了，就为其在文件末尾分配一个附加块，指针由基本块指向附加块，再次满后，再次为其分配附加块。如果此时c的基本块满了，则也为其分配一个附加块。 图3-6索引文件分块结构 但是该方法存在的缺点是在基本块没有写满的时候，仍需占用存储空间，而有些字符，如二级汉字，实际上很少会出现，所以如果基本块空间分配过大会浪费，而如果分配较小，一个字符后可能会出现很多个链

33、接块，在文件中分散存储，将影响查询和原文生成的速度。 方法二：在索引库中每加入一次文件，则为相应文本字符添加一块与该字符上一块连接。 方法二的不足是块的数目和大小完全由每次加入文本库的文本内容决定。不同字符的块大小将极为不平衡。如回车、换行或汉字 “的”的索引块较大，而二级汉字的块将很小。且这也将限制每次索引库中加入文件不能过小，否则将会出现繁多的小块，因而也会影响查询和原文生成的速度。 具体在处理索引文件结构时需要结合实际情况选择不同的索引创建方法，比如若是每个字符在所有文档中出现的概率相差不多，并且能够估计到文档的大小，则采用第一中预留的方案，能够快速的检索并且不会出现很多的 “碎片”。若

34、是文件的大小完全无法预料，则只能采用第二种。3.1.4几种索引存储结构的比较 在上面的三个小节中提到了三种索引存储结构分别是正排表、倒排表和互关联后继数组模型。下面给出三种索引结构的简要分析。 由3.1.1的分析可以知道，对正排表进行信息检索的时候，等于直接对源文件进行全文扫描，索引的建立并没有加快检索的速度，但是却在建立索引时耗费了空间和时间，这种方法没有实用的价值，一般不采用。 相比来说倒排表就很是一种实用性很强的索引存储，倒排索引由于其组织结构的形式(具体分析见3.1.2)，对信息的检索能够变的非常快，所以倒排表成为了一种主流的索引文件格式，在大部分的全文检索系统中的都采用这种索引结构。

35、 互关联后继数组模型是一种新颖的全文检索的模型，他的特点：1)能够处理无结构的数据(这点与pat树有一样的功能)。2)创建的空间效率比较高。 3)可以通过索引生成原文。 不足之处：4)文件管理方面，由于所有的倒排文件都是通过树或是森林来管理，所以系统要维持整个森林要花费很大的代价。 5)互关联后继数组在实现上的复杂度要远远大于倒排表。 6)在处理不相邻的检索关键字方面比较吃力。 7)在文本预处理时，互关联后继树模型对 “stop word”就无能为力。 与之相比倒排表具有以下的优点：1)倒排表技术是一种比较普遍通用的技术，针对倒排表的研究也比较多，所以相关的技术也比较容易实现。 2)经过改进倒

36、排表结构形式也能够达到比较好的检索效率，以弥补检索效率的问题，在空间效率上可以利用索引压缩技术进行改进。 3)在网络上面，检索的返回结果只是一个链接，并不需要全文的还原，所以互关联后继树模型这方面的优势并没有很明显。 综合比较起来，本文采用倒排表格式的索引存储格式。 3 . 2基于单字的索引器构造 全文检索的核心技术是将源文档中有的基本元素的出现信息记录到索引库中。在中文系统中，基本元素可以是单个汉字字符，也可以是词。因此，存在两种基本的索引库结构，即基于字表的索引库和基干词表的索引库。基于字表索引库的建造方法有很多种，不同的字表的构建方法会对应不同的检索策略。下面介绍其中一种字表法索引库的构

37、造方法及检索策略。3.2.1单字索引数据结构 单字的索引库数据结构一般采用字表法，字表法索引库的主要部分是每个字的字表信息。字表结构如表3-1所示，其中字符i对应的字表记录了该字符在源文档中所出现的位置Pix。该位置采用了字符相对于文档头的偏移字符数表示，而不按通常情况采用相对于文档头的偏移字节数，这样可以大大减小位置的数值大小，有利于进一步采用压缩技术。建立字表索引时，需要扫描整个源文档，对出现的 每一个有效字符，计算其在文档中出现的位置，并将该位置的值加入到对应的字表中。 表3-1字表结构啊P11，P12， P13啊P21，P22， P23的Pi1，Pi2， Pi3中Pj1，Pj2， Pj

38、3 索引库中的一个字表记录了对应字符在源文档中的所有位置信息。考察一个字符串，如两个字的字符串XY(其中X,Y表示任意的汉字字符)，假设X的位置为)Px，如果字符串XY在源文档中出现，则Y的位置Py必定等Px+1,(1为两个汉字间的字符距离)。在索引库中X的字表中将包含Px，而Y的字表中也必然包含Px十1。进行检索时，扫描X和Y各自对应的字表，若文档中有该词出现，则必定有X对应的字表中存在位置值Px,Y对应的字表中存在位置值Py使得Py= Px+1成立，每查到一对这样的位置值，就是检索到字串XY一次。扫描完两字的字表，就可检索出该字符串的所有出现。 上面简要介绍了字表的用法，在具体实现的时候的

39、数据结构要稍微复杂一些，因为某个字符的字表中不但要包含文档的信息还要有某字符在该文档中出现的位置信息，由于字符在每一个文档中出现的次数与位置都不一样，所以在实现的时候采用了一种比较复杂的数据结构，就是字表倒排文档。 字表倒排文档的数据结构是每个汉字字符对应的字表中，包含该字符出现在所有文档中的全部位置。为了区分每个位置公到属于哪个文档，每个字符的字表被分为多个字表段，每段对应一个文档，记录该字符在此文档中的出现位置。字表采用倒排文件结构，如表3一所示。 字段表1字表段1文档编号字频位置序号 表3-2字表倒排文档 每个字表段起始部分记录当前文档的编号，随后是该字符在文档中的出现频率，最后是该字符

40、在文档中的所有出现位置序列。每个字符的所有字表段按文档编号递增的顺序排列，如果该字符在文档k中没有出现，则不存在文档k对应的字表段。 3.2.2单字索引的创建方法 上面简要介绍了基于字表的索引库的结构，下面给出基于单字索引的创建方法。 该索引创建方法不需要排序，分为如下两步： 第一步分析源文档，产生临时的中间文件，这个过程称为分析过程。当前只针对GB码字符进行处理，其中包含全部字符，既有汉字，又有一般的数字，标点符号等。GB码第一个字节的范围是0XAI-0XF7，第二个字节的范围是0XA1-0XFE。汉字从 “啊”开始，首字节为176-247，第二个字节为161-254。根据这种分布规律，可以

41、方便地定位每个字符对应的字表信息。源文档经过处理，将其包含的每个字符的对应信息写到一个临时的中间文件中。对于每个字符，其在临时文件中的对应信息包括:该字所出现的当前文档编号、在该文档中的出现频率、出现的位置序列和该字符出现在下一个文档的数据的指针(数据在文件中的偏移值)。 第二步处理临时文件，依次从临时文件中读取每个字符出现在每一篇文章中的数据信息，生成最终的倒排文件，在这里称为创建过程。生成的最终倒排文件中包含每个字符出现在所有文档中的信息。包含该字符出现的当前文档的编号、出现频率和相应的位置序列。处理过程如下图所示。 源文档分析临时文件最终倒排文件文档编号频率位置序列文档编号频率位置序列前

42、向指针 图3-7生成索引文件流程图 323优化的基于单字索引创建方法 在上面所论述的基于单字的索引创建方法中，对于源文件的分析过程本身需要一定的时间，随着处理数据集规模的增大，相应的分析时间增大，第二步 (创建过程)所需的时间相应的迅速增大。该过程需要大量的随机读取操作来遍历每个字符对应的所有信息。当数据的规模增大时，遍历每个字符的临时数据的操作变得很慢。这是由于字符对应的每个字表的数据在临时文件中有一定距离，遍历需要不断地移动文件指针来读取这些数据。 利用操作系统提供的虚拟内存技术可以优化索引的创建过程。Windows操作系统用虚拟内存技术来动态管理运行时的交换文件。为了提供比实际物理内存还

43、多的内存容量以供使用，Windows操作系统占用了硬盘上的一部分空间作为虚拟内存。当CPU有要求时，首先会读取内存中的资料。当内存容量不够用时，Windows就会将需要暂时储存的数据写入硬盘。内存映射文件技术是WindowsNT 提供的一种新的文件数据存取机制。利用内存映射文件技术，系统可以在2GB的地址空间中为文件保留一部分空间，并将文件映射到这块保留空间。一旦文件被映射之后，WindowsNT将仔细管理页映射、缓冲以及高速缓冲等任务。通过把临时文件映射到虚拟内存中，可以大大加快对临时文件的访问速度。 对于较小的源数据集，分析处理后生成的临时文件也较小，使用内存映射文件可以大大加快创建过程。

44、但当数据规模增大时，该方法的性能迅速降低，甚至比没有使用内存映射文件都差。性能的降低一方面由于机器有限的内存，其小于临时文件的大小。另外一方面，同一个字符相邻的数据在临时文件中距离过大，导致大量的缺页中断，系统性能大大降低。解决该问题的有效方法是把原有的单个的大的中间文件分成多个小的临时文件，在分析过程中生成多个小的临时文件，创建过程依次处理每个临时文件，将其映射到虚拟内存中，可以充分利用直接内存访问的速度，并且减少缺页中断。在实际应用中，可以采用了统计的方法，通过对一个较大的数据集的分析，将原有的一个大的临时文件拆分成多个小的临时文件，每个字符的索引数据存放于其中的一个临时文件中。井且每个临

45、时文件中存放的数据的大小相差很小。这样，每个小的临时文件的大小小于当前内存的大小，从而可以有效地使用虚拟内存技术加快存取。33基于词表的索引器构造由上文可以知道以中文的词组作为索引单元也是一种常用的索引文件构造方式，基于分词的中文全文检索索引器的构造是以词为索引项的索引结构。 3.3.1词表索引数据结构 典型的基于词的倒排索引结构 (见图3-8)包含两部分：1)中文词组成向量 (称之为词汇表)，它包含了词的基本信息和词索引在索引文件中的偏移量。2) 对于词汇表中的每一个词，都有一个它出现过的文档列表，它包含了出现文档编号，在此文档中该词的词频和出现位置序列。文献频率出现列表文档ID字频位置序列ID索引指针W1基本空间Ne