支持查询的XML数据压缩算法研究

摘要

近年来XML已越来越被广泛的用于互联网上各种数据交换与数据表示,越来越多的公司与组织都通过XML来进行数据的交换与存储。但是XML有个致命的缺点:结构数据冗余。XML表示有效数据的同时,引入了大量的重复的半结构性元素标记数据。这些数据增加了宽带的传输负荷,同时增加了XML数据的存储成本,造成存储空间不必要的浪费。因此,压缩XML数据成为非常必要的工作。而在压缩数据上支持不全部解压即可快速查询的需求越来越大。现有的一些XML数据压缩算法的压缩率及查询效率不尽如人意。而商业的或研究型的XML数据库这方面的性能也较低,有很大的提升空间。
　　 为此,本文分析了现实中的XML数据的特性,特别是大数据量的XML数据的特性,据此提出一种新的压缩算法。该压缩算法不但能高效的压缩XML数据,也支持在压缩的数据上快速的实现用户的查询。
　　 首先,为了提高查询效率,在XML结构上提出了一种新的编码方案,本文称之为层次奇数编码法,并从理论上分析了该编码特有的性质。
　　 其次,用二进制串压缩XML文档中大量冗余的元素标记名和属性名这样的结构数据,并用Hash的方式实现以提高查询时的效率。然后,通过分析现实中XML文档数据的特性,特别是大数据量的XML文档数据特性,以及现实中用户对XML数据的常用的查询需求,本文定义并提出一种同构子树的概念。以此为基础,创新性的提出一种同构子树索引结构,合并同构子树中的节点,进一步压缩XML文档的冗余结构数据。同时,由于这种索引结构考虑到现实用户的查询需求与模式,相比传统的索引,在压缩数据上的查询效率更高效。并且,根据本文提出的层次奇数编码值的特性,为了进一步压缩数据,即压缩引入的节点编码值,提出了一种n元组合并算法。这样不但进一步压缩了数据,而且相对于不合并压缩层次奇数编码值,在合并的n元上采用n元组分裂等操作还能提高查询效率。
　　 再次,本文深入分析了XML数据上基于内容的常用的查询需求,以此为基础,提出一种将一般XML内容数据和常用短关键词查询域内容数据分离压缩的方案。此方式可以很好的降低用户的平均查询反应时间。
　　 再其次,分析、讨论了在同构子树索引及n元组分裂的算法上进行Xpath简单路径查询、分支路径查询、带值的内容查询以及Xquery查询中常用到的Xpath轴查询算法。同时,设计了一辅助的缓冲池,以进一步提高查询效率。
　　 最后,本文和现有的几个经典压缩查询算法做了实验对比。实验结果说明本文的算法具有较高的压缩率,并且平均查询时间明显比经典算法的更短。

目录

文摘

英文文摘

第一章 引言

1.1 课题背景及意义

1.2 研究课题领域现状

1.2.1 通用压缩技术

1.2.2 不支持查询的XML数据压缩算法

1.2.3 支持查询的XML数据压缩算法

1.2.4 XML数据通用索引现状

1.3 本文的主要工作和目标

1.4 本文组织结构.

第二章 相关技术与理论

2.1 XML技术与规范

2.1.1 XML文档、内容简介

2.1.2 XML各种规则及语法

2.1.3 XML的研究内容

2.2 Huffman压缩算法

2.3 LZ77压缩算法

2.4 本章小结

第三章 XML数据压缩与索引的建立

3.1 XML文档解析器

3.1.1 SAX解析器

3.1.2 DOM解析器

3.2 XML结构数据编码算法

3.2.1 XML结构数据编码现状

3.2.2 层次奇数编码算法

3.3 结构数据压缩与索引的建立算法

3.3.1 XML结构数据哈希压缩

3.3.2 同构子树合并压缩建立索引

3.3.3 n元组合并压缩算法

3.4 内容数据压缩

3.4.1 常用短关键词查询域内容数据识别

3.4.2 基于Huffman与LZ77的一般文本内容数据压缩方案

3.4.3 基于LZ77的常用短关键词查询域内容数据压缩算法

3.5 压缩算法效率的理论分析

3.6 XML数据压缩总体架构与流程

3.7 本章小结

第四章 基于IST索引的压缩数据查询

4.1 XPath查询语言介绍

4.2 查询缓冲池设计

4.3 n元组节点查询算法

4.3.1 n元组分裂算法

4.3.2 n元组分裂ID的基数排序算法

4.4 IST索引上的XPath路径查询算法

4.4.1 XPath简单路径查询

4.4.2 XPath分支路径查询

4.5 IST索引上基于内容关键词的XPath查询算法

4.6 xPath轴查询算法

4.6.1 XPath轴查询意义

4.6.2 轴查询算法

4.7 IST索引上查询的总体架构与流程

4.8 本章小结

第五章 实验

5.1 实验环境与数据

5.2 压缩效果与分析

5.3 查询结果与分析

5.4 本章小结

第六章 总结与展望

6.1 本文总结

6.2 展望

致谢

参考文献

在学期间取得的研究成果