Home » Archive

Articles tagged with: merge sort

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 …