Compression de données/Taux de compression


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

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
  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.