## Saturday, 18 June 2011

### 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.
• 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.