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

8

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?

Jack M
la source
13
Votre code n'est pas un code. Comment comptez-vous décoder 00010?
3
En fait, il existe une preuve très simple de ce fait qui repose sur le principe du pigeonnier. en.wikipedia.org/wiki/…
chazisop
Si vous pouviez compresser chaque message de 3 bits en <= 3 bits, vous pourriez compresser un message infiniment long en quelques bits seulement. Par exemple, si votre proposition fonctionne, vous pouvez simplement xor avec la valeur 3 bits la plus courante, ajouter la valeur au début et compresser. puis continuez à répéter jusqu'à ce qu'un message ne prenne que quelques bits.
JarkkoL

Réponses:

16

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 pointC travaille sur S en calculant le rapport

CompressionRatio(C,S)=xSlength(C(X))XSlength(X).
Un petit taux de compression est bon. Par exemple, s'il est1/2 cela signifie que nous pouvons en moyenne compresser les chaînes S de 50% en utilisant C.

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

Théorème: LetSêtre l'ensemble de toutes les chaînes de longueur au plusn et Ctout schéma de compression. alorsCompressionRatio(C,S)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.

Andrej Bauer
la source
Je vous remercie. Donc, l'auteur a mal parlé, non? Il a dit «messages de longueur fixe» et «considérer les 8 messages de 3 bits», mais aurait-il dû dire «messages de longueur maximale fixe» et «considérer les 14 messages possibles d'au plus 3 bits»?
Jack M
@JackM: ou encore mieux: "considérez toutes les chaînes de longueur au plus 3 sur l'alphabet {0,1}"
Vor
7

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înes, 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 stringsest incompressible siC(s)|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)|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)|s| (analogue au théorème décrit dans la réponse d'Andrej).

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

je=0n-12je=2n-1<2n.

Vor
la source
4

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?

detmar
la source
Est-ce vraiment nécessaire? Il me semble que dans certaines situations, il est parfaitement raisonnable de permettre à la longueur d'être implicite - comme si vous avez un protocole où CHAQUE message est précédé de sa longueur codée comme un mot à largeur fixe. Puisqu'il précède chaque message, compressé ou non, il peut être négligé. Et le message d'Andrej répond à la question tout en permettant à la longueur d'être implicite, donc votre restriction semble inutile. Encore un bon point à soulever dans les deux cas, bien sûr.
Jack M
En fait, pensez-vous que votre restriction d'avoir à coder explicitement la longueur équivaut à la restriction d'Andrej d'avoir à coder toutes les chaînes de moins de 3 bits?
Jack M
@JackM: Dans la plupart des cas, un schéma de compression sera utilisé non seulement pour mapper des éléments de données uniques à d'autres éléments de données uniques (si tout va bien plus petits), mais plutôt pour mapper des séquences de morceaux de données vers d'autres séquences de morceaux (si tout va bien plus courtes) des données. Si les séquences d'entrée sont toutes dans un seul flux qui comprend suffisamment d'informations pour les subdiviser, alors la "longueur d'entrée" doit inclure toutes les informations nécessaires pour analyser l'entrée d'un seul flux, et la "longueur de sortie" doit inclure toutes les informations nécessaires pour analyser la sortie.
supercat
0

En comptant le cas trivial de longueur nulle, il y a 2n+1-1chaî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 longueurn 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].

supercat
la source