Idée reçue : Tout est compressible

D’abord, il faut préciser ce qu’on entend par compressible. Un fichier musical, un fichier contenant une image, un fichier contenant une séquence vidéo peuvent être comprimés en acceptant de dégrader le son, l’image ou la séquence. Alors bien sûr, tout est compressible : à l’extrême, un seul point noir peut être considéré comme la version compressée de votre photo… mais cela ne sera pas très utile pour vous identifier quand vous prendrez un rendez-vous avec une personne inconnue. La compression « avec pertes » compresse tout, mais elle dégrade tout aussi.

De toutes les façons, quand il s’agit d’un texte, pas question d’accepter que le fichier restitué après décompression soit différent de celui confié au départ à l’algorithme de compression. Dans le cas de fichiers de textes (mais aussi de programmes, de données numériques, etc.), on exige de la compression sans pertes, et il ne peut pas en être autrement.

Nous ne considérerons donc ici que la compression « sans pertes », c’est-à-dire les méthodes de compression qui au moment de la décompression reconstituent exactement, sans dégradation aucune, ce qu’on leur a confié au départ.

Est-ce que tout fichier est compressible (sans pertes) ?

L’expérience semble montrer que oui (et c’est bien là le piège !). En utilisant un compresseur usuel de fichiers, comme zip, on diminue assez facilement de moitié la taille des fichiers (on passe par exemple de 10 Mo à 4 Mo). Pourtant, un raisonnement élémentaire montre que tout ne peut pas être compressible : il n’est pas possible que tous les fichiers confiés à un algorithme de compression sans pertes puissent avoir leur taille réduite.

Considérons pour simplifier des fichiers de ‘0’ et de ‘1’ qu’on souhaiterait compresser en fichiers de ‘0’ et de ‘1’ (en informatique, on est toujours dans cette situation). Considérons pour simplifier encore qu’on ne s’intéresse qu’aux fichiers de 10 caractères. Il y en a 1024 (= 210) en tout. Si on pouvait les compresser tous (avec le même algorithme), cela signifierait qu’on réussirait à leur associer à chacun un fichier de moins de 10 caractères, qui leur soit propre : il est évidemment nécessaire que chacun ait un représentant particulier si on veut que la décompression puisse avoir lieu sans confusion (si deux fichiers différents étaient associés au même fichier compressé, on ne pourrait pas opérer de décompression !).

Eh bien, c’est impossible. En effet, il y a 2 fichiers d’un seul caractère, 4 de deux caractères, 8 des 3 caractères, …, et 512 de 9 caractères, ce qui fait un total de : 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 = 1022 fichiers possibles pour en représenter 1024. Il manque deux fichiers pour pouvoir représenter tous les fichiers possibles de 10 caractères à l’aide de fichiers plus courts.

Plus généralement, on vérifie sans peine qu’il y a au plus un fichier sur 1024 de longueur n qui peut être représenté en gagnant plus de 10 caractères dans sa représentation ; et plus généralement encore, qu’il y a moins d’un fichier sur 2k qui peut être compressé de plus de k caractères parmi les fichiers de n caractères.

En clair, en prenant des fichiers au hasard et pour une simple raison de représentation, seule une infime partie de ces fichiers peut se compresser de manière significative. Notez bien : au plus un sur mille compressible de plus de 10 caractères, un sur un million compressible de plus de 20 caractères, un sur un milliard compressible de plus de 30 caractères, etc. Pour un fichier choisi au hasard, être compressible est exceptionnel !

Alors pourquoi cette illusion que tout fichier informatique est compressible ?

Simplement parce que les fichiers qu’on soumet aux algorithmes de compression sans pertes ne sont pas choisis au hasard, ils ne sont pas composés de caractères tirés avec une loterie. Ce sont des fichiers possédant des régularités particulières : certains caractères sont plus utilisés que d’autres, certaines séquences de caractères sont utilisées plusieurs fois. Ce sont ces régularités (repérées par les algorithmes de compression) qui font qu’en pratique tous les fichiers que nous manipulons sont compressibles. En pratique tout semble compressible, cependant, ne cédons pas à l’illusion et retenons bien que si on choisit un fichier au hasard alors, sauf cas tout à fait exceptionnel, il ne sera pas compressible du tout.

En résumé : les fichiers que nous manipulons sont tous compressibles sans pertes, mais cela est dû à ce qu’ils sont tous réguliers. En général, un fichier constitué au hasard ne sera pas compressible du tout.

Vous en doutez encore ? Fabriquez un fichier en prenant vraiment des caractères au hasard parmi les 256 possibles que les codages actuels permettent. Utilisez pour cela les fonctions random des algorithmes de programmation. Faites passer le fichier aléatoire obtenu dans un compresseur… vous aurez la désagréable surprise de récupérer quelque chose de plus gros !