Chapitre 5
Codage source et Compression des donnees
Exemple : Code ASCII (8 bits) : tous les caractères sont codes sur 8 bits
Le message “BONJOUR” est code par 7 X 8 = 56 bits
Boltzman (1850): l’Entropie décrit le désordre dans un système physique
Claude Shannon (1952): L’Entropie décrit la quantité d’information dans un
signal
Notions importantes
• Longueur Moyenne d’un codage :
Lmoy=nombre de bits du message codé / nombre de symbols du message
• Efficacite du codage E= H(x)/Lmoy
Codage de Huffman
• Qu'est-ce que le codage Huffman ? (Définition)
• Le codage de Huffman est un principe de compression sans
perte de données basé sur les statistiques d'apparition des
caractères dans le message.
• Huffman code ainsi avec une longueur variable les différents
caractères (les plus fréquents bénéficiant d'un code court) afin
de réduire la taille totale des données compressées.
Comment encoder avec le Codage Huffman ?
(Principe de chiffrement)
• Le code Huffman calcule la fréquence d'apparition des lettres dans le texte, et
trie les caractères du plus fréquent au moins fréquent.
• Exemple : Le message DCODEMESSAGE contient 3 fois la lettre E, 2 fois les lettres
D et S, et 1 fois les lettres A, C, G, M et O.
• L'algorithme de Huffman va créer un arbre ayant pour feuilles les lettres
trouvées et pour valeur (ou poids) leur nombre d'occurrence dans le message.
Pour créer cet arbre, rechercher les 2 noeuds les plus faibles (plus petit poids) et
les accrocher à un nouveau noeud dont le poids est la somme des 2 noeuds.
Répéter l'opération jusqu'à n'avoir plus qu'un seul noeud, qui deviendra la racine
(et qui aura comme poids le nombre total de lettres du message).
• Le code binaire de chaque caractère est alors obtenu en parcourant l'arbre de la
racine jusqu'à la feuille et en notant le parcours (0 ou 1) à chaque noeud.
➔ de Gauche a droite on met « 0 » en descendant et « 1 » en remontant
• L'ensemble des associations caractère-binaire constitue le dictionnaire.
• Comment décoder le Code Huffman ?
• (Principe de déchiffrement)
• Le déchiffrement du code Huffman requiert la connaissance de l'arbre ou
du dictionnaire de correspondance (caractères <-> codes binaires)
• NB: Le dictionnaire est indissociable du message, sans lui, le message ne
peut pas être décodé.
• Exemple : Décoder le message 00100010010111001111 avec le dictionnaire
décrit ci-dessous:
D=00 O=01
I=111 M=110
E=101 C=100
• Rechercher 0 ne donne aucune correspondance, continuer alors avec 00 qui est
code de la lettre D, puis 1 (n'existe pas), puis 10 (n'existe pas), puis 100 (code
pour C), etc
• Exemple : Décoder le message 00100010010111001111 avec le dictionnaire
décrit ci-dessous:
D=00 O=01
I=111 M=110
E=101 C=100
• Rechercher 0 ne donne aucune correspondance, continuer alors avec 00 qui est
code de la lettre D, puis 1 (n'existe pas), puis 10 (n'existe pas), puis 100 (code
pour C), etc
Solution
00100010010111001111
DCODEMOI
