> 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 -- https://mail.python.org/mailman/listinfo/python-list
