# Compression de données/Taux de compression

* 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
* 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
[ Modifier le sommaire ]
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 :
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

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