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 formula_1 est relié au rapport entre la taille formula_2 du fichier comprimé formula_3 et la taille formula_4 du fichier initial formula_5. Le taux de compression est généralement exprimé en pourcentage. Un taux de signifie que la taille formula_2 du fichier comprimé formula_3 est la moitié de formula_4. La formule pour calculer ce taux est :
formula_9
Exemple : formula_4=, formula_2=
formula_12
L'algorithme utilisé pour transformer formula_5 en formula_3 est destiné à obtenir un résultat formula_3 de taille inférieure à formula_5.
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 :
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 formula_53 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.

Compression de données/Codage de Shannon-Fano

Le codage de Shannon-Fano ou codage de Fano-Shannon est un algorithme de compression de données sans perte élaboré par Robert Fano à partir d'une idée de Claude Shannon.
Il s'agit d'un codage entropique produisant un code préfixe très similaire à un code de Huffman, bien que pas toujours optimal, contrairement à ce dernier.
Principe.
La probabilité de chaque symbole à compresser doit être connue.
Dans la plupart des cas, des fréquences ou occurrences fixes calculées à partir des données à compresser sont utilisées ; on parle alors de codage de Shannon-Fano semi-adaptatif (qui nécessite deux passes successives sur les données à compresser : la première pour calculer les probabilités, la seconde pour compresser à proprement parler).
Il est également possible d'utiliser des probabilités fixes non dépendantes des données à compresser (codage statique) ou des probabilités variant au fur et à mesure de la compression (codage adaptatif).
Le processus est de trier les symboles à compresser par ordre croissant de leurs nombre d’occurrences. Puis l'ensemble trié des symboles est séparé en deux groupes de telle façon que le nombre d'occurrences des deux parties soient égaux ou presque (le nombre d'occurrences d'un groupe étant égale à la somme des occurrences des différents symboles de ce groupe). On réitère le processus jusqu'à obtenir un seul arbre. On associe ensuite par exemple le code 0 à chaque embranchement partant vers la gauche et le code 1 vers la droite.
Comparaison avec le codage de Huffman.
L'approche du codage de Shannon-Fano est descendante : l'algorithme part de l'ensemble des symboles et divise cet ensemble récursivement jusqu'à arriver à des parties ne contenant qu'un seul symbole.
L'inconvénient de cette approche est que, lorsqu'il n'est pas possible de séparer un ensemble de symboles et deux sous-ensembles de probabilités à peu près égales (c'est-à-dire lorsque l'un des sous-ensembles est beaucoup plus probable que l'autre), les codes produits ne sont pas optimaux.
Le codage de Huffman a une approche ascendante : l'algorithme part des symboles et regroupe ceux ayant la probabilités la plus faible, jusqu'à avoir regroupé tous les symboles.
Cette approche permet d'obtenir systématiquement un code optimal au niveau du symbole, dans le pire cas de la même longueur que le code de Shannon-Fano équivalent, dans tous les autres cas plus court.
Les codages de Shannon-Fano et de Huffman souffrent cependant tous les deux du même inconvénient : ils codent les symboles sur un nombre de bits entier.
Un codage arithmétique, optimal au niveau du bit, permet de coder des symboles sur un nombre de bits arbitraire (y compris 0), et d'atteindre l'entropie de Shannon.
Principe détaillé.
L'algorithme se base sur le nombre d'occurrence de chaque caractère pour établir la table des codes binaires de taille variable.
Supposons que la phrase à coder est « "this is an example of a huffman tree" ».
Il s'agit de la même phrase que pour le chapitre sur le codage de Huffman afin de pouvoir comparer les résultats.
On recherche tout d'abord le nombre d'occurrences de chaque caractère.
Dans l'exemple précédent, la phrase contient 2 fois le caractère "h" et 7 espaces.
Chaque caractère constitue une des feuilles de l'arbre à laquelle on associe un poids égal à son nombre d'occurrences.
 this is an example of a huffman tree
Occurence de chaque caractère, trié du plus fréquent au moins fréquent :
Contrairement à l'algorithme d'Huffman, le tri n'est fait qu'une seule fois.
De plus, le code binaire se construit au fur et à mesure, en commençant par diviser le tableau en deux parties auxquelles on associe le bit 0 et le bit 1 respectivement.
Chaque division doit produire deux moitiés de poids égaux si possible.
Chaque moitié est alors divisée à son tour, jusqu'à ce qu'il ne soit plus possible de diviser.
À chaque étape, on ajoute une ligne au tableau indiquant les divisions effectuées, le bit associé en gras, et :
On obtient donc cette table de codage binaire :
La phrase « "this is an example of a huffman tree" » se code alors sur 136 bits au lieu de 288 bits (si le codage initial des caractères tient sur 8 bits).
 t h i s i s a n e x a m p l e 
 1100 10000 10001 1011 000 10001 1101 000 001 1010 000 010 11111 001 1001 11100 11010 010 000
 o f a h u f f m a n t r e e
 11011 011 000 001 000 10000 11110 011 011 1001 001 1010 000 1100 11101 010 010
Utilisations.
Comme le codage de Huffman est très similaire au codage de Shannon-Fano et donne de meilleurs résultats, ce dernier n'est pratiquement plus utilisé aujourd'hui.
Le codage de Shannon-Fano est utilisé après une compression par LZ77, pour le codage entropique de l'algorithme implode, utilisé historiquement dans le format ZIP.
L'algorithme implode a été détrôné par l'algorithme deflate, remplaçant le codage de Shannon-Fano par un codage de Huffman.

Compression de données/Codage entropique