Lossless compression

Lossless compression reduces the number of bits used to represent data while preserving enough information to reconstruct the original data exactly.

Entropy coding: A coding method that assigns shorter bit sequences to more probable symbols and longer ones to less probable symbols. It turns symbol-frequency estimates into compact, exactly decodable bitstreams.
Information theory: The mathematical study of information, communication, and uncertainty. It provides the framework for measuring how compactly a source can be encoded.
DEFLATE: A lossless data format combining LZ77 matching with Huffman coding. It underlies widely used ZIP archives and gzip streams.
Lossy compression: Data compression that discards information to reduce size, preventing exact reconstruction of the original. It can achieve smaller files by allowing controlled changes that lossless compression forbids.
Huffman coding: A prefix-code construction that gives more frequent symbols shorter binary codewords. It is a classic entropy-coding method used in formats such as DEFLATE.
Shannon entropy: A measure of the average uncertainty of a random variable, calculated from its outcome probabilities. It gives a lower bound on average code length for ideal lossless coding.
gzip: A file format that wraps DEFLATE-compressed data with metadata and integrity checks. It packages losslessly compressed files for storage and transfer.
No free lunch theorem of data compression: A limitation showing that a compressor cannot shorten every possible input without making some other inputs longer or restricting the source. It explains why gains depend on patterns in the data rather than applying uniformly.
Arithmetic coding: An entropy-coding method that represents a sequence as a progressively narrowed interval of numbers. It can encode symbol probabilities more closely than assigning a separate whole number of bits to each symbol.
Prefix code: A code in which no codeword is the prefix of another, allowing unambiguous sequential decoding. Prefix-free representations let decoders identify codeword boundaries without extra separators.

Linked from 22 pages