JDN Développeurs avait déjà abordé les algorithmes de compression graphique (JPEG, MPEG, DivX...). Nous commençons ici une série plus générale sur les algorithmes de compression, en commençant par la catégorie la plus utile pour les données critiques : la compression sans perte.

La compression sans perte est utilisée quand il est nécessaire de garder l'information intacte : il ne doit pas y avoir de différences entre le fichier original et ce même fichier après compression et décompression. Ce type de compression est vital non seulement pour le texte, mais également pour tout type de fichier devant conserver une qualité optimale (images TIFF ou programmes). La compression avec perte est réservée aux données dont la qualité se limite aux perceptions humaines.

Il existe foultitude d'algorithmes selon les usages et les prérequis : nous en aborderons les principaux ici : RLE, Huffman et LZW.

RLE : Run-Length Encoding
Cet algorithme prend simplement la suite d'octets/pixels/caractères qu'on lui fournit, y repère les répétitions d'élément, et transforme chaque ensemble en une paire "nombre de fois où l'élément apparaît, élément". Par exemple, pour une chaîne, la compression de "Aaaaaaaaaaaaaaaaaaaaaaaaaaargh!" donnerait "1A26a1r1g1h1!". On passe donc de 31 caractères utilisés à 12, ce qui nous fait une différence de 38,7% des plus raisonnables.

Cet algorithme pêche malheureusement par sa trop grande simplicité : fonctionner sur la base de répétitions simples lui interdit nombre de taux intéressants, notamment lorsqu'on compresse un texte (qui typiquement comporte bien moins de répétitions que de caractères isolés). Par exemple, la phrase "Je ne sais pas quoi écrire comme exemple!", comportant 41 caractères, serait "compressée" (on dira plutôt encodée) en "1J1e1 1n1e1 1s1a1i1s1 1p1a1s1 1q1u1o1i1 1é1c1r1i1r1e1 1c1o2m1e1 1e1x1e1m1p1l1e1!". Avec un résultat de 80 octets, le succès est mitigé. Cet algorithme est donc surtout efficace lorsque l'on sait que les informations comporterait plus de répétitions qu'autre chose... ce qui n'est fréquent que dans le multimédia (deux pixels de même couleur qui se suivent, par exemple...).

Huffman
Cet algorithme travaille également à partir de la fréquence des caractères, mais trie les caractères par ordre décroissant de fréquence, puis construit un arbre afin d'obtenir le code binaire de chaque caractère. Le caractère le plus fréquent est ainsi décrit dans le fichier final en prenant le moins de place possible, tandis que les caractères moins fréquents y prennent plus de place.
Pour notre "Je ne sais pas quoi écrire comme exemple", la fréquence serait ainsi :

L'arbre binaire est ensuite construit de bas en haut, chaque paire d'élément devenant un noeud, à partir de la fréquence la plus basse. On continue comme ceci à chaque noeud jusqu'à ce que toutes les branches soient reliées à une racine commune. Ceci fait, on remonte chaque branche en donnant à chaque noeud un 0 à la valeur à gauche et un 1 à celle à droite.

Le résultat est une compression assez efficace tant pour les textes que pour les fichiers multimédia.

Forum

Réagissez dans les forums de JDN Développeurs

LZW : Lempel-Ziv-Welch
Construisant toujours sur la répétition d'éléments, LZW se démarque en encodant les octets par mots (de 12 bits) plutôt qu'octet par octet, construisant ainsi un dictionnaire de chaines lors de la compression. Chaque mot ne se trouvant pas dans le dictionnaire y est ajouté. Au final, on se retrouve avec un suite d'entiers pointant vers un dictionnaire.
Idéalement, les fichiers les mieux compressés sont ceux constitués d'une simple suite d'octets similaires. Dans la réalité, cet algorithme se montre néanmoins très efficace dans la plupart des circonstances, au point d'avoir été adopté dans le format Gif.