Talk:Magic compression algorithm
2N-2?
While I was thinking about how to explain the problem nicely, a thought occurred to me. If the compressed sequence has 2N-1 possible combinations, then we have a problem with 0 length files. As an example, consider a plain sequence of N=4 bits - there are 16 such sequences. Then we can use compressed sequences of 3 bits, of which there are 2^3=8; or those of 2 bits, of which there are 2^2=4; or those of 1 bit, of which there are 2^1=2. However, we cannot use those of 0 bits, because there's no file left. Therefore there is no 2^0 term, and there are a total of 2^3+2^2+2^1=14 different compressed sequences, ie. 2N-2. See what I mean? Modest Genius talk 17:41, 28 August 2007 (UTC)