Aucun algorithme de compression ne peut compresser tous les messages d'entrée?

Je viens de commencer à lire un livre intitulé Introduction to Data Compression, de Guy E. Blelloch. À la première page, il déclare:

La vérité est que si un message est raccourci par un algorithme, alors un autre message doit être allongé. Vous pouvez le vérifier en pratique en exécutant GZIP sur un fichier GIF. Il est en effet possible d'aller plus loin et de montrer que pour un ensemble de messages d'entrée de longueur fixe, si un message est compressé, alors la longueur moyenne des messages compressés sur toutes les entrées possibles sera toujours plus longue que l'original saisir des messages.

Prenons par exemple les 8 messages 3 bits possibles. Si l'un est compressé en deux bits, il n'est pas difficile de se convaincre que deux messages devront s'étendre à 4 bits, ce qui donne une moyenne de 3 1/8 bits.

Vraiment? J'ai du mal à m'en convaincre. En fait, voici un contre-exemple. Considérez l'algorithme qui accepte en entrée toute chaîne de 3 bits et mappe sur les sorties suivantes:

000 -> 0
001 -> 001
010 -> 010
011 -> 011
100 -> 100 
101 -> 101
110 -> 110
111 -> 111

Vous y êtes donc - aucune entrée n'est mappée sur une sortie plus longue. Il n'y a certainement pas de "deux messages" qui se sont étendus à 4 bits.

Alors de quoi parle exactement l'auteur? Je soupçonne soit qu'il y a une mise en garde implicite qui n'est tout simplement pas évidente pour moi, soit qu'il utilise un langage beaucoup trop général.

Avertissement: je me rends compte que si mon algorithme est appliqué de manière itérative, vous perdez en effet des données. Essayez de l'appliquer deux fois à l'entrée 110: 110 -> 000 -> 0, et maintenant vous ne savez pas lequel de 110 et 000 était l'entrée d'origine. Cependant, si vous ne l'appliquez qu'une seule fois, cela me semble sans perte. Est-ce lié à ce dont parle l'auteur?

Ce qui vous manque, c'est que vous devez considérer tous les bits de taille 3 ou moins . C'est-à-dire: si dans un schéma de compression pour des bits de taille 3 ou moins, nous compressons l'une des chaînes de 3 bits en une chaîne de 2 bits, alors une chaîne de taille 3 ou moins devra s'étendre à 3 bits ou plus.

Un schéma de compression sans perte est une fonction $C$ des chaînes de bits finis aux chaînes de bits finis qui est injective, c'est à dire, si $C(x) = C(y)$ puis $x = y$, c'est à dire, $C(x)$ détermine uniquement $x$.

Considérons un schéma de compression arbitraire $C$ et laisse $S$être un ensemble de chaînes binaires. Nous pouvons exprimer à quel point$C$ travaille sur $S$ en calculant le rapport

Si nous essayons de compresser toutes les chaînes de longueur au maximum$n$ alors nous sommes en difficulté:

Théorème: Let$S$être l'ensemble de toutes les chaînes de longueur au plus$n$ et $C$tout schéma de compression. alors$\text{CompressionRatio}(C,S) \geq 1$.

Ainsi, le meilleur schéma de compression au monde est la fonction d'identité! Eh bien, seulement si nous voulons compresser des chaînes de bits aléatoires . Les chaînes de bits qui se produisent dans la pratique sont loin d'être aléatoires et présentent beaucoup de régularité. C'est pourquoi il est logique de compresser les données malgré le théorème ci-dessus.

Juste une note supplémentaire à la bonne réponse d'Andrej:

Vous pouvez également jeter un œil à la complexité de Kolmogorov :

Définition : étant donné une chaîne$s$, sa complexité Kolmogorov $C(s)$ par rapport à un modèle de calcul fixe est la longueur du programme de shortes (par exemple machine de Turing) qui produit $s$.

Informellement $C(s)$mesure son contenu d'information ou son degré de redondance ; un string$s$est incompressible si$C(s) \geq |s|$

Deux théorèmes fondamentaux sont:

1) indépendamment du modèle de calcul, il existe une constante $c$ de telle sorte que pour chaque chaîne $s$: $C(s) \leq |s| + c$ (informellement, étant donné une chaîne $s$ vous pouvez le coder en dur dans un programme qui le produit simplement sans aucun traitement ni compression)

2) pour tous $n$ il existe une chaîne $s$ de longueur $n$ c'est incompressible: $C(s) \geq |s|$ (analogue au théorème décrit dans la réponse d'Andrej).

La preuve est simple: il y a $2^n$ chaînes binaires de longueur $n$, mais moins de descriptions (programmes) de longueur $< n$:

$\sum_{i=0}^{n-1} 2^i = 2^n - 1 < 2^n$.

Votre contre-exemple est faux.

Votre liste de valeurs compressées contient des informations cachées, ce qui rend la longueur moyenne supérieure à 3 bits. Les informations supplémentaires correspondent à la longueur de la chaîne de sortie.

Avec nos yeux, nous pouvons voir dans votre table que la première chaîne de sortie n'est longue que de 1 bit, et les autres sont de 3 bits, mais vous trichez si vous n'encodez pas explicitement ce fait. Encodons cela en ajoutant un bit de plus; 0 signifie "longueur = 1" et 1 signifie "longueur = 3".

Votre table devient donc vraiment:

000 -> 00
001 -> 1001
010 -> 1010
011 -> 1011
100 -> 1100 
101 -> 1101
110 -> 1110
111 -> 1111

... qui fait en moyenne 3,75 bits.

ÉDITER

Voici une réflexion après coup, qui illustre le même point. C'est une belle question de quiz:

Le code Morse est composé uniquement de points et de tirets. Appelons le point 0 et le tiret 1. Toutes les lettres majuscules sont codées en quatre bits maximum.

E = . = 0
Q = --.- = 1101

Il y a 26 lettres majuscules. Mais quatre bits ne devraient pouvoir coder que 16 valeurs distinctes. Que se passe-t-il?

En comptant le cas trivial de longueur nulle, il y a $2^{n+1}-1$chaînes de bits dont la longueur est au plus n (si les longueurs sont connues pour être des multiples exacts de huit, le nombre est plus petit mais plus difficile à calculer). Ainsi, toutes les chaînes de longueur$n$ ou moins pourrait être représenté en utilisant des chaînes de longueur fixe $n+1$. Si de nombreuses chaînes seront beaucoup plus courtes que la longueur maximale, cependant, il peut être utile d'utiliser des schémas de codage alternatifs qui ajoutent plus d'un à la longueur des chaînes maximales, mais moins à la longueur des chaînes plus courtes. Par conséquent, la quantité d'informations véhiculée par la connaissance de la longueur exacte d'une chaîne dépend de la durée supposée de la chaîne et de sa volonté de remplir des chaînes plus courtes.

Étant donné que ces facteurs dépendent beaucoup de l'application, il est utile de supposer un modèle de calcul dans lequel les chaînes d'entrée sont supposées contenir des informations qui seraient suffisantes pour permettre au lecteur de savoir où elles se terminent (même si elles ont été remplies avec des quantités arbitraires de données arbitraires) et les chaînes de sortie doivent faire de même. Un tel modèle de calcul permettra à toutes les opérations qui fonctionneraient sur des enregistrements de données individuels de fonctionner aussi bien sur n'importe quelle séquence concaténée d'enregistrements de données [le code qui saurait quand arrêter de lire des enregistrements non compressés entiers peut être présumé savoir aussi bien quand s'arrêter. lecture de fichiers compressés entiers].