Low Complexity Parametrized Codes for LZ77 Compression

Abstract

In the LZ77 compressors family the compression ratio can be increased in two possible ways: first, by better parsing of the input data into distance, length pairs and literal characters, and second, by better encoding of the result of the parsing. The parsing can be enhanced by increasing the size of the sliding window and by using sophisticated parser heuristics to decide which match to take and which to discard. This topic was studied by several people already and is beyond the scope of this paper. The efficiency of coding depends on how good estimates we can give on the probabilities of the distance, length and literal values. The most widely used LZ77 derivatives use a semi-static approach with Huffman coding. This requires two passes over the input data and the transmission of the codetables along with the compressed data, too. In this paper I investigate the case where constraints are on processing power and memory at the decompressor side. Having a certain parser, we want to code the distance, length pairs and literal characters as effectively as possible. Because of the constraints I omit arithmetic code and also omit Huffman code. Codes for representing integers of an assumed distribution (with exponentially decaying overall behaviour) are already proposed by several researchers. These codes are simple, require no additional memory but can adapt only in a restricted way or not at all to the actual distribution of the values. Thus they only perform well if the actual distribution is `near´ to the assumed one. I will present a new family of codes that keep the simplicity of the already known codes but can adapt better to the actual distribution through a few integer parameters. As the distribution is still assumed to have exponentially decaying tendency these codes perform well encoding the distance and length values, but usually are not suitable for the literal characters.