Lossless compression

A lossless encoder and decoder agree that a complete valid representation reconstructs the original byte or symbol sequence, not merely a similar substitute. Exact correspondence matters for programs, text and records.

Lossy methods may discard information for a smaller representation. A visually similar reconstructed image does not establish equality of its original pixels or file bytes. The required recovery level must be specified first.

References: [1]

Runs can represent repeated values, dictionaries can reuse recurring phrases, and variable-length codes can favor frequent symbols. Huffman and LZW organize these opportunities differently; formats can combine several methods.

Decoder requirements such as trees, initial dictionaries, lengths and end markers also count toward total size. Some information is regenerated by shared rules and some must be transmitted. Ignoring framing or metadata exaggerates compression savings.

References: [2] [3] [4]

There are 2ⁿ inputs of length n but fewer than 2ⁿ binary strings shorter than n. Unique recovery therefore rules out mapping every input to a shorter output. Some must remain unchanged or expand with overhead.

Already compressed or poorly modeled data may offer little further saving. Evaluation should include complete output size, time and memory. Losslessness specifies recovery, not a compression ratio, corruption detector or resource bound.

References: [1]