Saturday, 18 June 2011

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.


0 comments:

Post a Comment