Vendredi 6 novembre 1998 Arash Habibi TD5.text Ce TD portait sur le codage en compression (par opposition au codage d'erreur) Pascal Mathis a fait un tres bon poly la-dessus et je me suis appuye la-dessus en partie. Plan de mon TD : 1. Exemples de code a->0 do->01 goto->11 HAUT -> 0 b->01 re->1011 printf->010 BAS -> 1 c->101 mi->1 etc.... d->1 2. L'information vehiculee par un symbole Tant qu'on ne le dira pas explicitement, les symboles seront consideres comme equiprobables. On avait vu au TD...2 (?) que si vous avez 4 niveaux, (ABCD) alors chaque echantillon vehicule 2 bits d'information (intrinsequement, ie independamment de tout codage) De meme si on a 2 niveaux, (AB) alors chaque echantillon vehicule 1 bit d'information. Que dire si on a trois niveaux ? (ABC) Alors, toujours d'apres le TD2, le debit binaire sur une ligne sur laquelle il y a trois niveau est de log2(3).R Donc chaque echantillon transporte log2(3) = 1.58 bits. Donc un echantillon sur 3 bits, meriterait plus que 1 bit pour chaque caractere, mais pas tout a fait 2 bits. CQFR : Chaque ensemble de symboles, vehicule une certaine quantite d'information (-log2(p_i) pour le symbole c_i ou p_i est la proba d'apparition du symbole c_i) Mais lorsqu'on code, alors l'information vehiculee par le codage peut etre plus grande que celle vehiculee par l'ensemble de symboles de depart. Par exemple A->00 B->01 C->10 ABC vehicule 1,58 bits/symbole alors que le code vehicule 2 bits. Ca signifie que certains codages sont plus redondants que d'autres. Pour les codes d'erreur, on cherche a introduire de la redondance dans le code. Pour la compression on cherche a eliminer la redondance de maniere a trouver LE CODE OPTIMAL qui ne vehicule qu'exactement l'information portee par l'ensemble de symboles de depart. 3. Le codage prefixe. On cherche le code optimal. On montre que ce code optimal est prefixe. C'est a dire qu'aucun mot du code n'est le prefixe de l'autre. Dans ces cas-la, le codage peut etre represente par un arbre. Les feuilles de l'arbre sont les mots de code. Interet du codage prefixe : pas besoin de separer les mots de code. 4. Differents types de compression - D'abord eliminer les mots de code qui ne correspondent a aucun symbole Par exemple supposons qu'une communication entre deux informaticiens ne necessite pas un vocabulaire de plus de 2000 mots. :^) En moyenne les mots ont 6 lettres. Si chaque lettre est code par un caractere ASCII, alors une communication de 1000 mots revient a transmettre 1000 x 6 x 8 = 68000 bits. Alors qu'en fait pour connaitre les 2000 mots, il suffit d'avoir 11 bits. Et du coup, 1000 mots reviennent a 11000 bits. Pourquoi ? parce qu'avec 6 fois 8 bits, on peut faire beaucoup plus de choses qu'avec 11 bits et qu'entre informaticiens on n'a pas besoin de toutes ces choses qui, par dessus le marche demandent de la bande passante en plus. Un codage ou tous les mots de code correspondent a un symbole sont des codes COMPLETS. Dans leur representation en arbre, toutes les feuilles correspondent a un mot de code. Dans le dictionnaire ce n'est pas le cas, dans abc non plus. - Meme lorsque tous les mots de code correspondent a un symbole, ce n'est pas toujours evident. Supposons un ensemble de symboles abcdefgh. un fichier qui est compose de 100 fois a suivi d'une occurrence des autres caracteres : aaaaaaaaaaa..(100 fois)....aaaaaaaabcdefgh Que dire d'un code : a->000 b->001 c->010 d->011 e->100 f->101 g->110 h->111 Avec un tel codage, le fichier devrait contenir (100+7)x3 = 321 bits Que dire d'un code : a->0 b->1000 c->1001 d->1010 e->1011 f->1100 g->1101 h->1110 Avec un tel codage, le fichier devrait contenir 100x1 + 7x4 = 128 bits Et encore ce n'est pas un code complet. a a une proba de 100/107 -log2(p_a) = 0.0976 b - --- ----- -- 1/107 -log2(p_b) = 6.74 c - --- ----- -- 1/107 -log2(p_c) = ---- d - --- ----- -- 1/107 -log2(p_d) = ---- e - --- ----- -- 1/107 -log2(p_e) = ---- f - --- ----- -- 1/107 -log2(p_f) = ---- g - --- ----- -- 1/107 -log2(p_g) = ---- h - --- ----- -- 1/107 -log2(p_h) = ---- Donc en theorie on peut encore coder ce fichier sur 6.74 x 7 + 100 x 0.0976 = 56.95 bits. La grandeur - Sigma p_i log2(p_i) represente la moyenne de ces nombres de bits par symbole. C'est l'entropie du codage. Dans les deux cas, on va voir le codage de Huffmann. Ca nous donne un code complet et optimal. - Une autre demarche consiste a : Au lieu de donner peu de bits pour les symboles qui reviennent souvent, on peut donner le meme nombre de bits pour tout le monde, mais on peut se prendre de nouveaux symboles pour des choses qui reviennent. -> Codage par dictionnaire Lempel-ziv (cf compress, gzip, gif(lzw)). 5. Huffmann Explication : construction de l'arbre de Huffmann et elaboration du codage. Exemple : l'ane sauvage de Somalie cf le Tannenbaum. Une jeune chercheuse en biologie brillante mais tres pauvre, vient de faire une decouverte sensationnelle ... Elle a 1800 F. Elle voudrait envoyer la sequence des 100 000 000 bases de l'ADN de l'ane sauvage de Somalie Sachant que la transmission soute 0.001 centimes par bits, va-t-elle y arriver ? Pouvez-vous l'aider a y arriver si vous savez que la probabilite d'avoir une Ad : 0.5 Cy : 0.3 Gu : 0.15 Th : 0.05 (Faire un codage d'Huffmann) 6. Lempel-Ziv Au lieu de coder les caracteres sur 8 bits, on les codes sur 16 bits. Au lieu de 256 possibilites, on a 65536 possibilites. On prepare un dictionnaire des symboles : a -> 0 b -> 1 c -> 2 ... X -> 255 ? -> 256 ? -> 257 ... ? -> 65535 Les 256 places sont deja prises par les caracteres ASCII. La fonction : MotCode_t Dico(symbole_t s) rend le mot de code correspondant un symbole donne boolean InDico(symbole_t s) rend vrai ou faux selon que le symbole s se trouve dans le dico ou non. On cherche a compresser un fichier F1 en un fichier F2 void ChercheCodePlusGrandQue(symbole_t s) { s <- strcat(s, NextChar(F1)); if(InDico(s)) ChercheCodePlusGrandQue(s); else { AppendSymbolInFile(F2, Dico(s)); AddSymboleInDico(s); } } while(!EOF(F1)) { c <- NectChar(F1); ChercheCodePlusGrandQue(c); } Exemple : ABCABCABCABCABCABC A appartient au dico donc j'attend pour la suite, AB n'appartient pas au dico donc j'ecris AB dans F2 et j'ajoute AB dans le dico. C appartient au dico donc j'attend pour la suite CA n'appartient pas au dico donc j'ecris CA dans F2 et j'ajouet CA dans le dico. B appartient au dico donc j'attend pour la suite BC n'appartient pas au dico donc j'ecris BC dans F2 et j'ajouet BC dans le dico. A appartient au dico donc j'attend pour la suite AB appartient aussi au dico donc j'attend toujours la suite ABC n'appartient pas au dico donc j'ecris ABC dans F2 et j'ajoute ABC dans le dico. ABC appartient au dico donc j'attend pour la suite ABCA ... A la fin on va avoir dans le dico des mots qui representent ABCABCABCABCABC...1000fois... ABC Donc on pourra representer des pages et des pages par un symbole. Remarquable : le decodage se fait sans dictionnaire. Enfin disons que le recepteur peut reconstruire son propre dictionnaire sans l'aide de personne. Le recepteur recoit A et B et les reconnait et sait aussi que AB ne figure pas au depart sur le dictionnaire de qui que ce soit. De cette facon, le recepteur peut savoir que le premier nouveau mot dans le dictionnaire de l'emetteur est AB. et ainsi de suite.