Bonjour je travaille actuellement sur un projet dont le but est de pouvoir compresser ou décompresser un fichier selon l’algorithme de Huffman.

Cependant pour la compression, j’ai un doute sur plusieurs points à savoir le type de fichier de compression, son contenu et la méthode de décompression à utiliser.

Le fichier contenant le texte compressé doit-il être obligatoirement un fichier binaire (.bin) ou peut-il s’agir d’un simple fichier (.txt) ?

Ma seconde préoccupation concerne le contenu du fichier contenant le texte compressé.
Supposons que nous avons la phrase suivante à compresser : this is an example for huffman encoding

Et que le code associé aux caractères est le suivant :

Symbole    Code

c :             01010

d :             01011

g :             01100

l :             01101

p :             01110

r :             01111

t :             10000

u :             10001

x :             11110

h :             11111

m :             0010

o :             0011

s :             0100

a :             1001

e :             1100

f :             1101

i :             1110

n :             000

  :             101

Le fichier contiendra : 1000011111111001001011110010010110010001011100111101001001001110011011100101110100110111110111111100011101110100101001000101110000001010001101011111000001100

Mais également le code associé à chaque caractère. Finalement, il y aura dans le fichier :

1000011111111001001011110010010110010001011100111101001001001110011011100101110100110111110111111100011101110100101001000101110000001010001101011111000001100

01010

01011

01100

01101

01110

01111

10000

10001

11110

11111

0010

0011

0100

1001

1100

1101

1110

000

101

Est-ce juste ?

A présent, pout la décompression, comment puis-je décompresser le fichier si je ne sauvegarde pas mes caractères dans le fichier qui a été compressé ?

Je pourrai certes reconstituer mon arbre binaire mais comment puis- je dire que tel ou tel code corresponde à un caractère donné ? 

Merci d'avance

Hello,

Zekeee a écrit:

Le fichier contenant le texte compressé doit-il être obligatoirement un fichier binaire (.bin) ou peut-il s’agir d’un simple fichier (.txt) ?

L'extension du fichier n'est qu'indicative.  Tu peux lui donner l'extension que tu veux: .Zekeee peut faire l'affaire (certaines extensions comme .exe ou .dll par exemple sont quand même déconseillées).

Et tous les fichiers sont binaires, simplement certains sont human readable.

-
Edité par edgarjacobs 18 novembre 2022 à 23:32:36

D'accord, je peux donc créer un simple fichier '.txt'

Merci mais pour mes autres questions concernant l'algorithme de huffman. Aurais tu des suggestions de réponses à me proposer ?

Salut,

En général pour Huffman, on sauvegarde la table avant, c'est a dire ton tableau, donc pour chaque caractère, le caractère lui même, et la séquence binaire associée (qui peut être une taille sur un nombre fixe de bits) suivi du nombre de bits correspondant à cette taille par exemple).

L'arbre de Huffman n'est-il pas un arbre binaire de bits représenté sous la forme d'un tableau?
Si on sauve la longueur de l'arbre binaire, l'arbre binaire lui-même et les bits des codes, on devrait pouvoir reconstituer le texte original.

D'accord,

Du coup, si je comprend bien avec l'exemple : abca et le code a = 1, B = 00, c = 01.

Mon fichier txt contiendra

a1

B00

C01

100011

Dois-je écrire dans le fichier comme tel ou je dois privilégier une autre forme d'affichage telle que celle-ci par exemple ?

a1B00C01

100011

PierrotLeFou a écrit:

L'arbre de Huffman n'est-il pas un arbre binaire de bits représenté sous la forme d'un tableau?
Si on sauve la longueur de l'arbre binaire, l'arbre binaire lui-même et les bits des codes, on devrait pouvoir reconstituer le texte original.

Non, ce n'est pas exactement ça. On sauve le tableau, et une fois qu'on a les codes, la taille des données, le nombre de données, se déduit directement de l'encodage non ambiguë de la séquence.

Pourrais tu me donner un exemple stp ? Parce que j'ai vraiment du mal avec la compréhension du stockage des données dans les fichiers tant pour la compression que pour la décompression.

Veux-tu parler de la façon de placer 8 bits dans chaque octet?
Puisque le nombre de bits n'est pas le même pour tous les caractères, on pourrait d'abord placer un bit par octet.
Et ensuite compresser à 8 bits par octet.

Et comment sait-on le nombre de bits dans le dernier octet? On pourrait ajouter un N+1ième octet donnant justement cette information.

-
Edité par PierrotLeFou 19 novembre 2022 à 14:47:01

edgarjacobs a écrit:

Hello,

Zekeee a écrit:

Le fichier contenant le texte compressé doit-il être obligatoirement un fichier binaire (.bin) ou peut-il s’agir d’un simple fichier (.txt) ?

L'extension du fichier n'est qu'indicative.  Tu peux lui donner l'extension que tu veux: .Zekeee peut faire l'affaire (certaines extensions comme .exe ou .dll par exemple sont quand même déconseillées).

Et tous les fichiers sont binaires, simplement certains sont human readable.

-
Edité par edgarjacobs il y a environ 15 heures

Il faut cependant faire attention à la différence qu'on retrouve sur les plateformes windows vs unix lors de l'ouverture d'un fichier via fopen. Il y a une différence entre un fichier ouvert en mode texte vs un fichier ouvert en mode binaire sous windows. Les autres plateformes usuelles s'en foutent.

Zekeee a écrit:

D'accord,

Du coup, si je comprend bien avec l'exemple : abca et le code a = 1, B = 00, c = 01.

Mon fichier txt contiendra

a1

B00

C01

100011

Dois-je écrire dans le fichier comme tel ou je dois privilégier une autre forme d'affichage telle que celle-ci par exemple ?

a1B00C01

100011

Bah c'est toi qui décides, tu crées ton propre format.

Soit tu fais tout en mode texte et le fichier contiendra «en clair» :

A1
B00
C01
100011

Mais comme chaque caractère prendra en gros 8 bits, tu n'auras que très peu ou pas de compression.

soit tu fais tout en mode binaire et là tu auras quelque chose qu'on pourra représenter par (et ce n'est qu'un exemple) :

• un header décrivant ton arbre
• un bloc de données

Zekeee a écrit:

Pourrais tu me donner un exemple stp ? Parce que j'ai vraiment du mal avec la compréhension du stockage des données dans les fichiers tant pour la compression que pour la décompression.

Pour stocker tout ça en binaire de manière non ambiguë : d'abord considère que tu as une fonction AddBit pour l'écriture, et une GetBit pour la lecture qui liront ou écriront les bits à la suite (dans un tableau de char pour un fichier binaire, ou bien un '1' ou '0' pour un fichier texte mais peu efficace)

D'abord, tu stockes ta table : on commence par sa taille. Ta table en haut fait 19 entrées.

Je choisi de les stocker sur 8 bits (je considère donc qu'une table peut faire max 255 entrées) (mais je pourrais employer un système à la UTF8 si je voulais avoir un nombre d'entrée illimité tout en gardant 8 bits pour les cas simples. On en reparle si tu veux.

Donc 19, ça fait 00010011 sous 8 bits.

Ensuite le tableau : je prends les 3 premières lignes uniquement pour l'exemple :

c :             01010

d :             01011

i :             1110                 (je fais exprès d'en prendre un de 4 chiffres)

on stocke c sous 8 bits (ASCII) 01100011

puis il va falloir stocker une taille variable de bits. Pareil, disons que je plafonne à 32 bits possible (mais on pourra étendre avec une méthode à la UTF8), donc je vais utiliser 5 bits (car 2^5 = 32) pour coder le nombre de bits nécessaires pour le code. Ici 5 bits nécessaires, donc je code 00101

Pus j'ajoute le code : 01010

Pareil pour la 2e ligne, j'aurai 01100100 pour le d, 00101 pour la taille du code (5bits) puis le code 01011

Pour la ligne du i, j'aurai 01101001 pour le i, cette fois 00100 pour la taille du code (4bits) puis 1110

Finalement mon code de table est :

00010011 01100011 00101 01010 01100100 00101 01011 01101001 00100 1110

donc 

0001001101100011001010101001100100001010101101101001001001110

puis les autres entrées de la table, et enfin ton code binaire de tout en haut (ton premier post).

Pour la lecture, si je prends la séquence ci dessus, je prends 8 bits pour la taille de mon tableau

puis je fais un for sur cette taille.

Pour chaque entrée, je prends 8 bits de code ASCII du caractère, puis 5 bits pour la taille du code n, puis n bits pour le code

Une fois cela fini, je lis immédiatement ma séquence (celle de ton premier message), en construisant un arbre. A chaque lecture je vais a gauche pour un 0, a droite pour un 1 jusqu'à la feuille (ça tu as compris le concept ?)

-
Edité par Fvirtman 22 novembre 2022 à 22:48:06

Voici de quoi pourrait avoir l'air les fonctions getBit et PutBi (ébauche non testée)
On ne place qu'un seul bit dans ce qu'on envoie et/ou reçoit.
getBit retourne -1 sur une fin de fichier.
putBit termine si on lui envoie -1 comme bit.

Les fichiers doivent être ouverts en mode binaire ("rb" ou "wb")
-
char getBit(FILE *file) {
    static uint8_t byte;
    static char shift = 0;
    shift = (shift+7) % 8;
    if(shift == 7) {
        byte = fgetc(file);
        if(byte == EOF) {
            shift = 0;
            return -1;
        }
    }
    return (byte>>shift) & 1;
}
void putBit(char bit, FILE *file) {
    static uint_t byte = 0;
    static char shift = 7;
    if(bit < 0) {
        fputc(byte, file);
        fputc(7-shift, file);   // Nombre de bits dans le dernier byte.
        return;
    }
    byte = byte | (bit<<shift);
    if(shift == 0) {
        fputc(byte, file);
        byte = 0;
    }
    shift = (shift+7) % 8;
}

-
Edité par PierrotLeFou 23 novembre 2022 à 3:59:28

J'ai finalement trouvé une solution. J'écris chaque 0 ou 1 sur 1 octet. Comme ça je peux utiliser la fonction fread. C'est gourmand en mémoire mais avec cette méthode, je peux décompresser mon fichier sans avoir à trop me casser la tête. Merci à tous.

Disons que c'est une solution intermédiaire pour avoir un résultat rapide.

Tu peux te faire une fonction AddBit ou Getbit rajoute/lit juste un octet si tu veux.

Et tout ton algo de Huffman passe par ces fonctions.

Ainsi tu n'as qu'à modifier ces fonctions et uniquement ces fonctions pour avoir une sortie texte, ou bien une sortie avec un octet par bit comme tu fais, et puis plus tard si tu le souhaites, 1 bit pour un seul bit.