Compression sans perte

Les algorithmes de compression de données sans perte ne peuvent pas garantir la compression pour tous les ensembles de données d’entrée. En d’autres termes, pour tout algorithme de compression de données sans perte, il y aura un ensemble de données d’entrée qui ne devient pas plus petit lorsqu’il est traité par l’algorithme, et pour tout algorithme de compression de données sans perte qui rend au moins un fichier plus petit, il y aura au moins un fichier qu’il rend plus grand. Ceci est facilement prouvé avec des mathématiques élémentaires en utilisant un argument de comptage, comme suit :

• Supposons que chaque fichier est représenté comme une chaîne de bits d’une certaine longueur arbitraire.
• Supposons qu’il existe un algorithme de compression qui transforme chaque fichier en un fichier de sortie qui n’est pas plus long que le fichier original, et qu’au moins un fichier sera compressé en un fichier de sortie plus court que le fichier original.
• Disons que M est le plus petit nombre tel qu’il existe un fichier F de longueur M bits qui se compresse en quelque chose de plus court. Soit N la longueur (en bits) de la version compressée de F.
• Parce que N<M, tout fichier de longueur N garde sa taille pendant la compression. Il y a 2N fichiers de ce type possibles. Avec F, cela donne 2N+1 fichiers qui se compressent tous dans l’un des 2N fichiers de longueur N.
• Mais 2N est plus petit que 2N+1, donc par le principe du pigeonhole il doit y avoir un certain fichier de longueur N qui est simultanément la sortie de la fonction de compression sur deux entrées différentes. Ce fichier ne peut pas être décompressé de manière fiable (lequel des deux originaux devrait-il donner ?), ce qui contredit l’hypothèse selon laquelle l’algorithme était sans perte.
• Nous devons donc conclure que notre hypothèse initiale (que la fonction de compression ne rend aucun fichier plus long) est nécessairement fausse.

Tout algorithme de compression sans perte qui rend certains fichiers plus courts doit nécessairement rendre certains fichiers plus longs, mais il n’est pas nécessaire que ces fichiers deviennent très longs. La plupart des algorithmes de compression pratiques offrent une fonction d' »échappement » qui permet de désactiver le codage normal pour les fichiers qui deviendraient plus longs en étant codés. En théorie, un seul bit supplémentaire est nécessaire pour indiquer au décodeur que le codage normal a été désactivé pour l’ensemble de l’entrée ; cependant, la plupart des algorithmes de codage utilisent au moins un octet complet (et généralement plus d’un) à cette fin. Par exemple, les fichiers compressés deflate n’ont jamais besoin de croître de plus de 5 octets par 65 535 octets d’entrée.

En fait, si nous considérons des fichiers de longueur N, si tous les fichiers avaient la même probabilité, alors pour toute compression sans perte qui réduit la taille d’un certain fichier, la longueur attendue d’un fichier compressé (en moyenne sur tous les fichiers possibles de longueur N) doit nécessairement être supérieure à N. Donc, si nous ne savons rien des propriétés des données que nous compressons, nous pourrions aussi bien ne pas les compresser du tout. Un algorithme de compression sans perte n’est utile que lorsque nous sommes plus susceptibles de compresser certains types de fichiers que d’autres ; l’algorithme pourrait alors être conçu pour mieux compresser ces types de données.

Donc, la principale leçon de l’argument n’est pas que l’on risque de grosses pertes, mais simplement que l’on ne peut pas toujours gagner. Choisir un algorithme signifie toujours implicitement sélectionner un sous-ensemble de tous les fichiers qui deviendront utilement plus courts. C’est la raison théorique pour laquelle nous devons avoir différents algorithmes de compression pour différents types de fichiers : il ne peut y avoir aucun algorithme qui soit bon pour tous les types de données.

L’astuce qui permet aux algorithmes de compression sans perte, utilisés sur le type de données pour lequel ils ont été conçus, de compresser systématiquement ces fichiers sous une forme plus courte, c’est que les fichiers sur lesquels les algorithmes sont conçus pour agir présentent tous une forme de redondance facilement modélisable que l’algorithme est conçu pour supprimer, et appartiennent donc au sous-ensemble de fichiers que cet algorithme peut rendre plus courts, alors que d’autres fichiers ne seraient pas compressés, voire deviendraient plus gros. Les algorithmes sont généralement assez spécifiquement adaptés à un type de fichier particulier : par exemple, les programmes de compression audio sans perte ne fonctionnent pas bien sur les fichiers texte, et vice versa.

En particulier, les fichiers de données aléatoires ne peuvent être compressés de manière cohérente par aucun algorithme de compression de données sans perte concevable : en effet, ce résultat est utilisé pour définir le concept d’aléa dans la théorie de la complexité algorithmique.

Il est provablement impossible de créer un algorithme capable de compresser sans perte n’importe quelle donnée. Bien qu’il y ait eu de nombreuses affirmations au fil des ans de sociétés parvenant à une « compression parfaite » où un nombre arbitraire N de bits aléatoires peut toujours être compressé en N – 1 bits, ce genre d’affirmations peut être écarté sans risque sans même regarder d’autres détails concernant le schéma de compression prétendu. Un tel algorithme contredit les lois fondamentales des mathématiques car, s’il existait, il pourrait être appliqué de manière répétée pour réduire sans perte n’importe quel fichier à la longueur 0. Les algorithmes de compression prétendument « parfaits » sont souvent qualifiés par dérision d’algorithmes de compression « magiques » pour cette raison.

D’autre part, il a également été prouvé qu’il n’existe aucun algorithme permettant de déterminer si un fichier est incompressible au sens de la complexité de Kolmogorov. Il est donc possible que n’importe quel fichier particulier, même s’il semble aléatoire, soit significativement compressé, même en incluant la taille du décompresseur. Un exemple est celui des chiffres de la constante mathématique pi, qui semblent aléatoires mais peuvent être générés par un très petit programme. Cependant, même s’il est impossible de déterminer si un fichier particulier est incompressible, un théorème simple sur les chaînes incompressibles montre que plus de 99 % des fichiers de toute longueur donnée ne peuvent pas être compressés de plus d’un octet (y compris la taille du décompresseur).

Contexte mathématiqueEdit

Abstrativement, un algorithme de compression peut être considéré comme une fonction sur des séquences (normalement d’octets). La compression est réussie si la séquence résultante est plus courte que la séquence d’origine (et les instructions de la carte de décompression). Pour qu’un algorithme de compression soit sans perte, la carte de compression doit former une injection des séquences de bits « ordinaires » vers les séquences de bits « compressées ».

Le principe du pigeonhole interdit une bijection entre la collection de séquences de longueur N et tout sous-ensemble de la collection de séquences de longueur N-1. Par conséquent, il n’est pas possible de produire un algorithme sans perte qui réduit la taille de chaque séquence d’entrée possible.

Points d’application dans la théorie de la compression réelleEdit

Les concepteurs d’algorithmes de compression réelle acceptent que les flux de haute entropie d’information ne peuvent pas être compressés, et en conséquence, incluent des installations pour détecter et traiter cette condition. Un moyen évident de détection consiste à appliquer un algorithme de compression brut et à tester si sa sortie est plus petite que son entrée. Parfois, la détection se fait par heuristique ; par exemple, une application de compression peut considérer que les fichiers dont les noms se terminent par « .zip », « .arj » ou « .lha » ne sont pas compressibles sans détection plus sophistiquée. Une façon courante de gérer cette situation consiste à citer l’entrée, ou les parties incompressibles de l’entrée dans la sortie, en minimisant la surcharge de compression. Par exemple, le format de données zip spécifie la ‘méthode de compression’ de ‘Stored’ pour les fichiers d’entrée qui ont été copiés dans l’archive verbatim.

Le défi du million de chiffres aléatoiresEdit

Mark Nelson, en réponse aux revendications d’algorithmes de compression magiques apparaissant dans comp.compression, a construit un fichier binaire de 415 241 octets au contenu hautement entropique, et a lancé un défi public de 100 $ à quiconque souhaite écrire un programme qui, avec son entrée, serait plus petit que ses données binaires fournies tout en étant capable de les reconstituer sans erreur.

La FAQ du groupe de discussion comp.compression contient un défi de Mike Goldman offrant 5 000 $ pour un programme capable de compresser des données aléatoires. Patrick Craig a relevé le défi, mais plutôt que de compresser les données, il les a divisées en fichiers séparés se terminant tous par le chiffre 5, qui n’était pas stocké comme partie du fichier. L’omission de ce caractère a permis aux fichiers résultants (plus, conformément aux règles, la taille du programme qui les a réassemblés) d’être plus petits que le fichier original. Cependant, aucune compression réelle n’a eu lieu, et les informations stockées dans les noms des fichiers étaient nécessaires pour les réassembler dans le bon ordre dans le fichier original, et ces informations n’ont pas été prises en compte dans la comparaison de la taille des fichiers. Les fichiers eux-mêmes ne sont donc pas suffisants pour reconstituer le fichier original ; les noms des fichiers sont également nécessaires. Patrick Craig a reconnu qu’aucune compression significative n’avait eu lieu, mais a fait valoir que le libellé du défi ne l’exigeait pas vraiment. Un historique complet de l’événement, y compris la discussion sur la question de savoir si le défi a été techniquement relevé ou non, se trouve sur le site Web de Patrick Craig.