Home » Archive

Articles tagged with: Kolmogorov complexity

Data compression, Headline »

[3 Jun 2010 by Keshav Shetty | 7 Comments | 20,574 views]
Random data compression – Is it possible? How to use merge sort?

This is continuation of my previous article on Random data compression possibilities.
Some of the readers asked how reverse merge sort (merge unsort) can be used to represent 256 unique values using 128bytes(best case) or 224.25(worst case).
As illustrated in previous article using merge sort we sort the random input and store bit information of the list from where we picked the smaller number. Actually we are reshuffling the original position and stored bit information represents how a input changed its position from original list to sorted list. Lets take an example …

Data compression, Headline »

[20 Dec 2009 by Keshav Shetty | 8 Comments | 11,745 views]
Random data compression – Is it possible? (Part 2)

This is continuation of my previous article on Random data compression possibilities.
Compression of unique values
As I indicated in previous article if for every 256 bytes each value appears only ones, then we can achieve the compression using any of the below techniques.
1. Using insertion sort – by remembering the position. Using this technique for every 256 byte – we can save exactly 32 bytes, i.e for first element no need to remember any position, for next value one bit sufficient to remember weather current element inserted after or before previous …

Data compression, Featured, Headline »

[7 Dec 2009 by Keshav Shetty | 6 Comments | 29,267 views]
Random data compression – Is it possible? Part 1

Random data compression lossless – Is it possible?
The answer is NO (…. and yes!!!)
This is little lengthy blog to show and prove the difficulties and possible ways. This article divided into three section.
(Before you read further I suggest you to read Mark Nelson “The Million Random Digit Challenge“)
1. Why it is not possible to compress random data. (brief introduction to Kolmogorov theory)
2. Why it is possible (Quantum theory, matter and anti matter introduction)
3. The future for compression and possible solution with transition representation and unsorting techniques
If you want to skip …