Algorithm that makes maximum compression of completly diffused data.
dreamingforward at gmail.com
Mon Nov 4 04:40:36 CET 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
More information about the Python-list