| The concept of context-free grammar-based coding, in short, is to use context-free grammars for data compression. In a context-free grammar-based code, a data sequence to be compressed is first transformed into a context-free grammar from which the sequence can be fully recovered, and then compressed indirectly by using an arithmetic code to encode the context-free grammar. This thesis presents the transition from context-free grammar-based coding to context-dependent grammar-based coding.; In the first half of this thesis, we revisit context-free grammar-based codes by reexamining their redundancy and further investigating their compression performance for sources with countably infinite alphabets.; Redundancy. In the literature, the compression performance of context-free grammar-based codes for sources with finite alphabets was evaluated against that of the best arithmetic coding algorithm with finite contexts. In this research, we first define semi-Markov sources and semi-finite-state sources. Based on the definition of semi-finite-state sources and the idea of run-length encoding, we then propose two-step run-length encoding (TSRLE) algorithms with finite contexts. It is proved that for any individual sequence, the best compression rate given by TSRLE algorithms with k contexts is no greater than the best compression rate among all arithmetic coding algorithms with k contexts, where k is a finite positive integer. Furthermore, it is shown that there exist stationary, ergodic semi-Markov sources for which the best TSRLE algorithms without any context outperform the best arithmetic coding algorithms with any finite number of contexts. By evaluating the compression performance of context-free grammar-based codes for sources with finite alphabets against TSRLE algorithms with k contexts, a redundancy result stronger than all previous corresponding results is established in this thesis. (Abstract shortened by UMI.)... |
