Compression de fichier texte par l'algorithme de Huffman

Lorsque des textes se retrouvent dans des dossiers compréssés (.zip), ils seront compressés. La compression d'un fichier texte se fait toujours sans perte d'information.

​

Huffman

Pour compresser, il faut coder les caractères les plus fréquents sur un plus petit nombre de bits. En effet, "normalement", avec le code ASCII, tous les caractères sont codés sur le même nombre de bits, ce qui prend de la place.

Pour cela, on peut créer un arbre binaire. Il faudra alors enregistrer le code ET l'arbre car il existe de nombreux arbres possibles pour un texte donné. (Pour un exemple d'arbre, il est proposé de se référer au pdf fourni)

​

Burrows-Whiller

On peut également utiliser la permutation circulaire de Burrows Whiller qui consiste à "faire passer" la première lettre d'une expression en dernière position, par exemple. On classe alors les permutations par ordre alphabétique, on relève le dernier caractère de chacune et la position alphabétique du texte de départ. Souvent, les lettres semblables se retrouvent associées.

Un exemple réalisé en cours :

tete/a/tete 8

ete/a/tetet 4

te/a/tetete 9

e/a/tetetet 5

/a/tetetete 10

a/tetetete/ 1

/tetetete/a 11

tetetete/a/ 6

etetete/a/t 2

tetete/a/te 7

etete/a/tet 3

(tete/a/tete)

​

On obtient " /tttt/eeeea "

​

​

Move to front

Après Burrows-Whiller on obtient: 7,etttteeea (par exemple) ⇒ « 7 » est le numéro du texte de départ après permutation et classement par ordre alphabétique, et les lettres constituent la dernière colonne (voir ci-dessus)

On crée un dictionnaire :

a, b, c, d, e,.....,t,...z

0, 1, 2, 3, 4.........25

e→ 4 ⇒ étape du « move to front » : le e passe devant dans le dictionnaire :

e, a, b, c, d.......,z

0, 1, 2, 3, 4........25

(s'il y avait eu d'autres « e » à la suite, ils auraient été codé « 0 »)

t→ 19 ⇒ move to front : le t passe devant : les trois t suivants sont codés 0

t, e, a, b, c, d..........z

0,1, 2, 3, 4, 5.........25

Le « e » est codé « 1 » PUIS encore move to front :

e, t, a, b, c, d.........z

0, 1, 2, 3, 4, 5.......25

e→ 0 ; e→ 0 ; a→ 2

On obtient finalement pour codage : 4, 19, 0, 0 , 0, 1, 0, 0, 2

>>Ces trois méthodes sont associées pour créer des fichiers zip. Dans l'ordre, on a : Burrows-Whiller, move to front, Huffman (pour décoder, il suffit de faire l'inverse)

​

Il nous a été permis de récupérer un document pdf détaillant précisément ces méthodes de compression. Vous pouvez le consulter ci-dessous. Il contient, entre-autre, un exemple d'arbre binaire.