Lempel-Ziv-Welch 96219 31426383 2008-07-09T07:06:19Z Gui777 422823 /* Principe */ {{Traduction}}'''LZW''' (pour ''Lempel-Ziv-Welch'') est un [[Algorithmique|algorithme]] de [[compression de données]] sans perte. Il s'agit d'une amélioration des algorithmes [[LZ77 et LZ78|LZ77]] (1977) et [[LZ77 et LZ78|LZ78]] (1978), tous les deux écrits par [[Abraham Lempel]] et [[Jacob Ziv]]. LZW fut créé en [[1984]] par [[Terry Welch]], d'où son nom. L'algorithme LZW avait été [[brevet]]é par la société [[Unisys]]<ref>[http://www.unisys.com/about__unisys/lzw Unisys: LZW Patent Information]</ref>. Il a été utilisé dans les [[modem]]s (norme V42 bis) et est encore utilisé dans le [[format de donnée|format]] d'[[image numérique]] [[Graphics Interchange Format|GIF]] et les fichiers audio [[mod]]. L’algorithme a été conçu de manière à être rapide à implémenter, mais n’est la plupart du temps pas optimal car il effectue une analyse limitée des données à compresser. == Description de l'algorithme == L’algorithme de compression construit une table de traduction de [[chaîne de caractères|chaînes de caractères]] à partir du texte à compresser. Cette table relie des codes de taille fixée (généralement 12-[[bit (informatique)|bit]]) aux chaines de caractères. La table est initialisée avec tous les caractères (256 entrées dans le cas de caractères codés sur 8 bits). A mesure que le compresseur examine le texte, il ajoute chaque chaîne de 2 caractères dans la table en tant que concaténation de code et de caractères, avec le code correspondant au premier caractère de la chaîne. En même temps qu’il enregistre ces chaines, le premier caractère est envoyé en sortie. Chaque fois qu’une chaîne déjà rencontrée est lue, la chaîne la plus longue déjà rencontrée est déterminée, et le code correspondant à cette chaîne avec le caractère concaténé (le caractère suivant du flux entrant) est enregistré dans la table. Le code pour la partie la plus longue de la chaîne de caractère rencontré est envoyé en sortie et le dernier caractère est utilisé comme base pour la chaîne suivante. L’algorithme de décompression à seulement besoin du texte compressé en entrée. En effet il reconstruit une table chaine de caractères / code identique à mesure qu’il régénère le texte original. Cependant un cas inhabituel apparaît chaque fois que la séquence ''caractère''/''chaîne''/''caractère''/''chaîne''/''caractère'' (avec le même caractère pour chaque ''caractère'' et la même chaîne de caractère pour chaque ''chaîne'') est rencontré en entrée et que ''caractère''/''chaîne'' est déjà présent dans la table. Quand l’algorithme de décompression lit le code pour ''caractère''/''chaîne''/''caractère'', il ne peut pas le traiter car il n’a pas encore stocké ce code dans la table. Ce cas particulier peut être géré car le programme de décompression sait que le caractère supplémentaire est le ''précédent caractère rencontré''.<ref>Welch, T. A. (June 1984). "[http://www.csa.com/partners/viewrecord.php?collection=TRD&recid=A8436773AH A technique for high-performance data compression]." ''Computer''. Vol. 17, pp. 8-19.</ref> == Algorithme == Algorithme de compression : <code> w = Nul; tant que (lecture d'un caractère c) faire si (wc existe dans le dictionnaire) alors w = wc; sinon ajouter wc au dictionnaire; écrire le code de w; w = c; fin si fin tant que écrire le code de w; </code> Algorithme de décompression : <code> lecture d'un caractère c; w = c; tant que (lecture d'un caractère c) faire si (c > 255 && l'index c existe dans le dictionnaire) faire entrée = l'entrée du dictionnaire de c; sinon si (c > 255 && l'index c n'existe pas dans le dictionnaire) faire entrée = w + w[0]; sinon entrée = c; fin si; écrire entrée; ajouter w+entrée[0] au dictionnaire; w = entrée; fin tant que; </code> ==== Exemple ==== ====== Compression ====== La table suivante montre le résultat de l'exécution de l'algorithme de compression sur la chaîne suivante: TOBEORNOTTOBEORTOBEORNOT On suppose qu'on utilise un code ASCII de 256 caractères (8-bits) comme dictionnaire de base. La longueur de cette chaîne est de 24 caractères. Elle nécessite donc 24 * 8 = 192 bits d'espace de stockage. {| class="wikitable" width='70%' cellpadding="5" !c!!w!!wc!!sortie!!dictionnaire |- |T |&lt;NIL&gt; |T | | |- |O |T |TO |T |TO = &lt;256&gt; |- |B |O |OB |O |OB = &lt;257&gt; |- |E |B |BE |B |BE = &lt;258&gt; |- |O |E |EO |E |EO = &lt;259&gt; |- |R |O |OR |O |OR = &lt;260&gt; |- |N |R |RN |R |RN = &lt;261&gt; |- |O |N |NO |N |NO = &lt;262&gt; |- |T |O |OT |O |OT = &lt;263&gt; |- |T |T |TT |T |TT = &lt;264&gt; |- |O |T |TO | | |- |B |TO |TOB |&lt;256&gt; |TOB = &lt;265&gt; |- |E |B |BE | | |- |O |BE |BEO |&lt;258&gt; |BEO = &lt;266&gt; |- |R |O |OR | | |- |T |OR |ORT |&lt;260&gt; |ORT = &lt;267&gt; |- |O |T |TO | | |- |B |TO |TOB | | |- |E |TOB |TOBE |&lt;265&gt; |TOBE = &lt;268&gt; |- |O |E |EO | | |- |R |EO |EOR |&lt;259&gt; |EOR = &lt;269&gt; |- |N |R |RN | | |- |O |RN |RNO |&lt;261&gt; |RNO = &lt;270&gt; |- |T |O |OT | | |- | |OT | |&lt;263&gt; | |} Après la compression, nous obtenons une séquence de codes de 9 bits sur la sortie : TOBEORNOT<256><258><260><265><259><261><263> Elle nécessite 16 * 9 = 144 bits d'espace de stockage. ====== Décompression ====== Le résultat de l'algorithme de décompression, sur la séquence compressée de codes de 9 bits, est présenté dans ce tableau : {| class="wikitable" width='70%' cellpadding="5" !k!!w!!entry!!w+entry[0]!!sortie!!dictionnaire |- |T |T | | |T | |- |O |T |O |TO |O |TO = &lt;256&gt; |- |B |O |B |OB |B |OB = &lt;257&gt; |- |E |B |E |BE |E |BE = &lt;258&gt; |- |O |E |O |EO |O |EO = &lt;259&gt; |- |R |O |R |OR |R |OR = &lt;260&gt; |- |N |R |N |RN |N |RN = &lt;261&gt; |- |O |N |O |NO |O |NO = &lt;262&gt; |- |T |O |T |OT |T |OT = &lt;263&gt; |- |&lt;256&gt; |T |TO |TT |TO |TT = &lt;264&gt; |- |&lt;258&gt; |TO |BE |TOB |BE |TOB = &lt;265&gt; |- |&lt;260&gt; |BE |OR |BEO |OR |BEO = &lt;266&gt; |- |&lt;265&gt; |OR |TOB |ORT |TOB |ORT = &lt;267&gt; |- |&lt;259&gt; |TOB |EO |TOBE |EO |TOBE = &lt;268&gt; |- |&lt;261&gt; |EO |RN |EOR |RN |EOR = &lt;269&gt; |- |&lt;263&gt; |RN |OT |RNO |OT |RNO = &lt;270&gt; |} == Principe == L'algorithme général est le suivant : * Initialisation : un dictionnaire de mots prédéfinis est rempli. * Lecture : ** Un caractère supplémentaire est ajouté au tampon TANT QUE celui-ci contient des mots présents dans le dictionnaire ** Si le tampon contient une séquence qui ne correspond à aucun mot du dictionnaire, on ajoute cette séquence au dictionnaire : elle sera donc de la forme A + B où A est un mot du dictionnaire et B un caractère, A est renvoyé et sorti du tampon. * Fin de l'entrée : le tampon est renvoyé s'il n'est pas vide (il correspond à un mot du dictionnaire). Notons que les codes binaires sont au début généralement émis sur 8 bits, jusqu'à ce que ces 8 bits ne suffisent plus à coder l'indice que l'on désire(par exemple l'indice 256, qu'il est nécessaire de coder sur 9 bits). On émet alors l'indice 0 pour signifier que l'on augmente le nombre de bits émis de 1. Prenons un exemple : supposons que la phrase à coder soit « repetition ». À chaque lettre est associé son code [[ASCII]]. Le dictionnaire est initialisé et associe l'indice 1 au code '0', l'indice 2 au code '1' ... etc. jusqu'à l'indice 256 qui correspond au code '255'. {| class="wikitable" |- ! Étape !! Tampon !! Émis !! Rajout au dictionnaire |- | 1 || '114'+'101' (re) || '115' (r) || 257 : '114'+'101' (r-e) |- | 2 || '101'+'112' (ep) || '102' (e) || 258 : '101'+'112' (e-p) |- | 3 || '112'+'101' (pe) || '113' (p) || 259 : '112'+'101' (p-e) |- | 4 || '101'+'116' (et) || '102' (e) || 260 : '101'+'116' (e-t) |- | 5 || '116'+'105' (ti) || '117' (t) || 261 : '116'+'105' (t-i) |- | 6 || '105'+'116' (it) || '106' (i) || 262 : '105'+'116' (i-t) |- | 7 || '116'+'105' (ti) = '261' || '0' (besoin d'un bit supplémentaire) || Aucun ajout |- | 8 || '261'+'111' (tio) || '261' (ti) || 263 : '261'+'111' (ti-o) |- | 9 || '111'+'110' (on) || '112' (o) || 264 : '111'+'110' (o-n) |- | 10 || '110' (n) || '111' (n) || Pas d'ajout |} * Au début de la compression, les codes binaires seront émis sur 8 bits. * À l'étape 1, on charge dans le tampon les 2 premiers caractères. Cette suite n'est pas présente dans le dictionnaire, donc on la rajoute. On émet ensuite sur 8 bits le code '115' (car le code '114', r en ASCII, a pour indice '115' dans le dictionnaire) et l'on supprime du tampon les caractères émis. * À l'étape 7, la chaîne '116'+'105' étant déjà présente dans le dictionnaire (indice 261), on émet le code '0' car 261 ne peut se coder sur 8 bits, il nécessite un minimum de 9 bits. Les codes émis seront donc désormais émis sur 9 bits. * À l'étape 8, on charge un nouveau caractère dans le tampon. La chaîne n'est pas présente dans le dictionnaire, donc on la rajoute. On émet ensuite l'indice de la chaîne '116'+'105' (261) et on la supprime du dictionnaire. * Les étapes suivantes suivent logiquement. ==Liens== ===Programmes associés=== *"[[lha]].exe" sous DOS. *[[7-zip]]. ===Voir aussi=== * [[LZ77 et LZ78]] * [[LZMA]] * [[LZSS]] * [[Deflate]] * [[Transformée de Burrows-Wheeler]] ===Lien externe=== * {{fr}} [http://rlwpx.free.fr/WPFF/comploc.htm Comparatif des performances de différentes méthodes de compression de fichiers] ===Notes et références=== <references/> [[Catégorie:Algorithme de compression sans perte]] [[Catégorie:Théorie de l'information]] [[cs:LZW84]] [[de:Lempel-Ziv-Welch-Algorithmus]] [[en:Lempel-Ziv-Welch]] [[es:LZW]] [[he:אלגוריתם למפל-זיו]] [[hu:LZW]] [[it:Lempel-Ziv-Welch]] [[ja:LZW]] [[ko:LZW]] [[nl:Lempel Ziv Welch]] [[pl:LZW]] [[pt:LZW]] [[ru:Алгоритм Лемпеля — Зива — Велча]] [[sv:LZW]] [[vi:LZW]] [[zh:LZW]]