Huffman

En parcourant les normes, la compression de Huffman est une technique vénérable, décrite pour la première fois par D. A. Huffman en 1952. Elle demeure néanmoins une technique de compression importante et utile et est spécifiée par la norme de CCITT Group 3 Facsimile, étant prise en charge par le format d'image TIFF. La norme du Group 3 spécifie en fait une variante de l'algorithme Huffman classique, mais est toujours généralement appelée compression Huffman. La compression Huffman code un flux d'octets en une séquence de codes binaires de longueur variable. Le principe derrière l'algorithme est de déterminer la fréquence statistique des différents symboles dans le flux d'entrée et de coder le message en utilisant des codes de bits courts pour les symboles les plus fréquents et des codes de bits plus longs pour les symboles moins fréquents. À titre d'illustration, considérons un fichier ASCII codé comme une séquence de codes 8 bits de longueur fixe. La lettre A est codée comme 01000001 (41h) et la lettre Z est codée comme 01011010 (5Ah). Cependant, en moyenne, la lettre A apparaît plus fréquemment que la lettre Z. Donc, si nous codons A avec un code court, disons 011, et Z avec un code plus long, disons 0111111, alors nous aurons réduit le nombre de bits nécessaires pour représenter un fichier. La technique, appelée codage de longueur variable comme codage de longueur variable, n'est pas ce que Huffman a réellement décrit. La contribution de Huffman était un algorithme pour déterminer l'ensemble de codes optimal pour un ensemble de données donné à coder. Cette situation se fait en ordonnant les symboles d'entrée par fréquence, puis en construisant un arbre binaire à partir d'eux. Le code bit pour un symbole donné est ensuite déterminé par le chemin d'accès à ce symbole dans l'arborescence. À chaque niveau, une branche gauche contribue 1 bit au codage des symboles et une branche droite contribue 0 bit. Lorsqu'un noeud terminal est atteint, le symbole d'entrée s'y trouvant est codé avec le motif binaire construit à partir du chemin vers ce symbole. Pendant le décodage, les bits sont lus dans le flux d'entrée et sont utilisés pour parcourir l'arborescence. Lorsqu'un noeud terminal est atteint, le symbole associé à ce noeud est émis vers le flux décodé. L'arbre réel, appelé arbre de Huffman, est construit de bas en haut, en commençant par tous les noeuds terminaux ordonnés en augmentant la fréquence. Les deux noeuds avec la fréquence la plus basse sont combinés pour former un noeud parent dont la fréquence est définie comme étant la somme des fréquences de ses deux noeuds enfants. Le processus est répété jusqu'à ce qu'un seul noeud, la racine de l'arbre, soit atteint. Notez que l'arborescence utilisée pour coder un flux de données est requise pour décoder la représentation compressée du flux de données. Deux problèmes avec la compression Huffman sont qu'elle nécessite deux passages sur un fichier, un pour déterminer la fréquence du symbole et un pour le codage réel, et le second problème c'est que la manipulation au niveau du bit requise de la représentation codée est plus coûteuse en calcul que l'octet de manipulation orientée. Le premier problème peut être résolu en supposant une distribution de fréquence de symboles standard et un ensemble de codes binaires, ce qui est le cas avec la norme Group 3 Facsimile Standard.

Algorithme