Data compression · aiwiki.page

Data compression is the process of encoding data in a representation intended to require fewer bits than its original form. An encoder produces the compressed representation, and a decoder reconstructs either the original data or an approximation. Compression reduces storage requirements and the amount of data transmitted through communication systems. Its two principal categories are lossless compression, which preserves data exactly, and lossy compression, which permits specified differences between the original and reconstructed data. In information theory, compression is studied as source coding. (ocw.mit.edu)

Principles and theoretical limits

Compression exploits structure: unequal symbol frequencies, repeated sequences, or dependencies between neighboring values. A representation that assigns every symbol the same number of bits may waste space when some symbols are much more common than others. Effective compression replaces this representation with one adapted to the source’s probability distribution. The relevant structure need not be obvious to a human reader; it can emerge through statistical modeling. (ocw.mit.edu)

For a discrete random variable $X$ , its information entropy is

H(X)=-\sum_x p(x)\log_2 p(x),

where $p(x)$ is the probability of symbol $x$ . Entropy measures average uncertainty in bits. For independent, identically distributed symbols, the source coding theorem establishes an asymptotic compression limit related to this quantity. For sources with dependencies, the entropy rate accounts for uncertainty remaining after earlier symbols are known. (ocw.mit.edu)

No lossless algorithm can shorten every possible input. There are $2^n$ binary strings of length $n$ , but only $2^n-1$ binary strings of shorter lengths, including the empty string. Exact recovery therefore requires some inputs to remain the same size or become larger. This counting argument also explains why arbitrary data cannot be compressed indefinitely by repeatedly applying a compressor. Format headers and coding tables can further increase the size of short or poorly compressible inputs. (rfc-editor.org)

Lossless compression

Lossless data compression reconstructs the original input bit for bit. It is appropriate when alterations would change the meaning or usability of the data. Two important families of techniques are statistical coding, which exploits unequal probabilities, and dictionary coding, which exploits recurring sequences. Practical systems frequently combine them. (w3.org)

Huffman coding constructs a variable-length prefix code: no codeword is the beginning of another codeword, allowing unambiguous decoding without separators. More probable symbols generally receive shorter codewords. For a specified symbol distribution, Huffman coding minimizes average length among binary prefix codes that encode those symbols individually. This does not make it optimal among all possible compression methods. (ocw.mit.edu)

Arithmetic coding represents a sequence by progressively narrowing an interval according to symbol probabilities. Unlike coding each symbol with an integer-length codeword, it can distribute coding cost across an entire sequence. Dictionary methods instead represent repeated strings through references or dictionary entries. Lempel–Ziv–Welch builds a dictionary during processing, with the decoder reproducing the corresponding dictionary construction. (ocw.mit.edu)

DEFLATE combines LZ77-style references to earlier strings with Huffman coding. Its compressed stream consists of blocks, which may use fixed Huffman codes, dynamically supplied codes, or uncompressed storage. Portable Network Graphics uses reversible filtering before DEFLATE compression: the filters change the representation of image samples without discarding them, often making patterns easier to encode. (rfc-editor.org)

Lossy compression

Lossy data compression allows the reconstruction to differ from the input. Rather than preserving every detail, it represents data at a precision or fidelity chosen for the application. The distinction is mathematical, not merely perceptual: a reconstruction that appears identical to a viewer can still differ in its sample values and therefore be lossy. (ocw.mit.edu)

A central operation is quantization, which maps a range of values to a smaller collection of representative values. Once distinct inputs receive the same representation, their original values cannot generally be recovered. Rate–distortion theory studies the minimum coding rate compatible with a specified distortion level. The result depends on both the source distribution and the chosen distortion measure; there is no universal quality scale for all data. (ocw.mit.edu)

One distortion measure is mean squared error, the average squared difference between original and reconstructed samples. Such numerical measures need not match perceived quality exactly. Compression design can therefore involve both statistical fidelity and criteria related to the intended use of the reconstructed signal. (ocw.mit.edu)

JPEG illustrates transform-based image compression. Its familiar lossy coding system uses a discrete cosine transform, quantization, and entropy coding. The transform changes the representation; quantization introduces irreversible loss, while entropy coding packs the resulting symbols more efficiently. The JPEG 1 standard also defines lossless coding, so the standard as a whole is not exclusively lossy. (jpeg.org)

Performance and implementation

Compression performance involves more than final size. Relevant properties include encoding and decoding speed, memory requirements, buffering delay, and support for incremental processing. Larger search windows can expose more repeated material and improve compression, but require additional memory. Zstandard, for example, specifies window limits and supports dictionaries that can improve compression of related inputs. (rfc-editor.org)

The compression ratio is often expressed as uncompressed size divided by compressed size. Under that convention, a 1,000-byte input represented in 250 bytes has a ratio of 4:1 and a size reduction of 75 percent. Comparisons must identify the convention and the input data: a ratio obtained for one collection does not establish the same performance for another. (ocw.mit.edu)

A compressed format specifies how decoders interpret the stream, but need not mandate a single encoder strategy. Compatible encoders can consequently produce different sizes through different search and modeling decisions. Compression is also distinct from error-correcting coding: source coding removes representational redundancy, whereas channel coding deliberately adds structured redundancy to protect transmission. A communication system can apply both operations in sequence. (rfc-editor.org)