Quand on développe sur des plateformes avec des ressources limitées, on cherche a économiser chaque octet et parfois on aimerait pourvoir compresser les données “statiques” d’une application et de ne les décompresser que quand l’usage arrive.
La réflexion que je pose ici, concerne des algorithmes ou des idées de compression à utiliser dans le cadre d’applications embarquer.
Sans refaire toute la génèse des algorithmes et du traitement du signal, il ressort trois axes importants de la compression qui sont :
- Le type de données à compresser (entropie, format (fichier ou buffer vs. flux) ;
- L’algorithme à utiliser au regard de caractéristiques spécifiques de ces données ;
- La perte acceptable de la qualité des données (intégrité).
L’objectif général étant finalement d’amener les données à utiliser au mieux (de remplir) le média qui les stocke ou les transporte. Sans entrer dans des considérations universitaires, il apparait intuitivement qu’un flux de données imprévisible (bruit blanc) représente la compression ultime d’un signal.
- En effet, une compression optimale serait celle qui élimine toutes les redondances inutiles tout en minimisant la perte d’information ;
- Inversement, plus un signal est redondant, plus son entropie est faible. La redondance signifie que certaines parties du signal sont prévisibles ou répétitives.
- Le bruit blanc étant un signal aléatoire dont les échantillons sont indépendants et identiquement distribués, il a une entropie maximale car chaque échantillon est imprévisible.
Un certain nombre de principes simples viennent à l’esprit pour compresser un flux d’informations, comme de réduire sa fréquence d’échantillonnage au juste nécessaire (application du théorème de Shannon) ou d’utiliser le juste nombre d’état pour l’échantillonner (conv. analogique / numérique). Il est aussi possible d’appliquer sur chaque échantillon des transformations continues (comme les logarithmes) afin de réduire les pertes acceptables selon la dynamique du signal original. Les capacités de traitement du signal permettant aujourd’hui d’appliquer des filtres temporels ou fréquentiels qui permettent de réduire l’entropie des signaux en “ébavurant” les parties qui portent peu d’information (son inaudibles dans la “compression psychoacoustique” / MP3) ou des éléments d’images sans intérêt ou invisible à l’œil. A nouveau, on considère ici que ces éléments le portent pas l’entropie de la données et sont donc exclus.
Sans faire l’inventaire exhaustif des algorithmes de compression, on retrouve plusieurs catégories d’algorithmes. Même si je classe séparément les algorithmes avec et sans perte de données, il apparait bien souvent que les algorithmes avec perte, commence par un filtrage de l’entropie au regard des usages du signal avant d’appliquer des algorithmes de compression sans perte.
Compression RLE (Run Length Encoding)
Famille de compresseurs utilisant les répétitions dans un signal pour ne transmettre que l’état (parfois) et le nombre de répartitions. Peu efficace, utilisé dans des flux simples (fax, images noir et blanc).
Compression Huffman
C’est un algorithme qui encode les données en fonction de leur fréquence d’apparition. Il attribut des signes binaires les plus courts aux données les plus fréquentes. Il peut nécessiter de parcourir une première fois toutes les données pour obtenir les fréquences et définir un dictionnaire avant de lancer la compression proprement dite.
Compression LZW (Lempel-Ziv-Welch)
Il s’agit d’un algorithme sans perte avec codage de répétitions (motifs). Il utilise un mécanisme de dictionnaire interne autogénéré (non transmis). Il s’applique à des flux et produit peu de latence.
The Design and Implementation of LZW (the GIF compression algorithm) (commandlinefanatic.com)