Compression des données ( Codage Huffman )

[invited467ddce]

Bonjour,

J'aimerais qu'on m'explique l'après Huffman.
Je m'intéresse à la compression des données mais malheureusement je ne comprends pas toutes les étapes.

En me renseignant sur internet j'ai pu trouver quelques méthodes de compressions ( répétition, prédiction, dictionnaire, ... ), mais je vais par exemple simple vous montrez la partie que je comprends pas.

Admettons que notre codage de Huffman nous donne :

A = 11
B = 111
C = 101
D = 1000
E = 10
F = 1011
...
etc...

( Données prises aux hasards )

Comment vont ensuite être compressées les données?

En effet on a des lettres codées sur 2 bits, d'autres 3 et d'autres 4 bits.

Comment l'ordinateur vas reconnaître tout ça?

Exemple:

101111

Peut donner soit : 1011 11 => FA
soit : 101 111 => CB

Merci pour votre aide
-----

[cristolab]

Bonjour,

En fait si tu veux encrypter par l'algo de Huffman, il y a deux étapes à respecter :
- Création d'un arbre binaire (b-tree) par pondération des occurences.
- Encryptage des caractères en utilisant notre arbre binaire.

CREATION DE L'ARBRE BINAIRE :
Prenons par exemple le mot TATAYET (oui je sais c'est pas terrible mais idéal pour l'exemple).
Dans un 1er temps il nous faut compter les occurences de chaque caractère utilisé :
T : 3 fois; A : 2 fois; Y : 1 fois; E : 1 Fois

Le but, est de générer un arbre dont toutes les lettres utilisées (T,A,Y et E) seront ses feuilles (le bout des branches ) pondérées par leur occurence respective dans le mot TATAYET (donc 1 pour Y et E).

Le second but est de mettre les lettres les moins présentes dans le mot (pour notre exemple Y et E) le plus bas possible, de façon à créer un noeud parent pondéré de la somme des valeurs de ses enfants (1(Y) + 1(E) ) qui lui même va être associé à un autre noeud ou à une feuille (A) pour générer un nouveau noeud parent ayant pour valeur la somme de ses enfants. Et ainsi de suite jusqu'à la racine de l'arbre.

Au final on doit obtenir un arbre qui ressemble à ça :

. . . . . . . [(7)]. . . . .
. . . . . . /. . . . \ . . . .
. . . . [(4)] . . . [T:3]
. . . . / . . .\ . . . . . . .
. . [(2)] . . [A:2] . . .
. . /. . . \ . . . . . . . . .
[Y:1] . . [E:1] . . . . .

En fait le plus compliqué c'est de construire cet arbre.
Ensuite il reste à déterminé la valeur binaire de chaque feuille.
On peut par exemple dire que quand on descend d'un noeud vers la gauche, on rajoute un "0" et vers la gauche on rajoute un "1".

. . . . . . . [(7)]. . . . .
. . . . . 0/. . . . \1 . . .
. . . . [(4)] . . . [T:3]
. . . 00/ . .\01 . . . . . . .
. . [(2)] . . [A:2] . . .
000/. .\001 . . . . . . . . .
[Y:1] . [E:1] . . . . .


Donc dans notre arbre les lettres auront donc le codage binaire suivant :
T = 1
A = 01
E = 001
Y = 000

Donc pour encrypter TATAYET on devra écrire : 1 01 1 01 000 001 1. Ce qui fait 13 bits, au lieu des 63 en ASCII (7 octets de 8 bits).

Et j'arrive à ta question je pense... En fait lors de la décompression, la séquence binaire est lue en parcourant l'arbre binaire... l'algorithme sait donc à quel moment le bit en cours de lecture est sur une feuille (une Lettre) et qu'il faut repartir du haut de l'arbre !

Par exemple, quand on va lire notre TATAYET encrypté (1 01 1 01 000 001 1 ) :

1 : Stop, c'est une feuille (1 = T)

0 : On continue c'est un noeud
01 : Stop c'est une feuille (01 = A)

1 : Stop, c'est une feuille (1 = T)

0 : On continue c'est un noeud
01 : Stop c'est une feuille (01 = A)

0 : On continue c'est un noeud
00 : On continue c'est un noeud
000 : Stop c'est une feuille (000 = Y)

etc...

Voila j'espère avoir été le plus clair possible !

Bon Courage

[invited467ddce]

Oui, merci beaucoup.

Cependant ayant compris cette étape, une nouvelle question me vient;

L'arbre est donc fournis avec le fichier?

Je voudrais savoir aussi si cet algorythme a connu des version plus élaborées et si oui comment procède-t-on?

De plus si vous avez de bon liens à me fournir sur le sujet, je suis preneur.

Merci

[invited467ddce]

Oula, en plus je viens de me rendre compte que j'ai pas tout à fait compris en voyant des arbres plus complexe que ton exemple.

Dans ton exemple le 1 est systèmatiquement une feuille. Mais j'ai vu d'autres arbres où celà n'était pas le cas. En effet tu n'as que 4 lettres à coder, mais si tu en avais 26, tu irais jusqu'à 25 bits, ce qui n'est pas très avantageux.

Merci si tu peux reprendre ton explications pour un exemple plus complexe ^^.

[A voir en vidéo sur Futura]

[Philou67]

Il ne faut pas oublier que les mots les plus longs sont aussi ceux les moins utilisés (et inversement).

[cristolab]

Bonjour,

Oui, en fait l'intérêt de ce codage, est de créer un arbre binaire comme nous l'avons fait ci dessus et de le stocker dans le fichier.
Alors c'est sur que pour une chaine de quelques caractères, on ne gagne pas grand chose à la compression, sil il faut tenir compte de la taille de l'arbre à enregistrer... Mais sur des chaines plus grandes, le taux de compression peut devenir très intéressant.

Cet algorithme est en fait adaptable... Dans notre cas nous avons compter les occurences de chaque caractère (on pourrait aussi compter les séquences de caracètères en suivant le même principe) pour définir notre arbre : Nous l'avons donc créé Dynamiquement. L'inconvénient c'est le temps de traitement passé à compter les occurences. Sinon on peut créer l'arbre Statiquement : On peut décider de travailler avec un arbre statique par exemple en considérant la probabilité de trouver plus tel ou tel caractère sur un certain type de fichiers. Du coup plus besoin de stocker l'arbre dans le fichier puisque ce sera toujours le même.

Cette façon d'encrypter peut être intéressante quand on travaille sur un certain type de fichier ou l'on sait qu'on retrouvera très régulièrement certains caractères ou séquences de caractères.

Pour les liens, tu peux regarder sur Wikipedia mais c'est assez léger pour définition. Ensuite les algos dérivant de celui de Huffman, ne portent plus le même nom...

Bon Courage !

[cristolab]

Oula, en plus je viens de me rendre compte que j'ai pas tout à fait compris en voyant des arbres plus complexe que ton exemple.

Dans ton exemple le 1 est systèmatiquement une feuille. Mais j'ai vu d'autres arbres où celà n'était pas le cas. En effet tu n'as que 4 lettres à coder, mais si tu en avais 26, tu irais jusqu'à 25 bits, ce qui n'est pas très avantageux.

Merci si tu peux reprendre ton explications pour un exemple plus complexe ^^.

Non , heureusement que non !

Dans un arbre plus complexe, on aurait 2 ou même 3 niveaux de plus, si on voulait toujours encoder les caractères de l'alphabet. Et puisque chaque niveau de l'arbre rajoute un seul bit... On passerait donc à 5 ou 6 bits maximum. On est loin des 25 bits par caractère.

(je ne refais pas un arbre car c'est pas évident à faire ici sur le forum)

C'est important de construire ton alphabet encrypté en lisant ton arbre de la racine vers ses feuilles ! (en respectant le 0 à gauche et le 1 à droite ). Et donc impossible d'arriver à 25 bits !

Si ton arbre arrive à une profondeur de 25 niveaux, tu pourrais encoder une liste de plusieurs millions d'éléments.

Bon Courage

[Philou67]

Critolab, je vais poser une question de candide (huffman, c'est ancien pour moi).

On aurait pu construire l'arbre de TATAYET ainsi :

. . . . . . . . . [(7)]
. . . . . . . . /. . . . \
. . . . . . . /. . . . . . \
. . . . . . /. . . . . . . . \
. . . . [(2)] . . . . . . .[(5)]
. . . . /. . .\ . . . . . . /. . .\
. .[Y:1] . [E:1] .[A:2] . [T:3]

Dans ce contexte, l'écriture de TATAYET serait de 11 10 11 10 00 01 11 ce qui fait 14 bits (légèrement moins bon que le codage que tu proposes).
Cependant, lors de la construction de l'arbre, difficile de faire le bon choix. Ne faudrait-il pas utiliser une pondération qui tienne compte à la fois du nombre d'occurrence, mais également de la taille du mot par rapport à la position dans l'arbre (ce qui allonge considérablement la construction de l'arbre).

[invited467ddce]

Oula, je comprends plus rien.

Philou67 pose une bonne question.
Car en effet son arbre met précisément le doigt sur la partie que je comprends plus.

Dans ton arbre cristolab tu avais tout simplement 0 = continue et 1 = stop ( en gros )

Tandisque dans selui de Philou, et surtout si on le prolonge se ne sera pas toujours le cas.

Donc comment l'ordinateur sais quand stoper dans ce cas là?

Car si on prolonge l'arbre on aura forcément des conflits ( enfin je crois :s ), comme j'avais donné l'exemple dans mon premier post.

C'est à dire dans la chaine : 110111, doit on couper 1101 11 ou 110 111...

[cristolab]

Critolab, je vais poser une question de candide (huffman, c'est ancien pour moi).

On aurait pu construire l'arbre de TATAYET ainsi :

. . . . . . . . . [(7)]
. . . . . . . . /. . . . \
. . . . . . . /. . . . . . \
. . . . . . /. . . . . . . . \
. . . . [(2)] . . . . . . .[(5)]
. . . . /. . .\ . . . . . . /. . .\
. .[Y:1] . [E:1] .[A:2] . [T:3]

Dans ce contexte, l'écriture de TATAYET serait de 11 10 11 10 00 01 11 ce qui fait 14 bits (légèrement moins bon que le codage que tu proposes).
Cependant, lors de la construction de l'arbre, difficile de faire le bon choix. Ne faudrait-il pas utiliser une pondération qui tienne compte à la fois du nombre d'occurrence, mais également de la taille du mot par rapport à la position dans l'arbre (ce qui allonge considérablement la construction de l'arbre).

Bonjour,

Oui c'est pour ceci que j'ai précisé précédemment qu'il est important de mettre les caractères de faible valeur (donc moins présents dans la chaine en encrypter) le plus bas possible dans l'arbre.
Ainsi, les caractères les plus présents, seront donc plus haut, et donc un code binaire plus léger (le code binaire étant de longueur égale à la profondeur du caractère dans l'arbre).

Après en effet, ton arbre n'est pas optimal mais il est tout à fait bon !


Bon Courage !

[cristolab]

Oula, je comprends plus rien.

Philou67 pose une bonne question.
Car en effet son arbre met précisément le doigt sur la partie que je comprends plus.

Dans ton arbre cristolab tu avais tout simplement 0 = continue et 1 = stop ( en gros )

Non ! 1 ne voulait pas dire Stop... c'est juste que en suivant 1 dans mon premier Arbre, on arrivait directement à une feuille (et non un noeud) donc forcement on sait que le "parsing" (l'interpretation) stoppe à ce moment.
Je vais reprendre le codage complet du mot TATAYET pour que tu comprennes :
(1 01 1 01 000 001 1 ) :

1 : Stop, c'est une feuille (1 = T)

(on remonte à la racine)

0 : On continue c'est un noeud
01 : Stop c'est une feuille (01 = A)

(on remonte à la racine)

1 : Stop, c'est une feuille (1 = T)

(on remonte à la racine)

0 : On continue c'est un noeud
01 : Stop c'est une feuille (01 = A)

(on remonte à la racine)

0 : On continue c'est un noeud
00 : On continue c'est un noeud
000 : Stop c'est une feuille (000 = Y)

(on remonte à la racine)

0 : On continue c'est un noeud
00 : On continue c'est un noeud
001 : Stop c'est une feuille (001 = E)

(on remonte à la racine)

1 : Stop, c'est une feuille (1 = T)

Le Codage binaire de chaque Caractère, correspond à sa position dans l'arbre ! le E par exemple egal à 001, correspond donc à sa position (gauche/gauche/droite) en descendant de la racine vers les feuilles.

[invited467ddce]

Ah ok en effet, j'avais mal compris, car je pensais à des situations impossibles.

Ok, merci bien pour ton aide.
Je vais continuer de réfléchir sur ce sujet, et si j'ai un problème, je reviens.

Par contre j'ai regardé sur wiki ( et ailleurs ) et j'ai pas trouvé beaucoup d'aide sur la compression des données...

[Philou67]

En gros, ma question tend à demander la chose suivante : en plus de mettre les occurrences les plus faibles en bas de l'arbre, faut-il chercher à équilibrer les branches de l'arbre ?

[cristolab]

En gros, ma question tend à demander la chose suivante : en plus de mettre les occurrences les plus faibles en bas de l'arbre, faut-il chercher à équilibrer les branches de l'arbre ?

Il doit être relativement équilibré de façon à avoir une profondeur de codage minimum.

Il doit aussi être équilibré par rapport à ses valeurs : Un Déséquilibre de cet ordre signifiera, qu'un enfant (son ou ses caractères) d'un noeud ou de la racine est bien moins présent que l'autre enfant (son ou ses caractères) dans le texte à compresser. Du coup on aura optimisé le codage de caractères "rares" au détriment de caractères peut être plus présent...

Pour l'algorithme exact de création de l'arbre de Huffman, je ne le connais pas, mais je vais essayer de me pencher dessus.

[Philou67]

C'est pour cette raison que je proposais de pondérer en fonction de l'occurrence ET de la taille du mot.