【作者】 冯静；

【导师】 金远平；

【作者基本信息】 东南大学 ， 计算机应用技术， 2006， 硕士

【摘要】 随着信息时代的到来,人们面对着与日俱增的庞大信息,对其存储和处理均有一定的困难。故对数据采用压缩技术,实现数据约简,具有重大的研究价值和实践意义。从信息冗余类型角度考虑,数据压缩技术分为语法压缩和语义压缩。语法压缩基于数据统计,减少数据冗余;语义压缩基于语义,减少内容冗余。从压缩的角度考虑,数据分为数值型数据与非数值型数据。在很多实际应用场合,都会产生大型数据表,可用二维表结构来逻辑表达的数据,也称结构化的数值性数据。语法压缩被建议用于处理非数值型数据,如文字,图像,音视频等,而如果用于处理大型数据表,不能提供较理想的解决方案。现在人们研究如何将语义压缩用于大型数据表。语义压缩是指发掘数据中语义模型,揭示数据中蕴含的含义,潜在的关联,并运用到数据压缩过程中。语义压缩一般属于有损压缩,即允许一定的误差存在。在关于大型数据表的语义压缩方法的研究中,现有的一些语义压缩方法,如Fascicles、ItCompress、SPARTAN等,在灵活性和压缩性能方面存在一定的缺陷性。本文根据实际数据特性,提出一种双向语义压缩框架(Bidirectional Semantic Compression, BSC),以及由此衍生的三种压缩算法,并进行了实验验证。BSC结合了列方式压缩和行方式压缩,综合分析了各种数据特性,如相关关系、时序性等,采用不同的压缩策略。如数据属性线性相关关系明显,选用主成分分析—聚类分析压缩算法;如线性相关关系不明显,而数据又不存在时序性,选用预测模型分析—聚类分析压缩算法;如线性相关不明显,而数据具有时序性,选用预测模型分析—时序分析算法。由BSC框架中衍生出的三种压缩算法,实验证明了算法的适用性较好,压缩效率要优于其它语义压缩算法。采用以上提到的相应的压缩算法,在给定允许误差范围内,对原数据表进行重新组织,制定压缩计划。压缩计划采用了XML语言的形式。更多还原

【Abstract】 Along with the coming of information epoch, people are facing a huge amount of information, which is increasing rapidly and momently. Compressing the data to store them efficiently therefore becomes more and more important both theoretically and practically.There are two techniques for data compression. The first one is statistics-based and it decreases the numeral redundancy in the data. The second one is semantic-based and it decreases the content redundancy in the data.From the point of view of compression, data can be classified as non-numerical and numerical data. Effective exploratory analysis of massive, high-dimensional tables of data, which is viewed as structured numerical data, is a ubiquitous requirement for a variety of application environments.The first data compression methods have been proposed for non-numerical data, such as text corpora and multimedia data. These methods, however, fail to provide adequate solutions for compressing structural numerical data, as they view the table as a large byte string and do not account for the complex dependency patterns in the table. For the structural numerical data, people propose the semantic compression theory. The semantic compression explores the semantic model, reveals the connotative signification and latent relationship, which are applied to compression algorithm. In a general way, semantic compression belongs to the lossy compression, and grants the prescribed error bounds.The research of the paper is on the semantic compression algorithms for massive data tables. The existing semantic compression methods have some disadvantages in adaptability and performance. The paper proposes a Bidirectional Semantic Compression (BSC) framework that takes advantage of data characteristic and data-mining models to perform lossy compression for massive data tables.BSC integrates the column-wise compression and the row-wise compression, analyze all kinds of data characteristics, such as linear correlation and time-serials property, and exploit different compression strategies.If there are evident linear correlation among attributes of the data table, BSC exploits the PCA-Clustering compression algorithm; If there aren’t evident linear correlation among attributes of the data table, and the data haven’t the time-serials property, BSC exploits PMA-Clustering compression algorithm; If there aren’t evident linear correlation among attributes of the data table, and the data have the time-serials property, BSC exploits PMA-TS compression algorithm.Extensive experiments were conducted and the results indicate the superiority of BSC over previously known techniques.The original data tables are reorganized by the compression methods mentioned above, within the prescribed error bounds, resulting in the compression plan described in the form of XML.更多还原