Data compression
= Data compression
{wiki}
<Data compression> represents data using fewer <bits> than a specified original representation. The saving can reduce storage in a <file system> and reduce the number of <bits> sent through a <communication channel>. At a fixed transmission rate, fewer <bits> arrive sooner; this makes better use of a fixed transmission budget. Both the encoded data and the instructions needed to interpret them contribute to the size of a stored file.
There are two different promises. <Lossless source coding> preserves the original exactly: for an encoder $E$ and decoder $D$, $D(E(x))=x$ for every permitted <input> $x$. Thus $E$ must be an <injective function>. <Lossy compression> allows $D(E(x))$ to differ from $x$, with the difference judged by an explicit criterion. A program or numerical record may require exact recovery; a preview image may tolerate altered <pixels> in return for fewer <bits>.
The appeal of <lossless source coding> is that repetition can be described rather than copied. <Run-length encoding> says "repeat this value twelve times"; a <prefix code> can give more frequent symbols shorter descriptions. These are distinct ways to exploit structure, and neither promises savings for every <input>. <Image compression> supplies especially visible examples of both <lossless source coding> and <lossy compression>.
Claude E. Shannon's 1948 paper made the role of <probability distributions> precise. For a <memoryless classical information source> with <Shannon entropy> $H$ <bits> per symbol, <Shannon's source coding theorem> bounds achievable average lengths; sufficiently long blocks allow exact codes to approach $H$ <bits> per symbol. This is a statement about a specified source and average lengths, not a promise to shorten every message.<A Mathematical Theory of Communication by Claude Shannon>[Theorem 9 and its coding constructions]{ref}