Techniques for Specialized Data Compression

Background

The base technique of data compression, that is included in most contemporary compression methods, is statistical coding. It uses statistics of occurrence of respective symbols in the input stream to minimize the size of the output stream. The most widely-used technique of this kind is Huffman coding, which assigns short codewords to frequent input symbols, and long codewords to rare symbols (Huffman, 1952). The Huffman coding is optimal in the sense that no other codeword assignment could produce shorter output stream. Further improvement is still possible by assigning value ranges, instead of individual codewords, to input symbols. Such approach is taken by the arithmetic coding, where the entire input stream is encoded with a binary fraction representing its cumulative probability (Rissanen, 1976).

Most real-world data types exhibit some form of correlation between symbols within them, which cannot be exploited by mere counting occurrences of individual symbols in the input stream. There are three popular types of solutions to this problem. The first (also historically) exploits the idea of grouping input symbols into phrases, which are treated in a way similar to the other input symbols. One approach of this kind (represented, e.g., by Deflate) uses the processed input stream buffer as a dictionary (Ziv & Lempel, 1977) whereas another (represented, e.g., by LZW) maintains an explicit phrase dictionary (Ziv & Lempel, 1978). Although solutions of this type do not achieve superior compression ratios, due to their modest usage of resources, they became the standard of general-purpose compression, used commonly in compression utilities, such as PKZip, gzip, 7-Zip, or WinRar, proprietary container formats, such as CDR, CHM, JAR or SWF, and in various data transmission protocols.