Discussion :

[junior7872]

Qui peut m'aider à comprendre comment fonctionne l'Arbre d'Huffmann et comment on code les lettres ?

[Invité(e)]

Bonsoir
La question est un peu vague...
Quel est le problème ?
recherche de sites ou livres traitaint d'huffman, un bout d'algo incompris ?
Comme site, wikipedia est pas mal.

mabu

[junior7872]

j'ai besoin de construire un arbre d'huffman à partir d'une phrase donnée et je ne perçois pas la logique de cette construction.
l'ordre des lettres a t il une importance ? comme cela fonctionne t il ?
merci d'avance pour ton aide

[mathieu_t]

Salut!

Alors, le codage d'huffman se base sur la fréquence (ou proba) d'apparition des caractères pour compresser : ceux qui ont la plus forte proba d'apparition seront codés sur peu de bits, les autres sur plus de bits...

Par exemple si dans un fichier texte tu as 4 types de caractères:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
A : 3 / 16
B : 2 /16
I :  4 / 16
E :  7/16

On voit que E a la plus forte proba d'apparition, on fait un classement du plus grand au plus petit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
E   7/16
I    4/16
A   3/16
B   2/16

Ensuite tu additionne les 2 du bas et tu réordonnes si il faut

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
E         E     (7/16)
I   -->  A+B    (5/16)
A         I     (4/16)
B

Comme ça jusqu'à ce qu'il en reste 2 (ici plus qu'un étape mais si tu as un alaphabet de 8 caractères par ex c plus long):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
Etape1      Etape2                  Etape3
 
E         E     (7/16)       (A+B)+I  (9/16)
I   -->  A+B    (5/16)  -->    E      (7/16)
A         I     (4/16)
B

ça c'était l'étape d'arbre, maintenant il faut attribuer les codes :
tu pars de la droite et tu vas vers la gauche : à chaque colonne, tu mets 0 en haut, 1 en bas: ça donne

::--------------------------------------------------------------------------------
En 3:
"(A+B)+I" = 0
"E" = 1

::--------------------------------------------------------------------------------
En 2:
"A+B" et "I" héritent du 0 qui vient du "(A+B)+I" (de l'étape 3), et on leur rajoute un bit:
"A+B" = 00 (le 2è 0 c'est pcq il est en haut par rapport à I)
"I" = 01

"E" de l'étape 2 hérite du bit '1' de l'étape 3, il n'a pas été associé avec un autre caractère, il reste à '1'

::--------------------------------------------------------------------------------
En 1:
"E" de l'étape 1 hérite du bit '1' de l'étape 2, il n'a pas été associé avec un autre caractère, il reste à '1'

"I" hérite bit de l'étape 2, il n'a pas été associé avec un autre caractère, il reste à '01'

"A" hérite de "A+B", on lui rajoute un 0 car il est en haut par rapport à B:
"A" = 000

"B" hérite de "A+B", on lui rajoute un 1 car il est en bas par rapport à A:
"B" = 001


[EDIT]
::--------------------------------------------------------------------------------
Au final:

E = 1
I = 01
A = 000
B = 001

On voit bien que E est codé sur moins de bits que les autres, idem pour I comparé à A et B... Ce codage est donc intéressant car les caractèrs fréquemment utilisés sont codés sur peu de bits, ce qui en moyenne prend moins de place dans le fichier texte...

Voilà, en espérant ne pas m'être trompé c'est ça...
A+

[junior7872]

merci pour ton explication, je vais refaire mon exo en suivant tes explications !!!

[junior7872]

une p'te question encore !
dans une phrase à coder, par exemple "comment ça marche", j'obtiens les fréquences d'apparition suivantes :
mace_hontr
3222211111
jusque là tout va bien !!
maintenant, y a t il un ordre logique dans les lettres pour la construction de l'arbre ? (par ordre alphabétique et ordre d'apparition je ne vois pas le lien logique)

[mathieu_t]

Je comprends pas bien ce que tu entends par "ordre logique"...
L'ordre est du plus fréquent en haut au moins fréquent en bas... Ensuite si 2 lettres ont la même féquence, peu importe l'ordre dans lequel tu les mets, ça reviendra au même sur l'efficacité de la compression même si leur codage sera différent...