Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[REBOL] Re: Compression

From: joel:neely:fedex at: 17-Apr-2001 16:56

It's a good thing this thread was posted to the REBOL mailing list instead of a hard-core tech list like cypherpunks (at least before it got covered over with spam). Those folks had NO patience with technical faux pas nor naiveté. First, let's remember the difference between lossy and lossless (de)compression. Lossy compression schemes (e.g. JPEG) approximate original data in a way that takes less data (i.e., increased compression ratios) to achieve a poorer approximation. In other words, the more you compress, the worse the reconstructed data compare with the original. This works well (up to a point) with photos meant to be viewed by humans, since we don't notice the noise of the approximation as being too different from the normal background texture of most images. But try to use JPEG on a simple "spot color" graphic, and you'll see the effects VERY quickly. Lossless compression schemes (e.g., RLE, LZW, etc.) operate by finding patterns in the original data and replacing them with what amounts to instructions that can be followed to reproduce the patterns exactly. In general, lossless compression schemes don't advertise the compression rates of lossy schemes, but that's the price you pay for perfect reproduction (such as you MUST have for executable code, for example). As Ryan mentioned in another post, 3 bytes can only represent 16777216 distinct values. A quick calculation from the email I am replying to (considering only spaces and letters) shows an entropy of ~4.166 bits per character. That means that the set of all possible 3-byte binary values could only code the set of all possible ~5.76-character messages (made up of only space and letters, conforming to the original source model). Therefore, any lossless compression scheme over all messages in this population will top out at about 48% savings. Ryan Cole wrote:
> While I tend to think Paul is mistaken, take in mind that fractal > generators may be infinitely small compared to the data that they > can produce. 3 / 7 is liberally 3 bytes, how many megs of data can > it produce? >
It doesn't matter. Although the sequence "3/7" is a valid encoding for the infinite message 0.42857142857142857142857142857142857142857142857... (and therefore highly efficient ;-) I challenge you to find an equally compact encoding for the highly-similar message 0.42857142857142857142857142857142857142857412857... (yes, they are different, if you look closely enough). If both of these messages are in the set of possible messages I need to be able to encode, then the average cost of an "a/b" encoding begins to cost more as the set of possible messages grows. What makes the whole system cost even more is that you also have to take the size of the (de)compression algorithm itself into account. Consider that the absolute best possible compression technique (averaged, again, over the entire set of messages capable of being handled) would be to use a dictionary containing every possible message. If all messages were equally likely, the best possible compression would be to represent each message by its position in the dictionary (in binary, of course). Finally, I don't claim comprehensive knowledge, but everything I've read about "fractal compression" makes it sound like a lossy compression scheme. -jn-