3 ms·
They work because while most possible data is unstructured, most real-world data is highly structured. On average over all possible inputs, any compression sch
by aidenn0 10y ago
They work because while most possible data is unstructured, most real-world data is highly structured. On average over all possible inputs, any compression scheme must have 1x compression.
Consider images of slides for a presentation that are text on a flat background. If you know the value of the pixel just to the left of the current pixel, then if you guess that the current pixel will be the same, you will be right most of the time. This is obviously not true for random noise. Consider a really simple compression scheme where a pixel is stored as a single bit of a 1 if it is the same color as the previous pixel, and the color is stored as usual, but with an additional 0 bit prepended to the color. When you guess wrong, you pay a tax of 1 bit, but when you guess right you save N-1 bits where N is the number of bits per pixel.
For random noise, this will grow the input quite a bit, but for simple flat-shaded graphics it will shrink the input quite a bit.
- eridius 10y agoOn average, any lossless compression scheme must have >= 1x compression. Lossy compression schemes can have less (since they're discarding information), and lossless compression schemes certainly can average out to > 1x (this is trivially observable by taking any 1x-average scheme and adding a fixed-length header to the output).