论文部分内容阅读
摘要：随着Internet的迅速发展，大量信息充实了我们的生活，索引成为人们检索信息的必要途径之一。另一方面XML逐渐成为数据表示与交换的标准，对于XML数据文档的查询变成当今研究的热点
关键词：XML；后缀树；后缀数组；自索引；BWT
中图分类号：TP311.13 文献标识码：A 文章编号：1674-7712 (2012) 06-0099-01
一、数据压缩知识
数据压缩技术的发展。
随着计算机技术的飞速发展，数据压缩作为解决海量信息存储和传输的支撑技术受到了人们的极大重视，对数据压缩算法的研究也不仅局限于信息论中有关信源编码的范畴，数字图像信号、语音信号的分析和处理等技术被大量引入到有关的研究领域。
1977年，两位以色列科学家Jacob Ziv和Abraham Lempel发表了名为“A Universal Algorithm for Sequential Data Compression”（顺序数据压缩的通用算法）的论文，提出了一种不同与以往的基于字典的压缩方法——LZ77，他们在1978年又提出了LZ77的改进算法——LZ78，这两个算法吧数据压缩的研究推向了一个全新的阶段。1984年，Terry Weleh发表的论文“A Technique for High Performance Data Compression”（高性能数据压缩技术）描述了对LZ78算法的改进和具体实现技术，成为LZW算法。目前，无损数据压缩领域中流行的数据压缩方法多是基于字典的压缩技术。UNIX系统上的一个实用压缩软件COMPRESS和Windows系统下的压缩软件Winzip和Winrar中所使用的压缩算法都是基于字典压缩技术的。
当数据压缩被用于减少存储空间时，可以减少程序的总执行时间。这是因为存储量的减少将导致磁盘存取次数的减少，虽然数据的压缩/解压缩过程会增加额外的程序指令，但由于程序的执行时间通常少于数据的存储时间，因此中的执行时间将减少。也正因如此，数据压缩技术在计算机技术飞速发展的今天仍然有着很重要的作用。
二、XML压缩索引
（一）XML压缩背景
上文中已经述说了XML的优点，但和其它形式的数据表示相比，XML文档往往很大。因此有些时候，传输速度和存储空间会非常重要。具体来说：
1.XML是一种清晰而易用的文本标记格式，但它的弱点就是当有大量数据需要交换，而程序内部处理部分又非常少时，会导致XML文档非常大，这样过大的空间占用意味着更大的处理代价；
2.由于本文压缩算法多年来一直是大量研究项目的课题，目前已经非常成熟。这种类型的算法都能方便的将XML进行压缩，但将XML文本作为一般文本文件进行压缩，这类算法都不大可能改善处理的速度，而且还会增加了解压后再解析的步骤；
3.我们把XML文档用于索引结构，这样就不能只保持了XML文档的结构而无法对XML进行索引搜索。也就排除了一些简单的XML压缩算法。
（二）XML压缩方法
当压缩文档时，通常首先考虑常用的压缩算法，如：Lempel-Ziv和Huffman，以及在它们上面实现变化的一些常用实用程序。在类Unix平台上通常是gzip；在其它平台上，zip更为常用，比如：PKZIP、Info-ZIP和WinZip。但这些实用程序实际上意在充分地减少XML文件的大小。但是，都没有保持了XML文档的结构，或是无法对XML文档进行索引。这样本文选择使用BWT压缩算法而不是顺序Lempel-Ziv算法。
（三）BWT数据压缩
利用BWT压缩算法，我们先把字符文本进行转换，然后进行压缩，这样就解决了XML文档过大的弊端。而且BWT压缩算法要比顺序LZ算法，解压时速度有所提高。BWT算法的具体介绍我们在第5章进行讲解。
三、系统设计
（一）XML文件整体输出
首先，我们先不考虑XML文件的结构，这样把XML数据文件提交给程序，会按照普通文本文件的方式进行处理。程序先读取整个文件的内容，之后将它们作为一个字符串，进行后缀数组排序，然后BWT转换。但是这样的结果并不如意，有以下两个缺点：
1.程序执行的效率不高，文件内容如过大，导致整体的速度下降；
2.不便于查找，整体进行排序换转后打乱了文件结构，不能成为索引；
（二）以XML文件结构进行输出
由于不能破坏XML文件的结构，只能按照XML现有的标签内容进行。这样我们就引入了XML解析器，它可以分析出XML文件的结果和具体内容。先用解析器解析XML文件，我们就方便的判断出，什么是标签，什么是数据。把每个标签或者数据，单独进行排序转换。
具体过程：
1.XML解析器读取分析XML文件；
2.建立一个空的XML文件，进行添加排序转换后的数据；
3.如分析出标签开始，则提取此标签，对其进行排序转换，把结果插入新的XML文件；并记住此标签的级别，用于插入下级标签时使用；
4.如分析出数据，则对数据进行排序转换，并直接把新数据插入包含它的标签中；
5.如分析出标签结束，则关闭此级标签，结束数据转换；并记录新的标签级别，用于插入平级标签时使用。
参考文献：
[1]Donald Knuth.Art of Computer Programming[M].2002,Volume,3
[2]N.Jesper Larsson.Structures of String Matching and Data Compression[D].Sweden:Lund University,1999
[3]包小源,宋再生,唐世渭,楊冬青,王腾蛟.SuffIndex——一种基于后缀树的XML索引结构[J].计算机研究与发展,2004,41(10):1793-1801
关键词：XML；后缀树；后缀数组；自索引；BWT
中图分类号：TP311.13 文献标识码：A 文章编号：1674-7712 (2012) 06-0099-01
一、数据压缩知识
数据压缩技术的发展。
随着计算机技术的飞速发展，数据压缩作为解决海量信息存储和传输的支撑技术受到了人们的极大重视，对数据压缩算法的研究也不仅局限于信息论中有关信源编码的范畴，数字图像信号、语音信号的分析和处理等技术被大量引入到有关的研究领域。
1977年，两位以色列科学家Jacob Ziv和Abraham Lempel发表了名为“A Universal Algorithm for Sequential Data Compression”（顺序数据压缩的通用算法）的论文，提出了一种不同与以往的基于字典的压缩方法——LZ77，他们在1978年又提出了LZ77的改进算法——LZ78，这两个算法吧数据压缩的研究推向了一个全新的阶段。1984年，Terry Weleh发表的论文“A Technique for High Performance Data Compression”（高性能数据压缩技术）描述了对LZ78算法的改进和具体实现技术，成为LZW算法。目前，无损数据压缩领域中流行的数据压缩方法多是基于字典的压缩技术。UNIX系统上的一个实用压缩软件COMPRESS和Windows系统下的压缩软件Winzip和Winrar中所使用的压缩算法都是基于字典压缩技术的。
当数据压缩被用于减少存储空间时，可以减少程序的总执行时间。这是因为存储量的减少将导致磁盘存取次数的减少，虽然数据的压缩/解压缩过程会增加额外的程序指令，但由于程序的执行时间通常少于数据的存储时间，因此中的执行时间将减少。也正因如此，数据压缩技术在计算机技术飞速发展的今天仍然有着很重要的作用。
二、XML压缩索引
（一）XML压缩背景
上文中已经述说了XML的优点，但和其它形式的数据表示相比，XML文档往往很大。因此有些时候，传输速度和存储空间会非常重要。具体来说：
1.XML是一种清晰而易用的文本标记格式，但它的弱点就是当有大量数据需要交换，而程序内部处理部分又非常少时，会导致XML文档非常大，这样过大的空间占用意味着更大的处理代价；
2.由于本文压缩算法多年来一直是大量研究项目的课题，目前已经非常成熟。这种类型的算法都能方便的将XML进行压缩，但将XML文本作为一般文本文件进行压缩，这类算法都不大可能改善处理的速度，而且还会增加了解压后再解析的步骤；
3.我们把XML文档用于索引结构，这样就不能只保持了XML文档的结构而无法对XML进行索引搜索。也就排除了一些简单的XML压缩算法。
（二）XML压缩方法
当压缩文档时，通常首先考虑常用的压缩算法，如：Lempel-Ziv和Huffman，以及在它们上面实现变化的一些常用实用程序。在类Unix平台上通常是gzip；在其它平台上，zip更为常用，比如：PKZIP、Info-ZIP和WinZip。但这些实用程序实际上意在充分地减少XML文件的大小。但是，都没有保持了XML文档的结构，或是无法对XML文档进行索引。这样本文选择使用BWT压缩算法而不是顺序Lempel-Ziv算法。
（三）BWT数据压缩
利用BWT压缩算法，我们先把字符文本进行转换，然后进行压缩，这样就解决了XML文档过大的弊端。而且BWT压缩算法要比顺序LZ算法，解压时速度有所提高。BWT算法的具体介绍我们在第5章进行讲解。
三、系统设计
（一）XML文件整体输出
首先，我们先不考虑XML文件的结构，这样把XML数据文件提交给程序，会按照普通文本文件的方式进行处理。程序先读取整个文件的内容，之后将它们作为一个字符串，进行后缀数组排序，然后BWT转换。但是这样的结果并不如意，有以下两个缺点：
1.程序执行的效率不高，文件内容如过大，导致整体的速度下降；
2.不便于查找，整体进行排序换转后打乱了文件结构，不能成为索引；
（二）以XML文件结构进行输出
由于不能破坏XML文件的结构，只能按照XML现有的标签内容进行。这样我们就引入了XML解析器，它可以分析出XML文件的结果和具体内容。先用解析器解析XML文件，我们就方便的判断出，什么是标签，什么是数据。把每个标签或者数据，单独进行排序转换。
具体过程：
1.XML解析器读取分析XML文件；
2.建立一个空的XML文件，进行添加排序转换后的数据；
3.如分析出标签开始，则提取此标签，对其进行排序转换，把结果插入新的XML文件；并记住此标签的级别，用于插入下级标签时使用；
4.如分析出数据，则对数据进行排序转换，并直接把新数据插入包含它的标签中；
5.如分析出标签结束，则关闭此级标签，结束数据转换；并记录新的标签级别，用于插入平级标签时使用。
参考文献：
[1]Donald Knuth.Art of Computer Programming[M].2002,Volume,3
[2]N.Jesper Larsson.Structures of String Matching and Data Compression[D].Sweden:Lund University,1999
[3]包小源,宋再生,唐世渭,楊冬青,王腾蛟.SuffIndex——一种基于后缀树的XML索引结构[J].计算机研究与发展,2004,41(10):1793-1801