Remerciez-le!

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

Information, calcul et communication MT-EL EPFL - Semestre d’automne 2014-2015

Information, calcul et communication MT-EL EPFL - Semestre d’automne 2014-2015 Semaine 9: S´ erie d’exercices sur la compression de donn´ ees [Solutions] 1 Algorithme de Shannon-Fano a) En utilisant le jeu des questions, voici le code qu’on trouve: lettre nb apparitions nb questions mot de code I 4 3 111 N 4 3 110 O 4 3 101 C 4 3 100 M 3 3 011 A 3 4 0101 T 3 4 0100 L 2 4 0011 U 2 4 0010 F 1 4 0001 R 1 5 00001 E 1 5 00000 b) Au total, on a donc besoin de 19 × 3 + 11 × 4 + 2 × 5 = 111 bits, i.e. L(C) = 111 32 = 3.468975 bits par lettre. c) L’entropie de la s´ equence est ´ egale ` a H(X) = 3.42923. On v´ eriﬁe donc bien que H(X) ≤L(C) ≤ H(X) + 1, on on voit en fait que L(C) est beaucoup plus proche de H(X) que de H(X) + 1. d) La s´ equence contient 12 lettres diﬀ´ erentes: si on veut utiliser le mˆ eme nombre de bits par lettre, on a donc besoin de 4 bits par lettre au minimum (car 24 = 16, qui est la puissance de 2 la plus proche au-dessus de 12), et donc de 32 × 4 = 128 bits au total. On utilise donc 17 bits de plus qu’avec le code de Shannon-Fano. e) La s´ equence commen¸ cant par DIDON... a un tr` es grand nombre de D (11 pour ˆ etre plus pr´ ecis): on s’attend donc ` a une plus faible entropie. f) En utilisant ` a nouveau le jeu des questions, voici le code qu’on trouve: lettre nb apparitions nb questions mot de code D 11 2 11 N 6 2 10 O 5 3 011 I 4 3 010 U 3 3 001 A 1 4 0001 T 1 5 00001 S 1 5 00000 1 f) Le nombre total de bits utilis´ es est cette fois-ci de 17 × 2 + 12 × 3 + 1 × 4 + 2 × 5 = 84 bits, i.e. L(C) = 84 32 = 2.625 bits par lettre. Quand ` a l’entropie de la s´ equence, elle est ´ egale ` a H(X) = 2.56475. A nouveau, on v´ eriﬁe bien que H(X) ≤L(C) ≤H(X) + 1, et que L(C) est plus proche de H(X) que de H(X) + 1, mˆ eme si les probabilit´ es des lettres sont assez irr´ eguli` eres dans le cas pr´ esent. g) La s´ equence contient 8 lettres diﬀ´ erentes: si on veut utiliser le mˆ eme nombre de bits par lettre, on a donc besoin de 3 bits par lettre au minimum (car 23 = 8) et donc de 32 × 3 = 96 bits au total. On utilise donc 12 bits de plus qu’avec le code de Shannon-Fano. 2 Codage par plages (run-length encoding) a) Vu que chaque ligne de la premi` ere image est unicolore, son code RLE est donn´ e par 1111|1111|0111|0111|1111|1111|0111|0111 (longueur totale de 32 bits) Sur chaque ligne de la deuxi` eme image, on voit le mˆ eme motif de 4 pixels noirs (encod´ es par 1011) suivis de 4 pixels blancs (encod´ es par 0011), donc le code RLE de l’image est 1011|0011|1011|0011|... (longueur totale de 64 bits) Sur la troisi` eme image, les deux premi` eres lignes sont des s´ eries altern´ ees de noir et blanc, donc avec le codage RLE, chacun des pixels est repr´ esent´ e par 4 bits! (0000 si le pixel est blanc, ou 1000 si le pixel est noir). Donc rien que l’encodage des deux premi` eres lignes requiert 16 × 4 = 64 bits1! Les six prochaines lignes ne requi` erent chacune que 4 bits, comme sur la premi` ere image. Au total, on a donc besoin de 64 + 24 = 88 bits; clairement pas une compression! b) Dans cet exercice, on a choisi d’encoder l’image ligne par ligne, mais rien ne nous empˆ eche de faire la mˆ eme chose colonne par colonne. Pour pr´ eciser notre choix dans le code RLE, il suﬃt d’ajouter un bit au d´ ebut: 0 pour “ligne par ligne” et 1 pour “colonne par colonne”. On peut aini repr´ esenter la deuxi` eme image avec 33 bits au total: 1|1111|1111|1111|1111|0111|0111|0111|0111 c) On voit bien que le codage RLE des deux premi` eres lignes est loin d’ˆ etre optimal. Une fa¸ con de rem´ edier ` a ¸ ca est de changer la structure des paquets, en ajoutant un bit au d´ ebut de chaque paquet (dont la longueur passe donc ` a 5 bits): si ce bit vaut 0, alors les quatre prochains bits sont ` a interpr´ eter au sens du code RLE ci-dessus; par contre, si le premier bit du paquet vaut 1, alors les quatre prochains bits sont simplement les couleurs des 4 pixels de l’image. Ainsi, la troisi` eme image sera encod´ ee par la s´ equence de bits suivante: 11010|11010|10101|10101|00111|00111|01111|01111|00111|00111 pour une longueur totale de 50 bits (51 si on ajoute le premier bit 0 de la partie b) pour dire qu’on proc` ede ligne par ligne). 2 39 17 16 15 13 39 17 16 15 13 15 13 39 17 16 15 13 0 0 0 0 1 1 1 1 a b c d e 39 17 16 15 13 33 28 61 100 a b c d e 0 0 0 0 1 1 1 1 Figure 1: ` a gauche: code de Shannon-Fano code; ` a droite: code de Huﬀman 3 Algorithme de Huﬀman L’arbre binaire pour les deux diﬀ´ erents codes apparaˆ ıt sur la ﬁgure ci-dessus. Le dictionnaire obtenu par le code de Shannon-Fano est: a →00, b →01, c →10, d →110, e →111 Donc le nombre moyen de bits utilis´ e par le code de Shannon-Fano est: (39 + 17 + 16) × 2 + (15 + 13) × 3 100 = 228 100 = 2.28 bits/lettre Le dictionnaire obtenu par le code de Hufman est: a →0, b →100, c →101, d →110, e →111 Donc le nombre moyen de bits utilis´ e par le code de Huﬀman est: 39 × 1 + (17 + 16 + 15 + 13) × 3 100 = 222 100 = 2.22 bits/lettre La limite th´ eorique donn´ ee par le th´ eor` eme de Shannon est l’entropie: Entropie = −0.39 log2(0.39)−0.17 log2(0.17)−0.16 log2(0.16)−0.15 log2(0.15)−0.13 log2(0.13) ≈2.18 bits/lettre A noter que dans ce cas, la borne inf´ erieure ne peut pas ˆ etre atteinte. Du fait que les codes de Huﬀman sont optimaux (pour la compression sans pertes), on ne peut donc pas trouver dans ce cas un sch´ ema de compression qui fasse mieux que 2.22 bits/lettre. Le th´ eor` eme de Shannon est vrai pour tous les codes et toutes les sources. Dans certains cas, la borne inf´ erieure que constitue l’entropie ne peut ˆ etre atteinte (de fait, le th´ eor` eme ne dit pas qu’elle doit l’ˆ etre). 1On n´ eglige ici les deux pixels blancs qui se suivent de la ﬁn de la premi` ere ligne au d´ ebut de la seconde. 3 uploads/S4/ icc-serie-2-3-sol.pdf