Compression

Lossless compression algorithms

• Burrows-Wheeler transform. Preprocessing useful for improving lossless compression.
• Deflate. Data compression used by ZIP.
• Delta encoding. Aid to compression of data in which sequential data occurs frequently.
• Incremental encoding. Delta encoding applied to sequences of strings.
• LZW. (Lempel-Ziv-Welch). Successor of LZ78. Builds a translation table from the data to compress. Is used by the GIF graphical format.
• LZ77 and 78. The basis of further LZ variations (LZW, LZSS, ...). They are both dictionary coders.
• LZMA. Short for Lempel-Ziv-Markov chain-Algorithm.
• LZO. Data compression algorithm that is focused on speed.
• PPM (Prediction by Partial Matching). Adaptive statistical data compression technique based on context modeling and prediction.
• Shannon-Fano coding. Constructs prefix codes based on a set of symbols and their probabilities.
• Truncated binary. An entropy encoding typically used for uniform probability distributions with a finite alphabet. Improve binary encoding.
• Run-length encoding. Primary compression that replaces a sequence of same code by the number of occurences.
• Sequitur. Incremental grammar inference on a string.
• EZW (Embedded Zerotree Wavelet). Progressive encoding to compress an image into a bit stream with increasing accuracy. May be lossy compression also with better results.

Entropy encoding

Coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols .
• Huffman coding. Simple lossless compression taking advantage of relative character frequencies.
• Adaptive Huffman coding. Adaptive coding technique based on Huffman coding.
• Arithmetic coding. Advanced entropy coding.
• Range encoding. Same as arithmetic coding, but looked at in a slightly different way.
• Unary coding. Code that represents a number n with n ones followed by a zero.
• Elias delta, gamma, omega coding. Universal code encoding the positive integers.
• Fibonacci coding. Universal code which encodes positive integers into binary code words.
• Golomb coding. Form of entropy coding that is optimal for alphabets following geometric distributions.
• Rice coding. Form of entropy coding that is optimal for alphabets following geometric distributions.

Lossy compression algorithms

• Linear predictive coding. Lossy compression by representing the spectral envelope of a digital signal of speech in compressed form.
• A-law algorithm. Standard companding algorithm.
• Mu-law algorithm. Standard analog signal compression or companding algorithm.
• Fractal compression. Method used to compress images using fractals.
• Transform coding. Type of data compression for data like audio signals or photographic images.
• Vector quantization. Technique often used in lossy data compression.
• Wavelet compression. Form of data compression well suited for image and audio compression.

Posted in: Algorithm