Using a spreadsheet I calculated the cost of a unique encoding and the numbers suggest that random data can be theoretically compressed. I say theoretically because reality doesn’t always do things by the numbers. Reading data using an arithmetic encoder with probabilities other than a power two usually reads slightly less bits on average than the calculated number of bits and you can’t actually read or write part of a bit. The probability of compressing random data is extremely low. Only a little less than 3E-13 percent of the data sets would save anything.

While the encoding is not practical because of this, it is interesting to me firstly because it suggests it is possible to compress random data. It also suggests that when compressing an endless data stream it will only reduce it in size and never enlarge it.. Like any other compression algorithm it would enlarge some files of a given length.

The algorithm is based on variable length data sets of one bit symbols. A data set consists of symbols until a 1 is encountered then ends when a 0 is encountered. There can be any number of 0 symbols before the first 1 symbol and any number of 1 symbols before the final 0. The smallest data set is simply a 1 followed by a 0.

These sets can also be encoded by encoding the count of extra symbols in the form of a binary selection of whether there are more extra symbols or the data set is ending. An index into the extra symbol count is needed to determine how many are 0 symbols and how may are 1 symbols.

This is the encoding which is read then written as 0 symbols until a 1 symbol is encountered then 1 symbols until a 0 symbol ends the dataset. The probability of the symbol to end the data set is calculated to break even until the index into the extra characters becomes large enough to allow the end of set symbol to match the size of the output symbol and start saving bits. A limit needs to be placed on the length of a data set because theoretically reading a set could go on forever with nothing ever being output.

To illustrate how data is read, the first symbol read has a probability of 25 percent to end the data set for 2 bits or 75 percent for at least one extra symbol costing 0.415037 bits. If the data set ends there are no extra symbols so no index is needed and a 1 and 0 are written for 2 bits breaking even. If the end of data set symbol is not read, additional symbols are read until an end of data set symbol is encountered

The second symbol read has a probability of one third to end the data set for 1.584963 bits or two thirds for another extra symbol at 0.584963 bits. If the data set ends an index into the extra symbol count of one so far is read. There is always extra symbol count plus one possibilities for the index which is two in this case for 1 bit. That makes a total of 3 bits read for the output of 010 or 110 or 1 bit for the first two extra symbols.

It takes quite some time before the end of data set can be read at 1 bit and start showing a profit. It isn’t until the data set reaches 55 symbols that it starts showing a profit. That’s like flipping a coin and getting heads 53 times in a row. It’s possible but probably not in my lifetime. It’s not quite that bad because the coin is weighted more for heads at the start but still.

While I think the algorithm could compress some data, it just isn’t practical. It is nice to think that something otherwise thought impossible could be done.

Spreadsheet Data