Home Original page

Algorithm that makes maximum compression of completly diffused data.

Mark Janssen dreamingforward at gmail.com
Sun Nov 3 22:40:36 EST 2013 
> Note that I *can* make a "compression" algorithm that takes any
> length-n sequence and compresses all but one sequence by at least one
> bit, and does not ever expand the data.
>
> "00" -> ""
> "01" -> "0"
> "10" -> "1"
> "11" -> "00"
>
> This, obviously, is just 'cause the length is an extra piece of data,
> but sometimes you have to store that anyway ;).

And how many bits will you use to store the length?

> So if I have a list of
> N length-Y lists containing only 1s or 0s, I can genuinely compress
> the whole structure by N log2 Y items.

But you cheated by using a piece of information from "outside the
system": length.  A generic compression algorithm doesn't have this
information beforehand.
-- 
MarkJ
Tacoma, Washington
More information about the Python-list mailing list