Algorithms for Data Compression Based on Grammars and Trees

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

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.