Compression/Décompression

    Ce programme permet de compresser/décompresser un fichier suivant les principes posés par Huffman.

II - Les arbres de Huffman

    Le principe des arbres de Huffman, c'est que les données sont codées selon un nombre de bits variables. Alors que d'ordinaire, un caractère est codé sur un octet, il sera ici représenté par x bits, ce x variant selon la fréquence de ce caractère dans l'ensemble des caractères utilisés.

   Pour compresser un fichier, deux lectures de ce dernier s'avèreront nécessaires. La première servira à déterminer la fréquence de chaque caractère dans le fichier.
 

   Si le fichier contient par exemple la phrase : "Abracadabra", ce premier passage renverra un tableau du style :
 

Lettre	Occurrence
a	5
b	2
c	1
d	1
r	2

   A partir de ces données, un arbre sera construit.
 

   On retrouve les lettres, en bas du schéma, en bleu. A chacune d'entre elles, est associé un poids (en rouge). On construira ensuite l'arbre en regroupant à chaque fois les deux ensemble de plus faible poids.
    Pour chaque branche de l'arbre, on associera 0 si on part à gauche et 1 pour la droite (en vert).
    Si on lit ensuite l'arbre à partir de son sommet, on constatera que a sera codé par 0, d par 1011 et r par 11 ...

    On a donc bien un codage variant en fonction de la fréquence.

    On effectuera ensuite un deuxième passage dans le fichier et on remplacera chaque caractère par son codage.
 

III - Environnement...

    Ce codage a été conçu en Turbo Pascal pour MS-DOS. Il peut donc être lancé par MS-DOS ou par une session DOS de Windows.
    Je déconseille de le lancer directement à partir de son icône (sous Windows) car j'ai remarqué qu'il fonctionnait différemment (compression inachevée) de son lancement par une session DOS...
 
 

IV - Utilisation du programme

Lancement du programme : Possibilité de compresser ou de décompresser un fichier.
Choix de la compression : L'utilisateur entre le nom du fichier compressé puis le nom du fichier généré ...

Remarques : Cette méthode de compression est basé sur la fréquence des caractères. Moins un fichier contiendra de caractères de type différent plus le codage sera court et la compression efficace.
    Ainsi sur des fichiers textes, la compression sera en général très efficace (50 %) mais elle ne vaudra rien pour des fichiers exécutables ...

V - Description des fichiers

    Le fichier codage.zip est à télécharger. Il faudra ensuite le décompresser avec winzip ou pkunzip..

   Vous obtiendrez après cette opération les fichiers suivants :

• codage.exe : l'exécutable.
• codage.pas : le code source en Pascal.