:: Enseignements :: ESIPE :: E3INFO :: 2008-2009 :: Algorithmique - Slot 2 ::

---

Codage de Huffman

---

Ce TD a pour objectif de se familiariser avec l'algorithme de Huffman

---

Exercice 1 - Codes

• Un code sur un alphabet A est un ensemble de mots C tel qu'aucun mot de A^* ne puisse s'écrire de deux façons différentes comme combinaison de mots de C.
• Remarque: on ne demande pas que tous les mots de A^* soient représentables comme concaténations de mots de C.
• Les ensembles suivants sont-ils des codes sur l'alphabet binaire:
  • C_1={01,11,10}
  • C_2={01,0}
  • C_3={0,01,11,10}
  • C_4={0,10,111,110}

Exercice 2 - Huffman

• En considérant la fréquence des caractères comme fonction de poids, calculez l'arbre de Huffman associé au message: adaabdeeabcac
• Calculez celui associé au message ghdgkdhghghk

Exercice 3 - Codage/ Décodage

• Comment représenter les données pour faire le code de Huffman ?
• Comment utiliser l'arbre pour coder un message ?
• Coder les messages des exercices précédents.
• Combien de bits a-t-on gagné?
• Comment envoyer le message compressé?
• On reçoit le message suivant, compressé par la méthode de Huffman. Quel est le message d'origine ?
  
  001E01T01N1I0001C1S1L01R1D100000100101010100111001100110011100110010111

---