Data Compression

Lossless compression reduces file size without any loss of information, allowing the original data to be perfectly reconstructed from the compressed version. This is critical for text, source code, databases, and any application where data integrity is non-negotiable.

• Mechanism: Exploits statistical redundancy (e.g., repeated patterns, common characters).
• Common Algorithms: DEFLATE (used in ZIP, gzip, PNG), LZ77/LZ78, Lempel–Ziv–Welch (LZW), Brotli, Zstandard.
• Use Cases: Software distribution, medical imaging (DICOM), legal documents, version control systems (Git).
• Limitation: Compression ratio is bounded by the entropy of the source data.

Lossy compression achieves significantly higher compression ratios by permanently discarding information deemed less important to human perception or the specific application. The decompressed data is an approximation of the original.

• Mechanism: Utilizes perceptual models or domain-specific tolerances (e.g., human visual/auditory systems).
• Common Algorithms & Formats: JPEG (images), MP3 (audio), H.264/HEVC (video), Ogg Vorbis (audio).
• Use Cases: Streaming media, web images, telephony, and any scenario where perfect fidelity is less critical than bandwidth or storage savings.
• Trade-off: Controlled by a quality parameter that adjusts the degree of information loss versus file size.

Run-Length Encoding (RLE) is a simple, lossless compression technique that replaces sequences of identical data elements (runs) with a single data value and a count. It is most effective on data with many long runs.

• Mechanism: Scans data linearly, encoding runs as (count, value) pairs.
• Example: The string AAAAABBBCCCC compresses to 5A3B4C.
• Use Cases: Early bitmap image formats (BMP, PCX), fax transmission (CCITT Group 3/4), simple data streams with low entropy.
• Limitation: Can inflate file size if data lacks repeated sequences (high entropy).

Dictionary coding is a lossless compression paradigm where sequences of data are replaced by references to an earlier occurrence stored in a "dictionary." The Lempel-Ziv (LZ) family of algorithms is the most prominent implementation.

• Mechanism: The encoder builds a dictionary of previously seen strings; repeated occurrences are replaced with a (distance, length) pointer to the dictionary entry.
• Key Algorithms: LZ77 (sliding window), LZ78 (explicit dictionary), and their derivatives like LZSS, LZW, and DEFLATE.
• Use Cases: Foundation for universal compression in formats like ZIP, gzip, PNG, and HTTP compression.
• Characteristic: Adaptive, building the dictionary on-the-fly from the data being compressed.

Entropy encoding is a final, lossless stage in compression that assigns variable-length codes to symbols based on their probability of occurrence. More frequent symbols get shorter codes, minimizing the average code length.

• Huffman Coding: Generates an optimal prefix code via a frequency-sorted binary tree. Used in DEFLATE, JPEG, and MP3.
• Arithmetic Coding: Encodes an entire message into a single fractional number, achieving compression closer to the theoretical entropy limit. Used in high-efficiency codecs like H.265/HEVC.
• Use Case: The ubiquitous backend for nearly all modern compression schemes, following initial redundancy reduction steps.

Transform-based compression is a core technique in lossy codecs that converts data (like image blocks or audio samples) from the spatial/time domain into a frequency domain representation, where perceptual irrelevancy is more easily identified and discarded.

• Discrete Cosine Transform (DCT): Used in JPEG and MPEG video standards. Concentrates signal energy into fewer coefficients.
• Wavelet Transform: Used in JPEG 2000 and modern audio codecs. Provides multi-resolution analysis, often superior to DCT.
• Mechanism: After transformation, high-frequency coefficients (representing fine details less perceptible to humans) are quantized more aggressively or zeroed out, achieving compression.