Golomb Coding : l’algorithme discret qui compresse vos données sans effort
Golomb et Rice Coding : quand les maths rencontrent la compression
Tous les algorithmes de compression ne se valent pas. Gzip ou LZ4 font très bien l'affaire dans la plupart des cas. Mais quand vos données suivent une distribution géométrique, un autre outil s'avère souvent plus efficace : le codage de Golomb.
Une distribution particulière
Dans une distribution géométrique, les petites valeurs apparaissent beaucoup plus souvent que les grandes. Ce schéma se retrouve dans de nombreux contextes : les tentatives de reconnexion réseau, les différences entre images vidéo, ou encore la fréquence des erreurs dans les logs.
Le codage de Golomb exploite précisément cette caractéristique. Il attribue des séquences courtes aux valeurs fréquentes et des séquences plus longues aux valeurs rares.
Un paramètre unique
Le fonctionnement repose sur un paramètre M. Chaque entier est divisé en quotient et reste. Le quotient s'encode en unaire, le reste en binaire. Cette approche simple permet d'obtenir d'excellents ratios quand la distribution géométrique est présente.
Rice coding : la version optimisée
Robert Rice a proposé une variante plus rapide. Il impose que M soit une puissance de deux. Résultat : les divisions et modulos deviennent des décalages de bits et des masques. Sur les processeurs modernes, ces opérations sont bien plus rapides.
Les usages actuels
On retrouve ces algorithmes dans plusieurs domaines :
- Les codecs vidéo H.264 et H.265 utilisent une variante appelée Exp-Golomb
- La compression vocale s'appuie sur Rice coding
- Les outils de bio-informatique traitent les séquences d'ADN avec des variantes de Golomb
- Les objets connectés minimisent leur consommation grâce à ces méthodes
Les avantages pour le développeur
Trois points rendent ces algorithmes attractifs :
- Un seul paramètre à configurer
- Une complexité constante en temps et en mémoire
- Un comportement déterministe, identique à chaque exécution
Les limites à connaître
Attention toutefois : si vos données ne suivent pas une distribution géométrique, Golomb coding peut dégrader la taille des fichiers. Dans ce cas, les algorithmes adaptatifs comme Zstandard ou LZMA restent plus adaptés.
Un principe intemporel
Golomb coding illustre une idée simple : bien comprendre la structure de ses données permet de choisir l'outil le plus efficace. Un algorithme des années 1960 reste pertinent parce qu'il répond précisément à un besoin spécifique.