Implémentation naïve de compression RLE en C#

En 2020, Gabriel Lavallée, un de mes étudiants au Collège Lionel-Groulx, m'a posé des questions sur la compression RLE, et j'ai fait un petit exemple pour l'aider à comprendre les enjeux. Cet exemple compresse des pixels RGB dans un tableau dynamique d'entiers non-signés contenant en pratique des paires {combien,quoi}, représentant chaque pixel par un entier pour les besoins de cette transformation. Si ça vous intéresse, le voici.

Version de base

Le programme n'utilisera que des outils de la bibliothèque .NET de base.	`using System; using System.Collections.Generic; public class Program {`
J'ai créé un petit type Pixel représentant un triplet RGB. Les fonctions clés pour nos besoins sont : Des opérateurs de comparaison de contenu entre deux instances de Pixel, du fait que RLE demande de compter les éléments consécutifs identiques dans une séquence. J'ai implémenté operator== et operator!= ici, en omettant volontairement Equals(object) et GetHashCode pour ne pas alourdir le code inutilement Notez que l'opérateur == aurait pu être exprimé en termes de conversions en uint, comme l'indique le commentaire accompagnant cette fonction Un opérateur de conversion d'un Pixel en uint, pour faciliter la création du tableau compressé (le combien et le quoi auront tous deux la forme d'un entier non-signé) J'ai ajouté une méthode de conversion en string pour faciliter l'affichage des instances de Pixel	`struct Pixel { public byte R{ get; } public byte G{ get; } public byte B{ get; } public Pixel(byte r, byte g, byte b) { R = r; G = g; B = b; } public static bool operator==(Pixel p0, Pixel p1) => p0.R == p1.R && p0.G == p1.G && p0.B == p1.B; // (int) p0 == (int) p1 public static bool operator!=(Pixel p0, Pixel p1) => !(p0 == p1); public static explicit operator uint(Pixel p) => (uint) (((p.R << 16) \| (p.G << 8)) \| p.B); public override string ToString() => $"{(uint)R} {(uint)G} {(uint)B}"; }`
La compression RLE en soi s'exprime assez aisément : On note le premier élément de la séquence à compresser. Ici, j'utilise des indices, donc l'indice 0 est mon point de référence J'ai utilisé b pour base car le mot base est un mot réservé en C# On cherche le premier élément différent de ce point de référence Ici, je commence à b + 1 et je parcours pix à la recherche du premier Pixel différent de pix[b] Une fois cet élément trouvé, on conserve : Le combien, donc le nombre d'éléments identiques à notre point de référence (ici, i - b avec conversions en uint car la soustraction de deux entiers donne un entier signé), de même que Le quoi, donc la valeur de pix[b] convertie en uint ... et on prend l'indice courant, i, comme nouveau point de référence (nouveau b) Il restera toujours une partie résiduelle à la fin de la boucle, car par définition, la dernière séquence de valeurs identiques consécutives ne sera pas terminée par un élément de valeur différente (sinon, ce ne serait pas la dernière!). Pour cette raison, les éléments des indices dans l'intervalle [i,pix.Count) sont ajoutés au résultat pour terminer le travail Cet algorithme pourrait se généraliser en l'exprimant de manière générique, mais c'est moins agréable en C# que ce ne le serait en C++ (imposition d'interfaces, ralentissement du code)	`static List<uint> CompresserRLE(List<Pixel> pix) { var rés = new List<uint>(); if(pix.Count == 0) // cas dégénéré return rés; int b = 0; int i = b + 1; for(; i < pix.Count; ++i) if(pix[i] != pix[b]) { rés.Add((uint)(i - b)); // combien rés.Add((uint)pix[b]); // quoi b = i; } // reste de i à pix.Count rés.Add((uint)(i - b)); // combien rés.Add((uint)pix[b]); // quoi return rés; }`
Un programme de test naïf montre que le tout fonctionne. Notez que Main affiche les valeur de rle en format décimal, mais un affichage hexadécimal serait plus clair.	`public static void Main() { // 5 noirs, 3 bleus, 2 rouges var lst = new List<Pixel>() { new Pixel(), new Pixel(), new Pixel(), new Pixel(), new Pixel(), new Pixel(0, 255, 0), new Pixel(0, 255, 0), new Pixel(0, 255, 0), new Pixel(255, 0, 0), new Pixel(255, 0, 0) }; var rle = CompresserRLE(lst); foreach(var p in rle) Console.Write($"{p} "); } }`

Version avec transformations

Que doit-on faire si l'on souhaite compresser des données avec transformations? Par exemple, si on ne souhaite tenir compte que des teintes de rouge de nos instances de Pixel?

Une solution simple est de paramétrer l'algorithme de compression en lui ajoutant une transformation à appliquer aux éléments. Le code suit; notez que je n'ai pas répété ce qui demeure identique, par souci de simplicité et d'économie.

En acceptant une transformation en paramètre, la fonction de compression peut comparer les versions transformées de chaque Pixel, et compresser la séquence à traiter sur la base de ces valeurs transformées.

   // ...
   static List<uint> CompresserRLE(List<Pixel> pix, Func<Pixel,Pixel> transfo)
   {
      var rés = new List<uint>();
      int b = 0;
      int i = b + 1;
      for(; i < pix.Count; ++i)
         if(transfo(pix[i]) != transfo(pix[b]))
         {
            rés.Add((uint)(i - b)); // combien
            rés.Add((uint)transfo(pix[b])); // quoi
            b = i;
         }
      // reste de i à pix.Count
      rés.Add((uint)(i - b)); // combien
      rés.Add((uint)transfo(pix[b])); // quoi
      return rés;
   }

La version « ordinaire » (sans transformation) de la fonction de compression devient une délégation vers la fonction générale, mais dans laquelle la transformation est une fonction identité (p => p)

   static List<uint> CompresserRLE(List<Pixel> pix) =>
      CompresserRLE(pix, p => p);

Le programme de test dans ce cas montre une compression « ordinaire » et une autre qui ne tient compte que du ton de rouge de chaque Pixel

   public static void Main()
   {
      // 5 noirs, 3 bleus, 2 rouges
      var lst = new List<Pixel>()
      {
         new Pixel(), new Pixel(), new Pixel(), new Pixel(), new Pixel(),
         new Pixel(0, 255, 0), new Pixel(0, 255, 0), new Pixel(0, 255, 0),
         new Pixel(255, 0, 0), new Pixel(255, 0, 0)
      };
      var rle = CompresserRLE(lst);
      foreach(var p in rle)
         Console.Write($"{p} ");
      rle = CompresserRLE(lst, p => new Pixel(p.R, 0, 0));
      foreach(var p in rle)
         Console.Write($"{p} ");
   }
}

Voilà!