0
$\begingroup$

It is not possible to losslessly compress all files of size $n$ using a single algorithm, as there are more files of size $n (2^n)$ than of size $p, p: p < n ( 2^n-1)$. Via the pigeon hole principle, if we only tried to compress files of size $n$ with a single algorithm, there would be at least one file it was impossible to compress.

If we wanted to be able to compress files with differing lengths $n_k$, the number of files of length $n_k$ we can compress for each $n_k$ becomes even smaller.

Today when reading a story about how a file that was several gigabytes when compressed uncompressed to one gigabyte, I had an idea for a universal compression algorithm.


Let $a_i$ be a compression algorithm.
Let $g_j$ be a file.
$|g_j|$ denotes the length of $g_j$.
Let $f(a_i, g_j)$ be a function that returns $(|g_j| - |a_i(g_j)|)$.

Let $S_N = \{g_j : |g_j| \le N\}$.

Let $A = \{a_i : \, \forall \, g_j \in S_N \, \exists a_i in A : f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$.
$\#A$ denotes the number of elements in $A$.

Let $m$ be the length of the label of the compression algorithm chosen. The first $m$ bytes of every compressed file denote the compression algorithm chosen.
$m = \lceil(\log_2{\#A})\rceil$.

Then you can compress all $g_j \in S_N$, by iterating through A until you find $a_i : f(a_i,g_j) - m \gt 0$.

Even better.

For each $g_j$, let $a_j$ be the corresponding compression algorithm.

Let $h(a_i, g_j) = f(a_i,g_j) - m$.

$${ \, \forall \, a_i \in A, g_j \in S_N, a_j = \displaystyle{ \underset{a_i \in A, g_j \in S} { \operatorname{argmax} } } \, (h(a_i, g_j))}$$


Is there a reason why the above is not done?

While the above is an algorithm, and one could argue that the pigeon hole principle thus applies, this does not imply what it may at first seem to imply. The above algorithm call it $a^v$ is a little different.

Let $a_i: S_N \to Y_N^i$ denote that algorithm $a_i$ maps a family of files $(S_N = \{g_j : |g_j| \le N\})$ is mapped to another family of files $Y_N = \{y_j : y_j = a_i(g_j)\}$.

$\forall a_i \in A, a_i: S_N \to Y_N^i$.
However, $a^v : S_{N+m} \to Y_{N+m}^v$.
So $a^v$ compresses a different family of files from $a_i \ in A$.

The pigeon hole principle merely states that $a^v$ cannot compress all files of length $N+m$; this is irrelevant, since $a^v$ only intends to compress a small subset of files of length $N+m$ (those whose first $m$ bits are the labels of some $a_i \in A$.

$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, Yuval Filmus, fade2black, Luke Mathieson Oct 24 '17 at 23:02

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Please state upfront what you suppose your envisioned universal compression algorithm to achieve: can any input be thrown at it - and be reconstructed faithfully? $\endgroup$ – greybeard Oct 21 '17 at 11:54
  • $\begingroup$ @greybeard no, only files in $S_N$. $\endgroup$ – Tobi Alafin Oct 21 '17 at 12:02
  • 2
    $\begingroup$ @TobiAlafin You cannot compress all files of length at most $N$ for the same reason that you cannot compress all files. There are $2^{N+1}-1$ files that you need to compress. If you compress every file of length at most $N$, then every compressed file must have length strictly less than $N$. But there are only $2^N-1$ such files, which isn't enough. $\endgroup$ – David Richerby Oct 21 '17 at 15:22
  • 2
    $\begingroup$ You say "Then we can compress all $g_j\in S_n$", which is a claim of universal lossless compression. The impossibility of universal lossless compression has nothing to do with algorithms: it is a simple matter of the cardinality of sets. "Choose an algorithm from a family of algorithms" is still an algorithm: if property_1 then compress_with_algo_1; else if property_2 then compress_with_algo_2; else... That doesn't help anything: it's still an algorithm and no algorithm can compress everything. $\endgroup$ – David Richerby Oct 21 '17 at 15:30
  • 3
    $\begingroup$ You claim that you have an algorithm that can compress all files of length $N$. It doesn't matter what that algorithm does. You know that no such algorithm can exist. $\endgroup$ – David Richerby Oct 21 '17 at 15:44
2
$\begingroup$

Then you can compress all $g_j ∈ S_N$, by iterating through $A$ until you find $a_i|f(a_i,g_j)−m>0$.

I'm not sure what the notation means (the pipe here, and also $\#A$ elsewhere), but still: this is not a meaningful algorithm since the set

$\qquad A = \{a_i : \, \forall \, g_j \in S_N \, f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$

is empty.

I think you got lost in notation. $S_N$ = $\Sigma^{\leq n}$ and $A$ is the set of all algorithms that compress all strings in $S_N$ by at least some non-zero number of bits. As you cited, there are no such algorithms.

In the updated question, you write:

$\qquad A = \{a_i : \, \forall \, g_j \in S_N \, \exists a_i \in A : f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$

This definition is circular, hence $A$ is not well-defined. Did you mean

$\qquad A = \{ a \mid \exists g \in S_N. f(a, g) > x \}$

with $x > 0$ something that does not depend on $A$?

Now $A$ is infinite (and undecidable as per Rice's theorem) and, arguably, completely useless: any string s can be compressed well by the trivial algorithm

compress_s(x) {
    if x == s
        return "0"
    else
        return "0" + x
    end
}

Note that this version of $A$ contains all these bogus algorithms. So, you have thrown all information while compressing, instead encoding the string in the algorithm's source code (mathematically and literally).

And, as others note, the resulting algorithm would still be subject to the pidgeon-hole principle.

Is there a reason why the above is not done?

Even if it were possible, it'd be horribly inefficient. In essence, the idea of your algorithm is:

Try all (compression) algorithms (I know); pick the smallest result and encode the result together with its code.

That's clearly neither a clever nor a useful algorithmic idea.

$\endgroup$
  • $\begingroup$ Do you think that Kolmogorov complexity might be good to describe here? The last paragraph pictures that case ;) $\endgroup$ – Evil Oct 21 '17 at 16:50
  • $\begingroup$ @TobiAlafin You need to make up your mind about what you want to define before posting questions about it, and make sure you know what you are defining. Otherwise you're wasting everbody's time. This is the last edit I'll do; you've been given enough explanations for why what you think you're doing is impossible. $\endgroup$ – Raphael Oct 21 '17 at 18:56
  • $\begingroup$ @Evil I don't see an immediate connection; if you do, why not post an answer? $\endgroup$ – Raphael Oct 21 '17 at 18:56

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