InfoMall数据检索服务的设计以及全文检索系统的初步实现.doc

《InfoMall数据检索服务的设计以及全文检索系统的初步实现.doc》由会员分享，可在线阅读，更多相关《InfoMall数据检索服务的设计以及全文检索系统的初步实现.doc（28页珍藏版）》请在沃文网上搜索。

1、摘要中国Web信息博物馆是北京大学网络实验室研究和开发的中国万维网（World Wide Web）历史信息的存储和展示系统。但现有系统提供的服务不能满足用户对宝贵的历史网页数据的信息需求，因而限制了它的广泛使用。本文试图从实际出发，探讨和尝试如何利用保存下来历史网页数据提供公共信息服务。本文通过对InfoMall网页信息博物馆的数据需求的分析，利用基于时间、空间、内容的网页数据三维模型，设计了InfoMall数据检索服务，并规约了服务原语，设计了系统组成。例如，利用我们提供的服务,用户可以查询“1997年2月到2005年2月期间内蒙古自治区范围内所有*域名下内容包含民主的网页文档的全文”。本文

2、设计和实现了InfoMall数据检索服务的系统组成中的主要模块全文索引系统。我们主要针对InfoMall数据的特点和数据检索服务的需求，在空间利用率和系统灵活性两个方面做了探讨和优化。关键词InfoMall，历史网页，信息检索，倒排文件，索引AbstractWeb InfoMall is a digital library to store web pages of Chinese World Wide Web periodically and exhibit them to people online, which is designed and developed by Computer

3、Network and Distributed Systems Laboratory of Peking University. However current available services are too limited to meet users information needs and prevent it from being widely used. That is a great waste of the valuable archaic web pages. In this article, we present our ideas of how to use thes

4、e archaic web pages to provide information service to public.In this article, we analyzed the users information needs and designed a powerful service called InfoMall Data Retrieval Service, using a three-dimensional model based on time, space and content. We specified the syntax of query and designe

5、d the component of the system. In addition, we designed and implement the full text retrieval system that is a key component of InfoMall Data Retrieval Service, which is designed to be both flexibility and spacial effective.KeywordsInfoMall, archaic web pages, information retrieval, inverted file, i

6、ndex目录论文评定i摘要ii关键词iiAbstractiiiKeywordsiii目录iv1引言11.1背景11.2相关工作21.3本文贡献22数据检索服务的设计32.1数据模型32.2服务52.3服务原语62.4数据传输协议82.5系统组成模块83全文检索系统设计和实现93.1系统设计目标93.2系统结构和处理流程113.3系统设计决策133.4重要的数据结构和算法143.4.1词典结构143.4.2倒排文件索引项143.4.3倒排文件索引构建算法153.5索引数据压缩163.5.1压缩编码163.5.2同步点问题193.5.3减小索引空间的进一步改进204总结和未来工作展望20参考文献2

7、1致谢23- iv -1 引言1.1 背景中国Web信息博物馆（InfoMall）16是在国家973和985项目支持下，北京大学网络实验室研究和开发的中国万维网（World Wide Web）历史信息的存储和展示系统。它以“天网”搜索引擎17为基础，存储其搜集来的网页（以中文网页为主）。目前，InfoMall维护2001年以来从中国万维网上搜集的近12亿篇网页（约20TeraByte），并且网页数量以每月1000万的速度增长（20TB和1000万，这两个数字准吗？）。存储历史网页可以做什么呢？文献1中认为，保存Web不仅是对人类精神财富的保护，还具有重要的史料价值。我们希望利用这些宝贵的数据，

8、结合海量索引，网页再现，海量信息检索，网页建模，海量信息分类，数据挖掘等信息技术，不仅从中提取和检索有用的信息，而且能挖掘出有意义的社会现象和其背后的规律，甚至为社会科学研究开辟一条新路。InfoMall目前提供三项简单的服务。通过浏览器界面，用户可以根据URL检索历史网页，浏览该URL的历史网页，并顺着超链接浏览和体验已经消失的过去的万维网。第二，提供人工整理的历史事件专题回放，集中展示媒体和社会舆论对某个重要历史事件的报道和剖析。另外，InfoMall还提供数据申请服务，任何研究机构根据一定的协议都可以申请免费使用InfoMall历史网页数据和搜索引擎用户查询日志数据18，然后通过硬拷贝的

9、方式得到数据。但这些简单的服务还远远不够。目前整理历史事件专题需要大量的人工工作，所以提供的专题数量有限，而且整理出来的专题受创建者个人偏好的影响，不一定是大多数用户所关心的。尽管我们尝试让用户自己定制和分享自己关心的专题19，但利用现有的服务，用户只能根据已有的对某些万维网站点URL的了解得到网页，而很难通过内容定位到包含特定网页，所以制作专题过程仍然需要用户大量的时间和精力。我们希望把现有服务整合起来，并通过统一的数据访问接口，提供更加丰富，更加自动和便利的数据服务。1.2 相关工作随着万维网的蓬勃发胀，人们越来越认识到保存万维网历史的重要性和紧迫性。在国外，Internet Archiv

10、e13保存了从1996年以来近400亿篇历史网页，并提供类似InfoMall的服务。Witten等人的著作“Managing Gigabytes: Compressing and Indexing Documents and Images”5对文档压缩方法，索引构建算法，索引压缩方法做了全面细致的比较和研究，是文本信息处理的权威著作。北京大学天网组的研究人员对于海量信息的存储、检索和服务做了大量深入细致的研究工作。黄连恩等设计实现了InfoMall历史网页存储系统，使得网页搜集器搜集的数据得以保存，并提供目前的服务。赵江华在文献12中对信息检索的基本问题做了介绍，对分布式检索系统设计与实现，尤

11、其是索引数据的组织方式做了全面的阐述。彭波在文献20中提出了一种混合索引技术和倒排文件分块组织方法，并对倒排文件缓存、搜索引擎检索效果评估方法等做了探讨研究。朱家稷在21中利用一种基于多维的Web分析模型对Web资源分布特性进行分析，得到很多有益的结论。本文的工作很多都是基于他们的研究工作基础之上的。1.3 本文贡献万维网在人们生活中扮演着越来越重要的角色，随着万维网信息量的不断膨胀，搜索引擎显现出它无可替代的应用价值和随之产生的商业契机。研究机构和商业公司都对Web信息检索的研究投入了大量的精力，但对于如何保存易失的以网页为载体的宝贵信息，如何利用这些信息提供公共信息服务却没有给予充分的重视

12、。本文试图从实际出发，对这一课题做了一些有益的探讨和尝试。本文第二部分在对InfoMall系统数据和应用前景细致分析的基础上，提出和定义了InfoMall数据检索服务，定义了服务原语，设计了服务的实现。本文的第三部分重点讨论了利用压缩技术减少全文索引的倒排文件索引的大小，为海量历史网页数据的检索服务提供现实可行的基础设施保障。2 数据检索服务的设计2.1 数据模型InfoMall历史网页数据不同于搜索引擎的数据。搜索引擎的索引数据是在一次集中的网页抓取动作中收集来的，时间跨度较小，可以认为，它是整个万维网在某个时间点的一个“快照”。对于网页链接进行分析以改进检索效果的技术都基于这种假设。实际上

13、在网页搜集期间可能有网页的生成、湮灭和变化，网页之间链接的生成、湮灭和变化，只是对于一般的分析来说，这种变化相对整个万维网结构的影响可以忽略不计。但InfoMall定期存储从万维网上抓取得网页，我们必须考虑相同网页（具有相同URL）在时间跨度上可以有不同的版本，而且这一特性正是这种数据的价值所在。文献21在研究万维网的资源分布特点时将其从空间、时间、内容三个维度来分析和考察。这一模型可以作为考察历史网页数据时的一种有效的模型，如图1所示。时间空间内容（日、月、年）（地区、主机、URL）（文档向量、特征向量、主题）图1对于每个维的属性在考察时可以进行分层，相应的可以有不同的考察粒度。“粒度是指数

14、据单元的细节程度或综合程度的级别。细节程度越高，粒度级别就越低21”。比如，在内容维，我们可以按照向量空间模型(vector space model)6将一篇文档内容视为一个在整个字典空间中的一个向量。也可以通过对文档内容的分析提取文档的“特征向量”来表示一篇文档。甚至只根据文档内容归属的类别来粗略的表示文档的内容。其他两个维度也可以类似的方法进行不同粒度的考察。另一方面，研究者通常将万维网抽象为一个有向图。有向图中以网页文档为顶点，以网页之间的相互链接关系为有向边。如图2所示为一个具有六个网页的万维网结构图。图2当我们引入时间维之后，万维网可以抽象为一个随着时间动态变化的有向图，这些“平面的

15、”有向图组合成为一个“立体的”图结构（当然它实际上也可以视为一个普通的有向图来研究）。图3为考察网页在三个不同时间点的情形得到的万维网历史结构图。时间图3t1t2t3在万维网历史结构图中，同一个网页过去版本和现在版本之间有一条边连接起来。从图中我们可以看出网页的产生、湮灭、变化，以及链接关系的产生、湮灭和变化。这种动态的万维网结构图不仅可以用来分析万维网结构特性，研究万维网的演变特点、万维网的资源分布特性，而且可以利用这些信息研究新的历史网页文档的检索算法，从海量的网页信息中有效的检索到相关网页文档。InfoMall存档的历史网页数据实际上完整的保留了这样一个复杂的图结构，我们面临的问题就是如

16、何建立和发掘这个图结构以提供高质量的数据检索服务，为进一步的数据挖掘提供基础设施。2.2 服务根据以上的数据模型和应用前景，结合对InfoMall申请使用数据需求的分析18，我们认为，InfoMall数据检索服务要提供以InfoMall历史网页文档为核心数据，以内容、空间、时间为查询纬度的，面向高层应用的客户服务器体系结构的数据检索服务。通常，一个现代信息检索系统不仅要对用户提供检索(Retrieval)功能，还要同时支持浏览(Browsing)。但InfoMall服务的对象是高层应用，而不是直接提供给最终用户，所以不提供用户界面（UI，User Interface）。高层应用利用得到的数据可

17、以进行各种研究和应用，例如提供高质量的信息检索，利用数据库技术进行数据挖掘等等。从内容维上讲，以网页文档为中心，指充分利用InfoMall珍贵的历史网页数据，提供以单篇文档为内容服务粒度，以词级布尔查询为最小查询粒度的数据服务。例如，用户可以查询“包含领袖、北大两个词的所有网页的网页全文”。除了网页文档以外，也考虑提供对查询日志的检索服务，但它的数据格式可以用传统的数据库技术提供服务。检索的返回结果可以有两种类型：网页原文或排序元数据。排序元数据指为了使用某种特定的排序算法对检索结果进行排序而需要得到的关于检索词和检索文档集的统计信息，且这些信息不能通过文档集的任何一个子集来得到。比如，为了支

18、持基于向量空间模型的文档排序算法，我们需要提供索引词词频（tf，term frequency），索引词文档频率（df，document frequency）；为了支持7提出的网页排序算法，我们需要提供PageRank值，词在文档中的位置信息（proximity）等。只通过单篇文档可以获得的特性不属于排序原数据。从时间维上讲，提供以某个时间段为查找范围的历史网页查询服务。但是这里的最小查询粒度受网页搜集系统搜集频率和存档频率的影响。例如，天网搜索引擎的搜集系统目前对中国万维网进行一轮全面的搜集需要大约20天的时间。所以一般地，时间粒度无法小于这个时间间隔。不过可以通过改造搜集系统，针对特定用户的

19、需求对某个空间纬度上万维网的特定区域进行高频率的搜集，以提供更小空间粒度的查询需求。从空间纬上讲，提供以URL或者物理位置为限定的历史网页查询服务。例如，用户可以查询“1997年以来北京市范围万维网上的所有网页”，或者“1997年1月到1998年1月域名下的所有网页”。2.3 服务原语检索服务的用户需要通过某种数据查询语句来描述信息需求。根据以上的数据模型和服务定义，我们参考SQL语言的查询语言部分，定义检索服务原语如表1中所示（使用Augmented BNF9语法）。 = “select” “from” “where” 1* “max” = “IR-metadata” / “Web-page

20、s” = = any legal URL according with RFC1738 syntax = / / = “content” “contains” 1* = any legal Chinese character string = “time” “between” and = any legal formatted string according with iso8601 = “location” “at” = / = “URL:” = “GEO:” = any legal code accord with GB2260 = any decimal number表1说明：的表示采

21、用国际标准ISO86017中定义的时间日期的表示格式。这种格式兼顾了可读性和机器处理的方便性。例如，2000年1月30日8点30分59秒可以表示为”2000-01-30 08:30:59”。为RFC173810规定的统一资源定位符。表示处理请求的服务器的URL。因为将来InfoMall数据检索服务系统可以实现为一个分布式系统，可以同时向多个服务器发出请求，所以请求中要指明由哪个服务器处理请求。多个服务节点直接也可以用类似的原语传递数据。URL中的协议部分表示数据传输所使用的协议，随着InfoMall数据检索服务的发展和改进，使用的数据传输协议可以变化。布尔查询只支持“与”操作，因为InfoMa

22、ll数据量如此庞大，提供“或”、“非”操作是不现实的，也没有应用需求。当然，用户可以在现有服务的基础上实现这些操作。指明要检索的数据类型，也就是检索结果的类型。“IR-metadata”表示要求返回符合条件的所有网页文档的排序元数据。“Web-pages”表示要求返回符合条件的所有网页文档原文。同样因为数据量的问题，当检索结果类型是网页全文时，结果的传输需要很长的传输时间。我们用表示结果所包含的最大条目个数。如果用户不指定，系统也要有一个默认的值。地区编码采用中国国家标准GB2260-8411规定的中国地区编码。这样可以借助标准化数据带来的好处为客户提供统一灵活的服务。例如，150000代表内

23、蒙古自治区，152700代表内蒙古自治区伊克昭盟，152701代表内蒙古自治区伊克昭盟东胜市。下面给出一个查询的例子。向一台服务器:1234查询“1997年2月到2005年2月期间内蒙古自治区范围内所有*域名下内容包含民主的网页文档的全文”，查询可以表示为”select Web-pages from :1234 where content contains 民主 time between 1997-02 to 2005-02 location at GEO: 150000 location at URL: *”2.4 数据传输协议用户通过网络发送符合上述语法的数据需求描述，服务器执行检索并通过

24、网络传送检索结果给用户。可以考虑使用ftp协议或者http协议传输数据。当然也可以定制一种专用的应用层协议来提供更简单、高效的服务。采用的协议要在查询的的URL中表现出来，以利于系统的扩展。2.5 系统组成模块综上所述，提供InfoMall数据检索服务的系统至少需要图4所示的一些基本模块和数据库支持。时间索引提供“时间维”的查询服务。目前InfoMall网页库的存储实际就是按照时间维度进行组织的，所以实现中实际不需要显式地按照时间对网页文档进行索引。网页URL索引结合地区编码和IP地址对应表用来提供“空间维”的查询服务。通过“地区编码和IP地址对应表”我们可以得到一个地区内的IP地址范围，再通

25、过反向地址解析最终可以得到属于某个地区的所有URL。URL索引使得我们可以通过一个URL得到所有时间维和内容维上的网页。目前InfoMall系统已经实现了网页的URL索引。全文索引提供“内容维”的查询服务，可以通过一个使用倒排文件的全文索引数据库来实现。这是InfoMall数据检索服务在实现时的关键模块。本文的其余部分主要讨论它的设计和初步实现。3 全文检索系统设计和实现3.1 系统设计目标根据前面所述的服务定义，这里所说的InfoMall网页文档检索服务目的不同于传统意义上的文本信息检索。它有如下特点：l 数据量特别大。InfoMall目前保存2001年以来12亿多篇网页（总计约20Tera

26、Byte），并且以平均每月1000万网页的速度扩大规模。而一般的搜索引擎需要索引的数据量较小，且规模相对稳定。如百度14声称其总量为6亿网页。l 不以排序效果为检索性能的评测指标。即返回的文档ID集合或者文档集合只是一个“集合”而不是“序列”。但是检索结果可以返回足够的排序元数据信息以满足可能的进一步对文档进行排序的需要。所以我们在设计时关注的不是检索系统的响应速度和检索效果的优化，而重点考虑InfoMall数据的异构性对索引系统的可扩展性提出的要求，以及超大数据量下如何减小保存词级全文索引数据和检索元数据所需的空间。InfoMall数据目前保存Web上以HTML语言写成的静态网页为主，但是随

27、着Web的不断发展，目前其数据类型已经远不仅仅是静态网页数据，人们越来越倾向于通过Web发布各种格式的数据和信息。为了让搜索引擎用户能够检索到这些信息，搜索引擎必须处理各式各样的不同类型的数据。例如google15，百度14等搜索引擎目前都提供对pdf，doc，甚至email的检索服务。InfoMall索引系统必须能够支持这种数据的异构性，并提供统一的服务接口。一个信息检索系统的设计必须考虑系统运行性能（system performance）和查询性能（retrieval performance）。我们把前者叫做效率（efficiency），后者叫做效果(effectiveness)。“效率”

28、的评价几乎存在于所有软件系统之中，任何算法和软件系统都需要从时间代价和空间代价上考虑取舍，比如系统响应时间、内存需求和磁盘空间需求。“效果”指检索返回结果满足用户查询需求的程度。检索效果的评测是信息检索领域的一个研究重点，一个典型的测试平台包括测试文档集(test collection)，相关度评测(relevance judgments)和各种不同的评测指标(measures)。常用的指标有Precision-Recall Curve, MAP, PN等6。对于一个联机运行的信息检索系统，最重要的效率指标就是系统的查询响应时间和系统的查询吞吐量。InfoMall数据检索系统希望满足用户对大规

29、模数据的检索需求，由于现有数据已经非常庞大，并且数据随着时间的不断增长，我们的设计目标不是提供快速的查询响应（例如，搜索引擎的查询响应时间一般在秒以内），而是对海量数据的有效索引和稳定的查询响应。系统返回结果针对是对布尔查询的，只是一个集合，并没有按照相关度进行排序，所以不能使用常用的针对有序查询结果的“效果”评价方法。但上层应用仍可以使用其返回的文档和排序元数据进行相关度排序。3.2 系统结构和处理流程一个中文全文索引和检索系统的一般结构如下：在文档预处理阶段，系统从文档库中提取出文档，给每个文档赋予一个全局唯一的标识（DocID）。InfoMall网页文档是带有时间特征的，而且其存储本身按

30、照抓取和存档时间进行组织。文档ID本身要包含时间信息，以利于检索时候的处理和优化。InfoMall的数据包括搜索引擎的搜集器搜集的各种网页、纯文本、图片等不同类型的数据，且中文文档又可能有GB2312，Big5等不同的字符编码，所以文档预处理过程需要做很多琐碎而细致的工作。对于HTML文件，还需要对整个文档进行解析，去除HTML标签，提取标签和正文中有效的文本信息。本质上说，索引是一种用来从索引词（term）找到对应文档的方法。索引的实现有不同的技术：倒排文件（inverted file, or posting file），签名文件（signature files）和位图（bitmaps）。文

31、献5证明，在一般的应用中，不论在索引空间还是在查询处理速度上，倒排索引都提供比另两者更佳的性能。目前倒排文件也是使用最为广泛的索引技术。索引过程中一个重要的步骤是索引词的产生。英文文本中单词直接用空白分隔，词的提取比较简单。而中文文档中词之间没有分隔符号，必须借助自然语言处理（NLP，Natural Language Processing）技术进行中文分词。分词的效果直接影响着中文文本检索系统的检索效果。在“天网”搜索引擎系统上的实践表明，北京大学计算语言所研制的中文切词软件具有较好的分词效果，我们决定采用它。中文分词之后需要确定索引词并计算他们在文档中出现的位置。我们决定使用分词后产生的词作

32、为索引词直接进行词级索引，而没有采用检索效果更佳的词索引结合二元组（bi-gram）索引，是出于空间优先的设计决策，因为那样会使词典和倒排文件大小急剧的膨胀。文献20中提出一种混合索引技术，是在保留混合索引提高检索效果的优点的同时兼顾空间效率的一种较好的选择。索引系统实现中最大的挑战是倒排文件的建立过程。顺序处理每篇文档，我们可以记录它包含的每个词的出现位置，这样对每篇文档中出现的每个词可以产生一个三元组，其中Positions代表索引词TermID在DocID中出现的位置。由于是按照文档顺序处理的，所以这些三元组的集合最初是按照DocID排列的，要通过倒排过程，把TermID相同的所有Doc

33、ID聚集到一起。索引建立的方法有很多，有基于链表的，基于排序的，基于词典分隔的，基于文本分隔的。文献5通过实验和算法复杂度比较了各种方法，证明基于排序的多路归并（Sorted-based multiway merge）结合索引数据的压缩是一种较好的方法。3.3 系统设计决策InfoMall全文检索系统的类图如下。在系统体系结构设计中，我们采用面向对象的思想设计，主要考虑了系统的灵活性和可扩展性。接口DocProvider代表文档源，提供可以用来进行分词处理的普通文本文档。通过对DocProvider接口的不同实现，可以方便的把整个索引系统用来为不同类型的文档源建立索引。例如，系统除了可以为In

34、foMall历史网页库建立全文索引，还可以索引文件系统中的文档。类TermSegmenter和DocStringParser负责对文本文档进行分词，并记录索引词在文档中的出现位置。类IndexBuilder是核心类，它实现了索引构建算法。EnDecodeStrategy类采用了“策略”设计模式4，可以方便地替换不同的编码算法，来取得较好压缩效果。各种编码算法都是接口EnDecoder的一个实现。为了支持InfoMall数据的异构性，我们设计了一种灵活的文档表示结构，以支持多种类型的文档且对文档提供丰富的描述。一个文档（类Document）是一个域（类Field）的集合，且其域的组成可以在文档处

35、理和索引的过程中动态变化。每个域是一个名字和值组成的二元组。这一模型可以灵活的定义结构化的或者非结构化的文档。例如，一个典型的HTML网页文档，可以包含ID域，正文域，URL域，抓取时间域等。当然，有的域需要建立索引，有的域则不需要，这可以通过域的属性来指定。文本文件，HTML文件，Microsoft Excel格式的文件，甚至数据库表格文件都可以处理为这种表示结构，并通过索引系统建立索引。3.4 重要的数据结构和算法3.4.1 词典结构词典用来记录每个索引词的ID，该索引词在倒排文件中表项的位置，以及表项的长度。在索引构建和查询时都需要频繁访问词典，所以它要保存在内存中。词典采用散列表实现，

36、每个索引词表示为如下的一个四元组：Term为索引词字符串，TermID为索引词的标识ID，EntryPosition为倒排文件中TermID对应的第一个索引项的位置，EntryLength为其所有索引项所占字节长度。3.4.2 倒排文件索引项每个索引词对于倒排文件中的一系列连续存放的索引项，每个索引项可以表示为：DocID为文档的唯一标识；Freq为该索引词在该文档中出现的频率，它的存在是因为解码时的同步问题，后面小节对此有讨论；pos1, , pos freq表示该索引词在该文档中各次出现的位置。索引建立过程中，对一个索引词的所有表项需要经过游程编码并压缩后存储起来。3.4.3 倒排文件索引

37、构建算法倒排文件索引的建立过程使用了基于排序的多路归并方法。基本步骤包括：（1）从文档源取得文档。（2）对文档进行分词得到三元组。（3）查看每个文档三元组，把新出现的索引词合并到词典中，并把Term转换为TermID，得到。（4）当三元组的数量恰好填满内存时，对整个三元组集合执行快速排序，使之以TermID递增（TermID相同时以DocID递增）排列。（5）使用“游程编码”处理递增排序的三元组，也就是把递增整数序列变换为差分序列（原来相邻整数之间的增量序列），然后使用一定的编码算法对数据进行编码以压缩排序结果，输出到一个临时的顺串文件（run file）。（6）当所有文档处理完毕后，对所有顺

38、串文件执行多路归并，结果输出为最终索引文件。（7）将最终得到的词典存入文件。其中（6）中的多路归并过程使用传统的最小值堆的方法实现，但要进行精细的编码解码步骤。算法的伪代码如表2所示。MinHeap heap;/ initialize minimum value heapfor each (run R)HeapValueType heapValue;R.getNextEntry(heapValue);heap.add(heapValue);HeapValueType preEntry;Initialize preEntry as an invalidate value;IndexEntries

39、 entries;while (not heap.empty()HeapValueType heapValue;Heap.pop(heapValue);If (heapValue.TermID != preEntry.TermID)Write new terms index entry into inverted file;Update position and entry length of heapValue.TermID in Lexicon;Entries.clear();Entries.add(heapValue);Update preEntry;If (RheapValue.run

40、ID.getNextEntry(heapValue) / true if not emptyDecode heapValue according to preEntry;heap.add(heapValue);表23.5 索引数据压缩3.5.1 压缩编码倒排文件的索引数据要经过压缩来减小空间。在基于排序的多路归并索引构建算法中，压缩又被赋予了另一层意义。由于构建索引过程中产生的中间结果（顺串文件）数据量特别大，不可能全部存放在内存中，必须把中间结果临时存放到外存，然后在需要时从外存读入内存进行处理，产生最终的索引。在这个过程中，中间结果是先压缩，后存入外存的。相应的，从外存读入中间结果之后，需

41、要先解压缩，然后才能做进一步的处理。文献5研究证明，压缩和解压缩步骤虽然增加了索引构建过程的CPU时间，但由此也减小了数据的磁盘IO时间，后者的受益远远大于前者的性能损失。数据压缩方法有两种基本思想。第一种，根据数据中每种符号出现的概率，赋予他们不同的表示，对于出现频率高的符号用较少的比特（bit）来表示，像莫尔斯（Morse code）电码一样，基于这一思想的方法统称为统计方法（statistical methods）。估计符号出现概率的过程叫做建模（modeling），通常这个过程和符号出现的上下文相关。然后根据概率把符号转换成比特流（bitstream），这个过程叫译码（coding）。

42、效果最好和最常用的译码方法有著名的哈夫曼编码（Huffman coding）和算术编码（arithmetic coding）。根据香农的信息论，先验概率为Prs的符号s的理想编码的长度为个二进制位。第二种，把词或文本段用指向一个字典表项的指针来代替，基于这一思想的方法统称为字典方法（dictionary methods）。常用的字典方法都是Ziv-Lempel编码的变种。文献5对编码压缩算法进行了详尽的分类和比较。对于每一个顺串文件需要以TermID为序存储了大量结构，当TermID相同时，以DocID为序递增。在此结构内部，位置信息pos也按递增排列。压缩时，第一步要进行游程编码，也就是把递

43、增整数序列变换为差分序列（原来相邻整数之间的增量序列）。这样做没有丢失任何信息，因为我们的处理都需要从整数序列的第一个开始进行的，只需迭代相加就可以恢复原始序列。但这么做只是把大整数换成了小整数，本身并不能减小数据存储空间。第二步，用某种编码方法对小整数进行编码，以实现压缩。随后对所有顺串文件归并，得到最终的倒排文件索引。最终倒排文件中每一项的编码方法和产生顺串文件时的编码方法是一样的，只是少了TermID。可以采用下面几种编码方法。Unary Code把整数x=1编码为x-1位1后跟1位0，一个整数x需要占用x个二进制位。例如3的编码为110。它假设下一个出现的符号是x的概率Prx=2-x。

44、Gama Code把整数x=1编码为的Unary Code表示，后接位的二进制表示。Unary Code部分实际表示其余部分共要用多少位来编码x，所以x一共需要用位来编码。例如3的编码为101。它假设下一个出现的符号是x的概率。Delta Code把整数x=1编码为的Gama Code表示，后接位的二进制表示。同样的，Gama Code部分实际表示其余部分共要用多少位来编码x，由于的Gama Code编码需要位，所以x一共需要用位来编码。例如3的编码为1001。Delta Code假设下一个出现的符号是x的概率为。用以上编码方法假设了某种概率，可以对DocID的增量、文档内位置增量pos进行编

45、码。但是我们可以通过建模更加精确的估计出DocID增量是x的概率Prx。假设一个文档集中出现的对总数为f。将它除以不同索引词的总数n，再除以文档总数N，得到p = f/(N*n)。它表示任何随机选取的文档包含任何随机选取的索引词的概率。一个索引词在文档中出现一次就需要在倒排文件索引中记录一个DocID增量值。假设倒排文档中出现的f个对是从文档集所有可能的N*n个对中随机选取的，这个过程可以视为一个贝努利(Bernoulli)过程。有了这个假设，DocID增量为x的概率可以表示为文档中连续x-1个非特定索引词后接着出现一次某个特定索引词的概率，即，说明x符合几何分布。这里隐含的条件是对的出现是独立同分布（贝奴利分布）的。由于DocID增量符合上面的几何分布，我们可以用Golomb Co