Compression de données/Taux de compression

Un livre de Wikilivres.


Le taux de compression est une mesure de la performance d'un algorithme de compression de données informatiques. Il est généralement exprimé en pourcentage, et noté τ. Deux définitions sont communément admises :

  • L'une définit le taux de compression comme le rapport du volume des données après compression sur le volume initial des données. De ce fait, plus le taux de compression est faible, plus la taille du fichier compressé résultant est faible. Le taux de compression ainsi défini est donné par la formule : τ = [Volume final] / [Volume initial]. C'est aussi l'inverse du quotient de compression.
  • L'autre définition exprime le taux de compression comme le gain en volume rapporté au volume initial des données. Cette définition est en fait complémentaire de la première. Plus le taux de compression est élevé, plus la taille du fichier compressé résultant est faible. La formule correspondante s'écrit : τ = 1 - ([Volume final]/[Volume initial]). Dans ce cas, le taux de compression est relié au quotient de compression q par l'équation τ = 1 - 1/q.


Le taux de compression est relié au rapport entre la taille du fichier comprimé et la taille du fichier initial . Le taux de compression est généralement exprimé en pourcentage. Un taux de 50 % signifie que la taille du fichier comprimé est la moitié de . La formule pour calculer ce taux est :

Exemple : =550 Mo, =250 Mo

L'algorithme utilisé pour transformer en est destiné à obtenir un résultat de taille inférieure à . Il peut paradoxalement produire parfois un résultat de taille supérieure : dans le cas des compressions sans pertes, il existe toujours des données incompressibles, pour lesquelles le flux compressé est de taille supérieure ou égale au flux d'origine.

Fichiers non-compressibles[modifier | modifier le wikicode]

Démonstration de l'existence de fichiers non-compressibles avec un algorithme de compression sans pertes

Ceci se démontre par l'absurde :

  • Considérons un algorithme de compression sans pertes .
  • Considérons l'ensemble de tous les flux de taille  : (avec la fonction de calcul de taille d'un flux).
  • L'algorithme étant sans pertes, il y a une bijection entre les flux d'origine et les flux compressés .
    • En effet, si l'algorithme n'était pas bijectif, alors il existerait deux flux et ayant le même flux compressé .
    • À la décompression, il n'est pas possible de savoir s'il faut restituer le flux ou  : ceci réclamerait au minimum un bit pour être codé.
    • Donc, soit l'algorithme est avec pertes (impossible par exemple de restituer le flux ), soit les deux flux et n'ont pas la même image compressée , car l'algorithme produira deux flux compressés différents d'au moins un bit.
    • En conséquence, un algorithme sans pertes ne peut être qu'une bijection de vers , c'est-à-dire qu'aucune image ne possède deux antécédents distincts : .
    • De plus, .
  • Prenons l'hypothèse que tout flux compressé est plus petit que le flux d'origine :
    • En prenant comme unité de taille l'octet ( valeurs distinctes), le nombre total de fichiers distincts de taille est .
    • Le nombre total de fichiers de taille au plus égale à est , ce qui correspond à une série géométrique : la valeur recherchée est donc [1].
    • On constate de façon triviale que  : donc, il y a strictement moins de fichiers de taille à que de fichiers de taille .
    • Or, l'algorithme est bijectif : donc, . Or, l'inégalité précédente donne , ce qui est absurde.
  • L'hypothèse est donc fausse, donc son opposé logique est vrai : .

Donc, quelle que soit la taille de flux utilisée ou la nature des données, il existera toujours au moins un flux compressé plus grand que son original, donc un flux non-compressible.

À noter qu'en prenant le cas extrême d'un flux d'un seul octet, le raisonnement est trivial (le flux compressé ne peut faire zéro octet de longueur), mais ne permet pas de généraliser la démonstration à toutes les tailles de fichier possibles, ni d'être indépendant de la nature des données du flux.

ATTENTION : Ceci n'est vrai que pour les algorithmes de compression sans pertes. En utilisant un algorithme avec pertes, on peut garantir au contraire que et donc que tout fichier est compressible, au prix justement d'une perte d'information plus ou moins importante lors de la compression/décompression du flux.

Notes et références[modifier | modifier le wikicode]

  1. On retranche 256⁰=1 de la somme car aucun flux compressé ne peut être de taille nulle.
  • Mark Nelson, La compression de données, Éditions Dunod, Paris, 1993.