ALGORITHME DE HUFFMAN

 

 

Le codage Huffman du nom de son concepteur est une méthode statistique de compactage. Son principe est de remplacer un caractère par une suites de bits, sachant que plus la probabilité d’apparition du caractère est forte et plus la séquence de bits représentant ce caractère sera courte.

L'idée qui préside à l'algorithme de Huffman est voisine de celle utilisée dans le code Morse : coder ce qui est fréquent sur peu de place, et en revanche coder ce qui revient rarement sur des séquences plus longues. En morse le « e », lettre très fréquente, est codé par un simple point, le plus bref de tous les signes. L'originalité de David Albert Huffman est qu'il fournit un procédé d'agrégation objectif permettant de constituer son code dès lors qu'on possède les statistiques d'utilisation de chaque caractère.

Pour réaliser le code Huffman, il faut connaître la fréquence des caractères utilisés dans un fichier avant de choisir les codes optimaux. Il faut donc lire tout le fichier avant de le compresser. Une autre conséquence est que pour décompresser, il faut connaître les codes et donc la table, qui est ajoutée devant le fichier, aussi bien pour transmettre que stocker, ce qui diminue la compression, surtout pour les petits fichiers. Ce problème est éliminé par le code de Huffman adaptatif, qui modifie sa table au fil des choses. Et peut donc démarrer avec une table de base. En principe il commence avec les caractères à même probabilité.

Plus précisément soit X1=(x1...xn) des symboles et (p1....pn) la probabilité d’apparition de ces symboles dans une séquence. Ainsi . Soit xi0 et xi1 les deux symboles qui ont la plus faible probabilité d’apparition. On étiquette les deux symboles xi0 et xi1 respectivement par 0 et 1. On crée un nouvel ensemble de symboles qui sont les n-2 symboles différents de xi0 et de xi1 affectés de leur probabilités, et un nouveau symbole qui a une probabilité de pi0 + pi1. Ainsi on obtient un ensemble de symboles de cardinal n-1 et un ensemble de probabilités de même cardinal. On peut donc appliquer de nouveau cet algorithme jusqu’à ce qu’il ne reste plus qu’un seul caractère de probabilité 1.

Ainsi grâce à cet algorithme on a constitué une table qui à tout symbole fait correspondre une séquence de 0 et de 1. En plus à un symbole qui a une forte probabilité correspond une séquence courte. La taille de la séquence augmente quand la probabilité diminue.

On obtient avec cet algorithme un arbre binaire et donc le décodage s’effectue très simplement en suivant l’arbre. Car une des branches correspond à 0 et l’autre à 1, et les feuilles sont les symboles. Ainsi ce codage est un codage bijectif et donc sans perte. Mais le codage Huffman ne permet pas toujours de réduire la taille des données car il faut stocker la table de conversion.

Pour illustrer le codage Huffman, on peut prendre l'exemple suivant :

On obtient avec cet algorithme un arbre binaire et donc le décodage s’effectue très simplement en suivant l’arbre. Car une des branches correspond à 0 et l’autre à 1, et les feuilles sont les symboles. Ainsi ce codage est un codage bijectif et donc sans perte. Mais le codage Huffman ne permet pas toujours de réduire la taille des données car il faut stocker la table de conversion.

Il existe trois variantes de l'algorithme de Huffman :


statique : Chaque octet a un code prédéfini par le logiciel. Les codes prédéfini n'ont pas besoin d'être transmis, mais la compression ne peut s'effectuer que sur un seul type de fichier.

semi-adaptatif : Le fichier est d'abord lu, de manière à calculer les occurrences de chaque octet, puis les codes sont attribués à partir des poids de chaque octet. Les codes resteront les mêmes jusqu'à la fin de la compression. Il sera nécessaire pour la décompression de transmettre les codes attribué.

adaptatif : C'est la méthode qui offre a priori les meilleurs taux de compression car l'arbre est construit de manière dynamique au fur et à mesure de la compression du flux. Cette méthode représente cependant le gros désavantage de devoir modifier souvent l'arbre, ce qui implique un temps d'exécution plus long. Par contre la compression est toujours optimale et le fichier ne doit pas être connu avant de compresser. Il ne faut donc pas transmettre ou stocker la table des fréquences des symboles. De plus, l'algorithme est capable de travailler sur des flux de données, car il n'est pas nécessaire de connaitre les symboles à venir.

Voici un lien ou vous trouverez les codes sources d'un projet de compression et decompression Huffman.

http://huffman.sourceforge.net