Il existe différents procédés pour compresser une information sans pertes, nous allons dans cet exemple nous intéresser à l’une des plus simples d’entre elles : le Run Length Encoding (RLE) (codage par plages en français).
Cet algorithme de compression est du point de vue théorique très simple à appréhender. En effet, on ne fait que remplacer des éléments identiques se succédant par un seul de ces éléments, suivi du nombre de répétitions.
exemple :
On peut voir avec cet exemple que la donnée compressée prend plus de place que la donnée source (7 caractères contre 6). Il est donc important de fixer un seuil du nombre de répétitions minimales à partir duquel on codera cette répétition afin d’éviter ce genre de situation, le but de la compression étant bien entendu de gagner de la place.
Le caractère ‘$’ est ici choisi comme caractère spécial (arbitraire), il permet d’indiquer une compression, et il est essentiel pour la phase de décompression (i.e. pour pouvoir retrouver la donnée source à partir de la donnée compressée).
On montre pour ces raisons que le seuil doit être supérieur ou égal à 4.
Ainsi, en appliquant un seuil de 4 on aura :
dans ce cas on ne gagne aucune place mais en tout cas on n’en perd plus.
Prenons un autre exemple :
on obtient une compression de 25% (on gagne 3 caractères sur 12).
Cette méthode n’offre malheureusement que de médiocres résultats. Par le passé, elle a été beaucoup utilisée, essentiellement pour la compression d’images. Il est en effet plus aisé de trouver des répétitions successives d’un pixel de même couleur dans une image qu’une répétition successive d’une lettre dans un texte en langue française par exemple. Dans le cas d’une image matricielle (bitmap en anglais) l’information est stockée sous la forme d’un tableau de points de couleurs (pixels). Dans une zone de l’image où la couleur est homogène on pourra donc trouver des successions de pixels identiques, et ainsi gagner en place de stockage à l’aide d’une méthode de compression tel que le RLE.
La compression sans perte (lossless data compression en anglais), appelée aussi compactage consiste en une nouvelle représentation d’une information sous une forme plus condensée. Le fait que l’on garde exactement la même quantité d’information avant et après la compression en fait une opération réversible.
Pour des données telles que du texte, un programme exécutable, un tableau excel, etc., une compression sans perte est indispensable, on ne peut pas se permettre d’altérer l’information originale.
La compression sans perte se base sur le fait que la plupart des données possèdent une certaine redondance statistique. Prenons un exemple simple : un texte écrit en langue française, statistiquement on y trouvera plus de e, s ou encore de a que de x ou y (source). Dans l’article précédent on pouvait compter ainsi 97 e, 78 r pour seulement 2 y ou un seul k. Il y a également peu de chance qu’un k suive un z. On pourra ainsi gagner de la place lors du codage d’une information en se basant sur la fréquence d’apparition des caractères dans le cas d’un texte.
Nous verrons dans le prochain article un exemple de mise en pratique de ce type de compression.
Comme dans tous échanges d’informations, la transmission de données compressées nécessite la compréhension du système de codage, aussi bien par l’émetteur que par le récepteur, afin que l’information transmise puisse être comprise par les deux interlocuteurs.
La compression de données est également l’objet de grands enjeux économiques liés aux limites technologiques. En effet, le stockage de données demande un matériel coûteux et encombrant, de plus la réduction de la consommation de bande passante lors d’une transmission de données permet une réduction des coûts.
En revanche, l’utilisation d’une donnée compressée induit une décompression et donc un surcroît de traitement pénalisant certaines applications.
On distingue deux types de compression : la compression sans perte (ZIP, PNG, FLAC, etc.) et la compression avec perte (JPG, MP3, AVI, etc.).
Une branche importante de la théorie de l’information est la compression de données, ou comment réduire l’espace nécessaire à la représentation d’une information.
Dans le cadre d’un projet informatique en première année à l’ENSISA (Ecole Nationale Supérieure d’Ingénieurs Sud Alsace) située à Mulhouse, nous traiterons dans ce blog de la compression de données, processus important lors de la transmission de données mais également dans le stockage de l’information.
Bienvenue et bonne lecture.