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 …