Lossless data compression

Lossless data compression is a form of data compression in which decoding reproduces the original data exactly. It exploits repetition, unequal symbol frequencies, or predictable relationships without discarding information. Unlike lossy compression, it does not permit approximation of the encoded input. Lossless methods include general-purpose techniques for byte streams and specialized formats for images and audio. Exact recovery is a property of the encoding and decoding process, not a guarantee that every input becomes smaller. (web.mit.edu)

Reversibility and fundamental limits

An encoder $E$ and decoder $D$ must satisfy

D(E(x))=x

for every supported input $x$ . Consequently, the encoder must behave as an injective function: two distinct inputs cannot have the same complete encoded representation. Any dictionary, model, or other information required for reconstruction must be available to the decoder, whether transmitted, reconstructed, or agreed in advance. (web.mit.edu)

No lossless algorithm can shorten every possible input. There are $2^n$ binary strings of length $n$ , but only $2^n-1$ strings shorter than $n$ , including the empty string. A counting argument therefore shows that distinct encodings cannot all be shorter. Some inputs must retain their length or expand. Headers and coding tables can also outweigh savings on small inputs; formats such as DEFLATE provide uncompressed blocks for cases where compression is unhelpful. (rfc-editor.org)

Information theory describes limits in terms of a source’s probability distribution. For a discrete random variable $X$ , its entropy is

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

For uniquely decodable symbol codes, the expected code length cannot be below $H(X)$ , measured in bits per symbol. The source coding theorem explains how coding increasingly large blocks can approach the entropy bound for an independent, identically distributed source. These are average limits, not minimum lengths for each individual message. For sources with dependencies, entropy rate captures the information per symbol remaining after context is considered. (ocw.mit.edu)

Principal techniques

Run-length encoding represents consecutive repetitions by a symbol and a count. For example, a run of twenty identical characters can be described without writing the character twenty times. The method works well on long runs, but may expand data consisting mainly of short runs because counts and markers require space. (jshun.csail.mit.edu)

Huffman coding assigns variable-length binary codewords to symbols according to their probabilities. Its codewords form a prefix code, meaning that no complete codeword begins another. Decoding can therefore identify symbol boundaries without separators. Huffman’s construction minimizes expected length among binary prefix codes for a given symbol distribution, although whole-number codeword lengths can leave a gap above entropy. Coding groups of symbols can reduce that gap per original symbol. (web.mit.edu)

Arithmetic coding represents a sequence through successive subdivisions of a numerical interval, using symbol probabilities to determine subdivision sizes. It avoids assigning a separate whole-number bit length to every symbol and can approach the information content predicted by the model. Its effectiveness depends on both the coding machinery and the accuracy of the probability estimates. (ocw.mit.edu)

Dictionary methods replace recurring strings with compact references. LZ77 uses references to previously decoded data, typically expressed as a distance and length. Lempel–Ziv–Welch (LZW) instead builds a table of strings and emits table indices. The decoder reconstructs the same evolving table, so the entire dictionary need not be transmitted separately. Such methods exploit repeated sequences rather than only individual-symbol frequencies. (rfc-editor.org)

Modeling and reversible preprocessing

Compression often combines a model or reversible transformation with an entropy coder. A model estimates which symbols are likely, possibly using preceding symbols as context. Adaptive methods update their state while processing the stream; encoder and decoder must follow matching rules so that reconstruction remains unambiguous. A model that ignores dependencies can miss substantial redundancy even when it accurately counts individual symbols. (web.mit.edu)

Reversible preprocessing changes how data is represented rather than removing information. Predictive coding stores the difference between an actual value and a prediction derived from previously available values. Small, concentrated residuals may be easier to encode than the original values. Reconstruction adds each residual to the same prediction. Both PNG filtering and FLAC audio coding use this general principle. (w3.org)

Formats and applications

DEFLATE, specified in RFC 1951, combines LZ77-style matching with Huffman coding. Its stream consists of blocks that may use fixed Huffman codes, transmitted coding tables, or uncompressed storage. It supports sequential processing with bounded intermediate storage, but its format does not itself provide random access to arbitrary positions in the original data. (rfc-editor.org)

Portable Network Graphics (PNG) applies reversible scanline filters before compression. Decoding decompresses the filtered bytes and reverses the filters to recover the image samples. Losslessness concerns those encoded samples: it does not undo information discarded before encoding or imply that different PNG encoders produce identical file bytes. PNG also includes chunk-level redundancy checks for detecting transmission damage. (w3.org)

Free Lossless Audio Codec (FLAC) compresses pulse-code-modulated audio using relationships between nearby samples, prediction, and residual coding. It reconstructs the encoded sample values exactly. Its specification requires integer arithmetic when encoding and decoding sample values to avoid rounding errors, while allowing floating-point analysis when selecting coding parameters. FLAC also defines a streamable subset that restricts parameters to make decoder resource requirements more predictable. (rfc-editor.org)