面向Ziv-Lempel压缩文本的多查询处理技术

摘要

随着计算机技术的飞速发展和信息化的推进，全球的数据量正在以指数的趋势迅猛增长，而不断增长的数据集对数据查询提出很多新问题，对计算机内存的要求也越来越高，很多情况下，数据集已经无法完全被载入计算机内存了。因此，近些年来对数据压缩以及在压缩数据上进行查询逐渐成为一个全新的研究热点。另外，查询又分单一查询和多查询。在压缩数据上的单一查询已有很多人在这方面做出了突出的贡献，然而在压缩数据上的多查询处理技术至今仍是空白，但是这一处理技术在拼写检查、指纹识别、信息检索、生物计算等诸多领域中都扮演着重要的角色，因此，研究高效的面向压缩数据的多查询处理技术迫在眉睫。
　　本文研究了在Ziv-Lempel压缩文本上的多查询处理技术，开创了这一领域的先例，为后人进行压缩数据上的多查询处理技术的研究奠定了一定的基础。由于大规模系统应用中部分查询之间具有相关性特性，根据这一特性，针对Ziv-Lempel压缩数据，提出了一种多查询处理技术。通过分析多查询之间的相关性，提出了新的公共子串定义，让公共子串满足一定的长度和出现次数。提出提取公共子串的算法以及有效地过滤重复或者存在包含关系的公共子串。基于提取的公共子串，在压缩文本中快速定位多个查询，构造候选集，并加以校验。这种利用公共子串代表多个查询的方法可以大大减少查询代价，从而提高多查询处理技术的效率。
　　最后，在真实数据集上评估了提出的多查询处理技术的性能。实验结果显示，提取公共子串的方法能够快速、高效地获得公共子串集合，过滤掉冗余的公共子串。同时，多查询处理技术能够提供快速、高效的查询性能。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．2 面临的挑战及本文贡献

1．3 本文的组织结构

第2章 相关工作

2．1 经典的压缩方法简介

2．1．1 BWT变换算法

2．1．2 MTF变换算法

2．1．3 Ziv-Lempel系列压缩算法

2．1．4 RLE压缩算法

2．1．5 哈夫曼编码

2．2 本章小结

第3章 背景知识及问题定义

3．1 LZ索引

3．1．1 正向trie结构

3．1．2 反向trie结构

3．2 问题定义

3．3 本章小结

第4章 多查询串相关性分析

4．1 公共子串

4．2 公共子串提取算法

4．3 基于公共子串的过滤策略

4．4 本章小结

第5章 多查询处理技术

5．1 基于公共子串的多查询处理技术

5．2 多查询处理算法

5．2．1 算法描述

5．2．2 校验候选集

5．2．3 还原文本子串

5．3 本章小结

第6章 实验测试与分析

6．1 实验环境

6．2 查询长度与查询时间的关系分析

6．3 参数与查询时间的关系分析

6．4 提取公共子串的时间

6．4．1 查询长度与提取公共子串的关系分析

6．4．2 参数与提取公共子串的关系分析

6．5 数据集大小与查询时间的关系分析

6．5．1 数据集大小与提取公共子串方法未改进之前的查询时间的关系分析

6．5．2 数据集大小与提取公共子串方法被改进之后的查询时间的影响

6．6 本章小结

第7章 结论

7．1 本文总结

7．2 工作展望

参考文献

致谢

攻硕期间发表的论文及参与的项目