Codage de Huffman
Fermé
rodja
Messages postés
5
Date d'inscription
jeudi 28 février 2008
Statut
Membre
Dernière intervention
31 mai 2008
-
28 févr. 2008 à 16:45
Humph - 28 févr. 2008 à 20:23
Humph - 28 févr. 2008 à 20:23
A voir également:
- Codage de Huffman
- Codage ascii - Guide
- Codage binaire - Guide
- Le codage optimisé proposé ci-dessous a été obtenu en appliquant l'algorithme du codage de huffman sur un texte. lucia a codé un mot en utilisant ce codage optimisé. elle a obtenu : 010011011000111 - Forum C
- Controleur de codage/decodage pci ✓ - Forum Pilotes (drivers)
- Fichier word illisible codage - Guide
1 réponse
Bonjour,
Le codage de Huffman désigne une manière de coder des données en fonction de leurs fréquences de répétition afin que celles-ci prennent le moins de place possible.
On prend typiquement l'exemple d'un texte. Tel qu'il est à l'état brut, chaque caractère est codé sur 8 bits. Huffman permet de detéminer sur combien de bit coder chaque caractère pour que le texte soit moins gourmand en place.
"Ceci est une phrase".
Cette phrase contient 19 caractères, soit 19 * 8 bits sur le codage classique.
Pour appliquer le codage de Huffman on s'appuie sur la fréquence de chaque caractère de la phrase.
1 a
2 c
4 e
1 h
1 i
1 n
1 p
1 r
2 s
1 t
1 u
3 espace
Le codage consiste à regrouper successivement les symboles de manières à faire de groupes dont la somme des fréquences d'apparition sont les plus proches possibles.
19 symboles, on va tenter 9 et 10 au premier tour.
a, e, c, s et a, h, i, n, p, r, t, u soit (1 + 2 + 4 + 2) et (1 + 1 + 1 + 1 + 1 + 1 + 1 + 3)
Puis on recommence dans chaque groupe afin de construire un arbre binaire. (chaque noeud à deux feuilles au maximum) Les noeuds intermédiaires sont des groupes de symboles et les feuilles, un des symboles.
Une fois l'arbre construit, pour chaque noeud, on place un 1 sur le trait vers son fils gauche et un 0 sur le trait vers son fils droit. Pour connaître le codage à attribuer à chaque symbole, on parcours l'arbre depuis la racine jusqu'au symbole voulu en écrivant les valeurs rencontrées de gauche à droite.
Dans notre exemple on redécoupera par exemple le premier lot en isolant 'e'. Son codage sera alors 1.
En redécoupant a, c et s en (a et c) et s on aura
e -> 1
a -> 111
c -> 110
s -> 10
Bref ce codage est valable pour donner une manière de coder des données qui se répètent de manière à ce qu'elle prennent le moins de place possible en attribuant à celles les plus fréquentes le codage le plus petit. Il est optimal lorsque toutes les fréquences sont des puissances de deux. (Car il n'y a pas de perte comme ici avec 9 et 10 -> déséquilibre)
Wikipédia, Codage de Huffman
Le codage de Huffman désigne une manière de coder des données en fonction de leurs fréquences de répétition afin que celles-ci prennent le moins de place possible.
On prend typiquement l'exemple d'un texte. Tel qu'il est à l'état brut, chaque caractère est codé sur 8 bits. Huffman permet de detéminer sur combien de bit coder chaque caractère pour que le texte soit moins gourmand en place.
"Ceci est une phrase".
Cette phrase contient 19 caractères, soit 19 * 8 bits sur le codage classique.
Pour appliquer le codage de Huffman on s'appuie sur la fréquence de chaque caractère de la phrase.
1 a
2 c
4 e
1 h
1 i
1 n
1 p
1 r
2 s
1 t
1 u
3 espace
Le codage consiste à regrouper successivement les symboles de manières à faire de groupes dont la somme des fréquences d'apparition sont les plus proches possibles.
19 symboles, on va tenter 9 et 10 au premier tour.
a, e, c, s et a, h, i, n, p, r, t, u soit (1 + 2 + 4 + 2) et (1 + 1 + 1 + 1 + 1 + 1 + 1 + 3)
Puis on recommence dans chaque groupe afin de construire un arbre binaire. (chaque noeud à deux feuilles au maximum) Les noeuds intermédiaires sont des groupes de symboles et les feuilles, un des symboles.
Une fois l'arbre construit, pour chaque noeud, on place un 1 sur le trait vers son fils gauche et un 0 sur le trait vers son fils droit. Pour connaître le codage à attribuer à chaque symbole, on parcours l'arbre depuis la racine jusqu'au symbole voulu en écrivant les valeurs rencontrées de gauche à droite.
Dans notre exemple on redécoupera par exemple le premier lot en isolant 'e'. Son codage sera alors 1.
En redécoupant a, c et s en (a et c) et s on aura
e -> 1
a -> 111
c -> 110
s -> 10
Bref ce codage est valable pour donner une manière de coder des données qui se répètent de manière à ce qu'elle prennent le moins de place possible en attribuant à celles les plus fréquentes le codage le plus petit. Il est optimal lorsque toutes les fréquences sont des puissances de deux. (Car il n'y a pas de perte comme ici avec 9 et 10 -> déséquilibre)
Wikipédia, Codage de Huffman
