Rule reduction—A method to improve the compression performance of grammatical compression algorithms

Many compression algorithms use Huffman codes or arithmetic codes for coding the output of a preceding redundancy reduction step. The technique presented here connects these usually separated steps in order to improve the overall compression performance. Estimating the code word length for each output symbol of the redundancy reduction algorithm, it is checked whether using a specific structure found in the first step yields an overall improvement in compression or not. Hence some structures found in the first step are discarded in the final representation of the data. This improves the compression performance since the final length of the code words is taken into account. Empirical test results showing the beneficial aspects of rule reduction are presented for a grammatical compression algorithm based on the so-called Sequential algorithm.