Compression of random binary data
Christian Gollwitzer
auriocus at gmx.de
Tue Oct 24 03:48:36 EDT 2017
Am 23.10.17 um 12:13 schrieb Marko Rauhamaa:
> Thomas Jollans <tjol at tjol.eu>:
>
>> On 2017-10-23 11:32, danceswithnumbers at gmail.com wrote:
>>> According to this website. This is an uncompressable stream.
>>>
>>> https://en.m.wikipedia.org/wiki/Incompressible_string
>>>
>>> 1234999988884321
>>
>> No, it's not. According to that article, that string is incompressible
>> by a particular algorithm. I can see no more general claims.
>
> Here's a compression algorithm that manages to compress that string into
> a 0-bit string:
>
> * If the original string is 1234999988884321 (whatever that means),
> return the empty bit string.
>
> * Otherwise, prepend a don't-care bit to the original string and return
> the result of the concatenation.
>
...and that's why there is the "Kolmogorov complexity". You need to
append the decompression program to the data to show how much you really
saved, which will turn out to be nothing compared to the "trivial
decompressor"
print "1234999988884321"
Christian
More information about the Python-list
mailing list