Discussion :

[hbx360]

Bonjour, je suis actuellement en train de codé l'algo de Huffman, mais il y a quelque chose que je ne comprends pas, c'est comment créer le dictionnaire. Par exemple si j'ai :

s : 111
e : 110
l : 101
c : 100
b : 000
a : 01

comment je fais pour mettre les codes ? Parce que si je met par exemple 111 dans un char j'aurai dans mon char :

0000 0111 mais j'ai toujours 1 octet !

J'ai une struct ou il y a un char pour la lettre et un char pour accueillir le code binaire de la lettre mais je me retrouve comme dit plus haut avec un code binaire de 1 octet. Voilà.

[gerald3d]

Bonjour.

Il te faut construire les octets par décalage de bit.

Regarde pour ce faire les opérateurs << et >>.

[hbx360]

ok merci pour ta réponse donc si je fais comme tu dis j'ai toujours mon problème.
Ce que je ne comprends pas c'est que si : a vaut 01 j'aurai dans mon char 0000 0001 et quand je ferai ma compression j'aurai
0000 0001 pour la lettre a ce qui fera un octet donc ça va pas.

[Bousk]

C'est sûr que si tu n'encodes qu'un caractère...
L'intérêt est de pouvoir écrire lac dans 1 octet 10101100. Pas d'avoir 3 octets 00000101 00000001 00000100.
Il faut faire des décallages de bits (bis).

[gerald3d]

D’après ce que je comprends de l’algorithmique le dictionnaire aura une taille de 6x8bits pour chaque lettre + 17 bits pour les codes, soit 65 bits au final.

Le code sera le suivant :

Code :

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

1
2
3
 
   000         01100010           01             01100001          100      01100011        101      01101100      110        01100101      111     01110011
préfixe b   code ascii de b   préfixe a     code ascii de a      pré. c        c           pré.l       l          pré. e         e         pré. s      s

Une fois construit tu va ajouter à ce dictionnaire tous les codes de ton texte.

Prenons par exemple le texte original suivant : cablesa

Tu vas échanger le code ascii de chaque lettre par son pendant dans le dictionnaire :

Code :

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

1
2
3
 
100 01 000 101 110 111 01
 c   a  b   l   e   s  a

Tu as maintenant ce mot codé sur 19 bits au lieu de 56 bits.

Ton fichier final aura donc une taille de : taille dictionnaire + encode du texte = 65 + 19 = 84 bits.

Bien entendu ici le taux de compression n'est pas bon du tout puisque notre fichier final est plus gros que l'original. Mais comme je ne connais pas le fichier source utilisé pour extraire le dictionnaire et comme j'ai pris un exemple farfelu, forcément le résultat est plus qu'aléatoire. . Mais le principe est là.

[hbx360]

Merci pour vos réponses.

@Bousk : L'intérêt est de pouvoir écrire lac dans 1 octet 10101100. Pas d'avoir 3 octets 00000101 00000001 00000100.
Il faut faire des décallages de bits (bis).

Ok ça j'ai compris. Mais comment tu associes la lettre au code binaire moi j'ai fais comme dit plus haut une struct avec un char pour ma lettre et un char pour recevoir le code binaire le problème c'est que le char pour le code binaire sera par exemple pour 'a' : 01 ce qui fera dans le char 0000 0001 mais comment tu fais pour que l'ordi comprenne que c'est 01 ?

Par exemple ce que je voulais faire c'est : lire mon fichier à compressé, je prends la première lettre je fais une condition si la lettre 'L' du fichier est égale à la lettre 'L' qui est dans mon tableau de struct je prends le code binaire et je l'insère dans un autre fichier mais là j'aurai 0000 0101 pour le 'L'. Donc sa va pas je comprends pas.

Ou bien est-ce qu'il faut lire la lettre 'L' (par exemple) qui est dans le fichier parcourir l'arbre jusqu'à trouver la même lettre qui est dans l'arbre et ensuite inséré le code binaire dans le nouveau fichier ? Ce qui complique grandement les choses je trouve car le programme devra faire plusieurs parcours de l'arbre pour trouver la bonne lettre.

Y a vraiment un truc que je ne pige pas.

Et comment on fait le dictionnaire ? On met dans un fichier la lettre 'L' par exemple et ensuite pour le code binaire ?

[gerald3d]

J'ai modifié mon post précédent. J'ai pris un exemple complet pour te montrer comment on construit le fichier final.

En espérant que cela t'aide un peu...