（计算机软件与理论专业论文）基于互关联后继树压缩模型的研究.pdf

摘要 摘要 随着信息时代的到来，人们需要处理的数据飞速增长，大量的数据要进行 存储与检索。数据不但占用海量的存储空问，而且对其检索也需花费大量的时 间与空间。目前针对文本文件压缩和检索的研究己经受到大家的关注。 文本压缩的主要作用是方便海量数据的存储和传输，所以压缩时间和压缩空 间效率( 包括压缩过程中的过渡空间与最终压缩空间) 是文本压缩研究领域的 关注点。同时，如何在全文索引中引入压缩也是当前的研究热潮。基丁以卜考 虑，本文研究了文本压缩模型，并且将其与全文检索结合起来。 本文讨论并比较了现有的流行的文本压缩模型和检索模型，介绍了一种新型 的全文数据库的数据模型互关联后继树( 文中简称为i r s t ) ，并用此模型来 进行文本压缩。互关联后继树是一种集存储、检索、数据挖掘和文本压缩的统 一模型，具有广泛的应用前景，目前已得到国家自然科学基金项目的支持。为 了实现有效的压缩，本文针对各种不同的需要给出了不同的数据结构。因为互 关联后继树具有快速查询、快速原文生成、小膨胀比等优点，基于互关联后继 树的文本压缩具有较好的压缩率和雎缩时间效率。本文还通过改进互关联后继 树的结构，将互关联后继树的全文检索与压缩功能合二为一，进一步减少互关 联后继树索引占用的空间，适用于当今呈指数增长的海量非结构化信息的存储 和检索。 实验数据表明本文的压缩算法可以与l z w 算法相媲美；在不影响检索速度的 前提下，索引压缩能有效地减少膨胀比。本文在讨论各种算法时，配有具体的 算法分析和实验结果分析。 关键词：文本压缩，全文检索，互关联后继树，i r s t ，部分解压 中图法分类号：t p 3 1 l i i i a b s t r a c t a b s t r a c t w i t ht h ea d v e n to ft h ei n f o r m a t i o na g e ，p e o p l en e e dt od e a lw i t ht h er a p i d f o w t hi nd a t af o rs t o r a g ea n dr e t r i e v a l m a s s i v ed a t ao c c u p yt o om u c hs t o r a g es p a c e ， a n di tn e e d sal o to ft i m ea n ds p a c et os e a r c h c u r r e n t l y , t h er e s e a r c h so ft e x t c o m p r e s s i o na n dr e t r i e v a la t t r a c tp e o p l e sa t t e n t i o n t e x tc o m p r e s s i o ni st of a c i l i t a t et h em a s s i v ed a t as t o r a g ea n dt r a n s m i s s i o n ，s o h o wt or e d u c ec o m p r e s s e dt i m em a dc o m p r e s s i o ns p a c ei st h ef o c u so ft e x t c o m p r e s s i o nf i e l d m e a n w h i l e ，h o wt or e d u c et h ei n d e xs p a c ei st h eh o tt o p i ci n f u l l t e x tr e t r i e v a lf i e l d b a s e do nt h ea b o v ec o n s i d e r a t i o n s ，t h i sp a p e rs t u d y st h et e x t c o m p r e s s i o nm o d e l s a n dc o m b i n e s t h e mw i m f u l l t e x tr e t r i e v a lm o d e l t h i sp a p e rd i s c u s s e sa n dc o m p a r e ss e v e r a lp o p u l a rc o m p r e s s i o nm o d e l sa n d f u l l t e x tr e t r i e v a l m o d e l s ，a n di n e d u c e s an e wf u l l t e x tr e t r i e v a lm o d e l i n t e r - r e l e v a n ts u c c e s s i v et r e e ( t h ep a p e ra l s or e f e r si ta si r s t ) u s e df o rt e x t c o m p r e s s i o n i r s ti s au n i f i e dm o d e lt h a ti n t e r g r a t e s s t o r a g e ，t e x tr e t r i e v a l ，d a t a m i n i n ga n dt e x tc o m p r e s s i o n i no r d e rt oa c h i e v ee f f e c t i v ec o m p r e s s i o n ，t h i sp a p e r p r o v i d e sd i f f e r e n td a t as t r u c t u r e sf o rd i f f e r e n tn e e d s b e c a u s eo fi r s t sr a p i di n q u i r y , r a p i do r i g i n a lt e x tc r e a t i o na n ds m a l le x p a n s i o nr a t e ，t e x tc o m p r e s s i o nm e t h o d sb a s e d o ni r s th a v e g o o dc o m p r e s s i o n r a t ea n de f f i c i e n c i a l c o m p r e s s i o nt i m e b y i m p r o v i n gt h es t r u c t u r e ，i r s ti n t e r g r a t e s t h ef u l l - t e x tr e t r i e v a lf u n c t i o na n d c o m p r e s s i o nf t m c t i o n ，r e d u c i n gt h es p a c eo ff u l l t e x ti n d e x e x p e r i m e n t a l d a t a ss h o wt h a tt h ei r s tc o m p r e s s i o n a l g o r i t h m sc a n b e c o m p a r a b l e t ol z wa l g o r i t h m w i t h o u t a f f e c t i n gt h es p e e do fr e t r i e v a l ，i n d e x c o m p r e s s i o nc a ne f f e c t i v e l yr e d u c et h es p a c eo fi n d e x t h i sp a p e ra n a l y s t st h e s e v a r i o u sa l g o r i t h m si nb o t ht h e o r ya n de x p e r i m e n t a lr e s u l t s k e yw o r d s ：t e x tc o m p r e s s i o n ，f u l l t e x tr e t r i e v a l ，i n t e r r e l e v a n ts u c c e s s i v et r e e s ， i r s t ，p a r t l yd e c o m p r e s s i o n i v 论文独创性声明 本论文是我个人在导f j i n 旨导下进行的研究工作及取得的研究成果。论文中除 了特另, c l d h 以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名 论文使用授权声明 日期：2 d ：8 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 作者签名：颦导师签名牲日期：础 第l 章绪论 1 1 数据压缩 1 1 1 概述 第1 章绪论 当今，信息化不断普及，数字化在人们生活中有着不可或缺的作用，但是 数字化或者信息化环节需要花费大量成本。如何有效存储这些不断扩展的信息， 并且迅速地从这些信息中找出人们感兴趣的知识是一个需要考虑的问题。信息 的传输和存储受到严峻的挑战。 如何才能充分发挥出信息化的优点而又降低成本? 我们的答案就是压 缩。大多数信息的表达都存在着一定程度的冗余，通过采用某种模型和编码方 法，可以降低这种冗余度。也就是说，用尽可能少的比特数来表示信源信息， 并且能够将其还原出来，还原后的信息能够被人们接受。这样一来，便可以减 少空间，降低存储和传输的要求。因此压缩可以使数字化的成本降低，应用更 加容易。 经过了长期的、出色的研究工作，数据压缩技术取得了丰硕的理论成果。 随着半导体器件的迅猛发展，信息处理能力不断提高，使得这些理论成果能得 以实现并广泛应用到各种产品中。 文本压缩( t e x tc o m p r e s s i o n ) 是数据压缩( d a t ac o m p r e s s i o n ) 的一个重要组 成部分，属于无损压缩( 1 0 s s l e s sc o m p r e s s i o n ) 。它的目标是通过对数据施加某种 操作或变换使之长度变短的同时，还必须保证原始数据能够从压缩产生的压缩 码中得以精确的还原。文本压缩对数据压缩技术的理论及应用技术的发展起到 了很大的推进作用，其中一些技术在今天得到了广泛的应用。 1 1 2 发展压缩技术的必要性 尽管象光纤这样的宽带传输媒质和光盘、磁盘等大容量存储媒体都广泛普 及，但是需要传输和存储的数据却比它们所能提供的容量增长得更快。解决方 复旦大学硕士学位论文 第1 章绪论 法之一就是数据压缩。因此即使在硬件存储器的容量越来越大的情况下，压缩 技术仍然是很重要的i lj 。 在计算机的处理能力还不十分强大时，利用软件方法做数据压缩实际上是 牺牲处理器的运算时间来节省外部存储空间，人们只有在数据备份和文件传输 时才考虑数据压缩。现在，处理器的性能得到了飞速的提高，处理器的速度一 般都比输入输出设备的速度高很多，这样，采用数据压缩技术可以降低i o 器件 的存储频率【2 1 ，因此改善系统性能同时又使外部存储器件需求最小。另外，随着 网络化的发展，网络正在走进千家万户。越来越多的网上图书馆和网上资料库 出现了，通过网络传输的电子文档也越来越多了。随着网络用户的增多，网络 通信线路变得越来越拥挤，成了网络通信速度的瓶颈。而通过使用数据压缩技 术，可以加大信道容量的利用率，减少对带宽资源的占用。 1 2 全文检索 国际上文本信息检索的发展始于2 0 世纪5 0 年代，最早出现在美国p i t s b u r g h 大学1 9 5 9 年建立的法律情报检索中。中文文本信息检索最早见于7 4 8 工程 中的汉字情报检索。 信息大致可分为两类：结构化数据和非结构化数据。结构化数据指的是诸如 企业财务帐目和生产数据、学生的分数数据等等；非结构化数据则是一些文本 数据、图象声音等多媒体数据等等。据统计，非结构化数据占有整个信息量的 8 0 以上【3 1 。如何快速检索出用户感兴趣的内容是大家关注的重点。全文检索应 运而生。 全文检索包含两部分：信息的存储与信息的检索。以各类数据诸如文字、声 音、图象等为处理对象，提供按照数据资料的内容而不是外在特征来实现信息 检索手段。它能提供快捷的数据管理工具和强大的数据查询手段。通过快捷的 数据管理工具，能帮助人们进行大量文档资料的整理和管理工作；强大的数据 查询手段，使人们能快速方便地查到他们想要的任何信息。将全文检索和压缩 结合，可以更加有效地存储信息，而不影响其检索速度。 文件检索技术一直是信息检索领域的重要研究课题。相比传统的标引检索， 全文检索技术提供了全新的、强大的检索功能，是发现信息、分析和过滤信息、 信息代理、信息安全控制等主要应用技术的基础。以全文检索为核心技术的搜 复旦大学硕士学位论文 2 第1 章绪论 索引擎已经成为网络时代的主流技术之一。 1 3 本文的工作与主要创新点 信息随着计算机和网络的发展受到广泛重视。一方面，信息量不断增大，为 存储和传输带来了压力；另方面，信息量的急速膨胀使得人们从中提取出感 兴趣的知识越来越困难，因此数据的压缩和检索成为一种必需。本文旨在提出 有效的文本压缩方法，并且在信息检索中引入压缩，提高索引的空间效率。 本文主要的创新点如下综述： ( 1 ) 提出一种新型的集存储和检索于一身的全文数据库模型互关联后 继树，并用此模型实现文本压缩功能，充分利用了互关联后继树检索 迅速、膨胀比小等优点。 ( 2 ) 根据互关联后继树的压缩模型与索引模型的一致性，将互关联后继树 压缩与互关联后继树全文检索合二为一，在不影响检索速度的前提下 减小全文索引的膨胀比。 ( 3 ) 讨论基于互关联后继树的压缩模型的部分解压方法，对本文提出的三 种压缩模型给出适合的部分解压方案。 本文讨论的中心主题是互关联后继树压缩模型的建立，其主线是互关联后继 树压缩模型怎么提高文本压缩的时间效率和空间效率，互关联后继树的文本压 缩与全文检索如何结合。根据实际情况给出不同的压缩模型和数据结构，以满 足不同的需求。在讨论各种算法时，配有具体的算法分析和实验结果分析。 本文内容安排如下： 第一章绪论，阐述了压缩和信息检索的重要性以及在现代化信息建设进程中 的重要作用。 第二章介绍国内外研究现状，讨论当前比较流行的文本压缩模型和信息检索 模型以及其自身性能的优缺点。其次，还介绍了互关联后继树检索模型的概念 和特点，证明其作为全文检索模型的有效性和高效性。 第三章和第四章扩展创毅点( 1 ) ，研究基于互关联后继树的静态词典压缩模 型和自适应词典压缩模型，从理论上和实验结果上都证明了基于后继树的文本 压缩模型具有较好的压缩率。 第五章在创新点( 2 ) 的基础上研究后继树全文检索与文本压缩的结合，减 复旦大学硕士学位论文 3 第1 章绪论 少索引膨胀比以进一步推广后继树索引模型的应用。试验结果证明后继树压缩 索引有效地减少了膨胀比，并且检索速度快于倒排表。 第六章在前三章的基础上，探讨了创新点( 3 ) ，研究了互关联后继树三种压 缩模型在部分解压方面的应用。 第七章总结本文的内容，并且提出互关联后继树压缩模型的拓展。 复旦大学硕士学位论文4 第2 章国内外研究现状 第2 章国内外研究现状 在第一章里，简单介绍了发展数据压缩和文本检索技术的必要性。本章的知 识介绍分为数据压缩、全文检索和互关联后继树三部分：( 1 ) 数据压缩部分先 介绍压缩技术的基本概念；然后阐述文本压缩的常用技术和几种主要的压缩模 型：h u f f m a n 编码、算术编码以及l z 族编码；最后简单介绍文本压缩技术的几 个典型的应用和评判标准。( 2 ) 全文检索部分给出了全文检索模型的分类，并 且介绍主要的索引模型：倒排表模型、p a t 树和p a t 数组模型、署名文件模型； 最后简单讨论了全文检索技术的应用。( 3 ) 最后一部分介绍互关联后继树的概 念和特点，为后面章节做知识铺垫。 2 。1 数据压缩 压缩包含两部分：模型和编码。压缩中，用于处理输入信息，并且计算符号 的出现频率的模块称为模型；根据计算出的频率，决定输出哪个或者哪些代码 的模块，称为编码。 不同的模型使用不同的方法计算字符的出现概率，由此概率可以得出字符的 熵；然后使用不同的编码方法，尽量接近我们期望得到的熵值。所以，压缩效 果一方面取决于模型能否准确地得到字符概率，另一方面也取决于编码方法能 否准确地用期望的位数输出字符代码。模型和编码两个模块具有相互独立性。 举例来说，一个使用h u f f m a n 编码方法的程序，完全可以采用静态或者自适应 的模型来统计字符在信息中出现的概率。 通过模型可以确定对某一个符号该用多少位二进制数进行编码。但问题是， 如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号， 并且使解码程序可以方便地分离每个字符的编码部分。编码也分为变长编码和 定长编码。定长编码是指词典中的每个编码的长度都是一样的，不会随着压缩 的深入而变化。变长编码则是指词典中的编码长度会随着压缩的深入或者词语 的出现频率而变化。 复旦大学硕士学位论文 5 第2 章国内外研究现状 2 1 1 文本压缩技术的分类 无损压缩和有损压缩 ( 一) 无损压缩 无损压缩又称为可逆编码。无损压缩的信源信息被全部保存，不会丢失， 所以可以保证被压缩的数据能够从压缩码中得到精确的还原。磁盘文件的压缩 就是无损压缩的一个常见例子。无损压缩适用于一切数据对象，当然不同的信 源达到的压缩性能可能有所不同。通常说的“文本压缩”都是无损压缩，本文 也只限于讨论无损压缩。 ( 二) 有损压缩 有损压缩也称为不可逆编码。由于有损压缩的信源信息不能被全部保存， 因此不保证被压缩的数据得到精确的还原。即在不影响人对原始资料代表的信 息造成误解的前提下，还原后的数据较之压缩前存在数据丢失。有损压缩往往 分为两个阶段，即首先对输入数据施行某种变换以便产生平滑的输出数据，然 后进行无损压缩。有损压缩允许通过一定的精度损失来换取较大的压缩比，适 用于语音、图形图像等数字化模拟信号，是各种多媒体应用的关键技术。 统计编码方法和词典编码方法 文本压缩属于无损压缩领域，一般把传统的文本压缩技术分为两大类：统 计编码方法和词典编码方法。 ( 一) 统计编码方法 统计方法，也称面向符号的方法或符号方法( s y m b o l - w i s em e t h o d ) ，是利用 信源信息的统计特性，来降低信息的冗余度。这种方法依据信源符号的概率分 布实现对符号的编码，基本原则是用较短的码字编码高频符号，用较长的码字 编码低频符号，使得平均码长最短。显然，统计频率是统计编码的重要步骤， 变长码是统计编码的重要特征。 经典的统计编码方法有许多种。s h a n n o n 4 1 与f a n o 在大致相同的时间研究出 了s h a n n o n - f a n o 编码方法。1 9 5 2 年，h u f f m a n 发明了著名的h u f f m a n 编码【5 l 。 后者避免了前者可能为高频符号分配长码字的缺点，问世不久即流行至今。 s h a n n o n l 4 表述了今天称作算术编码( a r i t h m e t i cc o d i n g ) 的编码思想。但是，直 到八十年代，现代算术编码思想才被明确下来。算术编码不仅比h u f f m a m 编码 的编码效率更高，而且平均码长可以任意逼近信源熵，成为理论上的最佳编码 复旦大学硕士学位论文 6 第2 章国内外研究现状 方法。 ( 二) 词典编码方法 词典方法是通过构造一个“词典”，存放提炼自当前位置之前已经编码了的 信源数据的“词条”。这样新输入的数据就可以通过在词典中搜索匹配的词条来 进行编码。现代词典编码方法以l z 7 7 和l z 7 9 ( 或统称l z ) 为代表，它们起源 于l e m p e l 和z i v 于1 9 7 7 和1 9 7 8 年发表的两篇经典论文【6 7 】。算法的名字来源于 提出算法的两位以色列研究人员j a c o bz i v 和a b r a h a ml e m p e l 的姓名的首字母。 这两族算法都得到了广泛的应用。 词典方法自从被提出来以后，由于它具有一系列独特的优点，所以得到广 泛的关注，并且引发了一波研究l z 算法的热潮。其间，不少l z 算法的变种算 法被提了出来，它 f 分别从不同的方面对算法作了改进。其中的一些算法也得 到了广泛的应用，例如l z w 算法。 2 1 2 几种主要的压缩模型 n u f f m a n 编码 h u f f m a n 编码完全依据字符的出现概率来构造平均长度最短的码字。 h u f f m a n 编码的码字遵循“前缀编码”的原则，即较短的编码决不能是较长编码 的前缀。一般而言，h u f f m a n 编码都是用二叉树来生成编码。可以证明h u f f m a n 编码是一种最佳码【s 】但是并不表示它是最优的编码。h u f f m a n 编码只能用近似 的整数位来表示单个符号，而不能使用理想的小数位，因此无法达到最理想的 编码效果。 上节介绍，模型和编码是相互独立的，因此h u f f m a n 编码可以使用静态统计 模型或者自适应统计模型。如果使用静态统计模型，编码前统计要编码的信息 中所有字符的出现频率，然后根据统计出的信息建立二叉编码树，进行编码。 静态模型简单易行，但是有其缺点：首先，对数据量较大的信息，静态统计要 消耗大量的时间；其次，必须保存统计出的结果以便解码时构造相同的编码树， 或者直接保存编码树本身；再次，事实上，即使不将编码树计算在内，对通常 含有0 - 2 5 5 字符集的计算机文件来说，静态统计模型统计出的频率是字符在整个 文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况。 使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在 复旦大学硕士学位论文 7 第2 章国内外研究现状 压缩后反而增大了。所以，“静态统计模型”一般仅作为复杂算法的某一部分出 现，在信息的某一局部完成压缩功能。本文的互关联后继树自适应词典压缩就 使用h u f f m a n 编码的静态统计编码完成一部分工作。 实用的是“自适应h u f f m a n 编码”，主要思想是编码器和解码器都从一棵空 的h u f f m a n 编码树开始，随着符号的读入和处理而按相同的方式修改码树。所 以在处理过程中的任何一步，编码器和解码器都必须使用相同的码字。 算术编码 在为符号分配固定长度码字的编码中，h u f f m a n 己经被证明是现有最好的一 种【9 1 ，但是h u f f m a n 编码使用整数个二进制位对符号进行编码，这种方法在许 多情况下无法得到最优的压缩效果。r i s s a n c n 在1 9 7 6 年以“后入先出”的编码 形式引入了算术编码的概念，1 9 7 9 年将它系统化，省去了乘法，使得速度得以 提高【1 0 1 ，1 9 8 1 年将它推广n - - 值图像编码上【1 1 】。 算术编码与h u f f m a n 编码不同，它不是将单个信源符号映射为一个码字，而 是将整个输入符号序列映射在实数轴f o ，1 ) 区间内的一个小区间，区间长度等 于该序列的概率；再在该小区间内选择一个代表性的二进制小数，作为实际的 编码输出，避开了编码中比特数必须取整的问题，从而达到高效编码的目的。 但是算术编码的实现有两大缺陷：( 1 ) 具有固定精度的计算机很难完成无限 精度的算术操作。( 2 ) 高度复杂的计算量不利于实际应用。 l z 编码 上世纪七十年代末提出的l z 编码开创了信息论中现代的基于词典编码的新 分支。与h u f f m a n 编码成鲜明对比的是：l z 码将变长的输入符号串映射称为定 长的码字。l z 码按照几乎相等的出现概率安排输入符号串，从而使频繁出现的 符号串比不常出现的符号串包含更多的符号。l z 编码是基于词典的编码的典型， 又分为l z 7 7 和l z 7 8 两种算法。 l z 码能够有效地利用字符出现频率的冗余度和高使用率模式冗余度，但通 常不能有效地利用位置冗余度。l z 码从一个空的符号表开始工作，然后在编、 解码过程中逐步生成表中的内容，所以l z 又称为自适应压缩。l z 编码只需要 扫描一次数据，无需有关输入数据统计量的先验信息。但是由于码表是由空到 满逐步自适应地建立的，每一消息起始段的压缩效果不好，因此消息应该要足 够长，以便算法能够累积足够的符号出现频率的信息，从而对整段达到较好的 压缩效果。 复旦大学硕士学位论文 8 第2 章国内外研究现状 l z w 是l z 7 8 算法的修正形式，保留了l z 码的自适应能力，压缩比也大致 相同，显著特点便是逻辑简单。l z w 压缩算法的基本原理【1 2 】：提取原始文本文 件数据中的不同字符，基于这些字符创建一个编码表，然后用编码表中字符的 索引来替代原始文本文件数据中的相应字符，减少原始数据大小。这里的编码 表不是事先创建好的，而是根据原始文件数据动态创建的。解码时还要从已编 码的数据中还原出原来的编码表。l z w 还能进行一个小小的改进i ”】：在待编码 正文的开始部分，对编号可以使用较少的位，随着节点的增多，编号使用的位 逐渐增加。当然这不可避免地增加了编、解码端的算法复杂度。 2 1 3 文本压缩技术的应用 文本压缩技术因为有无损、通用的独特优点，一部分算法还非常简单、容易 实现，并且资源开销不大，所以得到了广泛的应用。对它的应用主要体现在以 下三方面。 软件上的应用i 9 i 这是最活跃、最多样化的一类应用。 在u n i x 操作系统领域，最早的通用压缩程序之一是c o m p a c t ，但是它运 行得太慢。后来有了比c o m p a c t 运行更快、压缩更好的c o m p r e s s 。 8 0 年代，通过s q 程序，数据压缩首次进入了m s d o s 领域。后来a r c 程 序取而代之。a r c 程序不但可以实现压缩，还可以对文件进行归档处理。接下 来的有p k z i p 、l h a r c 和a i l i 等程序。以后发展出的程序一般都被广泛移植到 了各种操作系统和硬件平台上。 硬件上的应用 数据压缩算法在硬件中实现具有高速的特点。l z w 提出时就是被应用到磁 盘的数据读写通道的硬件电路中的。而近来提出的新的数据压缩算法，一般具 有较高的复杂度，不少作者都提出了它的硬件实现方案，充分利用现代先进的 半导体技术提高算法的运行速度。而不少工业厂商都致力于用硬件产品的形式 提供它们的数据压缩算法，例如i b m 公司一直致力于开发a l d c 系列高性能数 据压缩专用芯片。 通信的应用 在数据传输之前先进行无损的压缩可以有效地节约通信带宽，加快传输速 复旦大学硕士学位论文9 第2 章国内外研究现状 度。当然，能够这样做的前提是通信双方的压缩、解压缩算法必须相互成一对， 因为这样才能保证实现正确的还原。美国的s t a c 电子公司用专用芯片实现的基 于l z 7 7 的压缩算法被“1 4 英寸盒式磁带( q u a r t e ri n c hc a r t r i d g e ) 工业集团” 接受为工业标准，得到了广泛的应用。 2 1 4 压缩的评判标准 压缩算法的实现和原理有很大不同，但是它们是可以通过下面几方面来评 价： ( 1 ) 压缩率( c o m p r e s s i o nr a t i o ) 的大小； ( 2 ) 压缩及解压缩所需的c p u 时间； ( 3 ) 所需内存大小； ( 4 ) 适应性与灵活性。 在以上的评价方法中，压缩率是最重要的一个方面。在各种压缩软件和科技 文献中，压缩率有多种不同的定义。比如。数据压缩前的长度为口。压缩后的长 度为p ，那么，压缩率的定义包括：p a ，a l p ，8 ( p a ) ，l o o c p a ) ，1 0 0 ( 1 一p a ) ， 本文将压缩率定义为p a 。显然，压缩率越小，压缩算法的压缩性能越高。 压缩率只反映了压缩方法的一部分性能，不同的应用环境对压缩和解压缩的 具体要求也有区别。例如对于多次部分解压的文件，需要设计较好的压缩方法 来方便部分解压；而对于一次压缩多次解压的应用，则需要设计快速的解压算 法。任何压缩算法都不能同时在以上各方面达到最优。每一种压缩算法都有其 适用范围和环境，根据不同的应用和环境选用最合适的压缩算法才能达到最优 效果。 2 。2 全文检索 2 2 1 全文检索模型的分类 在全文检索研究领域中，基于概念、超文本信息检索最为活跃，并己取得了 突破性进展。研究者也从不同的角度提出了大量信息检索模型，比如布尔模型、 向量空间模型、概率模型以及它们的变形。有的模型已经在一定程度上实现了 复旦大学硕士学位论文 1 0 第2 章国内外研究现状 检索系统。 常见的全文检索模型一般有4 大类：布尔检索模型、向量空间模型、概率推 理模型与概念模型。 布尔检索模型 布尔检索模型是一种最早也是最简单的严格匹配模型。它基于集合论和布 尔代数，将用户提问表示成布尔表达式。检索系统将提问与文档进行逻辑匹配 操作，得出的命中文献集合为检索结果。布尔模型易于实现，检索速度快，但 是往往很难将用户的信息需求转换为布尔表达式；而且检索条件过于严格，完 全匹配会导致太多或者太少的结果文档被返回；同时也无法区分词条在文档中 所占的权重，缺乏文档分级的概念，因此布尔模型是一种简单但是不够理想的 快速检索模型。 向量空间模型 向量空间模型【1 5 ，1 6 】又称代数模型。它的基本思想是用带权值的向量空间来表 示用户的查询要求和数据库文档信息。其中向量空间中每一维为用户查询要求 和数据库文档的一个特征。特征的重要度称为权值。用户查询要求的向量权值 由用户指定；数据库文本向量的权值则根据特征在文本或文本集中的出现频率 决定。查询向量与文本向量间的余弦角通常用来测定该文本与该用户提问词之 问的匹配程度。 使用向量检索模型可以检索出所有与用户提问相关的文献，并且通过相关性 计算得到每一篇文档的相关度，从而系统可以按照相关度降序输出命中文献。 用户可以通过闽值的增减来控制输出文献量，这在检索理论上是一次重大突破。 很明显，向量空间检索模型相对于简单的布尔检索模型有巨大的优越性，但是 它在使用上也有明显的不足。首先，在将检索过程转化为向量的计算过程中， 因为文献之间的关系非常复杂，不可以仅仅将关键词的权简单相加；其次由于 任何一个提问都要对全部文献做出计算，计算量是比较大的，而且寻找一种简 单的算法比较困难。 概率推理模型 概率推理模型【1 7 】的基本思想是把信息检索看成事实的推理与证明过程。这个 推理网络是一个有向图，节点表示有效事实，边表示事实间的依赖关系。在网 络中，每个节点都有一个链矩阵，用来计算给定节点的父节点的概率。输出时 则按概率大小把文件显示给用户。 复旦大学硕士学位论文 第2 章国内外研究现状 概率模型比布尔模型，向量模型有所改进的是考虑了词条文档之间的统计概 率。在贝叶斯网络1 1 8 】的基础上，人们通过应用这种推理网络来提供更好的混合 不同的依据源的方法，这就得到了两种新的概率模型：推论网络( i n f e r e n c e n e t w o r k ) f i g l 和信任网络( b e l i e f n e t w o r k ) 【2 0 】。 概念模型 概念模型是一种全新的检索模型。该模型的基本原理和上述的几种模型有本 质的区别。该模型不是以单词或词组为中心组织检索数据库，而是以概念来取 代它们。我们用树状或网状结构来表示概念的组织和分类。使用概念模型检索， 就不再局限于词条本身，当用户输入一个查询词条时，不仅要找出与查询表达 式匹配的结果，而且搜索引擎根据该词语概念与其他词语概念的内在关联，也 要找出包含与查询表达式概念相同或相近的词语的文档。概念模型不是简单的 短语匹配，这种短语匹配往往得到成千上万毫无意义的结果，太多的无用结果 反而不能很好的满足用户的查询需求。 2 2 2 几种主要的全文检索的索引模型 倒排表( i n v e r t e dl i s t ) 模型 现在应用最广泛的模型就是倒排表模型。倒排表模型中，每个字或词都对应 一个链表，链表的每个节点记录下每个字或词在文本集中所有的出现位置，并 根据它们完成检索服务。 倒排表模型的思想比较简单，在索引创建过程中只需对文本集进行顺序扫描 并记下位置，并不需要更多的分析，对索引的填写总体上也是顺序进行的，因 此外存f o 操作相对较少。经过多年的发展，倒排表模型的空间效率也得到很大 的提高，有代表性的工作有：e l i a s 在1 9 7 5 年描述的y 和6 编码法；b o o k s t e i n 、 m o f f a t 、z o b e l 和w i t t e n 等研究的用于索引压缩的局部贝努里模型；以及目前在 静态全文数据库中得到广泛应用的g o l o m b 编码。 虽然倒排表模型难于再进一步提高检索效率，但是它的结构和创建过程本身 联系比较密切，并不需要进行一系列变化，而且准动态的倒排表模型的动态性 能相对其它模型也是比较好的。 p a t 树和p a t 数组模型 p a t 树【2 1 】( 也称为s u i f r i 【树) 是一种特殊的p a t r i c i a 树，它由g o n n e t 和m a n b e r 复旦大学硕士学位论文 1 2 第2 章国内外研究现状 提出。它将一个文本看成一组半无限串的叠加，而这组半无限串的排序结果被 表示成树的形式。p a t 树模型具有较高的检索速度，尤其对某些特殊的检索，如 前缀检索、范围检索等。但是它的空间开销大，特别创建过程中的空间开销更 大，创建效率也很低，而且无论是创建过程还是检索过程都严重依赖源文本， 而倒排表在检索中是不需要源文本的。 p a t 数组 2 2 1 由g o n n e t 、m a n b e r 和m y e r s 在改进p a t 树模型的过程中独立地发 现并应用，即将p a t 树的叶节点串行化就得到了p a t 数组。p a t 数组比p a t 树更直 观，完全可以不通过p a t 树去理解和创建，但是两者的思想是一致的。由于树这 种数据结构放入外存之后i o 的效率变得很低，而p a t 数组索引的创建和合并均 需大量移动数据，因此两者的动态性能都不理想。 署名文件模型和位图模型 署名文件【2 3 】有时也称散列函数法。它为每个文档设定一个宽度为w 的矢量， 把该文档的每个索引项都按照某个散列函数映射到矢量中的某几位上，并将相 应的署名的位数置为1 。当把文本中每个字符的散列值叠加时，就得到了合并后 的文本署名的全集。 要检测一个查询项是否在给定的文本中出现，我们就要计算此查询项的散列 函数值。如果某些文本的描述符中所有的对应位均被设定，则此术语可能出现 在该文本中。要解决这种不确定性，必须读入并扫描文本以检查查询项是否真 正出现。我们可以通过为每个查询项设置几个位并使署名足够长来降低这种失 败匹配的概率，但无论如何，总是需要进行失败匹配的检查，这在相当程度上 增加了查询过程的开销。 位图使用起来很容易而且很快，尤其适合布尔检索，但是位图空间开销特别 大。一些实验表明，位图空间开销可能是原文本的几十倍。尽管已经发现了一 些高效的位图压缩方法，但压缩后的空间开销仍然远大于倒排表和署名文件。 这导致位图是三种索引模型中应用最少的一种。 这两种模型同倒排表模型从实质上讲是同一基本观念的变体。二者均能提供 比倒排表更迅速的查询处理，但均需要大量的存储空间。由于索引空间的大小 是影响动态性能的一个较主要的因素，因此它们的动态性能在先天均比不上倒 排表模型。虽然这两种模型往往配合压缩技术，但是由于数据的压缩工作往往 在索引生成之后进行，且开销也很大，因此压缩仅仅提高了索引的空间效率， 而降低了动态性能。 复旦大学硕士学位论文 第2 章国内外研究现状 2 2 3 全文检索技术的应用 搜索引擎是全文检索技术中最主要的一个应用。目前，搜索引擎已经成为排 在收发电子邮件之后的第二大互联网应用技术洲。其应用范围已经扩展到 i n t e m e t 的各个领域。 i n t e r n e t 搜索引擎 i n t c r n e t 搜索引擎包括三个部分：收集网页的机器人、分类和索引及检索引 擎。全文检索技术是搜索引擎的核心支撑技术。 c o m 网站的站点检索 一个好的检索引擎是一个理想站点的关键。很多人在访问一个站点时喜欢使 用站点检索，站点检索应是分类目录导航和全文检索的完美结合。 企业信息门户的检索引擎 电子化企业应以建立企业信息门户为重点，把企业信息库的信息发布到公司 的i n t e m e t i n t r a n e tw e b 站点上，与i n t r a n e t 的同事共享公司信息，或者与公司的 客户合作伙伴分享公司信息。企业信息f - j p 的一个核心问题是建立一个高效的 知识检索解决方案。 电子商务网站的内容检索引擎 全文检索等信息检索手段对于一个电子商务站点是很重要的，借助信息检索 技术可以帮助客户快速定位到所要的信息或产品。 2 3 全文检索与压缩的结合 全文检索系统使得用户能够在海量文本中快速获取准确的信息，目前主要的 技术手段是建立全文索引，用在有序的全文索引中的快速定位代替在无序的文 本中的顺序匹配，因此大大提高了检索速度。但是全文索引占用空间很大，一 般与海量文本自身空间相当。这里存在一个二难矛盾：越是大的文本越需要全 文索引，而且需要的空间越大，但越是大的文本留给全文索引的空间越有限。 因此在全文检索系统中引入压缩技术很有必要。 倒排表是最流行的全文检索模型，因此适用于倒排表的索引压缩算法【2 5 2 6 1 是研究热点。索引压缩大大提高了倒排表的空间效率，但是压缩和解压也增加 了创建索引和检索的时问开销。 复旦大学硕士学位论文 1 4 第2 章国内外研究现状 a m i h o o d a m i r 等人也提出了能直接在用l z 算法压缩的文件上进行模式匹配 的一般算法2 7 1 。其它的方便在压缩文件上进行全文检索的压缩方案大多都是采 用静态的h u f f m a n 编码算法【2 8 2 9 1 ，因为字符的静态h u f f m a n 编码码字在整个文 本范围内都是保持不变的，非常方便进行检索。但其需要两趟扫描、需要附加 码本、压缩比不是很高的缺点依然存在。 2 4 互关联后继树知识介绍 互关联后继树3 0 1 ，也简称为i r s t ( i n t e r - r e l e v a n ts u c c e s s i v et r e e ) 。i r s t 是 在2 邻接矩阵模型的研究中发展出来的一种新模型。为了解i r s t 模型，我们 先给出一个实例，结合此实例给出下列定义。 例2 1 ：设有文本库为字符串a b c d a b d b c # 。 其中字符# 为文本库的结尾符，a ，6 ，c ，d z ，我们可得到如下二元的互关 联后继树表达式、互关联后继树、精简互关联后继表达式和精简互关联后继树 ( 详细请见定义2 6 和定义2 1 0 ) 。 a ( b ( c ) ，b ( d ) ) ，b ( c ( d ) ，d ( b ) ，c ( 撑) ) ，c ( d ( a ) ，撑) ，d ( a ( b ) ，b ( c ) ) 图2 1 互关联后继表达式 图2 2 互关联后继树 a ( b ( 1 ) ，b ( 2 ) ) ，b ( c ( 1 ) ，d ( 1 ) ，c ( 3 ) ) ，c ( d ( 1 ) ，撑) ，d ( a ( 2 ) ，b ( 3 ) ) 图2 3 精简互关联后继表达式 复旦大学硕士学位论文 1 5 第2 章国内外研究现状 图2 4 精简互关联后继树 图2 4 的精简互关联后继树中叶子的标记和后继分枝的序正好一致，为该叶 子的后继信息。 假设是数目有限的字母表，全文数据库中用到的字母均属于。记l l _ m ， 即字母表的字母数i f l 为m ，上例2 1 中= a ，b ，e , d ，# ，f l - 5 。 定义2 1 ( 前驱和后继) ：对任意口1 ，9 2 ，字符串中，盯，称为a ： 的前驱，口，称为口，的后继。 定义2 2 ( 全文数据库) ：对于任意字符串吼口，e 1 ，口。，q 。 卢1 2 ，n ，i 指明字符口i 在字符串中的位置，口l a 2 q 口构成一个全文 数据库，上例2 1 中全文数据库就是a b c d a b d b e # 。 定义2 3 ( 一元后继表达式) ：在全文数据库中若口。口，a ，。为相同的 字符，不妨记作，则，则所有和它的后继构成一个一元后继表达式 ( 盯1 1 + 1 ，口12 + 1 ，口1 ) ，其中为根节点，口1 1 + 1 ，口1 2 + 1 ，盯l 为后继 节点。上例2 1 中第二、第六、第八个字符均为b ，它和它的后继构成一元后继 表达式b ( c ，d ，# ) 。 定义2 4 ( 二元后继表达式) ：在全文数据库中，若 口。1 口“+ l ，d ，2 口1 2 + 1 ，口m 口l 是相同的二连字符，不妨记作口，其中 口，则所有口卢和它的后继构成一个二元后继表达式，记作 口( ( 口n + 2 ，口f 2 + 2 ，口s n + 2 ) ) ，其中口为根节点，口f l + 2 ，口m 2 ，口。+