1 Lossless compression
Lossless compression refers to methods that allow the original data to be perfectly reconstructed from the compressed representation. These techniques exploit statistical redundancy—patterns, repeated sequences, or biased probability distributions—without any loss of information. Lossless compression is essential for text, executable files, and any application where data integrity is paramount.
1.1 Entropy and redundancy
Entropy, introduced by Claude Shannon in 1948, quantifies the average information content per symbol in a source. It sets the theoretical lower bound on the average number of bits needed to represent a symbol. Redundancy is the difference between the actual bitrate and the entropy; compression algorithms aim to eliminate redundancy.
1.1.1 Shannon's source coding theorem
Shannon's source coding theorem states that the minimum average code length achievable for a source with entropy H is arbitrarily close to H, but not less, in an error-free encoding system. This provides a fundamental limit for lossless compression: no code can compress a source to fewer than its entropy bits per symbol on average.
1.2 Dictionary-based methods
Dictionary-based methods replace repeated substrings with references to a dictionary of previously encountered strings. The dictionary can be built dynamically during encoding or predefined. These methods are effective for data with long-range repetitions, such as text and source code.
1.2.1 LZ77 and LZ78
LZ77 (Lempel–Ziv 1977) uses a sliding window to reference earlier occurrences of a string, encoded as a length-distance pair. LZ78 (1978) builds a dictionary of phrases incrementally, assigning new entries as strings are encountered. Both algorithms form the basis of many modern compressors.
1.2.1.1 Deflate and ZIP
Deflate is a combination of LZ77 and Huffman coding, implemented in the widely used gzip and ZIP archive formats. It first applies LZ77 to find repeated sequences, then compresses the resulting symbols with Huffman codes. Deflate is a de facto standard for lossless file compression on the internet.
1.2.2 Lempel–Ziv–Welch (LZW)
LZW is a variant of LZ78 that creates a dictionary of variable-length strings. Each input string is replaced by a fixed-length code, with the dictionary growing as new patterns appear. LZW was used in early GIF and TIFF image compression, as well as Unix compress.
1.3 Statistical coding
Statistical coding assigns shorter codes to more frequent symbols and longer codes to rare ones, based on the symbol probabilities. These methods directly approach the entropy bound.
1.3.1 Huffman coding
Huffman coding builds an optimal prefix-free code for a given set of symbol probabilities by constructing a binary tree where the shortest codes correspond to the most probable symbols. It is widely used in combination with other techniques (e.g., Deflate, JPEG) and is the most common entropy coder.
1.3.2 Arithmetic coding
Arithmetic coding encodes an entire sequence of symbols into a single fractional number between 0 and 1, rather than assigning individual codes to each symbol. It can achieve near-entropy compression even for skewed probabilities and is often used in high-performance compressors (e.g., in JPEG 2000, H.264).
1.3.3 Run-length encoding (RLE)
RLE replaces consecutive identical values (runs) with a pair of run length and value. It is extremely effective for data with long runs of zeros or repeated pixels, such as simple graphics and facsimile (fax) images. Combined with other methods, RLE appears in early compression formats like PCX.
1.4 Universal codes
Universal codes are designed to encode integers without needing a predefined probability distribution. They assume that smaller integers are more probable and assign shorter codewords to them. These codes are used for parameters in various compression algorithms.
1.4.1 Elias gamma and delta coding
Elias gamma coding represents a positive integer by a unary-coded length field followed by the binary representation of the number. Delta coding further reduces the length field size by encoding it with gamma coding. Both are simple universal codes used in contexts like wavelet-based compression.
1.4.2 Variable-length coding
Variable-length coding (VLC) is a general term for any code where codewords have different lengths. VLCs are designed to match symbol statistics; examples include Huffman codes and universal codes. In multimedia standards, VLC tables are often fixed (e.g., in MPEG-2) or adaptively derived.
2 Lossy compression
Lossy compression reduces data size by discarding perceptually less important information, enabling much higher compression ratios than lossless methods. It is widely used for images, audio, and video, where exact reconstruction is not required for human perception.
2.1 Rate–distortion theory
Rate–distortion theory, developed by Shannon, studies the trade-off between compression rate and allowable distortion. It defines the minimum rate needed to achieve a given distortion level, guiding the design of lossy compressors.
2.1.1 Distortion measures (MSE, PSNR)
Common distortion measures include mean squared error (MSE) and peak signal-to-noise ratio (PSNR). MSE computes the average squared difference between original and reconstructed samples; PSNR (in dB) is derived from MSE relative to the maximum signal value. Both are simple to compute but only loosely correlate with perceptual quality.
2.2 Transform coding
Transform coding converts correlated data into a frequency or spatial-frequency domain, where energy is concentrated in a few coefficients. Quantizing or discarding low-energy coefficients yields compression with minimal perceptual impact.
2.2.1 Discrete cosine transform (DCT)
The DCT represents a signal as a sum of cosine functions of different frequencies. It is highly effective at decorrelating natural images, concentrating energy in low-frequency coefficients. The DCT is the core of JPEG, MPEG, and many other compression standards.
2.2.2 JPEG image compression
JPEG (Joint Photographic Experts Group) uses a block-wise DCT on 8×8 pixel blocks, followed by quantization and Huffman/arithmetic coding. Quantization tables are tuned for human visual sensitivity. JPEG achieves typical compression ratios of 10:1 to 20:1 with good perceptual quality.
2.2.3 MPEG video compression
MPEG standards (e.g., MPEG-1, MPEG-2, MPEG-4) combine intra-frame DCT coding with inter-frame motion compensation. Key frames (I‑frames) are compressed like JPEG, while predicted (P) and bidirectional (B) frames store only differences, substantially reducing bitrate.
2.3 Predictive coding
Predictive coding exploits correlation between successive samples by transmitting the difference between the actual value and a predicted value, which typically has lower entropy. It is fundamental to lossless and lossy compression.
2.3.1 Differential pulse-code modulation (DPCM)
DPCM encodes the difference between each sample and a linear prediction based on previous samples. The differences are then quantized and coded. Simple DPCM is used in some audio codecs and image codecs like JPEG‑LS.
2.3.2 Adaptive DPCM
Adaptive DPCM adjusts the predictor coefficients or quantizer step size based on local signal statistics. This improves performance for non‑stationary signals (e.g., speech) and is found in adaptive differential pulse‑code modulation (ADPCM) used in telephony.
2.4 Quantization
Quantization maps continuous or high‑precision values to a finite set of discrete levels, introducing irreversible information loss. It is the primary source of distortion in lossy compression.
2.4.1 Scalar vs vector quantization
Scalar quantization quantizes each sample independently, using a fixed number of levels. Vector quantization (VQ) groups multiple samples into a vector and maps it to the nearest codeword from a codebook. VQ can achieve lower distortion at the same rate but is more computationally complex.
2.4.2 Lloyd–Max algorithm
The Lloyd–Max algorithm iteratively optimizes a scalar quantizer for a given probability distribution by minimizing the mean squared error between input and output. It determines optimal decision boundaries and reconstruction levels, used in early speech coding and image compression.
3 Applications and standards
Many file formats and standards incorporate compression techniques to reduce size. These range from general‑purpose archive formats to specialized codecs for media.
3.1 Archive formats (ZIP, gzip, 7z)
ZIP (based on Deflate) is the most widely adopted lossless archiver on personal computers. gzip is the GNU version of Deflate, common in Unix/Linux for compressing single files. 7z, using LZMA (an LZ77 variant with range coding), achieves higher ratios but at slower speeds.
3.2 Image formats (PNG, JPEG, WebP)
PNG (Portable Network Graphics) uses Deflate (LZ77 + Huffman) for lossless compression, supporting 24‑bit color and transparency. JPEG, as described, is the dominant lossy format for photographs. WebP, developed by Google, supports both lossy (VP8 intra‑coding) and lossless modes and often yields smaller sizes than JPEG and PNG.
3.2.1 GIF and palette‑based compression
GIF (Graphics Interchange Format) uses LZW compression on palette‑indexed images (up to 256 colors). It supports simple animations and transparency but is limited in color depth. Despite its age, GIF remains popular for memes and short loops on the internet.
3.3 Audio compression (MP3, AAC, FLAC)
MP3 (MPEG‑1 Audio Layer 3) uses Huffman coding and a psychoacoustic model to discard inaudible frequencies. AAC (Advanced Audio Coding) improves quality at similar bitrates. FLAC (Free Lossless Audio Codec) uses linear prediction and Rice coding for lossless audio.
3.3.1 Perceptual coding and psychoacoustic models
Perceptual coding exploits the human auditory system’s limited sensitivity, masking weaker sounds by louder ones. Psychoacoustic models compute masking thresholds and shape the quantization noise so that it remains inaudible, enabling high compression ratios (e.g., 10:1 or more) for music.
3.4 Video compression (H.264, HEVC, AV1)
H.264/AVC, HEVC (H.265), and AV1 are modern video codecs that combine DCT residuals, motion compensation, and entropy coding. H.264 is ubiquitous in Blu‑ray and streaming; HEVC offers 50% bitrate savings; AV1, an open standard, provides competitive performance and is used by major streaming platforms.
3.4.1 Motion estimation and compensation
Motion estimation finds the best matching block in a reference frame, producing motion vectors. Motion compensation uses these vectors to reconstruct predicted frames. This inter‑frame technique removes temporal redundancy and is the key to high video compression efficiency.
4 Performance evaluation
Compression algorithms are assessed by several criteria, including ratio, speed, and quality. The choice of method depends on the application’s constraints.
4.1 Compression ratio and bitrate
Compression ratio is defined as the size of uncompressed data divided by compressed size. Bitrate (bits per sample or per second) is used for streaming media. Higher ratios (or lower bitrates) indicate better compression, but often at the cost of quality or speed.
4.2 Speed and memory trade‑offs
Encoder/decoder speed and memory usage vary widely. Simple RLE or dictionary methods run quickly, while heavy arithmetic coding or transform stages increase computational load. Real‑time video requires highly optimized codecs, whereas offline archiving can afford slower compression for higher ratios.
4.3 Objective metrics (bitrate, distortion)
Objective metrics such as PSNR and SSIM (structural similarity) quantify distortion and are used alongside bitrate to compare codecs. Rate–distortion curves plot achievable quality at given bitrates, enabling fair comparisons between different algorithms and parameter settings.