Data compression

Data compression is the process of encoding information using fewer bits than the original representation, aiming to reduce the storage space required or the bandwidth needed for transmission.

Overview and Fundamentals

At its core, data compression exploits statistical redundancy and perceptual irrelevance present in most data. Statistical redundancy refers to patterns, repetitions, or predictable structures within the data that can be represented more efficiently. Perceptual irrelevance, primarily used in lossy compression of multimedia data like images, audio, and video, involves the removal of information that is not easily perceptible to human senses. The primary goal is to create a compact representation of the original data, which can be reconstructed either exactly (lossless compression) or approximately within acceptable limits (lossy compression). The effectiveness of a compression algorithm is typically measured by the compression ratio, which is the size of the original data divided by the size of the compressed data. Other important metrics include the speed of compression and decompression and the computational resources required.

Lossless Compression

Lossless compression algorithms allow the exact original data to be reconstructed from the compressed data. This is essential for applications where data integrity is paramount, such as text documents, source code, databases, and executable files. Common techniques include:

• Run-Length Encoding (RLE): Replaces sequences of the same data value (runs) with a single data value and a count. It is simple and effective for data with many such runs, like simple graphic images.
• Dictionary Coders: These algorithms build a dictionary of data sequences from the input and replace recurring sequences with references to the dictionary. Prominent examples include the Lempel-Ziv (LZ) family of algorithms, such as LZ77 and LZ78, which form the basis for widely used formats like GIF, ZIP (using DEFLATE, which combines LZ77 and Huffman coding), and PNG.
• Entropy Encoding: This technique assigns shorter codes to more frequent symbols and longer codes to less frequent symbols, aiming to reach the theoretical minimum code length defined by the source's entropy. Key methods include Huffman coding and arithmetic coding. These are often used as a final step in combination with other algorithms (e.g., in JPEG for compressing coefficients after transformation).

Lossy Compression

Lossy compression reduces file size by permanently eliminating certain information, especially information deemed redundant or less important to human perception. The decompressed data is an approximation of the original. This is predominantly used for multimedia data where perfect fidelity is not required.

• Transform Coding: The data is transformed from the spatial or time domain into another domain (like frequency) where it is easier to identify irrelevant information. The most common example is the Discrete Cosine Transform (DCT) used in JPEG image compression and MPEG video coding. The transformed coefficients are quantized (reduced in precision), which is the primary lossy step.
• Perceptual Coding: This approach explicitly models human sensory perception to discard data that will not be noticed. For example, in audio compression (MP3, AAC), algorithms exploit auditory masking effects where a loud sound can make a simultaneous quieter sound inaudible. In video, temporal masking and spatial masking are similarly exploited.
• Chrominance Subsampling: Used in image and video compression (e.g., JPEG, MPEG), this technique reduces the resolution of color information (chrominance) more than the brightness information (luminance), as the human eye is less sensitive to color details.

Applications and Formats

Data compression is ubiquitous in modern computing and telecommunications.

• File Archiving: Tools like ZIP, RAR, and 7-Zip use lossless compression to bundle and reduce the size of collections of files for storage or transfer.
• Multimedia Storage and Streaming: Image formats like JPEG (lossy) and PNG (lossless); audio formats like MP3, AAC (lossy), and FLAC (lossless); and video formats like H.264/AVC, HEVC, and AV1 (lossy) all rely heavily on sophisticated compression to make digital media practical.
• Communication Systems: Compression is vital for efficient data transmission over networks, from modem protocols in the past to modern voice-over-IP (VoIP) and video conferencing, reducing bandwidth requirements.
• Databases and Operating Systems: Compression is used internally to save storage space and improve I/O performance.

Theoretical Limits and Trade-offs

The theoretical limit for lossless compression of a given data source is defined by its Shannon entropy, which represents the average minimum number of bits needed to represent each symbol. No algorithm can compress arbitrary data beyond this limit without loss. Lossy compression does not have a single theoretical limit, as it involves a trade-off between the bit rate (compressed size), the distortion (loss of fidelity), and the complexity of the encoding/decoding algorithms. This is often formalized by rate-distortion theory. In practice, choosing a compression method involves balancing these factors: compression ratio, speed, resource usage, and, for lossy methods, the acceptable level of quality degradation.