Beaucoup de projets à microcontrôleurs affichent des textes de menus et d'aide, d'erreurs ou de diagnostics au moyen d'une interface utilisateur ou de diagnostic. Une grande quantité de textes signifie toutefois une grande consommation de mémoire. Avec une compression adéquate, on arrive à stocker une telle quantité de texte dans la mémoire du microcontrôleur qu'on peut se passer le plus souvent d'une mémoire externe. Cet article présente une solution possible : la compression par dictionnaire.

Une compression efficace exploite la nécessaire présence de redondances dans les données à compresser. Dans le cas des textes, ces redondances proviennent de caractères qui apparaissent plus fréquemment que d'autres ou de séquences de caractères qui se répètent. On pourrait ainsi utiliser un codage entropique, comme le code de Huffman, où les caractères les plus fréquents sont représentés par des séquences de bits plus courtes que les caractères plus rares. Ou bien l'on pourrait utiliser un procédé de substitution comme le LZ77, encore appelé compression par dictionnaire, où des séquences de caractères récurrentes sont stockées dans un dictionnaire. Dans le texte, une telle séquence serait alors remplacée par un pointeur vers l'entrée correspondante du dictionnaire. Le procédé LZ77 ne nécessite même pas le stockage d'un dictionnaire séparé au sein des données compressées. Une partie des données décompressées constitue le dictionnaire qui se remplit lentement au cours de la progression de la décompression ; lorsque la taille maximale du dictionnaire est atteinte, il est déplacé grâce à une procédure de fenêtre glissante. Pour améliorer le taux de compression, les programmes de compression 7z ou zip utilisent une combinaison des deux procédés : la compression par dictionnaire suivie du codage entropique. Sur des textes courts, le gain des deux procédés reste toutefois limité. De plus, il n'est pas possible d'extraire des phrases d'un texte compressé sans décompresser le texte tout entier.

Analyse du texte à compresser

Prenez les textes de l'exemple concret du listage 1, on se rend compte qu'une compression par dictionnaire utilisant les redondances de mots entiers et de suites de mots sera efficace.
 
Listage 1. Extrait du texte à compresser sous forme de tableau de chaînes de caractères en C.
const char * const text[] = {
  /*   0 */ "Fuel System 1 Status",
  /*   1 */ "Fuel System 2 Status",
  /*   2 */ "Calculated Load Value",
  /*   3 */ "Engine Coolant Temperature",
  /*   4 */ "Short Term Fuel Trim Bank 1",
  /*   5 */ "Short Term Fuel Trim Bank 3",
  /*   6 */ "Long Term Fuel Trim Bank 1",
  /*   7 */ "Long Term Fuel Trim Bank 3",
  /*   8 */ "Short Term Fuel Trim Bank 2",
  /*   9 */ "Short Term Fuel Trim Bank 4",
  /*  10 */ "Long Term Fuel Trim Bank 2",
  /*  11 */ "Long Term Fuel Trim Bank 4",
  /*  12 */ "Fuel Pressure (Gauge)",
  ...
  /*  46 */ "OBD Requirements to Which Vehicle or Engine is Certified", // len=57
  ...
  /* 149 */ "Commanded Boost Pressure A",
  /* 150 */ "Boost Pressure Sensor A",
  /* 151 */ "Commanded Boost Pressure B",
  /* 152 */ "Boost Pressure Sensor B",
  /* 153 */ "Boost Pressure A Control Status",
  /* 154 */ "Boost Pressure B Control Status",
  ...
  /* 177 */ "Manifold Surface Temperature",
  /* 178 */ "Intake Manifold Absolute Pressure A",
  /* 179 */ "Intake Manifold Absolute Pressure B",
  ...
  /* 188 */ "Exhaust Gas Temperature Bank 2 - Sensor 7",
  /* 189 */ "Exhaust Gas Temperature Bank 2 - Sensor 8"
};

Le caractère « espace », qui apparaît fréquemment dans chaque texte, est utilisé comme séparateur de mots. Pour chaque espace, soit le compresseur crée une entrée dans le dictionnaire, soit le décompresseur en intercale une entre chaque mot. Cette dernière procédure ne fonctionne bien que s'il n'existe pas de traitement particulier des caractères spéciaux devant ou derrière un mot, c'est-à-dire que (Gauge) par ex. constitue une seule entrée dans le dictionnaire et non pas trois, soit (, Gauge et ).
 
  • Le texte entier est disponible sous la forme d'un ou de plusieurs tableaux de chaînes de texte en C. => Les textes individuels sont accessibles par des index de tableau, ce qui doit aussi être le cas des textes compressés.
  • Le texte contient de nombreux mots ou suites de mots qui apparaissent fréquemment. => Une forte redondance est une condition nécessaire à toute compression.
  • Le texte est en anglais, il n'utilise que le code ASCII à 7 bits (0 à 127). => Les codes ≥128 restent libres. Cela simplifiera plus tard l'étape 5 de la procédure proposée.
  • La plupart des mots du texte commencent par une majuscule. => Engine et engine sont deux entrées différentes du dictionnaire. On peut améliorer la compression si tous les mots commencent par une majuscule. Pour des raisons de lisibilité, il est toutefois préférable d'écrire les prépositions et les articles tout en minuscules.
  • Le texte contient peu de caractères spéciaux, par exemple ( ) # / -. => Lors de la production du dictionnaire, il y aura peu d'entrées comme (Gauge) distinctes d'une entrée ultérieure Gauge.
  • L'élément le plus long du texte complet fait 57 caractères. => Sa décompression nécessite un tampon de 57 octets de RAM.

Compression par dictionnaire

Étape 1 : production du dictionnaire
Cette étape découpe le texte à compresser en mots. L'espace est utilisée comme séparateur ; plus tard, elle est automatiquement insérée par le décompresseur. En même temps sont évaluées la fréquence de chaque mot et sa taille en mémoire (sa longueur plus le caractère de fin de chaîne). À la fin, le dictionnaire est trié par fréquence décroissante. En cas de fréquence identique, la plus grande longueur est prioritaire. Le listage 2 montre le dictionnaire déjà optimisé dans l'étape 2, avec la fréquence et la longueur en commentaire.
 
Listage 2. Extrait du dictionnaire optimisé sous forme de tableau de chaînes de caractères en C.
const char * const dictionary[] = {
   /*   0 */ "Sensor", // cnt=116 len=7
   /*   1 */ "Bank", // cnt=104 len=5
   /*   2 */ "-", // cnt=89 len=2
   /*   3 */ "2", // cnt=67 len=2
   /*   4 */ "1", // cnt=66 len=2
   /*   5 */ "Fuel", // cnt=45 len=5
   /*   6 */ "Temperature", // cnt=43 len=12
...
   /*  16 */ "Exhaust Gas", // cnt=16 len=12
...
   /*  30 */ "Status", // cnt=9 len=7
...
   /*  45 */ "System", // cnt=4 len=7
...
   /*  77 */ "8", // cnt=2 len=2
   /*  78 */ "Currently Being Utilized by the", // cnt=1 len=32
   /*  79 */ "Advance for #1 Cylinder", // cnt=1 len=24
...
   /* 125 */ "F", // cnt=1 len=2
   /* 126 */ "G" // cnt=1 len=2
};


Étape 2 : optimisation du dictionnaire
Si le texte contient des mots de même fréquence, toujours voisins dans leurs apparitions, par ex. Exhaust et Gas, on peut les combiner en une seule entrée du dictionnaire : Exhaust Gas. Cela contraint à réintroduire une espace entre les mots, ce qui est compensé par la disparition de l'un des caractères de fin de chaîne.
Si après la concaténation de deux entrées, l'entrée obtenue satisfait les mêmes conditions avec une entrée voisine, l'opération peut être répétée, ce qui produit des entrées de plus de deux mots.
Comme toute entrée dans le dictionnaire (chaîne de caractères en C) exige, outre sa taille en mémoire, un pointeur vers cette chaîne, on fera l'économie de ce pointeur pour chaque concaténation. Le gain réalisé dépend de la taille du pointeur sur le système cible. De plus, la taille du tableau dictIndex[] produit au cours de l'étape 3 est réduite du produit de la fréquence freq de l'entrée concaténée par la taille du pointeur : freq * sizeof(dict_index_t).

Étape 3 : codage du texte original
Quand le dictionnaire est terminé, on peut coder le texte au moyen de l'index du tableau des entrées. Voici un exemple de codage du premier texte du listage 1 :
 
text[0] = Fuel System 1 Status
  • Fuel = entrée dictionary[5]. Remplacer Fuel par l'index 5.
  • System = entrée dictionary[45]. Remplacer System par l'index 45.
  • 1 = entrée dictionary[4]. Remplacer 1 par l'index 4 (pas de compression).
  • Status = entrée dictionary[30]. Remplacer Status par l'index 30.
 
Les espaces disparaissent. On obtient le tableau suivant :
 
const dict_index_t dictIndex[] = {
   /*   0 */ 5, 45, 4, 30, /* Fuel System 1 Status */
   /*   1 */ 5, 45, 3, 30, /* Fuel System 2 Status */
   …
   /* 189 */ 16, 6, 1, 3, 2, 0, 77 /* Exhaust Gas Temperature Bank 2 - Sensor 8 */
};
 
Comme le nombre des index par texte compressé est variable, un deuxième tableau est nécessaire pour pointer sur le premier index de chaque texte du listage 1. On peut ainsi décompresser chaque texte indépendamment des textes qui le précèdent.
 
const start_index_t startIndex[] = {
   /*   0 */    0, /* first index of text[0] is dictIndex[0] */
   /*   1 */    4, /* first index of text[1] is dictIndex[4] */
...
   /* 188 */ 1207, /* first index of text[189] is dictIndex[1207] */
   /* 189 */ 1213  /* first index of non-existent text[190] is dictIndex[1213] */
};
 
La dernière entrée du tableau startIndex[] permet au décompresseur de calculer facilement pour tous les textes, même le dernier, le nombre de ses index.
Pour text[n], ce nombre est startIndex[n+1] – startIndex[n].
 
Étape 4 : extension du dictionnaire avec des paires d'index
Dans cette étape, on compresse des paires de mots (paires d'index) fréquentes et des séquences de mots (séquences d'index) de manière plus efficace. D'abord, on cherche la séquence la plus fréquente de deux index et on l'insère comme nouvelle entrée logique à la fin du dictionnaire. On ajoute effectivement au système du listage 3 un nouveau tableau bidimensionnel pair[][2] et on l'étend d'une entrée composée de deux index.
 
Listage 3. Tableau de paires d'index (calculé pour des index à 8 bits).
const dict_index_t pair[][2] = {
   /*  0 => 127 */ {   2,   0 }, // "–", "Sensor", cnt=78
   /*  1 => 128 */ {   1,   4 }, // "Bank", "1", cnt=40
   /*  2 => 129 */ {   1,   3 }, // "Bank", "2", cnt=40
   /*  3 => 130 */ { 128, 127 }, // "Bank 1", "– Sensor", cnt=31
   ...
   /* 57 => 184 */ {  15,  51 }, // "Air", "Flow", cnt=4
   ...
   /* 67 => 194 */ { 184,   0 }, // "Air Flow", "Sensor", cnt=3
   /* 68 => 195 */ {  56, 194 }  // "Mass", "Air Flow Sensor", cnt=3
};


Si le plus grand index du dictionnaire était 126, la première paire d'index dans pair[0] prend la valeur logique 127. Il faut alors remplacer dans le tableau dictIndex[], toutes les paires d'index pair[0][0] et pair[0][1] (listage 3 index 2 et index 0) par l'unique index 127. La taille du tableau dictIndex[] diminue donc de la fréquence de la paire d'index, tandis que celle du tableau pair[][2] augmente d'une entrée contenant cette paire d'index. Comme cette procédure est appliquée au tableau dictIndex[] autant de fois qu'on aura trouvé des paires avec une fréquence minimale, on aura trouvé non seulement des paires de mots voisins, mais des séquences de mots plus longues. Une paire d'index peut de nouveau contenir l'index d'une ou deux paires d'index (entrée 3, 67 ou 68 dans le listage 3).
Pour obtenir une compression effective et l'insertion d'une nouvelle paire dans le tableau pair [][2], la fréquence d'apparition freq d'une paire doit remplir la condition : freq > 2 * sizeof(dict_index_t).

Étape 5 : introduction d'index en ASCII
La réalisation effective comprend encore une étape qui, compte tenu de ses cas particuliers et ses conditions particulières, ne peut pas être détaillée ici. Par l'introduction d'index en ASCII pour des mots du dictionnaire qui n'apparaissent qu'une fois, ou pour des mots courts de faible fréquence non utilisés dans pair[][2], il est possible d'exclure du dictionnaire les mots qui ne contribuent pas à la compression. Ces mots sont inclus directement dans le tableau dictIndex[] avec les codes ASCII de leurs caractères et retirés du dictionnaire. Mais pour cela, il faut au préalable avoir décalé tous les autres index à des valeurs différentes des codes ASCII, soit, pour le code à 7 bits, à des valeurs ≥ 128. On trouvera des détails dans le code source public du compresseur et du décompresseur du projet Arduino en [3].

Considérations à postériori

L'exécution de ces différentes étapes met en lumière une problématique générale de la compression. L'espace nécessaire pour un index sizeof(dict_index_t) n'est pas connu avant la compression, mais est utilisé par l'algorithme pour décider si un mot court ou une fréquence d'apparition faible justifie une entrée dans le dictionnaire ou la production d'une paire d'index. Dans le cas présenté de la compression de textes de PID (Parameter Identifier), des index sur 8 bits suffisent, ce qui simplifie l'algorithme et la décompression. La compression des textes de défauts nécessite plus de 256 index. On utilise alors un codage entropique utilisant des index à 8 bits pour les mots les plus fréquents et 16 bits pour tous les autres, ce qui limite l'accroissement de taille du tableau dictIndex[].
Si la compression de texte obtenue avec les étapes 3 ou 4 est suffisante, on peut s'arrêter là. La routine de décompression exige alors moins d'espace mémoire et moins de temps d'exécution que si l'on exécute des étapes ultérieures.

Comment tout a commencé

Pourquoi est-ce que je me suis intéressé à la compression sans perte ? À cause de mes projets de diagnostic automobile OBD2 pour Elektor Projet[1] 'OBD2-Analyser NG', Projet[2] 'OBD2 for Raspberry Pi', Projet [3] 'OBD2 for Arduino'. De même que pour les appareils de diagnostic professionnels, il fallait mettre à la disposition de l’utilisateur plusieurs milliers de descriptions des codes de défauts (Diagnostic Trouble Codes, DTC). Le volume total de ces textes se monte à 211 Ko environ, ce qui a pu être réduit à 35 Ko environ grâce à l’algorithme de compression présenté ici, ce qui a permis de les charger dans la mémoire Flash de 128 Ko du µC à 8 bits AVR AT90CAN128 utilisé dans le projet [1].
Dans le projet Arduino [3], le petit Arduino Uno R3 ainsi que l’Elektor Uno R4, avec 32 Ko de mémoire Flash devaient convenir. Mais bien entendu, la mémoire restait largement insuffisante pour le texte des erreurs compressé. Toutefois, les 7 Ko occupés par les descriptions des identifieurs de paramètres OBD2 (PID) de ces projets (le plus souvent des données de capteurs) ont pu être compressés à 2 Ko environ. À titre d’exemple, le résultat obtenu avec mon algorithme de compression dans le cas des 190 brefs textes PID du listage1 est présenté ci-dessous.
Pour un µC à 8 bits AVR AT90CAN128 et le compilateur avr-gcc 4.9.2 (avec l’option d’optimisation –Os active), j’ai obtenu les valeurs suivantes pour l’empreinte mémoire de la routine de décompression (les autres valeurs sont calculées) :

 
 
 
 		 Texte source
[octets]
 
Texte compressé
[octets]

 		  
Décompresseur
[octets]

 		  
Tampon RAM pour la décompression [octets]
 
Textes DTC
 		  
216311
 		  
35340
 		  
566
 		  
106
 
 
Textes PID
 		  
7273
 		  
1820
 		  
314
 		  
57
 
 
(180278​)

➔ Intéressé(e) par la lecture d'autres articles du magazine Elektor ? Devenez membre dès maintenant !