全文检索系统论文

《全文检索系统论文》由会员分享，可在线阅读，更多相关《全文检索系统论文（38页珍藏版）》请在金锄头文库上搜索。

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

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

3、结构下的索引更新算法复杂度达到 了 O(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 de

4、vice, and compares the 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

5、index constructing in Chinese 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 compress

6、ion algorithm. This system 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 foundati

7、on, produces one kind index 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 f

8、oundation plan. The index organizational 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 by

9、te code compression technology 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 dyn

10、amic updating algorithm based 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)是以文本数据为主要处理对象，基于全文标引，使用自然 语言进行检索的技术。在信息检索领域，全文检索一直是一个比较复杂的问题.与普通数据 库检索所设计的结构化数据查询不同，全文检索不仅要查询结构化数据，而且还要查询非 结构化数据，比起标引检索来，全文检索提供了全新的，强大的检索功能，方便多角度、 多侧面的综合利用信息资源。当今以全文检索为核心技术的搜索引擎已成为网络时代的主 流技术之一。 在文本检索中，为了满足一定的查询性能要求一响

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

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

14、两点：一是在单汉字标引和检索技术中引入 受控标引和检索的技术和思想；二是引入人工智能技术。检索方面，比较实用的是 “首字 直接匹配法” ，词表法多集中在中文自动分词研究，自然语料统计分析等方面。 12 索引在中文检索中的位置及研究现状 全文检索是指计算机索引程序通过扫描文章中的每一个词，给每一个词建立一个索引， 指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进 行查找，并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表 查字的过程。 在上段全文检索的叙述中提到了索引，为什么要建立索引?索引对于全文检索到底意味 这什么？在 Otis Gospod

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

16、一格式的文件，这种格式的文件能够让你进行快速的检索，而不是只进行很慢的顺序扫描。 ”这个转化的过程就是索引化，该过程输出的结果就是 “索引气在上文中可以 知道索引是全文检索的 “心脏气下面的全文检索的模型结构图能够清晰的说明索引在全文 检索中的地位。 下图即为全文检索的模型结构图: 图 1-1 全文检索结构模型图 全文检索系统是按照全文检索理论建立起来的用来提供全文检索服务的软件系统，一 般来说，全文检索要具有建立索引和提供查询的功能。从上图中可以看 出，全文检索系统 中最为关键的部分是全文检索引擎，各种应用程序都需要建立在这个检索引擎之上。在检 索引擎中可以看出索引引擎占据了核心的位置，他是整个检索效率的重要决定因素，一个 全文检索应用的优异程度，根本上由全文检索引擎来决定。而全文检索的效率主要是由一 个索引引擎所决定的。 13 本文论文安排 鉴于上文的分析，知道一个优秀的索引引擎对于全文检索非常重要。本文的主旨就是 建立一个全文检索的索引系统。本文主要的工作安排如下：第二章主要阐述了基于中文全