compress string of data

[Josiah Carlson]

Terry Reedy wrote:

> "Josiah Carlson" <jcarlson at nospam.uci.edu> wrote in message
> news:bv3bdd$a0j$3 at news.service.uci.edu...
> 
>>Piet van Oostrum wrote:
>>
>>
>>>>>>>>Gerrit Holl <gerrit at nl.linux.org> (GH) wrote:
>>>
>>>
>>>>>How i could compress string of data?.
>>>>>
>>>>>
>>>>>>>import zlib
>>>>>>>zlib.compress("Hello, world")
>>>
>>>GH> 'x\x9c\xf3H\xcd\xc9\xc9\xd7Q(\xcf/\xcaI\x01\x00\x1b\xd4\x04i'
>>>
>>>GH> http://www.python.org/doc/current/lib/module-zlib.html
>>>
>>>Waw, that compresses it from 12 bytes to 20 bytes :=)
>>
>>
>>There is no such thing as universal compression
> 
> 
> Only if you specify invertibility (losslessness).
> 
> f(s) == '' compressess everything except '' itself ;-)
> 
> and that len(f(s)) < len(s) for some s and not just <= for all s (which
> allows identity 'compression' f(s) == s).
> 
> 
>>- some compressions  result in expansion.
> 
> 
> Which is to say that if a 1-1 function maps some strings to smaller
> strings, it must correspondingly map others to larger strings.  An
> interesting CS tidbit that people keep discovering by stumbling over.
> 
> Lossless universal expansion is possible: f(s) == ' '+s.  But it is into
> rather than onto, so only strings starting with ' ' can be inversely
> mapped.

Exactly (I was too short on time to say the equivalent this morning, and 
even if I had said the equivalent, it likely would not have been as clear).

  - Josiah