« 3R » signifie Recursive Range Reduction, ou Réduction Récursive des Bornes en français. Comme la plupart des algorithmes de compression, son fonctionnement n'est pas évident au premier abord, à cause des choix et subtilités un peu inhabituels. Mais une fois ceux-ci compris, 3R est assez élégant, c'est-à-dire que si on l'utilise bien, il remplit son rôle dans la plupart des cas avec un nombre minimal d'opérations très simples.
La compression revient à l'honneur dans ce magazine ! Ce sujet fascinant n'avait pas été traité depuis des années, à l'époque où les questions de l'entropie (le mot scientifique pour « quantité d'information ») ont été explorées [1][2]. Cela avait d'ailleurs donné lieu à de nombreux articles-apartés (jusqu'à dériver dans le domaine des CRC [3][4][5][6]) alors que l'objectif initial était de présenter un petit algorithme de compression qui venait d'être mis au point. Il a été décrit en détail en anglais [7], mais les explications y sont surtout techniques et manquent de contexte.
1. Rappels sur les principes de la compression de données
Il existe de nombreux types de systèmes, de méthodes, d'algorithmes et de programmes de compression, autant qu'il y a d'usages, de contraintes et d'applications. La classification complète remplirait des livres entiers et David Salomon en a écrit un aperçu dans son recueil [8]. 3R y apparaît depuis la quatrième...
