（计算机软件与理论专业论文）可查询的半结构化数据压缩方法研究.pdf

重庆邮电大学硕士论文 摘要 摘要 近年来，随着i n t e r n e t 的迅猛发展，x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 已经成为数据交换和表示的主要标准。由于x m l 具有良好的可扩展性和跨平台 性，越来越多的信息以x m l 文件的形式进行交换和存储。x m l 数据的一个缺点是 存在较大的数据冗余，会造成存储空间的浪费、查询效率的降低。因此对x m l 数 据进行有效压缩和查询成为一个重要的研究领域。 目前已有的x m l 数据压缩技术例如x m i l l 运用结构和内容分离的思想能够取 得两倍于传统的压缩技术g z i p 的压缩效率，但是它们并不支持压缩数据流之上 的查询处理。如果希望查询数据，则只能解压缩全部数据。但是频繁的解压缩会 造成系统资源大量的损耗，因此本文提出了一种基于x m l 数据流的压缩技术 x q c ( x m lq u e r yc o m p r e s s i o n ) ，实时完成x m l 数据流的压缩和解压缩，同时在压 缩的数据上应用x m l 的查询技术x p a t h 获得所需信息。该方法以私有的元素和属 性值为压缩粒度，在哈夫曼编码的基础上采用了一种与上下文无关的压缩模式来 保持原x m l 文件的结构。点查询( 指精确查询) 直接在压缩文档上执行，解压缩的 操作被限制在最终返回给用户的查询结果部分：范围查询中需要对查询谓词中的 元素和属性值进行解压，而不需要对整个文档解压。 本文分析了当前x m l 数据压缩与查询的研究现状和目前己有x m l 数据压缩方 法的不足，并指出了研究主题及目标。对数据压缩的基本原理，x m l 的数据模型， x m l 的数据压缩，和x m l 的查询语言进行介绍。重点阐述了x q c 系统的重要组成 结构和主要功能。实验表明在x m l 数据流环境中，相比较于) ( m i l l 技术，由于x q c 采取了同构压缩技术和两次s a x 文件扫描，因此在数据压缩率和压缩时间的性能 稍低。但是压缩性能的降低换来的是在压缩数据之上查询的执行效率的较大提 高。 关键词：可扩展标记语言，数据压缩，查询处理，冗余，哈夫曼 重庆邮电大学硕士论文a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，x m lh a sb e c o m et h em a i ns t a n d a r df o ri n f o r m a t i o ne x c h a n g e a n dr e p r e s e n t a t i o no nt h ew o r l dw i d ew e b i ti sc l e a rt h a ta ne n o r m o u sa m o u n to f d a t ai nt h ei n t e m e tw i l lb ee n c o d e di nx m li nt h en e a rf u t u r eb e c a u s eo fi t s e x t e n s i b i l i t ya n dc h a r a c t e r i s t i co fc r o s s p l a t f o r m h o w e v e r , r e d u n d a n c ya st h em o s t o b v i o u sd i s a d v a n t a g eo fx _ n i ld o c u m e n t si nt h e i rt e x t u a lf o r ml e a dt ow a s t i n gd i s k s p a c ea n dd e c r e a s i n gt h ee f f i c i e n c yo fq u e r y h o wt oe f f i c i e n t l yc o m p r e s sx m ld a t a a n de v a l u a t eq u e r i e so v e rc o m p r e s s e dx m ld a t ai saf u n d a m e n t a lp r o b l e m t h ee x i s t i n gx m l c o m p r e s s i o nt e c h n o l o g y ：x m i l lm a k e su s eo f t h es e p a r a t i o n b e t w e e ns t r u c t u r ea n dc o n t e n tt oi m p r o v e s sc o m p r e s s i o nr a t i o ，w h i c hi st w i c ea st h e c o n v e n t i o n a lc o m p r e s s i o nt e c h n o l o g y ：g z i p b u tt h e yd o n ts u p p o r tt h ed i r e c tq u e r y o nc o m p r e s s e dd a t a i nt h i sp a p e r , ax m l c o m p r e s s i o nm e t h o d ：x q ci sp r o p o s e d ， w h i c he f f i c i e n t l yc o m p r e s sa n dd e c o m p r e s st h es e m i - s t r u c t u r ed a t aa n dd i r e c t l yq u e r y t h ec o m p r e s s e dd a t ai nx p a t hs c h e m a t oa c h i e v et h ee f f i c i e n tq u e r yw i t h o u tf u l l d e c o m p r e s s i o n ，x q ca d o p t e dah o m o m o r p h i cc o m p r e s s i o ns c h e m ew h i c hp r e s e r v e s t h es t r u c t u r eo f o r i g i n a lx m l d a t a t h em a i nr e s e a r c hw o r k sa n ds p e c i f i cc o n t r i b u t i o n so ft h i s p a p e rc o v e rt h e f o l l o w i n ga s p e c t s ：f i r s t l y t h er e s e a r c hh i s t o r ya n dc u r r e n tr e s e a r c hs t a t u so fx m l w e r es u m m a r i z e d m o r e o v e r , t h ed i s a d v a n t a g e so fe x i s t i n gm e t h o d so fx m ld a t a c o m p r e s s i o nw e r ea n a l y z e di nd e t a i l f u r t h e r m o r e ，t h ed e v e l o p i n ga s p e c t sa n dg o a l s o ft h es t u d yo nx m ld a t ac o m p r e s s i o nw e r eg i v e n a n dt h eb a s i cp r i n c i p l eo fd a t a c o m p r e s s i o na n dt h er e l a t e dt e c h n o l o g yw i t hx m lw a si n t r o d u c e d t h ex q c c o m p r e s s i o ns y s t e ms t r u c t u r ea n dt h em a i nf u n c t i o nw e r er e p r e s e n t e da n dt h ef i n a l e x p e r i m e n tr e s u l ti n d i c a t e dt h a tx q cs y s t e mc o m p r e s s i o nr a t i oa n dc o m p r e s s i o nt i m e i sal i t t l el o w e rc o m p a r i n gw i t ht h ex m i l lc o m p r e s s i o nt e c h n o l o g y b u tt h e r e d u c t i o no fc o m p r e s s i o ne f f i c i e n c ym a k e st h ei m p r o v e m e n to ft h ep e r f o r m a n c eo f q u e r yo p e r a t i o no nc o m p r e s s e dd a t a k e yw o r d s ：x m l ，d a t ac o m p r e s s i o n ，q u e r yp r o c e s s i n g ，r e d a n d a n c y ，h u f f m a n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究_ 3 2 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得重庆自e 电态堂或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：松 签字日期：2 0 口年月吕e t 学位论文版权使用授权书 本学位论文作者完全了解重麽邮电态堂有关保留、使用学 位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件 和磁盘，允许论文被查阅和借阅。本人授权重麽邮电太堂可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：耸苦沃 新签名：舭附；o j z _ 签字日期：z c 0 6 年6 月弓日签字日期：功年6 月o o 日 重庆邮电大学硕士论文 1 1 引言 第一章绪论 随着现代社会逐步迈向信息化，在互联网迅速发展的推动下，产生了大量的 各种形式的信息。长期以来建立的大量孤立、自主、异构的空间信息己经无法满 足i n t e r n e t 时代人们对实现空间信息的共享和进行数据交换的迫切需要。面对 上述挑战，必须在理论和技术上寻求新的可行途径，以达到对孤立的空间信息进 行高效、灵活的交换和实现对广域、异构空间信息的共享，更好地在w e b 上制造、 加工、处理和发布空间信息，提供更便捷优质的空间信息的w e b 服务。近年来出 现的基于x m l 技术，正可以帮助我们应对这些挑战。可扩展标记语言x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 是一种半结构化的数据表现形式，它已经成为 i n t e r n e t 以及电子商务中进行数据交换和表示事实上的标准。 x m l 文档除了数据本身以外，还包括大量重复出现的结构描述信息。这些冗 余的结构信息造成了x m l 文档的容量偏大，因此x m l 数据的存储和传输代价比较 高。对于x m l 文档压缩可以采用传统的g z i p “。，b z i p 等压缩工具。 于此同时人们为了获取自己所需的信息，经常在x m l 文档上进行查询操作。 传统的压缩方法以整个x m l 文档作为压缩粒度，如果希望查询数据，则只能解压 缩全部数据。频繁的解压缩会造成系统资源耗尽，处理速度变慢，特别是在资源 有限的各种移动设备( 手机，p d a 等) 上显得尤为重要。例如商务人士携带以压缩 x m l 数据格式存储客户信息的p d a 在外出差办公。由于业务需要经常查询数据库 获得客户联系信息，订单状况，物流配送清单，还需要输入新的客户信息何订单 以更新数据库。如果每次查询或更新操作都需要解压缩整个文档，就会相当消耗 p d a 系统资源等。 因此如何有效地完成x m l 数据的压缩以节省储存空间，降低传输代价，同时 如果能支持对压缩的x m l 数据的进行直接查询处理以避免解压缩操作对系统资 源的消耗，成为一个迫切需要解决的问题和研究方向。 信息从结构化程度的角度可以划分为三类：第一种是完全结构化的数据，如 关系型数据和面向对象的数据；第二种是无结构的数据，如文本、声音数据等； 还有一种介于二者之间的数据类型，称之为半结构化数据，这种数据的特点是拥 有不规则、可变的数据结构。对于传统的结构化数据和无结构的文本数据，已经 拥有比较成熟的管理工具和技术：结构化数据可以采用关系型数据库或对象型数 据库进行管理；无结构的文本数据则可以采用信息检索( i r ) 的方式进行访问。如 何对半结构化的) 【m l 数据进行有效的管理，包括存储、索引、查询等，是一个有 重庆邮电大学硕士论文 待解决的问题。 1 2 研究的目的与意义 首先介绍个简单但是相当有用的例子：网络日志文件( w e bl o gf i l e s ) 。 每个网站服务器出于网络安全的目的往往会记录下本站的访问流量，而且这些记 录下来的日志文件是可以被分析的。日志文件亡l = 的每一行代表着一个h t t p 的访 问。如下所示例子： 2 0 2 2 3 9 2 3 8 1 6g e t h t t p 1 0 l t e x t h t m l l2 0 0 1 1 0 9 7 1 0 0 1 0 0 ：0 0 ：0 2 | _ 1 4 4 7 8 l j _ l h t t d ：w w w n e t c n i m o z i l l a 3 1 j a ( i ) 当前对于日志文件的使用有多种不同的文件格式：在上面的例子中使用的格 式是a p a c h e sc u s t o ml o gf o r m a t ：每一行纪录通过“l ”分割为1 1 个不同的 片断。文件的结构比较简单，并且格式比较固定，对于缺少的值用“一”进行代 替。 在经过了一段较长时间的收集以后，网络日志文件将占用很大的存储空间。 上述的网络日志文件如果出现1 0 0 0 0 0 条记录自匀话，日志文件大小有1 6 m ，g z i p 进行压缩后减少为1 6 m ： w e b l o g d a t ： 1 5 9 m w e b l o g d a t g z ：1 6 m 由于不同网站服务器的日志文件采用不同的文件格式，因此分析日志的处理 程序之间是不可移植的，每个网站的日志文件者厣要开发相应的独立的分析处理程 序。从灵活性和可复用性方面考虑，把上述网络日志文件转换为x m l 文件格式， 如下所示： 2 0 22 3 9 2 3 8 1 6 g e t h t t p i o t e x t h t m l 2 0 0 1 9 9 7 1 0 0 1 - 0 0 ：0 0 ：0 2 4 4 7 8 h t t p ：| | w w n e t j p m o z i i l a 3 1 j a ( i ) 分析这种日志文件的处理程序比较容易编写，并且这种格式的文件比较容易 转换其它格式。但是日志文件大小却增长了很多： w e b l o g x m l ： 2 4 2 m w e b t o g x m l g z ：2 1 m 传统的g z i p 压缩工具对整个x m l 格式文档中不同的标记( t a g ) ，数据值( d a t a v a l u e ) 以二进制的形式进行编码。如果日志分析处理程序需要查询某个时间点或 重庆邮电大学硕士论文绪论 时间段内的访问记录，必须把压缩的x m l 日志文件解压缩。 在硬件性能良好的服务器上，对x m l 文件进行压缩，查询时又进行解压缩的 操作可能运行的很好，并不存在什么问题。但是如果在手机，p d a 等资源有限的 设备上执行类似的操作可能导致系统资源耗尽，例如在p d a 上查询基于x m l 定肯u 的通讯录，可查询的列车时刻表，显示基于g m l 语言定制的电子地图等。在这些 设备上需要压缩数据以节省存储空间，同时频繁的查询需要解压缩而导致系统性 能降低。 针对上述问题，本文的研究目的是对现有的x m l 数据压缩中存在的问题，研 究面向x m l 的压缩方法和压缩环境下的查询处理问题，探讨如何实现对富含冗余 的、大容量的x m l 数据进行有效压缩、准确查询。 本文的两个主要研究目的是： ( 1 ) 研究x m l 数据的冗余消除问题：包括以元素和属性值为粒度的数据压缩， 以哈夫曼( h u f f m a n ) ”。编码为基础的上下文无关的压缩模式。 ( 2 ) 结合数据压缩技术和查询处理技术，建立能有效管理富含冗余的大容量 x m l 数据的x m l 数据压缩系统，并研究适合于x m l 压缩数据的信息查询技术的实 现。 1 3 国内外研究发展历史及其现状 随着i n t e r n e t 的迅速发展，使其成为全球信息传递和共享的重要资源， 由 于i n t e r n e t 上的数据多以半结构或无结构的形式出现，因此传统的数据模i 不 适合表示这些数据。x m l 的出现引起了人们极大的关注，x m l 是由嵌套的标记元 素构成的自描述标记语言。目前，x m l 文档己经成为i n t e r n e t 上的信息交换和 处理的重要标准。x m l 产生的最初原动力是为了解决h t m l 作为w e b 数据交掺 标 准而带来的混乱局面，与h t m l 相比，x m l 具有很大的灵活性，不但可以表示无 结构的文本信息，也可以表示高度结构化的数据，它极大地推动了互联网技术在 电子商务、电子数据交换和电子图书馆等多方面的应用。在这方面已经开展了一 些研究，如x m l 数据的存储技术、发布技术、x m l 数据查询与优化技术、索引技 术等。 随着x m l 数据的不断增加，如何有效地存储x m l 数据成为一个迫切需要解决 的问题。目前，虽然已经提出了一些x m l 数据的存储方法，但是x m l 的存储问题 仍然是研究的热点之一。 目前存在的x m l 文件的存储模式主要可以分为以下两类：关系模式和n a t i r e 模式。关系模式以传统的关系型数据库作为存储后台，将x m l 文档转化为关系中 的表来存储。而n a t i v e 存储模式通常以文件系统或专门设计的x m l 存储系统作 重庆邮电大学硕士论文 为后台，将x m l 文档无转化地存储到文件系统或专门的x m l 存储系统中。x m l 数 据的一个明显特征是其数据冗余较大，无论采用那种模式来存储x m l 数据，都必 须面对x m l 数据冗余较大这一特点。冗余既造成了存储空间的浪费，又增加了查 询处理的i o ，从而降低了效率，故有必要对x m l 数据进行压缩存储。 本节主要介绍基本的数据压缩算法发展以及现有的一些基于x m l 的压缩技 术的研究现状。 1 3 1 数据压缩发展历史 大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方 法，可以降低这种冗余度。对于数据压缩技术，比较系统的研究开始于上世纪 4 0 年代初提出的信息论。早期信息论研究的内容之一是在已知消息中各符号出 现的频率，设法构造一种编码技术使得信息所占的空间尽可能少。近二十年来， 由于模式识别、图像处理、计算机通信、数据库技术等技术的出现，促进了数据 压缩理论和应用的快速发展。 贝尔实验室的c l a u d es h a n n o n 和m i t 的r m f a n o 在1 9 4 9 年几乎同时提出 了最早的对符号进行有效编码从而实现数据压缩的s h a n n o n f a n o 编码方法。 d a h u f f m a n 于1 9 5 2 年第一次发表了论文“最小冗余度代码的构造方法”( a m e t h o df o rt h ec o n s t r u c t i o no f m i n i m u mr e d u n d a n c yc o d e s ) ，该算法成为经典的数 据压缩算法，为了纪念作者人们把该算法又简称为哈夫曼编码。 2 0 世纪8 0 年代，数学家们从新的角度入手，遵循h u f f m a n 编码的主导思想， 设计出另一种更为精确的编码方法算术编码| 4 i 。凭借算术编码的精妙设计和卓越 表现，人们终于可以向着数据压缩的极限靠近。算术编码得到的压缩效果可以最 大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。当然，算术编 码同时也给程序员和计算机带来了新的挑战：要实现和运行算术编码，需要更为 艰苦的编程劳动和更加快速的计算机系统。也就是说，在同样的计算机系统上， 算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。这 就是为什么算术编码不能在日常使用的压缩工具中实现的主要原因。 为了找到既在压缩效果上超越h u f f m a n ，又不增加程序对系统资源和时间的 压缩方法，1 9 7 7 年，j a c o bz i v 和a b r a h a r l ll e m p e l 发表了论文“au n i v e r s a l a l g o r i t h mf o rs e q u e n t i a ld a t ac o m p r e s s i o n ”。1 9 7 8 年，又发表了该论文的续篇 “c o m p r e s s i o no f i n d i v i d u a ls e q u e n c e sv i av a i l a b l e r a t ec o d i n g ”。在这两篇论文中 提出l z 7 7 5 1 和l z 7 8 算法。简单地说，这两种压缩方法的思路完全不同于从 s h a n n o n 到h u f f m a n 到算术压缩的传统思路，而是采用字典式编码。字典式编码 不但在压缩效果上大大超过了h u f f m a n ，而且对于好的实现，其压缩和解压缩的 重庆邮电大学硕士论文 绪论 速度也异常惊人。 当数据压缩被用于移或少存储空间时，可以减少程序的执行代价和执行时间。 这是因为存储量的减少将导致磁盘存取次数的减少，虽然数据的压缩和解压缩过 程会增加额外的代价，但由于这些代价通常少于数据的存取时间，因此总的代价 减少了。尽管存储系耄究的容量和性价比在近些年来的到了很大的提高，但不断出 现的i n t e m e t 应用、复杂；业务系统的数据等仍然使得数据压缩技术在计算机技术 飞速发展的今天起着彳艮重要的作用。 目前，根据不同差内应用领域，数据压缩技术的研究主要包括以下几个方向： ( 1 ) 图形、图像压缩技术； ( 2 ) 数据库压缩技术； ( 3 ) 声频、视频信号自勺压缩技术和传输信号的压缩技术； ( 4 ) 文本压缩技术。 其中，数据库压耋箱可以说是一种特殊目的的压缩技术，其目的不仅要减少数 据所占的存储空间，要求在压缩过程中不丢失信息，而且要求能够在一定程度上 对压缩数据进行存在圭桑作。 文本压缩是基本酌一种文件压缩，其目的是要减少文件所占的存储空间，要 求压缩了的文件在解压缩后，内容与未压缩之前完全相同，是一种无损压缩技术。 近年来，随着i n t e r n e t 的快速发展，数据的形式和内容都发生了深刻的变化，例 如出现了以承载半结才勾化数据为代表的半结构化文件、x m l 数据等。同时利用 数据库技术对这些数捐多型进行管理也是近年来的研究热点。对于这些数据的压 缩，已经不单纯应用二丈本压缩技术，而是数据库压缩技术、文本压缩技术等多种 技术的综合应用。 在本文中，主要研究支持信息查询的x m l 的压缩技术，所以重点介绍相 关的文本压缩。下面儿小节阐述了x m l 压缩技术及其研究现状。 1 3 2x m l 数据压缩研究现状 数据压缩起源于4 0 年代由c l a u d es h a n n o n 首创的信息论。大多数信息通过 一定的模型和编码方j 去，可以降低其所包含的数据冗余。传统的数据压缩方法仅 仅注重压缩效率，没= 有考虑到数据的随机存取和操作问题。基于x m l 数据的压 缩不同于普通压缩之处在于需要充分考虑到所处理数据的特殊性，分析数据的结 构和特点，在普通压缔算法基础上进一步提高压缩效率，并提供数据在压缩域上 的查询处理方法。 x m l 自身的特点决定了其数据冗余较大，由此造成了存储空间的浪费、查 询效率的降低。x m l 压缩技术就是针对x m l 数据的特殊数据模型，在x m l 结 重庆邮电大学硕十论文绪论 构特征和语义信息的帮助下对其进行压缩的过程。才艮据应用的目的不同，x m l 压缩技术又可以分为有损压缩和无损压缩；根据对查询的支持程度，又可以分为 支持查询的压缩技术和不支持查询的压缩技术。在本：文呻主要研究支持压缩域查 询的x m l 无损压缩方法。 不支持查询的压缩方法作为早期的x m l 压缩方法，目的单一，就是要解决 x m l 的冗余问题，以满足网络带宽和存储空间的要对乏。它们的共同特征是压缩率 都好与一般的压缩算法，如b z i p 等：其次是不支 孑随机存储，也就是如果要对 其进行查询处理，就必须进行完全解压缩。近年来，提出了多种不支持查询的压 缩方法，如x m i l l ，x m l p p m 等，这些压缩方法为了理义得j 安好的压缩效果，都不支 持随即存取和查询处理。 其中x m i l l “1 是最早的不支持查询的x m l 数据压缩系统。x m i l l 中压缩方法 的核心思想是将结构和内容分离，然后利用a p p r o ki m a t i o n m a t c h i n g 算法对相 似语义的数据项进行分组，形成数据容器( c o n t a i n e r ) 。对于结构，用字典编码 ( d i c t i o n a r ye n c o d i n g ) 方法对属性( a t t r i b u t e ) 和元素( e l e m e n t ) 进行替换。对 每个容器，利用通常的l z 7 7 算法分别进行压缩，最后将已经压缩的片断合并成 一个完整的压缩文件，能够取得两倍于g z i p 的压缩i 效鲁i 。 x m l p p m 提出了一种基于p r e d i c t i o nb yp a r t la lm a t c h ( p p m ) 的压缩方案。 与x m i l l 不同，x m l p p m 利用s a x 解析器将x m l 整理成个数据流，作为x m l p p m 的输入。根据语法，对元素或属性名、结构、属性值和i 故据项等分别利用相应的 p p m 算法进行编码压缩。由于p p m 算法是一种速度轻窆慢的压缩方法，所以) ( m l p p m 算法要比x m i l l 方法慢。但是在压缩率上，x m l p p m 要好与x m i l l 。 m l e v e n e 和p t w o o d ”。利用结构压缩算法( s t r u c t u r ec o m p r e s s i o n a l g o r i t h m ：s c a ) 对x m l 进行压缩。在此种方法中，) ( m l 文档必须具有相应的d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 。首先，s c a 算法采用分析树( p a r s et r e e ) 对数 据进行预处理，然后再对分析树剪切，形成剪切树( p r u n e dt r e e ) ，最后对剪切 树编码。s c a 的核心思想是两阶段最小描述长度编码( m i n i m u md e s c r i p t i o n l e n g t he n c o d i n g ) 的改进，力求用最短的编码对x h l 络构进行编码压缩。s c a 方 法的缺点是在对大容量) 【m l 文件压缩时，必须提供车交大的内存空间来存储中间数 据结构，如p a r s et r e e 和p r u n e d t r e e 等。 其它不支持压缩域查询的x m l 数据压缩方法= i 丕包括：王志宏、李建中等“1 提 出的基于编辑距离的x m l 文档聚类压缩方法：陈每贮敏、唐常杰等“”。在其提出的 s g c m 算法中，通过三个阶段实现对x m l 数据的压缩。从本质上来说，上述两种 方法都是x m i l l 方法的延伸。 尽管) ( m l 压缩技术已经取得了一些进展，但是对支持查询的x m l 压缩技术却 重庆邮电大学硕士论文 还很不成熟。现有的x m l 压缩和查询系统还不能够处理诸如x q u e r y 等复杂的查 询语句。在查询速度和压缩率上还没有取得比较满意的成果。所以有必要进一步 研究支持查询的x m l 压缩技术。 国内主要有哈尔滨工业大学的李建中、王志宏和四川大学的陈敏敏、唐常杰 等在x m l 压缩算法上做了大量的研究工作。复旦大学的吴永辉、周傲英等利用 x m l 模式规范化设计来消除x m l 冗余1 。北京大学的c o i x 和q b x s 系统”“在数 据集成和x m l 查询处理方面做了卓有成效的工作。 为了有效地查询x m l 数据，已经提出了许多种查询语言，例如x p a t h ，x m l q l ， q u i i t 和x q u e r y 等”。这些查询语一言的共同点是利用正则路径表达式r p e ( r e g u l a rp a t he x p r e s s i o n ) 来导航x m l 文档的查询。已有的x m l 查询处理方法 包括：采用半结构化数据模型，借鉴传统数据库技术实现面向x m l 的查询系统。； 基于传统数据库的数据模型，如关系型、面向对象等，其方法是首先对x m l 数据 进行结构化处理，然后通过传统的数据库技术实现对x m l 数据的查询“4 ”1 。 虽然在关于x m l 数据压缩方面已经开展了一些研究，但仍然没有解决x m l 压 缩数据库上的随机存取和复杂查询( 如t w i g 查询) 的问题。 目前，x m l 数据压缩技术正在成为x m l 研究领域的研究热点，由于x m l 结构 比关系数据等更加复杂和灵活，处理的代价也更大、更复杂，因而有关x m l 数据 压缩还有很多问题需要解决。国际上，这方面的研究也刚刚起步，特别是在支持 查询的x m l 压缩技术方面还有很大的发展空间。 1 4 论文的组织结构 本文内容共分六章，各章的内容简单概括如下： 首先，在第1 章中介绍本文的研究背景，x m l 的发展历史，基本技术与x m l 数 据压缩的研究现状。系统地分析比较了当前x m l 数据压缩的研究现状，并说明了 本文研究内容的必要性，介绍了论文的研究内容和主要贡献。 为了深刻的理解x m l 数据压缩，在第2 章中介绍了传统的基于统计方法的哈 夫曼编码，算术编码和基于字典的l z 7 7 压缩算法。这些编码算法是一切压缩技 术的基础。 第3 章中介绍了x m l 文档结构，数据模型和文档类型定义，并且着重介绍 x m l 的查询语言x p a t h 语言的特点和用法。 第4 章是本文的主要部分，提出了x m l 数据压缩系统的一个原型系统一x q c ， 以及系统的体系架构和主要功能模块。着重介绍系统所采用的压缩技术，并以实 际的例子对压缩前后的x m l 文档进行分析比较，分析了对压缩的x m l 文档的查询 处理过程。 重庆由b 电大学硕士论文 笫5 章是实验性能分析比较，在压缩比，压缩时间，查询响应时间等方面与 喜芒它压缩技术进行比较，说明x q c 获得了理想的压缩性能和较好的查询时间。 笫6 章中总结了本文的主要创新点，并指出了下一步的研究方向。 重庆邮电大学硕士论文数据压缩原理 第二章数据压缩原理 2 1 数据压缩与数据冗余度 数据压缩是把输入数据流( 源流或原始数据) 转变为另一种较小的数据流( 输 出流或压缩流) 的过程。流b p 存储器中的一份文件或一块缓存。数据压缩有很多 有名的方法。它们基于不同的理念，适合不同的数据类型，产生不同的效果。但 是原理都相同，即通过去除源文件的原始数据中的冗余度来压缩数据。在有关数 据压缩的任何讨论中，冗余度是一个相当重要的概念。 例如在典型的英文文本：中，字母e 最常出现而z 很少出现，称为字母冗余 ( a l p h a b e t i cr e d u n d a n c y ) 。这启示我们为字母安排变长码，使e 的码字最短而 z 的最长。另一类冗余度是丈本冗余( c o n t e x t u a lr e d u n d a n c y ) ，通常表现为字 母q 后常跟有字母0 ( 即在简单英语中，某些双字母及三字母比其它模式更常见) 。 图像冗余度则表现为，在一幅非随机的图像中相邻像素的颜色往往相近。 通过减少冗余度来压暂言的思想暗示了数据压缩的通用法则，即“对常见事件 ( 符号或短语) 赋短码，对稃若有事件赋长码”。实现这一法则的方法很多，一项对 任何压缩方法的分析表明它竹丁在本质上都遵循这一通用法则。 数据压缩的实现是把f 氏效( 长的) 表达方式改为高效( 短的) 表达方式，因此有 可能压缩只是因为通常计拿# 机中数据的格式比绝对需要长。采用低效( 长的) 数据 表示的原因是使数据易于处：理，而数据处理要比数据压缩更普遍和更重要。有一 个很好的例子：字符的a s c l i 表示要长于它的绝对需要，用7 位代码是因为定长 码易于处理。然而变长码更：有效，因为有些字符比其它字符更常用，因此可以赋 予更短的码字。 大多数的压缩方法可分为以下4 类：游程编码( r l e ) 、统计方法、基于字典 的( 有时称为l z ) 方法和变换。本章主要介绍常用的基于统计方法的哈夫曼编码 和基于字典的l z 7 7 ( 滑动窗) 编码。 2 2 哈夫曼编码 哈夫曼编码方法于1 9 5 2 年由d a h u f f m a n 提出。迄今为止，仍经久不衰，广 泛应用于各种数据压缩技才之中。 9 重庆邮电大学硕士论文 数据压缩原理 2 2 1 哈夫曼编码 哈夫曼编码的主要依据是变字长最佳编码定理。该定理的内容是“在变长 码中，对于概率大的符号，编以短字长的码；对于概率小的符号，编以长字长的 码：如果码制长度严格按照符号概率的大小的相反顺序排；列，则平均码字长一定 小于按任何其它符号顺序排列方式得到的码字长”。哈夫曼编码的具体实现步骤 如下： 概率统计( 如对一幅图像，或m 幅同种类型图像作灰度信号统计) ，得到 n 个不同概率的信息符号； 将n 个信源信息符号的n 个概率，按概率大小排序； 将n 个概率中，最后两个小概率相加，这时概率个数减为n 1 个； 将n 一1 个概率，按大小重新排序； 重复，将薪排序后的最后两个小概率再相加，相加和与其余概率再排 序： 如此反复重复n 一2 次，得到只剩两个概率序列； 以二进制码元( 0 ，1 ) 赋值，构成哈夫曼码字，编码结束。 按照以上步骤对出现频率分别为0 3 0 ，0 4 0 ，0 1 0 ，0 0 8 ，0 1 2 的字符 a 。a ：a 3 a 。a 。构造的哈夫曼数如图2 1 所示。 ( ，0 0 ) o 。i 圈 a 2 0 曰 a 1 0、l 、 圈 a 5 0 l 圈团 图2 1 哈夫曼树结构 2 2 2 哈夫曼解码 在开始压缩数据流之前，压缩器( 编码器) 必须根据符号概率( 或出现频率) 确 定码字。符号的概率或频率也需要放在压缩流中，以便让任何哈夫曼解压缩器( 解 重庆邮电大学硕士论文 数据压缩原理 码器) 都能够解码该压缩流。这容易实现，因为频率是整数，而概率也可以标定 成整数，通常只要在压缩流中添加几百字节就可以了。 无论何种情况，解码器必需知道流的开头是什么，然后读入它，为字母表构 造哈夫曼树，然后才能解码流的其它部分。解码算法很简单：从树根开始，读入 压缩流的第一位，如果是0 ，就沿树的左分支进行；如果是1 ，则沿右分支继续。 读入下一位，并向树叶方向前进一节。当解码器到达一个树叶，它就找到了原始 的、未压缩的符号码字( 通常是其a s c i i 码) ，并将其送出。就这样，再从树根开 始，对另外一位进行解码。 5 符号字母表可用来解释这一过程。4 个符号的输入串“a 。a 。a ：a 。”的编码是 1 1 1 0 1 1 0 0 1 0 。解码器从树根开始，读入第l 位是1 ，朝右走；读入第2 位是 1 ，向右走；第3 位也同样。第4 位这就到达树叶a 4 ，解出码字0 0 0 l 。再返 回树根，读1 1 0 ，两次向右，一次向右，到达树叶a 。，等等。 2 2 3 自适应哈夫曼编码 哈夫曼编码方法假定压缩器事先知道字母表中所有符号的出现频率，哈夫曼 树的构造在编码开始前已经完成，并且在以后的编码过程中保持不变。而实际应 用中符号的出现频率绝少能够预知。一个解决方法就是让压缩器对原始数据进行 两次读取，第一次只是计算各符号的出现频率，第二次才压缩数据。在两次处理 之间，压缩器构造哈夫曼树，这种方法称为半自适应的。另外一种方法叫做自适 应( 或动态) 哈夫曼编码，其主要思想是压缩器和解压器都从一棵空的哈夫曼树 开始，随着符号的读入和处理( 对于压缩器而言“处理”就是压缩；而对于解压 器而言“处理”则为解压缩) 而修改码树。压缩器和解压器应按相同方式修改， 所以在处理过程的任何一步它们都必须使用相同的码字，尽管这些码字每一步都 在变化。压缩器和解压器被称之为是同步的，或者是以步锁定( o c k s t e p ) 方式工 作的( 尽管它们不必一起工作，且压缩和解压缩通常不是同时进行) 。解码器的操 作与编码器的操作一一对应。 压缩器从一棵空的霍大曼树开始工作，对任何符号都没有分配码字。它把输 入的第一个符号不经压缩地直接写进输出流。然后把它添加进树中，赋予码字。 下次再见到这个符号时，就把它的当前码字写人数据流，并将其出现频率加l 。 由于这样做修改了树，那么就要检查该树是否还是哈夫曼树( 最佳码字) 。如果不 是，就要重新安排，这就必须改变码字。 解压器镜像对应着压缩器的相同步骤。当它读入一个未压缩符号，就把它加 进树中，并赋予一个码字；而当它读入一个压缩了的( 变长的) 码字，就利用当前 的哈夫曼树来确定它属于哪个符号并且用与压缩器同样的方式，对哈夫曼树进 重庆邮电大学硕士论文数据压缩原理 行更新。 2 3 算术编码 霍夫曼方法比香农一费诺方法更有效，但这两种方法都很少能产生最佳变长 编码。当符号的码长等于符号概率的2 的负整数次幂时，这些方法才能产生最佳 结果。这是因为这些方法是把整数个位的码字分配给字母表中的符号。概率为 0 4 的符号理想地应分配一个1 3 2 位的码字，因为- l 0 9 2 0 4 zi 3 2 。然而霍夫 曼方法原则上却只能给这样的符号分配i 位或2 位的码字。 算术编码克服了这个问题，它是把一个码字( 通常较长) 分配给整个输入流， 而不是给各符号分别分配码字。它逐个符号地读取输人流，每输入和处理一个符 号，就在码字后面加上几位。为便于理解，可以把生成的码字想像成 0 ，i ) 之间 的一个数。因此码字“9 7 4 6 5 0 9 ”应解释为“0 9 7 4 6 5 0 9 ”，尽管输出流中不含“0 ” 下面是算术编码的主要步骤： i ) 首先把“当前区间”定义为 0 ，1 ) 。 2 ) 对输入流中的每个符号s ，重复下面的两步： 2 1 ) 把当前区间分割为长度正比于符号概率的子区间。 2 2 ) 为s 选择一个子区间，并将其定义为新的当前区间。 3 ) 当用这种方法把整个输入流处理完后，输出应为能惟一确定当前区间的 任何数字( 即位于当前区间中的任意数字) 。 对任何处理过的符号，当前区间都缩小了，因此要用更多的位来表示，但关 键则是最终的输出是一个单独的数字，不含有单个符号的码字。平均码长可以用 输出长度( 以位为单位) 除以输入长度( 以符号为单位) 。 下面给出对短串“s w i s s m i s s ”的压缩步骤。表l 出了第一步所准备的 信息( 数据的统计模型) 。输人流中所出现的5 个符号可按任何顺序排列。对于每 个符号，首先统计它的出现频率，然后计算它的出现概率( 用频率除以符号串的 长度1 0 ) 。把区间 0 ，1 ) 划分给各个符号，顺序任意，每个符号所分得子区间的 大小正比于它的概率。因此“s ”得到子区间 0 5 ，1 0 ) ，宽度0 5 ，“i ”的子区 间是 0 2 ，0 4 )