Compression de données/Taux de compression

Compression de données

• Introduction
• Types de compression
• Techniques de compression sans perte
  • Codage par répétition
    • Run-length encoding
  • Codage entropique
    • Codage de Huffman
    • Codage de Shannon-Fano
  • Codage par dictionnaire
    • Lempel-Ziv-Welch (LZW)
  • Codage par modélisation de contexte
  • Transformée de Burrows-Wheeler
  • Archive de fichiers
• Techniques de compression avec pertes
  • Le format JPEG 2000
• Taux de compression
• Bibliographie et liens

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 $\tau$ est relié au rapport entre la taille $b$ du fichier comprimé $B$ et la taille $a$ du fichier initial $A$. Le taux de compression est généralement exprimé en pourcentage. Un taux de 50 % signifie que la taille $b$ du fichier comprimé $B$ est la moitié de $a$. La formule pour calculer ce taux est :
$\tau =1-(b/a)$

Exemple : $a$=550 Mo, $b$=250 Mo
$\tau =1-(250/550)=54\%$

L'algorithme utilisé pour transformer $A$ en $B$ est destiné à obtenir un résultat $B$ de taille inférieure à $A$. 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

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 $C$.
• Considérons l'ensemble $F$ de tous les flux de taille $N$ : $F:\forall A\in F_{N},Sz(A)=N$ (avec $Sz(A)$ la fonction de calcul de taille d'un flux).
• L'algorithme étant sans pertes, il y a une bijection entre les flux d'origine $F_{N}$ et les flux compressés $C(F_{N})$.
  • En effet, si l'algorithme n'était pas bijectif, alors il existerait deux flux $A$ et $A'$ ayant le même flux compressé $B$.
  • À la décompression, il n'est pas possible de savoir s'il faut restituer le flux $A$ ou $A'$ : ceci réclamerait au minimum un bit pour être codé.
  • Donc, soit l'algorithme $C$ est avec pertes (impossible par exemple de restituer le flux $A'$), soit les deux flux $A$ et $A'$ n'ont pas la même image compressée $B$, car l'algorithme produira deux flux compressés différents d'au moins un bit.
  • En conséquence, un algorithme $C$ sans pertes ne peut être qu'une bijection de $F_{N}$ vers $C(F_{N})$, c'est-à-dire qu'aucune image ne possède deux antécédents distincts : $\forall B\in C(F_{N}),\exists !A\in F_{N}/C(A)=B$.
  • De plus, $\forall (A,A')\in F_{N}^{2},(A=A'\Rightarrow C(A)=C(A'))\land (A\neq A'\Rightarrow C(A)\neq C(A'))$.
• Prenons l'hypothèse $H$ que tout flux compressé est plus petit que le flux d'origine : $\forall A\in F_{N},Sz(C(A))<Sz(A)$
  • En prenant comme unité de taille l'octet ($2^{8}=256$ valeurs distinctes), le nombre total de fichiers distincts de taille $N$ est $card(F_{N})=256^{N}$.
  • Le nombre total de fichiers de taille au plus égale à $(N-1)$ est $card(C(F_{N}))=\sum _{i=1}^{N}256^{i}$, ce qui correspond à une série géométrique : la valeur recherchée est donc $({\frac {256^{N}-1}{256-1}})-1$.
  • On constate de façon triviale que $({\frac {256^{N}-1}{256-1}})-1<256^{N}$ : donc, il y a strictement moins de fichiers de taille $1$ à $(N-1)$ que de fichiers de taille $N$.
  • Or, l'algorithme $C$ est bijectif : donc, $card(F_{N})=card(C(F_{N}))$. Or, l'inégalité précédente donne $card(C(F_{N}))<card(F_{N})$, ce qui est absurde.
• L'hypothèse $H$ est donc fausse, donc son opposé logique est vrai : $\exists A\in F_{N}/Sz(C(A))\geq Sz(A)$.

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 $card(C(F_{N}))<card(F_{N})$ 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

• Mark Nelson, La compression de données, Éditions Dunod, Paris, 1993.