Universal Lossless Compression? [closed]

Question

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$.

Answer 1

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.