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 | | I | N | S | T | R | U | M | O | F | A | H | L | G | D | C | P | Q |
| fréquence |
11 | 10 | 9 | 7 | 5 | 5 | 5 | 4 | 4 | 4 | 3 | 3 | 2 | 2 | 2 | 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 'D' est codé par 1001.
Saurez-vous décoder le message suivant ?
0110000101000100001001011110111011110101111011111110110001111011101101010111100000110000111001111101100010110101101110011101011011101000110010101100001101011110111101110000111110111011111110000110101111011011000111111111000111111001111011010110111101011101110111110011101100011010111011110011010000011100110101101111100111010100001100000010010111111111001100000111010
Sachant que le message contient 80 caractères, son poids est donc de 80 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
