（计算机软件与理论专业论文）全文索引技术中索引归并算法的研究与分析.pdf

摘要 摘要 索引的动态维护与更新是全文检索与全文索引技术中的一个重要研究和应用 方向，当随着i n t e m e t 的迅速发展，互联网上信息数据在急剧地增长，而在这种海 量数据的情况下，新的数据在不断增长，同时过时的数据就要被淘汰，这就需要 对信息数据频繁的插入和删除，因此，索引的动态维护中的归并算法的研究也就 处于了一个十分重要的地位。本论文主要针对常见的索引归并算法进行改良，并 对改良的算法在时间效率以及可行性上进行了研究论述。 索引的过程就是把原始的数据处理成一个有利于高效检索的数据形式，因此 索引的基本结构关系到动态索引维护与更新的效率，包括建立索引的过程，索引 的组织方式，正排表，倒排文件及倒排索引的建立，本文介绍了构造倒排索引的 过程，并分析静态索引技术的优缺点以及增量索引知识，还有索引动态更新对信 息检索技术的重要性。 本文比较了各种索引更新策略，包括原地更新策略，重建策略，重新归并更 新策略，并且分析了这些策略的成本代价，在此基础上研究了基于归并策略的各 种不同的索引归并算法，包括有立即归并算法，对数归并算法，几何划分归并算 法，类哈夫曼索引归并算法，同时分析了他们的优缺点，提出了各自的改良算法， 其中本文的重点是在详细分析几何划分归并算法的基础上，针对原有的几何归并 算法在索引过程中没有对文档删除，提出了带有索引垃圾碎片的回收的新的几何 归并算法，其中新算法采用了极限值的方法对删除的文档进行处理。 最后通过一个开源的全文检索与全文索引平台测试了立即归并算法，对数归 并算法及改进算法的索引合并过程和时间，验证了在相同条件下使用改进的算法 进行合并，时间上得到了提高。测试了几何归并删除文档索引碎片回收的可行性。 关键词：全文检索，倒排索引，索引合并，重新归并 a b s t r a c t i nr e c e n ty e a r , t h em a i n t e n a n c ea n d u p d a t eo f o n - l i n ei n d e xb e c o m et h eh o ti s s u ei i l t l l er e s e a r c ho fm l l t e x tr e t r i e v a l ，a st h e r a p i dd e v e l o p m e n to fi n t e m e t ，d a 舾o n 1 e i n t e r n e t1 sa l s oe x p l o d i n gr a p i d l y , h o w e v e r , n om a t t e rt h eh u g ed a t ae x i s t e d n e wd a t e c o n t l n u et og r o w , o u t d a t e dd a t en e e dt ob ee l i m i n a t e d a sw e l l ，w h i c hr e q u i r e st h e f r e q u e n tm s e r t i o na n dd e l e t i o no f d a t a , t h e r e f o r e ，a c c o r d i n g l y , i n d e x m e r g e ra 删1 1 1 1 e t i c 1 sp u to nt h ec e n t r a la r e n a i nt h i sp a p e r , w em a i n l ya i ma tt h e a n a l y s i so fi n d e xm e r e 2 l l g o r i t h mi nt h ef u l l _ t e x tr e t r i e v a la n dp r o v i d ei m p r o v e da l g o r i t 王m li nt e n i l so f t i m e c o n s u m p t i o n t h ef u n d a m e n t a lo fi n d e xi sc o n v e r to r i g i n a ld a t et of l e x i b l ed a t as t r u c t u r e t 0m a k e s e 抓nm o r ee f f e c t i v e ，b a s eo na n a l y s i s o ft h eb a s i cs t r u c t u r ew h i c hd o e si m p a c t e l - i i c i e n c yo fi n d e xu p d a t e ，i n c l u d eh o wt oc o n s t r u c ti n d e x ，s t r u c t l l r e so fi n d e xa n d i n v e r t e df i l e t o g e t h e rw i t hh o wt oc o n s t r u c ti n v e r t e d i n d e x ，w ea l s om e n t i o nt h e a d v a n t a g e sa n dd i s a d v a n t a g e so fs t a t i ci n d e x ，a n di n t r o d u c ei n c r e m e n ti 1 1 d e xa n dt h e i m p o r t a n c eo fd y n a m i cu p d a t ea tt h ee n do ft h i ss e s s i o n 2 i nt h et h e s i s ，w er e s e a r c h3i n d e xm a i n t e n a n c e s t r a t e g i e s ，i n p l a c ei n d e xu p d a t e ， m e r g e b a s e di n d e xu p d a t ea n dr e b u i l di n d e x u p d a t e ，w k c h岛c u so nc o s t c o n s u l l l p t l o ni nt h ed i f f e r e n ts t r a t e g i e s ，a c c o r d i n g l y , w ea n a l y z et h em e r g e b a s e di n d e x m a i n t e l l a n c e s t r a t e g i e s ，i n c l u d e di m m e d i a t em e r g e a l g o r i t h m ，l o g a r i t h m i cm e r g e ， g e o m e t r i cp a r t i t i o n i n ga n dd y n a m i cb a l a n c i n gt r e em e r g e r a l g o r i t h mt o g e t h e rw i t ht h e i r a d v a n t a g e sa n d d i s a d v a n t a g e sa n dw ep r e s e n ti m p r o v e d s o l u t i o n s g e o m e t r i c p a r t i t i o n i n g1 so u rf o c u sw h i c hh a v eb e e ns t u d i e di nd e t a i li nt h i sp a p e r , w ep r e s e mn e w g e o m 咖cm e r g et o g e t h e rw i t hg a r b a g ec o l l e c t i o nt o r e d u c et i m e c o n s 啪p t i o n t h e l i m i t sm e t h o di si n t r o d u c e dt od e l e t eo u t d a t e dd o c u m e n t s i nn e w a l g o r i t l u l l a tt h ee n do ft h i sp a p e r , w em a k eu s eo f a no p e ns o u r c ef u l l t e x tr e t r i e 、嘣s v s t e m t ot e s t1 砌1 e d i a t em e r g e ，l o g a r i t h m i cm e r g e ，g e o m e t r i cp a r t i t i o n i n gm e r g e a n dv a l i d a t e t h e1 m p r o v e da l g o r i t h m ，t h et i m ec o n s u m p t i o no fn e w a l g o r i t l l i l la r el o w e rt 1 1 a no 】d a p p r o a c hl i o me x p e r i m e n td a t a ，w h i c hm e a n sn e w a l g o r i t h mi sm o r ee f f e c t i v e k e y w o r d ：f u l l - t e x tr e t r i e v a l ，i n v e r t e di n d e x ，i n d e xm e r g e ，r e m e r g e l i 图索引 图索引 图2 1 全文检索的系统结构一7 图2 2 全文索引的索引器结构9 图2 3 全文索引的文件结构1 0 图2 - 4 正排表结构11 图2 5 倒排表模型结构1 2 图2 6 文档编号及其内容13 图2 7 新增字符2 后的索引1 7 图4 1 立即归并的索引合并过程2 7 图4 2 立即归并的改进2 路归并的索引合并过程3 0 图4 3 对数归并的索引合并过程3 1 图4 4 改进的对数归并索引合并过程3 3 图4 5 几何归并算法的索引归并过程( r = 3 ) 3 7 图4 6 带索引碎片回收几何划分归并索引过程( f 2 ) 4 2 图4 7 类哈夫曼动态索引合并过程( r e = c = 3 ，s - - n ) 4 5 图4 8 文档中带垃圾删除的动态调整索引合并过程( p = o 2 ) 4 5 图4 9 立即归并及其改进的索引归并过程对比4 7 图4 1 0 对数归并与改进的算法的索引合并过程对比4 7 图4 11r = 2 的几何划分归并4 8 图4 1 2r = 4 几何划分归并4 9 图5 1 相同条件下立即归并与改进的索引合并过程5 3 图5 2 相同条件下立即归并与改进的索引合并过程5 4 图5 3 有文档删除的几何归并索引合并过程5 6 v 表索弓 表索引 表2 1 倒排索引结构1 4 表4 1 索引构建成本3 6 表5 1 索引建立后待归并的索引桶信息5 2 表5 2 立即归并及其改进的索引合并时间5 4 表5 3 对数归并及其改进的索引合并时间5 5 表5 4 几何划分归并随r 不同的合并时间一5 5 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：泌望 日期：知够年，月乒日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：蛐导师签名： 日期：幻以年s 月芝甲日 第一章绪论 1 1 研究背景 第一章绪论 近年来，信息数字化和网络数字化已经成为了现代经济社会技术发展的客观 要求和必然趋势。当今世界上已经拥有超过1 0 亿的i n t e m e t 用户，上百万多个不 同级别的网络服务器l l j 。同时，包括政治，经济，科学，文化艺术等各个不同的社 会领域也都不同程度地实现了其资源信息的数字化和共享化。i n t e m e t 网络已名副 其实的成为世界最大的信息中心。人们越来越多地通过计算机网络来发布和传递 各种信息，并查询自己需要的信息。为能在海量的文本信息中找到自己的所需的 数据，人们迫切需要一个高效的检索工具。计算机网络己经成为计算机应用领域 发展最快、最热门的技术，计算机的应用已经逐步进入网络时代，随着计算机技 术的普及和i n t e m e t 网络技术的发展，互联网上信息数据也在急剧地增长，全文检 索与全文索引技术成为了计算机技术中研究的热点问题。全文检索是一种非常有 效的信息检索技术，它极大地提高了从海量数据中查找特定信息的效率。因此对 于全文检索技术进行更多广泛的研究是十分重要且必要的。而索引技术则是全文 检索中的关键核心，索引是检索的前提和基础，要实现某种检索功能，就必须建 立相应的索引机制。如果不对网页库或文档集建立索引信息，可以通过顺序查找 的方法完成u r l 到指定记录的过程，但是这个过程会消耗大量的f o ，数据量增 大的时候不能满足信息检索的快速响应请求，所以需要创建索引，索引是提高检 索效率必不可少的一项技术，是支持文本有效搜索的关键技术。索引性能的优劣是 影响检索质量的一个重要因素。所以索引对于全文检索系统来说是至关重要的。 因此对于全文检索技术中索引方面的研究是十分必要的。而当前信息数据的增长 速度和淘汰速度也均呈现不断加快的趋势，尤其是像新闻搜索等这种实时更新的 数据，数据信息添加和删除都非常地频繁。所以人们对全文检索的索引动态性要 求变得十分的迫切，应该说全文检索的索引动态性是未来的一个必然趋势。在这 个信息大爆炸的时代，高性能的索引动态维护已经成为时代的需要。本论文就是在 这样一个时代背景下，对索引归并算法进行研究与分析，主要针对全文检索技术 中的全文索引动态维护与更新方面的归并算法的研究，这方面的索引归并算法可 在动态变化的文本集中，即信息数据频繁增加与删除的文档集中，进行索引的归 电子科技大学硕士学位论文 _ , q s g l 2 3 4 1 o 1 2 研究的技术热点 评价一个大规模信息检索系统有两个方面基本的考虑：效果和效率。在文本 的信息检索中，也主要致力于对效果和效率方面的研究【5 】。很多专家都针对这两方 面进行了分析与研究，提出了不少关于性能和效果方面的改善方法。其中关于效 果方面的主要是语义检索模型，查询反馈等实验。效率方面的研究热点主要是集 中在索引压缩，查询执行优化，索引创建和动态更新等方面。 高效的文本索引是搜索应用的关键问题之一，在过去的几十年中，使用倒排 索引的查询处理效率有了大幅度的提高。倒排索引有四个前提假设：频繁查询， 极少删除，极少更新，很少添加，只有满足上述假设才能保证其高效性，但是在 很多应用中，文档以非常快的速率添加，例如新闻搜索，b l o g 搜索和桌面搜索等， 在这种动态环境下如何快速建立倒排索引是最近几年的研究热点【6 1 1 7 1 。 要做到快速建立倒排索引，在索引的归并算法中，面临的最紧迫最需要解决 的就是尽量避免大文件与小文件归并的情况发生，即全文检索中所说的”1 5 m 与 1 5 g ”的情况，以达到尽可能快的合并速度。现在对索引归并算法的研究，也是针 对这种情况进行研究的。所以，索引动态更新也成为了当今全文检索效率方面的 一个研究热点。 1 3 研究现状 尽管全文索引技术已经出现了几十年之久，但是直到互联网的出现，它才真 正得到普及【3 j 。索引是文本搜索的关键技术，因此索引尤其是全文索引技术也被广 泛地研究与应用。索引维护，一般可以通过离线索引和在线索引两种方式，在线 索引的技术相对复杂，大部分的论文著作主要是研究这一方面的。特别是在互联 网快速发展的今天，对全文索引进行更快，更有效的维护，可以让用户的查询更 加的方便，快捷。国内外的专家们都致力于快速建立倒排索引的研究，在合并性 能上有所提高，提出了许多高效归并的算法及维护策略。n i c h o l a sl e s t e r 8 】提出用 几何划分归并方法完成在线索引的快速构建。b f l t t c h e r 和c h a r l e s 等人提出了对数 归并算法，同时也提出t t g 动态文本集中的混合索引维护策略，而中科院计算所也 提出了类哈夫曼索引归并算法，在中科院开发的全文检索与索引开源平台f i r t e x 中 2 第章绪论 就运用到了这个算法。b r o w n ，c a l l a n 和c r o f t 1 0 】研究了一种高效增量索引的方法。 他们区别对待小于8 k 和大于8 k 的索引，当一个小的索引需要增大时，它将被拷 贝到一个大的连续的倒排索引文件中。然而对于一个大的索引项则不需要移动， 只需添加一个前向指针到新的存储段( s e g m e n t ) 罩_ 面。这也使得倒排索引可以通过 倒排索引文件串连起来。他们发现，当在7 个簇中创建一个索引的时候，查询性 能降低了6 。使用小的簇时代价偏高，在他们的模型中索引每簇大小为6 4 m 的 文本所花的时间是索引每簇大小为1 m 的文本的8 倍。 l e s t e r ，z o b e l 以及w i l l i a m s 1 l j 比较了三种索引维护策略：原地( i n p l a c e ) ，重 新合并( r e m e r g e ) 以及重建( r e b u i l d ) 。除了没有对连接链表进行优化外，i n p l a c e 策略类似b r o w n 所采用的方法。所有的倒排索引连续存放，如果没有足够的空间 写入新数据的时候，已有数据必须被拷贝到别的地方。他们研究发现，r e m e r g e 策略是最高效的更新索引的方法。但是，他们没有像b r o w ，c a l l a n 和c r o f t 所作 的那样，对预分配( p r e a l l o c a t i o n ) 策略之间和处理大索引策略之间的差异进行比较。 1 4 本文组织结构 本学位论文的文章组织结构如下： 第一章提出了信息检索技术中关于效率方面课题的研究与选题背景、研究热 点，国内外研究现状以及本学位论文的组织结构。 第二章介绍了索引技术的基本知识，包括建立索引的过程，全文检索与全文 索引思想，索引的组织方式，介绍了正排表，倒排文件及倒排索引的思想，构建 倒排文件索引的过程，分析静态索引技术的优缺点及增量索引，还有索引动态更 新对信息检索技术的重要性。 第三章研究了各种索引更新维护策略，包括原地更新，重建，重合并更新策 略等，并分析了他们的优缺点及算法成本。 第四章重点分析与研究了基于重新归并策略的各种不同的索引归并算法，包 括立即归并算法，对数归并算法，几何划分归并算法，类哈夫曼索引归并算法， 分析了他们的优缺点。针对立即归并算法，对数归并算法，几何划分归并算法， 提出了改进思路。最后通过树状图方式分析这几个算法性能，重点分析几何划分 归并，类哈夫曼归并根据参数的不同其性能的不同。 第五章建造实验数据，通过一个开源的全文检索与全文索引系统验证比较分 析了在相同条件下运用各种算法及改进算法合并的时间。 3 电子科技大学硕士学位论文 第六章在此论文基础了总结本文所作的工作，并提出后期的展望，需要进行 的一些前瞻性的研究工终。 4 第二章索引关键技术 2 1 索引的基本知识 第二章索引关键技术 索引是将文献中具有检索意义的事项( 可以是人名、地名、词语、概念、或 其他事项) 按照一定方式有序编排起来，以方便检索u 2 1 。 2 1 1 建立索引的过程 以g o o g l e 搜索引擎为例【1 3 】，其建立索引的过程大致分为三个阶段： 分析过程。该过程主要处理文档中可能出现的错误。按h t m l 语法规则分析 网页标签结构，调用中文分词和英文分词分析器提取索引词。分析过程中记录 每个索引词的文档频率d f 和文档内的词频仃，保存得到词典文件( 1 e x i c o nf i l e ) ， 并保存页面分析的结果到临时文件。 对文档进行索引。经过分析的文档经编码后被存进一个个存储桶中。根据 存放在内存中的词典( 散列表) ，文档中的每个词都被转换成对应的w o r d l d ， 然后将它们在文档中的出现情况转换成采样表，存放于前项桶中。并行索引可 以索引的速度，但并行索引的困难在于索引需要共享同一词典，而由于外来词 的存在，索引过程要对词典进行一定的修正。 排序过程。为了生成最后便于索引的倒排索引，需要将前向索引存储中的 信息按照w o r d l d 排序，最后生成标题和锚点信息的后向桶以及一个全文的后 向桶。可以对桶逐个地进行排序，也可以并行处理，具体视系统资源而定。对 生成的多个临时倒排文件，执行多路归并，压缩编码，输出得到最终的倒排文 件。 2 1 2 索引在信息检索中的作用 为什么要建立索引呢? 索引技术对于信息检索又到底意味着什么呢? 在搜索 引擎的所有概念中最为核心的概念就是索引，索引就是把原始的数据处理成一个 有利于高效检索的数据形式。 他们就为什么要进行索引给出了具体和形象的说 明：“假如你需要在很大量的文中进行某个特定信息的检索，并且你想在非常短的 电子科技大学硕士学位论文 时间内找到含有需要信息的文件，你会怎样写程序实现这些? 最简单的方法是顺 序扫描所有的文件寻找给定词和短语，但这种方式有一些缺点，其中最致命的是 当文件很大时根本没有足够的空间来存储该文件，这就是为什么需要建立索引了， 为了在大量文本中检索到所需要的信，首先必须把源文本集转换成另一格式的文 件，这种格式的文件能够让你进行快速的检索，而不是只进行很慢的顺序扫描。” 这个转化的过程就是索引话，该过程的输出结果就是“索引 。 索引是检索的前提和基础，要实现某种检索功能，就必须建立相应的索引机 制。如果不对网页库或文档集建立索引信息，可以通过顺序查找的方法完成u r l 到指定记录的过程，但是会消耗大量的i o ，数据量增大的时候不能满足信息检索 的快速响应请求，所以需要创建索引，索引是提高检索效率必不可少的一项技术， 是支持文本有效搜索的关键技术。索引性能的优劣是影响检索质量的一个重要因 素。所以索引对于检索系统来说是至关重要的【1 4 】【”儿川。 2 2 全文检索与全文索引 2 2 1 全文检索 全文检索( f u l l t e x tr e t r i e v a l ) 技术是一种重要的关键词检索方法。全文检索是 指计算机索引程序通过扫描文章中的每一个词，对每一个词建立一个索引，指明 该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索 引进行查找，并将查找的结果反馈给用户的检索方式。就是给定一个字符串或字 符串逻辑表达式，对文档库进行相应的检索，查找出与指定表达式相匹配的文档， 并将包含这些文字信息的文档作为检索结果返回给用户。全文检索技术分为两种 一种是根据检索表达式直接在原文档中匹配查找，这种方式适合于对小型文档库 的检索。另一种是对文档预先建立索引，检索时对索引进行检索，这种方式适合 于对大容量的文档库的检索，如网络上的文档检索。全文检索技术包含两方面的 核心问题一个是如何建立和维护索引库，另一个是如何提供快速有效的检索机制。 面向网络的全文检索系统所处理的对象是大规模的海量数据，要实现对它们快速 有效的全文检索，主要需要从以下三方面进行考虑，检索的快速响应，索引库的 建立与维护，索引数据的压缩【1 7 1 ”l 。 这个过程类似于通过字典中的检索字表来查字的过程。全文检索是以文本数 据为主要处理对象，并将文档的全部文本信息来作为检索对象的一种信息检索技 6 第二章索引关键技术 术。它是基于全文标引，使用自然语言进行检索的技术。在信息检索领域，全文 检索一直是一个比较复杂的问题，与普通数据库检索所设计的结构化数据查询不 同，全文检索不仅要查询结构化数据，而且还要查询非结构化数据，比起标引检 索来，全文检索提供了全新的，强大的检索功能，方便多角度、多侧面的综合利 用信息资源。这种检索方式在m 删搜索引擎，数字图书馆，办公自动化等诸多领 域中都具有广泛的应用价值，尤其是现在以全文检索为核心技术的搜索引擎已成 为网络时代的主流技术之一。 全文检索是一种非常有效的信息检索技术，它极大地提高了从海量数据中查 找特定信息的效率。因此对于全文检索技术进行更多广泛的研究是十分重要的。 全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软件 系统。一般来说，全文检索需要具备建立索引和提供查询的基本功能，此外现代 的全文检索系统还需要具有方便的用户接口、面向w w w 的开发接口、二次应用 的开发接口等等。功能上，全文检索系统的核心具有建立索引、处理查询返回结 果集、增加索引、优化索引结构等等功能，外围则由各种不同应用具有的功能组 成。结构上，全文检索系统核心具有索引引擎、查询引擎、文本分析引擎、对外 接口等等，加上各种外围应用系统等等共同构成了全文检索系统。 图2 - i 全文检索的系统结构 7 电子科技大学硕士学位论文 在图2 1 中，我们看到，全文检索系统中最为关键的部分是全文检索引擎，各 种应用程序都需要建立在这个引擎之上。一个全文检索应用的优异程度，根本上 由全文检索引擎来决定。因此提升全文检索引擎的效率即是我们提升全文检索应 用的根本。另一个方面，一个优异的全文检索引擎，在做到效率优化的同时，还 需要具有开放的体系结构，以方便程序员对整个系统进行优化改造，或者是添加 原有系统没有的功能。比如在当今多语言处理的环境下，有时需要给全文检索系 统添加处理某种语言或者文本格式的功能，比如在英文系统中添加中文处理功能， 在纯文本系统中添加x m l 或者h t m l 格式的文本处理功能，系统的开放性和扩 充性就十分的重要【1 9 】【2 0 】【2 1 1 。 2 2 2 全文检索的索引器结构 一个索引器由三部分组成，分别是文本预处理模块、建立索引模块，索引维 护模块。第一部分文本预处理是一般需要检索的文本成分都相对比较复杂，需要 用文本预处理将文档中的中文、数字、符号以及西文分开并归并然后分别对其建 立索引。第二部分功能是创建索引，利用选定的索引数据结构对源文档遍历建立 索引。第三部分功能是实现索引的维护，包括索引删除，索引增加，索引更渊2 2 1 2 3 1 。 文本在预处理模块中针对给出的待索引的文本进行预处理，然后再对经过处 理的文本进行索引的建立，在索引建立后由于待查文档的改变要对索引尽心维护。 索引维护主要涉及的问题是，源文档增加时将新的索引附加到原来的索引上，当 源文档改变时，如数据增加时，将其相对应的索引文件更新，但当某些文档不再 需要时，也要将其相对应的索引文件删除。具体的结构如图2 2 所示。 8 第二章索引关键技术 图2 2 全文索引的索引器结构 全文索引是在全文检索基础上对全部关键词进行建立索引的操作。一般全文 索引的研究内容主要有：全文索引的模型、索引的创建效率、索引的空间效率、 索引的检索效率、索引的动态效率、索引的语义能力等等方面。新一代的全文检 索系统除了全文检索功能外，还具备语义匹配、文本挖掘这类对语义理解要求较 高的功能，而这些功能的完成也有赖于全文索引。 这里以l u c e n e 为例，分析它的全文索引文件的概念结构。l u c e n e 的全文索引 i n d e x 由若干段( s e g m e n t ) 组成，每一段由若干的文档( d o c u m e n t ) 组成，每一个 文档由若干的域( f i e l d ) 组成，每一个域由若干的项( t e r m ) 组成。项是最小的概 念单位，它直接代表了一个字符串以及其在文件中的位置、出现次数等信息。域 是一个关联的元组，由一个域名和一个域值组成，域名是一个字串，域值是一个 项，比如将“标题 和实际标题的项组成的域。文档是提取了某个文件中的所有 信息之后的结果，这些组成了段，或者称为一个子索引。子索引可以组合为索引， 也可以合并为一个新的包含了所有合并项内部元素的子索引【2 5 】【2 6 1 。我们可以清楚 的看出，l u c e n e 的索引结构在概念上即为传统的倒排索引结构。全文索引文件结 构如图2 3 所示。 9 电子科技大学硕士学位论文 图2 - 3 全文索引的文件结构 2 3 全文索引的组织方式 全文索引文件的组织方式包括正排表和倒排表例。 记录( p o s t i n g ) 是指一个单词在一个文本中所有出现位置的序列。包含的信息一 般有：文本i d 、词频、出现位置，表示为 。 2 3 1 正排表 正排表以文档i d 为关键字，表中记录项记录文档中每个字的位置信息，查 找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。正排表 结构如图2 1 所示。 1 0 一 一 一 ，一 第二章索引关键技术 图2 4 正排表结构 这种全文索引的组织方式在建立索引的时候结构比较简单，建立起来也比较 方便且易于维护，因为这种索引它就是基于文档建立的，若是有新的文档要加入， 就直接为该文档建立一个新的文档块，然后直接挂接在原来索引文件的后面。而 若是有文档需要删除的时候，则直接找到该文档号的文档对应的索引信息，将其 直接进行删除。但是在查询的时候，这个方法建立的索引需要对所有的文档进行 扫描以确保没有遗漏，这样就使得检索的时间大大地延长，而检索的效率就很会 低下，对正排表进行信息检索的时候，就等于是直接对源文件进行全文扫描，这 样不仅索引的建立一点也没有加快检索的速度，反而在建立索引时耗费了空间和 时间，因此建立正向索引的方法是不提倡的。由于正排表的工作原理非常的简单， 但是由于其检索效率太低，几乎没有什么实用价值，所以在实际应用中一般不用 此数据结构，只是作为一种对比参考。 2 3 2 倒排索引 倒排索引是从书目录索引中受到启发而派生出来的，是目前应用最为广泛的 全文索引模型之一，它们可以通过离线合并的方法快速地被创建，现在最通用的 全文检索的方法都是倒排序索引结构。当数据量很大的时候，这种倒排序索引结 构在查询时能有很好的性能p 4 1 。 一个倒排索引就是这样一种结构，将一个查询关键字，比如说一个词语，映 射到一个倒排表中，然后用来指出某个文档中含有这个关键字。 所谓倒排文件【3 6 】【3 7 1 ，是描述一个词项集合元素和一个文档集合元素对应关系 电子科技大学硕士学位论文 的数据结构，记 d o c s = d l ，d 2 ，d 3 ，d n ) ，t e r m s = t l ，t 2 ，t n 当我们以“文档 为出发点时，我们可以讲d i 中包含哪些t j ，或者某一个t j 在d i 文档中出现了多少次。而“倒排文件”直接给出的是一个t j 出现在哪些d i 中， 进而还可以有它在某一个d i 文档中出现在哪些位置，出现的频率。用p l ( t j ) 表 示t j 出现于其中的文档记录的集合，称为对应于t i 的倒排表( i n v e r t e dl i s t ) 。 对于大规模的全文检索系统，倒排文件是目前为止最高效的数据结构。作为 数据结构，倒排文件索引模型中，索引包括两部分：第一部分是由不同词项组成 的索引，称为词典( v o c a b u l a r y ) ，词典是文档包含的所有词的集合，它包含单词和 指向文档列表的指针；第二部分由每个词出现过的文档集合构成，称为记录文件 ( p o s t i n gf i l e ) ，每个词项的对应部分称为倒排表，亦称记录表( p o s t i n gl i s t ) ，词 典中每一个词包含了一个记录表，可以通过词表访问，文档列表中记录了： d o c i 词语出现的文档号，n 岫i 词语在d o c i 中出现的总次数， p o s l ， p o s 2 ，】词语在d o c i 文档中出现的具体位置，如图2 5 所示。大部分的全文 索引和检索系统均是采用这种倒排表的数据结构来建立索引的，倒排文件结构适 用于对大型文本集合建立索引。 w o r d l d o c l ：n u m l ： p o s l ! p o s 2 ： ) ， d o c 2 ：n u m 2 ： p o s l ：p o s 21 ) 。 w o r d 2 d o c l ! n u m l ! p o s l ：p o s 2 ：。 ) ， d o c 2 ：n u m 2 ： p o s l ! p o s 2 ： ) 。 w o r d n d o c l ：n u m l ： p o s l ：p o s 2 ： ) ， d o c 2 1n u m 2 ： p o s l ：p o s 2 ： ) 图2 - 5 倒排表模型结构 通过倒排索引，可以很快地得知一个单词在哪些文档的哪些位置出现。对于 英文文档而言，词表中要去除一些经常出现但是意义不大的词，例如：t h e ，a ，a n ，o f , i n ， 0 1 1 等介词或冠词，这些词语被称为停用词，另外要对单词进行抽取词干的处理， 例如：p r o d u c e ，p r o d u c e r ，p r o d u c i n g ，p r o d u c e s 这些词都被看成是p r o d u c e 。而对 于中文文档的处理要相对复杂一些，因为中文没有明显的分隔符，所以在建立中 文文档的倒排索引时要进行分词的处理。 1 2 第二章索引关键技术 倒排文件索引构建方法如下： 现设有8 篇文章，文章的编号分别为l ，2 ，3 ，4 ，5 ，6 ，7 ，8 。文章的内容如图2 - 6 所示。 文档号文档内容 1 k e e p e ri nt h et o w nw il1k e e pt h eol dt o w nf o r e r v e r 2t h eo l dn i g h tk e e p e rk e e p st h ek e e pi nt h et o w n 3 k e e pi nt h eb i go l dh o u s ei nt h eb i go l dg o w n 4t h eh o u s ei nt h et o w nh a dt h eb i go l dk e e p 5w h e r et h eo l dn i g h tk e e p e rn e v e rd i ds l e e p 6t h en i g h tk e e p e rk e e p st h ek e e pi nt h en i g h t 7a n dk e e p si nt h ed a r ka n ds l e e p si nt h e1 i g h t 8w h ok e e pt h en e wh o u s ei nt h ev i l l a g e ? ik n o w 图2 - 6 文档编号及其内容 对这8 篇文档创建倒排索引，通常我们需要如下处理措施 扎我们现在有的是文章内容，即一个字符串，我们先要找出字符串中的所有 单词，即分词。英文单词由于用空格分隔，比较好处理。而中文单词间是连在一 起的需要特殊的中文分词处理。 b 文章中的”i n ”，1 0 0 ”，t h e ”等单词是没有什么实际意义的，就像中文中的 “的”“是”等字通常也无具体含义，一般来说，冠词、介词、连词等都可以算作是无 用词汇，这些不代表概念的词可以过滤掉。 c 用户通常希望查“h e ”时能把含“h e ，“h e ”的文章也找出来，所以所有的单 词需要统一大小写。 d 用户通常希望查“l i v e ”时能把含“l i v e s ，“l i v e d ，“l i v i n g ”的文章也找出来， 所以需要把“l i v e s ”，“l i v e d ，“l i v i n g ”还原成”l i v e ”，而且这样一来，信息获取系 统所需要检索索引的词汇数量就减少了，这样也可以缩小索引空间的大小。 e 文章中的标点符号通常不表示某种概念，也可以过滤掉。 经过上面处理后，提取了出文章中的关键词，为建立倒排文档做准备。 文章1 的所有关键词为：【k e e p 】【t o w n w i l l o l d f o r e v e r 文章2 的所有关键词为：【o l d 】【n i 曲t 】 k e e p t o w n 】 文章3 的所有关键词为：【b i g o l d h o u s e g o w n 】 文章4 的所有关键词为： h o u s e t o w n h a d b i g o l d k e e p 】 文章5 的所有关键词为：【w h e r e r d g h t k e e p n e v e r s l e e p 】 文章6 的所有关键词为： k e e p d a r k s l e e p 1 i g h t 文章7 的所有关键词为：【k e e p d a r k s l e e p 1 i g h t 】 电子科技大学硕士学位论文 文章8 的所有关键词为：【w h o k e e p n e w h o u s e v i l l a g e i k n o w 】 2 、) 有了关键词以后，我们就可以建立倒排索引了。上面的对应关系是：“文章 号”对“文章中所有关键词”。倒排索引把这个关系倒过来，变成：“关键词”对“拥有 该关键词的所有文章号”。8 篇文档经过倒排后变成了：关键词【文章号】。 但是通常仅仅知道关键词在哪些文章中出现还很不够，我们还需要知道关键 词在文章中出现的次数和出现的位置，通常有两种位置：幻字符位置，即记录该词 是文章中第几个字符( 优点是关键词亮显时定位快) ；b ) 关键词位置，即记录该词 是文章中第几个关键词( 优点是节约索引空间、词组查询快) 。 加上“出现频率”和“出现位置 信息后，我们的索引结构就变为： 关键词文章号【出现频率】出现位置，如表2 一l 所示。 表2 - 1 倒排索引结构 关键词 文章号【出现频率】出现位置 k e e p1 【2 1 1 ，6 ；2 1 3 1 4 ，5 ，7 ；3 1 1 ；4 1 】1 0 ；5 1 】5 ；6 【3 】3 ，4 ，6 ；7 1 1 2 ；8 1 1 2 t o w n 1 【2 1 4 ，9 ；2 1 1 0 ；4 1 1 5 ； w i l l 1 【1 1 5 o l d 2 1 1 】2 ；4 1 1 9 f o r e v e r i 1 】1 0 l i g h t 7 【1 】1 0 n i g h t2 【1 】3 ；5 【1 4 ；6 【2 】2 ，9 g o w n3 1 1 1 h o u s e 3 1 1 6 ；8 1 1 5 b i g3 1 2 1 4 ，9 ；4 1 1 1 8 w h o 8 1 1 n e w 8 1 1 】 h a d 4 1 1 6 d a r k 7 1 1 5 i 8 1 1 】9 k n o w 8 1 1 】1 0 v i l l a g e8 1 1 1 8 s l e e p5 1 1 8 ；7 1 】7 w h e r e 5 1 1 1 4 第二章索引关键技术 当倒排索引建立完成后，为了加快速度，全过程需要在内存中完全。在小数 据量时，有足够的内存保证该创建过程可以一次完成。数据规模增大后，可以采 用分组索引的技术，然后再归并索引的策略。该策略是，建立索引的模块根据当 时运行的系统所在的计算机的内存大小，将索引分为k 组，使得每组运算所需内 存都小于系统能够提供的最大使用内存的大小。按照倒排索引的生成算法，生成k 组倒排索引。然后将这k 组倒排索引归并，即将相同索引词对应的数据合并到一 起，就得到了以索引词为主键的最终的倒排文件索引，即反向索引。 在倒排索引【4 8 】中，词汇表对空间的需求相对较小，它的增长率为o ( n p ) ，其 中为0 到1 之间的常