Voici un nouvel article de la série sur la compression de données, qui fait suite à celui sur la compression RLE, la compression LZ et la compression ZX0.
À la fin de l'article sur la compression LZ, il avait été question de fréquence d'apparition des nombres pour les offsets de référence et les longueurs de motif. Cette constatation avait amené lors de l'article sur ZX0 à regarder le codage gamma, qui permet de coder des entiers avec un nombre de bits variable afin d'optimiser la taille des petits nombres (qui sont plus fréquents).
Revenons sur cette histoire de fréquence en l'étendant à tous les symboles présents dans les données à compresser. Il serait intéressant d'avoir un codage dépendant de la fréquence d'apparition des symboles : plus le symbole est fréquent, plus son code est court.
Ce codage est obtenu avec l'algorithme de Huffman.
En plus d'avoir des codes de longueurs variables en fonction de la fréquence, Huffman garantit qu'aucun code n'est le préfixe d'un autre code, ce qui rend l'algorithme de décodage très facile. Le codage est aussi optimal : il n'y a pas de codage préfixe plus court pour les fréquences données.
Algorithme de compression de Huffman
L'idée générale de l'algorithme est la suivante : après avoir calculé les fréquences d'apparition des symboles, on construit un arbre binaire où chaque symbole est une feuille de l'arbre, avec les symboles les plus fréquents proches de la racine. Le code d'un symbole correspond alors au parcours depuis la racine jusqu'à la feuille, en prenant 0 pour une branche et 1 pour l'autre.
Pour initier la construction de l'arbre, on crée une liste de nœuds, un par symbole associé à sa fréquence. Ensuite et itérativement jusqu'à avoir l'arbre complet, on prend les deux nœuds de plus petite fréquence et on crée un nouveau nœud parent avec comme fréquence la somme des deux fréquences.
Reprenons l'exemple qui nous suit depuis le début. Pour rappel, il s'agit de cette image :
................
....#######.....
..##@@@@@@@##...
.##@OOOOOOO@##..
.#@OoooooooO@#..
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
.#@OoooooooO@#..
.##@OOOOOOO@##..
..##@@@@@@@##...
....#######.....
................
On commence donc par calculer les fréquences (ou occurrences, cela revient au même) des symboles :
Fréquences des symboles :
'.': 78 (28.78%)
'o': 68 (25.09%)
'#': 46 (16.97%)
'@': 34 (12.55%)
'O': 30 (11.07%)
'\\n': 15 (5.54%)
Donc, plein de '.' et de "o", et pas beaucoup de retours à la ligne. À noter qu'avec 6 symboles différents, on pourrait utiliser un codage fixe sur 3 bits par symbole (2^3 = 8 possibilités). Voyons ce que donne Huffman en déroulant l'algorithme :
- On prend les deux nœuds de plus petites occurrences : '\n' (15) et 'O' (30)
- On crée un nœud parent "\nO" avec occurrences 45 (15 + 30)
- On prend les deux nœuds de plus petites occurrences : '@' (34) et le "\nO" (45)
- On crée un nœud parent "@\nO" avec occurrences 79 (34 + 45)
- On prend les deux nœuds de plus petites occurrences : '#' (46) et 'o' (68)
- On crée un nœud parent "#o" avec occurrences 114 (46 + 68)
- On prend les deux nœuds de plus petites occurrences : '.' (78) et le "@\nO" (79)
- On crée un nœud parent ".@\nO" avec occurrences 157 (78 + 79)
- On prend les deux nœuds de plus petites occurrences : "#o" (114) et ".@\nO" (157)
- On crée un nœud racine avec occurrences 271 (114 + 157)
Ce qui nous amène à l'arbre suivant :
[271]
/ \
<-- 0 / \ 1 -->
/ \
[114] [157]
/ \ / \
[46] [68] [78] [79]
# o . / \
[34] [45]
@ / \
[15] [30]
\n O
Pour trouver les codes associé à chaque symbole, on parcourt l'arbre depuis la racine jusqu'à chaque feuille, en prenant 0 pour la branche de gauche et 1 pour la branche de droite. Et cela donne :
'.' : 10 (longueur=2)
'o' : 01 (longueur=2)
'#' : 00 (longueur=2)
'@' : 110 (longueur=3)
'O' : 1111 (longueur=4)
'\\n': 1110 (longueur=4)
En prenant la moyenne des longueurs pondérées par les occurrences, on obtient une taille moyenne de 2.45 bits environ par symbole. C'est mieux que les 3 bits fixes, mais pas extraordinaire non plus en considérant que 3 bits auraient pu coder 8 symboles.
Cependant, il n'y a pas besoin de faire l'analyse au préalable et à la main pour savoir combien de bits sont nécessaires. L'algorithme de Huffman le fait tout seul.
La compression elle-même consiste ensuite à remplacer chaque symbole par son code binaire. Pour notre exemple, cela donne pour la première ligne la suite de bits suivante : 10101010101010101010101010101010, ce qui fait une suite d'octets : 0xAA 0xAA 0xAA 0xAA. On passe de 16 octets à 4. On voit aussi qu'un motif se répète... intéressant non ? J'évoquerai cela à la fin de l'article.
Algorithme de décompression
La décompression est très simple : avec le flux compressé et l'arbre, on parcours l'arbre en lisant les bits un par un. À chaque 0, on descend sur la branche de gauche, à chaque 1 sur la branche de droite. Lorsqu'on atteint une feuille, on émet le symbole correspondant et on repart de la racine.
Je vous laisse faire l'exercice avec 0xAA (c'est-à-dire 10101010) pour retrouver une série de quatre '.'.
Et l'arbre ?
C'est bien beau d'avoir codé les données grâce à l'arbre. Mais il nous faut l'arbre pour décoder le flux compressé. Il est donc nécessaire de le transmettre avec les données compressées. Il y a plusieurs manières de faire, mais voici une approche simple :
- Pour chaque nœud interne, on écrit un 0 (en bit) et on sérialise récursivement les deux nœuds enfants.
- Pour chaque feuille, on écrit un 1 suivi du code du symbole (sur 8 bits).
En commençant par la racine, on obtient un parcours en profondeur de l'arbre. Pour notre exemple, cela donne la séquence de bits suivante (les caractères sont ici pour la lisibilité, mais en pratique ce sont leur représentation binaire qui est utilisée) :
0
0
1 `#`
1 `o`
0
1 `.`
0
1 `@`
1 `\n`
1 `O`
Cela fonctionne puisque, par construction, chaque nœud interne a toujours deux enfants, sauf s'il n'y a qu'un seul symbole dans les données.
L'exemple ici prend 8 octets (avec quelques bits non utilisés dans le dernier octet). C'est assez petit par rapport aux données, ça va.
Les chiffres
Avec les données de l'exemple,. on obtient les résultats suivants :
- Taille originale : 271 octets (2168 bits)
- Taille compressée : 666 bits (84 octets, avec 6 bits de padding)
- Taille de l'arbre : 8 octets
- Taille totale compressée : 92 octets
Ce qui donne une taille finale compressée, arbre compris, de 33.95% de la taille originale.
Combinaisons
Si on regarde le flux compressé (hors arbre), voici ce que cela donne en hexadécimal :
0xAA 0xAA 0xAA 0xAA 0xEA 0xA0 0x00 0x2A 0xAE 0xA0 0xDB 0x6D 0xB0 0x55 0xD0 0x6F 0xFF 0xFF 0xFF 0xC1 0x5D 0x1B 0xD5 0x55 0xFC 0x57 0x1B 0xD5 0x55 0x5F 0xC5 0xC6 0xF5 0x55 0x57 0xF1 0x71 0xBD 0x55 0x55 0xFC 0x5C 0x6F 0x55 0x55 0x7F 0x17 0x1B 0xD5 0x55 0x5F 0xC5 0xC6 0xF5 0x55 0x57 0xF1 0x74 0x6F 0x55 0x57 0xF1 0x5D 0x06 0xFF 0xFF 0xFF 0xFC 0x15 0xD4 0x1B 0x6D 0xB6 0x0A 0xBA 0xA8 0x00 0x0A 0xAB 0xAA 0xAA 0xAA 0xAA 0x80
Comme indiqué plus haut, on remarque des motifs qui se répètent. Ce flux est donc probablement un bon candidat pour une compression supplémentaire avec LZ par exemple. Pourquoi pas ?
L'algorithme DEFLATE (utilisé dans le format .zip par exemple) fait le contraire : il applique d'abord LZ77 pour compresser les motifs répétitifs, puis applique Huffman pour compresser les symboles résultants. C'est un peu plus compliqué que cela, mais c'est l'idée générale, et c'est l'idée générale derrière plusieurs formats de compressions : des mélanges d'algorithmes.
Conclusion
Huffman est un algorithme de compression efficace sur des données avec des fréquences d'apparition de symboles non uniformes. Si tous les symboles sont également fréquents, il n'y aura pas d'avantage à utiliser Huffman par rapport à un codage fixe. De plus, il faut stocker l'arbre, il est donc important de vérifier que la taille gagnée par la compression compense la taille de l'arbre (il est aussi possible d'utiliser des arbres statiques connus à l'avance pour certains types de données, mais cela sera potentiellement moins efficace).
On retrouve cet algorithme dans de nombreux formats de compression, souvent combiné avec d'autres algorithmes. C'est une des bases de la compression de données, il est donc intéressant de connaître son principe de fonctionnement.
Cet article termine la petite série sur la compression de données sans perte.
Supplément
Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.