Data compression techniques

Data compression is the process of encoding data using fewer bits than the original representation, to reduce storage space and transmission time. Decompression restores the data.

Classification of techniques

1. Lossless compression: the original data is recovered exactly. Used for text, programs, medical images.

• Entropy encoding (statistical):
  • Run-length encoding (RLE): a run of repeated symbols is replaced by the symbol and its count. "AAAABBB" becomes 4A3B.
  • Huffman coding: frequent symbols get short codes, rare symbols get long codes.
  • Arithmetic coding: the entire message is encoded as one number in the range 0 to 1.
• Dictionary based: LZW and LZ77 replace repeated strings with dictionary references. Used in GIF, ZIP.

2. Lossy compression: some information is permanently discarded, which gives much higher compression. Used for images, audio, video.

• Prediction based: DPCM, delta modulation store differences between predicted and actual values.
• Transform based: DCT or wavelet transform concentrates energy in few coefficients, then small ones are quantized away. Used in JPEG.
• Vector quantization: blocks of samples are replaced by the nearest code word from a codebook.
• Perceptual coding: uses psychoacoustic or psychovisual models to drop what humans cannot notice (MP3).

3. Hybrid compression: combines both, for example JPEG (DCT + quantization + RLE + Huffman) and MPEG (motion compensation + DCT + Huffman).