Algorithms for Data Compression Based on Grammars and Trees

现代数据存储和数据传输系统可以同时处理各种类型的数据，包括文本、音频、图像、体积和视频数据。在这些系统中需要数据压缩，以便有效地利用有限的可用内存和带宽，同时满足消费者对数据传送服务的灵活性的需求。为了满足这一需求，本研究试图开发无损和有损数据压缩的创新算法。人们寻找适合于一般数据结构的压缩算法，以推断和利用数据中的关系来达到压缩目的。研究将集中在一种称为基于语法的压缩器的数据压缩器上。基于语法的压缩器使用语法来表示数据中的关系，从而语法的产生规则描述如何准确或近似地重构数据。数据压缩是通过使用约简规则将该文法或其关联的派生树缩减为更紧凑的形式来实现的。研究的具体目标是获得基于语法的压缩器，它能够处理一般数据结构(包括数据树、2-D和3-D数据以及其他规则结构)，能够以线性的时间和空间复杂度处理数据，提供良好的最大冗余性能，并且与其他通用压缩器相比具有通用性和良好的性能。重点将放在寻找健壮的基于语法的压缩器，其产生接近最先进的压缩性能，而不管它们应用于哪种类型的数据。

Modern data storage and data transmission systems cansimultaneously process data of various types, including text,audio, image, volumetric and video data. There is a need fordata compression in these systems, in order that efficient usemay be made of the limited amount of memory and bandwidth thatis available, while meeting the consumer's demand forflexibility in data delivery services. In order to satisfythis need, this research seeks to develop innovative algorithms for both lossless and lossy data compression. Compression algorithms are sought, which adapt themselves to general data structures, inferring and exploiting relationships in the data for compression purposes.The research will focus upon a type of data compressor called a grammar based compressor. A grammar based compressorrepresents relationships in the data using a grammar, so thatthe production rules of the grammar describe how the data is to be exactly or approximately reconstructed. Data compression is achieved by reducing this grammar or itsassociated derivation tree to a more compact form, through theuse of reduction rules. The specific goals of the research areto obtain grammar based compressors which are capable ofhandling general data structures (including data trees, 2-D and 3-D data, and other regular structures), which process data with linear time and space complexity, which provide goodmaximal redundancy performance, and which are universal andperform well with respect to other universal compressors.Grammar based compressors with good theoretical properties shall be tested by means of computer experiments on real data,and comparisons shall be made with state of the art compression systems. Emphasis will be placed on finding robust grammar based compressors, which yield near state of the art compression performance regardless of the type of data towhich they are applied.