Data Compression Part 3
The Lempel-Ziv (LZ) compression method is one of the most popular lossless storage algorithms.
DEFLATE is a variant of LZ that is optimized for decompression speed and compression ratio, although its compression speed can be very slow, PKZIP , gzip and PNG all use DEFLATE. LZW (Lempel-Ziv-Welch) was a Unisys patent until the patent expired in June 2003, this method was used for GIF images. Also worth mentioning is the LZR (LZ-Renau) method, which is the basis of the Zip method. The LZ method uses a table-based compression model, in which table entries are replaced with repeated data strings. For most LZ methods, this table is dynamically generated from the initial input data. This table is often maintained using Huffman coding (eg SHRI, LZX). A current LZ-based encoding scheme that works well is LZX , which is used in Microsoft’s CAB format.
The best compression tools use probabilistic model predictions for arithmetic coding. Arithmetic coding was invented by the Finnish information theorist Jorma Rissanen and turned into a practical method by Witten, Neal and Cleary. This approach allows better compression than the well-known Huffman algorithm and is well suited for adaptive data compression, where predictions are context sensitive. Arithmetic encoding has been used in the JBIG binary image compression standard, the DejaVu document compression standard. The Dasher text input system is a reverse arithmetic encoder.
