Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Compression (M1) – LZ78 & LZW C. Nicaud Dans ce chapitre, on s’int´ eresse ` a

Compression (M1) – LZ78 & LZW C. Nicaud Dans ce chapitre, on s’int´ eresse ` a un autre algorithme de compression adapt´ e au textes, invent´ e ´ egalement par Lempel et Ziv, ainsi qu’` a une de ses variantes. 1 Principe des algorithmes Ce sont des algorithmes de compression “avec dictionnaire”. Comme pour LZ77, quand on reconnaˆ ıt un mot de notre dictionnaire on l’encode par un num´ ero (son index dans le diction- naire) pour gagner de la place. La constitution du dictionnaire est dynamique pour s’adapter automatiquement au texte ` a compresser. Dans LZ77, le dictionnaire ´ etait constitu´ e de la fenˆ etre des W caract` eres pr´ ec´ edents. Dans LZ78 et LZW, on va cr´ eer et maintenir un dictionnaire en y ajoutant un mot ` a chaque ´ etape. 2 LZ78 Le principe est le suivant: • On commence avec un dictionnaire qui ne contient que ϵ 7→0 : cela signiﬁe qu’initialement il n’y a que le mot vide dans le dictionnaire, et que son indice est 0. • A chaque ´ etape on cherche le plus long pr´ eﬁxe v qui est dans le dictionnaire (donc tel que le pr´ eﬁxe suivant va n’est pas dans le dictionnaire) puis: – On ´ emet le couple (Dico[v], α), o` u Dico[v] est l’indice de v dans le dictionnaire. – On ajoute vα dans le dictionnaire, d’indice la taille du dictionnaire moins 1. – On repart dans le texte apr` es vα. L’algorithme ´ emet donc une s´ equence de couples (i, c) o` u i est un indice dans le dictionnaire, et c un caract` ere. Remarque : ` a la toute ﬁn, si la totalit´ e du mot est dans le dictionnaire, on prend le mot sans la derni` ere lettre pour v, pour qu’il reste un caract` ere α derri` ere (et ainsi ne pas avoir ` a ajouter un symbole “pas de caract` ere”). Exemple : consid´ erons le mot u = abaaaabaab, la barre | indique o` u on en est dans le texte. texte v alpha ajout au dico (init) eps->0 |abaaaabaaa eps a a->1 a|baaaabaaa eps b b->2 ab|aaaabaaa a a aa->3 abaa|aabaab aa b aab->4 abaaaab|aab aa b Donc la sortie sera: (0, a), (0, b), (1, a), (3, b), (3, b). Pour la d´ ecompression, il s’agit de reconstituer le dictionnaire exactement de la mˆ eme fa¸ con que l’algorithme de compression. Cela ne pr´ esente pas de diﬃcult´ e particuli` ere. Exemple : consid´ erons la s´ equence (0, a), (0, b), (1, a), (3, b), (3, b): 1 paire mot produit ajout au dico init 0->eps (0,a) a 1->a (0,b) b 2->b (1,a) aa 3->aa (3,b) aab 4->aab (3,b) aab On retrouve bien le mot u = abaaaabaab. 3 LZW C’est une variante de l’algorithme de Lempel-Ziv 78, invent´ ee en 1984 par Welch. Il est notam- ment utilis´ e dans le format d’image gif. L’id´ ee est la mˆ eme que pour LZ78, sauf que : • On connaˆ ıt l’alphabet et on commence avec tous les mots d’une lettre dans le dictionnaire (et non juste le mot vide comme pour LZ78). • A chaque ´ etape, on cherche v et α comme pour LZ78, mais on n’encode que v, par son num´ ero. On ajoute toujours vα dans le dictionnaire ensuite, et on repart de α puisqu’il n’a pas ´ et´ e encod´ e. Exemple : consid´ erons le mot u = abababaab sur l’alphabet A = {a, b}. La barre | indique o` u on en est dans le texte. Au d´ ebut, le dictionnaire contient a 7→0 et b 7→1. texte v alpha sortie ajout au dico (init) a->0, b->1 |abababaab a b 0 ab->2 a|bababaab b a 1 ba->3 ab|ababaab ab a 2 aba->4 abab|abaab aba a 4 abaa->5 abababa|ab ab . 2 Donc la sortie sera: (0, 1, 2, 4, 2). Attention (seule subtilit´ e du chapitre) : ` a la d´ ecompression, on a un temps de retard dans la cr´ eation du dictionnaire. Cela est du au fait que dans l’algorithme de compression, on ajoute vα dans le dictionnaire, mais on n’encode que v. Donc il faut attendre l’´ etape d’apr` es pour identiﬁer α, la premi` ere lettre du mot suivant, et retrouver quel mot avait ´ et´ e ajout´ e dans le dictionnaire ` a l’´ etape pr´ ec´ edente. Essayons de d´ ecompresser (0, 1, 2, 4, 2) sur l’alphabet A = {a, b}: Num v ajout au dico init 0->a, 1->b 0 a (il faut attendre le mot suivant pour identifier sa 1ere lettre) 1 b 2->ab (le v de la ligne au-dessus, suivi de la 1` ere lettre du v actuel) 2 ab 3->ba (le v de la ligne au-dessus, suivi de la 1` ere lettre du v actuel) 4 ??? 2 Et l` a, on est coinc´ e : comme on a un temps de retard dans la constitution du dictionnaire, le mot d’indice 4 n’est pas encore connu. Heureusement, il y a une solution ` a ce probl` eme. Si on appelle v le mot de cette ´ etape, alors on met ensuite dans le dictionnaire 4->abα, o` u α est la premi` ere lettre de v. Cela veut dire que v commence par a, et donc on peut trouver v = aba! La r` egle est g´ en´ erale : si a un moment dans la d´ ecompression on a besoin d’un mot qui n’est pas dans le dictionnaire, alors le mot dont on a besoin est le mot vα, o` u v est le mot produit ` a l’´ etape pr´ ec´ edente et α est la premi` ere lettre de v. Si on reprend l’exemple : Num v ajout au dico init 0->a, 1->b 0 a (il faut attendre le mot suivant pour identifier sa 1ere lettre) 1 b 2->ab (le v d’au-dessus, suivi de la 1` ere lettre du v actuel) 2 ab 3->ba (le v d’au-dessus, suivi de la 1` ere lettre du v actuel) 4 aba 4->aba (exception, pas d’indice 4, on utilise la r` egle ci-dessus) 2 ab Et on retrouve bien le mot abababaab. 4 Remarques diverses D’un point de vue algorithmique, le plus eﬃcace pour encoder le dictionnaire ` a la compression est d’utiliser un arbre preﬁxiel, (voir https://fr.wikipedia.org/wiki/Trie_(informatique)). Cependant, une table associative (ou hashtable en Java) est en g´ en´ eral suﬃsamment rapide en pratique. Si on veut utiliser un codage de longueur ﬁxe pour repr´ esenter les couples de la sortie de LZ78 ou les indices de la sortie de LZW, il faut ﬁxer une taille maximale pour le dictionnaire. Il faut ´ egalement une strat´ egie pour d´ ecider de quoi faire quand le dictionnaire est plein. Il existe trois strat´ egies principales : (i) ne plus modiﬁer le dictionnaire une fois qu’il est plein ; (ii) r´ e-initialiser le dictionnaire s’il est plein : avec juste le mot vide pour LZ78 et juste l’alphabet pour LZW ; (iii) enlever les feuilles de l’arbre pr´ eﬁxiel, c’est-` a-dire les mots du dictionnaire qui ne sont pr´ eﬁxe d’aucun autre mot du dictionnaire. Toutes ces m´ ethodes ne posent aucun probl` eme ` a la d´ ecompression, ` a condition que le d´ ecompresseur connaisse la taille maximale et la strat´ egie choisie en cas de saturation du dictionnaire. 5 Exercices (v´ eriﬁez que vous arrivez ` a les faire) 1. Compressez avec LZ78 et avec LZW le mot u = bbbabbaabbbb. 2. D´ ecompressez (0, ’b’), (0, ’a’), (2, ’a’), (3, ’b’), (4, ’a’) obtenu apr` es ap- plication de LZ78. 3. D´ ecompressez [1,2,0,4,1] obtenu apr` es application de LZW pour l’alphabet {a, b}. 3 6 Correction des exercices 1. On doit trouver : • pour LZ78 : (0, ’b’), (1, ’b’), (0, ’a’), (2, ’a’), (3, ’b’), (2, ’b’) • pour LZW : [1, 2, 0, 3, 4, 2, 1] 2. On doit trouver baaaaabaaba. 3. On doit trouver bbbaaab. 4 uploads/S4/ lz78.pdf