Également connu sous le nom de codage Huffman, un algorithme pour la compression sans perte de fichiers basé sur la fréquence d'occurrence d'un symbole dans le fichier en cours de compression. L'algorithme de Huffman est basé sur un codage statistique, ce qui signifie que la probabilité d'un symbole a une incidence directe sur la longueur de sa représentation. Plus l'occurrence d'un symbole est probable, plus sa représentation en bits sera courte. Dans n'importe quel fichier, certains caractères sont plus utilisés que d'autres. En utilisant la représentation binaire, le nombre de bits requis pour représenter chaque caractère dépend du nombre de caractères qui doivent être représentés. En utilisant un bit, nous pouvons représenter deux caractères, c'est-à-dire que 0 représente le premier caractère et 1 représente le deuxième caractère. En utilisant deux bits, nous pouvons représenter quatre caractères, et ainsi de suite.
Contrairement au code ASCII, qui est un code de longueur fixe utilisant sept bits par caractère, la compression Huffman est un système de codage à longueur variable qui attribue des codes plus petits pour les caractères plus fréquemment utilisés et des codes plus grands pour les caractères moins fréquemment utilisés afin de réduire la taille de fichiers compressés et transférés.
Par exemple, dans un fichier contenant les données suivantes:
XXXXXXYYYYZZ
la fréquence de «X» est de 6, la fréquence de «Y» est de 4 et la fréquence de «Z» est de 2. Si chaque caractère est représenté en utilisant un code de longueur fixe de deux bits, alors le nombre de bits requis pour stocker ce fichier serait 24, c'est-à-dire (2 x 6) + (2x 4) + (2x 2) = 24.
Si les données ci-dessus étaient compressées à l'aide de la compression Huffman, les nombres les plus fréquents seraient représentés par des bits plus petits, tels que:
X par le code 0 (1 bit)
Y par le code 10 (2 bits)
Z par le code 11 (2 bits)
donc la taille du fichier devient 18, c'est-à-dire (1x 6) + (2 x 4) + (2 x 2) = 18.
Dans l'exemple ci-dessus, des codes plus petits sont attribués aux caractères les plus fréquents, ce qui entraîne un plus petit nombre de bits dans le fichier compressé final.
La compression Huffman a été nommée d'après son découvreur, David Huffman.