|
La compression de données - Compressions sans perte RLE/RLE2 |
| Article posté par serioussam La méthode de compression RLE (Run Length Encoding), appelée aussi RLC (Run Length Coding), est l?une des plus simple qui soit. Le principe est de remplacer n éléments de v caractères identiques par le couple (n, v). Un peu comme le font les mathématiques en transformant une suite d?addition de ce type 5+5+5+5 en une multiplication, 4x5. Exemple de chaîne de caractère à compresser : AAAABBBCCCAACCA donnera 4A 3B 3C 2A 2C 1A. Les espaces ne figureront pas dans le fichier compressé, ils ne sont là que pour améliorer la lisibilité. Ainsi 12 éléments en remplacent 15 dans notre exemple, ce qui nous donne un taux de compression de 20% soit un gain de 3 octets. Dans notre exemple nous avons un assez bon taux de compression, mais la méthode RLE est très handicapante, en effet lorsqu?il s?agit de coder une chaîne où les séquences répétitives sont rares, on augmente rapidement la taille des informations sources. En effet pour coder 1 caractère nous utiliserons le couple (n, v) soit 2 octets. Ainsi dans les pires cas de compression la méthode RLE peut augmenter par deux la taille du fichier d?origine, dans un fichier texte on ne trouve que très rarement des répétitions de caractères qui se suivent mais pour les fichiers dont les répétitions sont importantes comme certaines images, nous pouvons diviser par 10 la taille des fichiers. Nos tests on montré en moyenne que la compression RLE donne des taux entre ?20% et 5% ce qui montre que cette méthode n?est pas vraiment exploitable malgré sa vitesse d?exécution très faible et sa consommation mémoire quasi-nulle. Nous avons remarqué que les faibles taux de compression de la méthode précédente étaient surtout dus à l?augmentation de la taille des informations qui n?ont pas plus être compressées. Nous avons donc décidé de réaliser une variante de la compression RLE minimisant la perte des informations non compressées. Pour le RLE simple, coder le couple (n, v) demande 16 octets, soit 8 octets pour n et 8 octets pour v, n nous donne la possibilité d?avoir des répétitions entre 0 et 255 caractères, ce qui est un nombre assez grand, donc la méthode RLE2 joue sur le paramètre n. Mais diminuer l?intervalle n ne suffit pas à améliorer les taux de compression, il faut donc trouver un moyen de transmettre le moins de bits possible dans le cas d?un caractère qui n?a pas plus être codé. Pour cela le RLE2 utilise un bit nommé bit témoin, ainsi si ce bit est à 1, cela signifiera que nous avons à faire au couple (n, v), si au contraire note bit témoin est à 0, alors ce qui suit est un simple caractère qui n?a pas plus être codé. Notre logiciel permet de régler le nombre de bits nécessaires pour coder n, par convention nous utiliserons 4 bits soit une occurrence maximum de 17 caractères, car une répétition minimale sera de 2 caractères. Pour coder le triplet (t, n, v) nous aurons besoin de 1+4+8=13 bits, et pour coder le couple (t, v) nous aurons besoin de 1+8=9 bits. Reprenons l?exemple précédent : AAAABBBCCCAACCA A partir de la table ASCII nous allons donner les correspondances en binaires des caractères A, B et C. A = 65 (10) = 01000001(2) B = 66(10) = 01000010(2) C = 67(10)=01000011(2) Ainsi notre chaîne de caractères AAAABBBCCCAACCA donnera en binaire (totale de 112 bits) : 01000001 01000001 01000001 01000001 01000010 01000010 01000010 01000011 01000011 01000011 01000001 01000001 01000011 01000011 01000001 Après compression nous obtiendrons (il faut savoir que le codage se fait au niveau binaire et est donc variable) : Le bit témoin sera repéré par t, le nombre de répétitions par n et enfin le caractère par v. 1001001000001 1000101000010 1000101000011 1000001000001 1000001000011 001000001 Notre chaîne de caractères une fois compressés ne fera que 74 bits soit 10 octets. Nous avons un gain de compression de 34%. Nous avons gagné 5 octets au lieu de 3 octets pour la méthode RLE simple. La méthode RLE dans les pires cas donne un taux de compression de ?100% alors que la méthode RLE donne un taux de compression de seulement ?12%. En pratique la méthode RLE2 donne des taux de compression entre ?2% et 25%. Plusieurs variantes de la méthode RLE existent, cette technique est principalement utilisée dans la compression d?images ou encore dans les images dites vectorielles. Le RLE est couramment utilisé dans les formats d?images BMP compressés, TIFF et en complément dans le JPEG. |
>> Vos commentaires [0]
|