Le codage de Huffman est un algorithme de compression des données sans perte inventé en 1952 par l'informaticien américain David Albert Huffman.
Ce codage est utilisé pour:
- la compression de fichiers (formats ZIP, GZIP, et BZIP2)
- la compression d'images (JPEG, PNG), audio (MP3), vidéo (MPEG, H.264)
- les transferts de données (protocoles réseau)
- les systèmes de stockage de bases de données
- la bioinformatique (séquences d'ADN et données génomiques)
- la transmission de données dans les télécommunications, ce qui augmente l'efficacité de l'utilisation de la bande passante
- les appareils ayant des ressources limitées comme les systèmes embarqués ou les smartphones (minimiser l'utilisation de la mémoire)
Pour un texte, on remplace chaque caractère par un code binaire dont la longueur est d'autant plus courte que le caractère est fréquent dans le texte.
Ce procédé rappelle le code morse puisqu'une séquence de traits et de points est d'autant plus courte que le caractère est fréquent.
Par exemple le 'E' très usité correspond à un point seulement, tandis que le 'P' est rendu par deux points et deux traits:
| A | B | C | D | E | F | G | H | I | J |
K | L | M | N | O | P | Q | R | S | T |
U | V | W | X | Y | Z |
| •- | -••• | -•-• | -•• | • | ••-• | --• | •••• | •• | •--- |
-•- | •-•• | -- | -• | --- | •--• | --•- | •-• | ••• | - |
••- | •••- | •-- | -••- | -•-- | --•• |
Pour encoder un texte, on commence par construire une table des fréquences comme ci-dessous:
| caractère |
E | | S | C | L | R | O | M | U | N | A | P | D | F | I | H | Q | Y | B |
| fréquence |
13 | 12 | 8 | 7 | 5 | 5 | 5 | 5 | 4 | 4 | 4 | 3 | 3 | 3 | 1 | 1 | 1 | 1 | 1 |
On place ensuite chaque caractère dans un arbre binaire dans lequel un caractère est d'autant plus proche de la racine que sa fréquence est élevée:
Le code binaire d'un caractère est obtenu en partant de la racine pour arriver au caractère,
un bit 0 étant ajouté lorsque l'on se déplace vers la gauche, et un bit 1 lorsque l'on se déplace vers la droite.
Par exemple le caractère 'H' est codé par 1001.
Saurez-vous décoder le message suivant ?
1111011010110110101111110000111011101011100111000010111001101101101101011011111010000000101011111111010111001110010000000001111011011011010110111001001001110111000101000011110111110100000001000111010001111101110101101101010100111111101111101010011110111010010111101101011111110111111001001101101111111111010101000101101000111110111010110110110110101110011011111001011000111000000111101101011100
Sachant que le message contient 86 caractères, son poids est donc de 86 octets,
quel est son taux de compression par encodage de Huffman, en ne comptant pas le poids de l'arbre qui est pourtant nécessaire pour son décodage ?
Recherche du mot
