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.