0
$\begingroup$

Given an unsorted list of Objects with a compression ration. Can you predict the impact on the ratio, if that list would have been sorted prior to compression?

Is there a reason to assume that sorting a list before compressing it will yield better comparison ratio?

I know that I did not mentioned the compression algorithm, please address it in you answer.

$\endgroup$
1
$\begingroup$

There are $x^n$ possible lists of $n$ objects, where there are $x$ different possible objects. So on average, over all possible such lists, a (non-lossy, optimal) compression algorith will give a file of size $n\log_2 x$ bits.

Of course, many decent algorithms will either know which objects are common in general, and make those take less space, or have an overhead stating which objects were common in this specific list, and make those take less space. So the uncommon lists will in that case actually take up more space after compression. But $n\log_2 n$ is the best guess for a "general" size for an arbitrary list.

Now presume we know that the list is sorted. Then there are only $\binom{x+n}{n}$ different possible lists. This is quite a lot smaller. How much smaller? If $x\gg n$ (i.e. most lists have only distinct objects), it's basically $\frac{x^n}{n!}$. This is a best case. The number of bits required on average to store a compressed list is for the best case $$n\log_2x-\log_2(n!)\approx n\log_2 x-n\log_2n+\frac{n}{\ln2}$$using Stirling's approximation.

$\endgroup$
  • $\begingroup$ How did you come with $n\log_2 x$? Also is it for an arbitrary list among $n$ or is it for all of them? $\endgroup$ – Ilya Gazman Aug 12 at 17:39
  • $\begingroup$ @IlyaGazman It's for a single, arbitrary list. And if you have $N$ different possible types for something, then you need on average $\log_2 N$ bits to encode any specific one. And it's a basic logarithm property that $\log_2 x^n = n\log_2 x$. $\endgroup$ – Arthur Aug 12 at 18:11
  • $\begingroup$ How come if I have $N$ objects encoded with $B$ bytes each. The everage compression is not depended on $B$? $\endgroup$ – Ilya Gazman Aug 13 at 0:21
  • $\begingroup$ If your objects are humongous, but there are only four possible types, then they can be compressed to $00,01,10$ and $11$ by an algorithm that knows what those four look like. $\endgroup$ – Arthur Aug 13 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.