Cet article contient quelques explications sur les choix effectués dans l'utilitaire HCD version 1.0 pour coder un algorithme de compression de type Huffman. Il fait suite à un article de gRosminet sur le même sujet posté ici. Cette version originale est dénommée HVO.

Dans son article, gRosminet lançait une invitation : « Je vous encourage à essayer de développer une version utilisant directement le mode natif des bits dans des entiers, même si cela peut se révéler être une acrobatie extrêmement périlleuse ». Ce qui suit explique comment y parvenir sur les points les plus importants en décrivant quelques solutions possibles.

Une comparaison rapide et simplifiée des performances de HCD avec celles de PowerArchiver est proposée.

Les questions, les commentaires et les suggestions sur cet article et sur HCD peuvent être envoyées à Cryptonyx.

1. Rappel sur l'algorithme de Huffman

Pour un f ichier de N octets Huffman a établi un algorithme qui permet de rendre la fonction suivante minimale :

L_i la longueur du codage d'un caractère du fichier en bits après transformation.

Sest la somme des L_i des N caractères du fichier original.

T est la taille du fichier compressé en bits.

Autrement dit, l'algorithme de Huffman permet de calculer les L_C de manière à rendre T minimale. En pratique, la méthode consiste à analyser la fréquance d’utilisation de chaque caractère et de lui affecté un code dont la taile dépend de cette fréquence. Un caractère qui apparaît souvent aura un code court et inversement.

Le taux de compression du fichier original sera :

t = 1 – (T / N)

Dans la suite de cet article, un caractère C est un caractère de type ASCII avec un codage compris entre 0 et 255 ou encore entre 0x00 et 0xFF en héxadécimal. En l’absence de compression, un caractère de ce type est codé de manière constante sur 8 bits.

Les détails de la méthode sont parfaitement décrits dans l’article de gRosminet et ne sont donc pas repris ici.

2. Evolutions par rapport à HVO

Les options en terme de structures de données et d'algorithmie prises dans HVO peuvent être différentes dans plusieurs cas. En particulier :

• la forme des codes de Huffman

• la génération de l'arbre des fréquences

• la gestion des entrées/sorties

• le nombre de fonctions

3. Alternatives proposées par HCD

Forme des codes de Huffman

Dans HVO, les codes de Huffman sont générés sous forme de chaînes de caractères formées de '0' et de '1'. Lors de la compression, une chaîne de caractères est crée par concaténation des chaînes de codes sur la base des caractères du fichier original. Quand une chaîne atteint la longueur de 32 caractères elle est convertie en une séquence de 32 bits (donc de 4 octets).

Cette méthode offre au moins deux avantages : les structures de données sont simples et claires et la longueur d'un code découle de la longueur d'un chaîne.

Son inconvénient principal est sa lenteur qui provient d'une part de la génération des chaînes et d'autre part de leur conversion en séquences de bits.

Une alternative à ce choix est d'utiliser des séquences de bits variables pour générer directement les codes. Cette approche, qui est plus "C" que "C++", offre cependant un (petit) inconvénient compte tenu du fait que la plus petite unité de stockage en mémoire est l'octet : il faut pouvoir connaître la longueur du code à tout moment. En pratique, il faut donc créer une variable pour gérer la longueur de chaque code.

Génération de l’arbre des fréquences

Dans HVO, l’arbre des fréquences est construit en utilisant un mécanisme de gestion de file de priorité.

Une alternative à ce choix est d'utiliser une liste des nœuds présentée sous forme de liste doublement chaînée et de la transformer en arbre avec l’alogorithme suivant :

Etape 1 : associer les 2 nœuds de fréquences les plus faibles pour créer un nœud de fréquence cumulée (le nouveau nœud devient la racine des 2 autres)

Etape 2 : enlever les 2 nœuds initiaux de la liste et y insérer le nouveau nœud en respectant l’ordre croissant

Etape 3 : répéter la procédure depuis l’étape 1 jusqu'à ce qu'il ne reste plus qu'un nœud au sommet qui devient la racine de l’arbre de Huffman

Gestion des entrées/sorties

Dans HVO, les caractères sont lus et écrits un par un, le système se chargeant des optimisations d’accès aux fichiers.

En pratique, cette optimisation n’est pas garantie. Une alternative intéressante et de nature à simplifier les choses et de charger tout le contenu du fichier d’entrée dans un tampon et de stocker tous les codes en sortie dans un autre tampon qui sera écrit en une seule fois sur disque. Cette approche permet d’obtenir la taille des différents fichiers sans faire de calculs.

Les messages d’information ont été réduits au minimum dans HCD.

Nombre de fonctions

Les choix expliqués ci-dessus ont permis de réduire de manière conséquente le nombre de fonctions nécessaires au codage de l’algorithme et d’augmenter considérablement les performances génrales. Cependant, la portabilité du code est réduite de par certains choix, valables seulement avec BCB sous Windows.

Il est possible de générer HCD avec une interface en français ou en anglais.

4. Structures de données et formats HCD

Les structures de données sont dans HCDFunctions.cpp.

// structure d'un noeud ou d'une feuille de l'arbre de Huffman

struct THuffmanNode {

unsigned char Value;                          // Code ASCII

unsigned int Frequency;                    // Frequence du code ou fréquence cumulée des sous-arbres

THuffmanNode *Pred;                        // Pointeur su prédecesseur

THuffmanNode *Next;                        // Pointeur sur suivant

};

THuffmanNode permet de construire soit une liste doublement chaînée soit un arbre. Les types de Code (unsigned short int) et Length (unsigned char) sont très importants pour les manipulation de bits et les écritures et lectures d’entête.

// Structure des statistiques pour chaque élément d'analyse

struct THuffmanStatistics {

unsigned long int Frequency;

unsigned short int Code;

unsigned char Length;      // Longueur du Code en bits

};

ThuffmanStatistics ne contient pas la valeur du code ASCII car cette valeur est l’indice du tableau :

Statistics = new THuffmanStatistics[MAXIMUM_ELEMENTS];

L’entête des fichiers compressés est définie comme suit :

La longueur totale de l’entête est donc variable. Pour des fichiers de petite taille (< 1 Ko), il est fréquent que la compression produise un fichier plus gros à cause de la taille de l’entête. Un cas théorique très défavorable, mais peu probable, donnerait un entête maximal de 1290 octets.

5. Astuces de programmation

Compression

Après avoir généré l’entête, il faut lire le fichier à compresser caractère par caractère. On positionne un index (j) sur le premier caractère qui suit l’entête. La longueur d’un code de Huffman est comprise entre 0 et 255. Le stockage a été choisi pour optimiser la vitesse de conversion. Par exemple, pour une longueur de 4 et une code de 0101 en binaire, le code stocké en mémoire sera 0101000000000000 car le format est de type unsigned short int. Il sera 01010000 dans la table du fichier compressé (le code est précédé de sa taille dans la table).

Pour transcoder un caractère quelconque, il suffit donc d’avoir son code de Huffman, puis de copier ce code à la suite de la chaîne de bits déjà construite par concaténation des codes précédents. Il nous reste à résoudre 2 difficultés : maintenir un pointeur sur le bit courant du fichier en cours de compression et copier les bits les uns après les autres. On utilise un compteur de bit limité à la taille d’un caractère (8) et la fonction ‘OU inclusif bit à bit’ pour résoudre ces problèmes.

L’algorithme est le suivant :

        // Parcours du tampon d'entrée caractère par caractère

        j = (unsigned long int)EndOfHeader;

                for(i = 0; i < ExpandedSize; i++) {

                // insertion du code correspondant dans le buffer

                                htCodeLength = Statistics[(unsigned char)(InputFileBuffer[i])].Length;

                                htCodeValue  = Statistics[(unsigned char)(InputFileBuffer[i])].Code;

                // le code commence à gauche de htCodeValue. si le bit le plus à gauche vaut 1,

                // le bit en cours du tampon de sortie est mis à 1, sinon il vaut déjà zéro grâce au memset

                                while(htCodeLength) {

                                                if(htCodeValue & 0x8000)

                                                                OutputFileBuffer[j] |= (unsigned char)(0x01 << (7 - BitPosition));

htCodeValue <<= 1;

                                                htCodeLength--;

                                                if(++BitPosition == 8) {    // après 8 bits, on passe au caractère suivant du buffer

                                                                BitPosition = 0;

                                                                j++;

                                                }

                                }

            }

En reprenant l’exemple précédent et en faisant l’hypothèse que le bit courant est 113, soit 1 en modulo 8, nous avons :

J = EndOfHeader + 14

BitPosition = 1 (donc deuxième bit du caractère)

htCodeLength = 4

htCodeValue = 010100000000000

La boucle while se déroule ainsi :

010100000000000 & 100000000000 = 0000000000000000

on écrit 0 dans le bit numéro 2 en partant de la gauche mais en fait il n’y pas d’action sur le tampon de sortie car il a été mis à 0 par le ‘memset’

htCodeValue devient 1010000000000000 après le << qui est un décalage à gauche

htCodeLength = 3

BitPosition = 2, retour au début de la boucle while

1010000000000000 & 100000000000 = 1000000000000000

on écrit 1 dans le bit numéro 3 en partant de la gauche :

0x01 << (7 – 2) donne 00100000

abcdefgh | 00100000 donne ab1defgh (a, b, c, d, e, f, g, h valent 0 ou 1)

                        etc.

Decompression

Après avoir lu l’entête, il faut aussi lire le fichier à décompresser caractère par caractère. On applique une méthode similaire à celle utilisée pour la compression (opérateurs binaires), mais on se sert de l’arbre de Huffman que l’on parcourt à droite si un bit vaut 1 ou à gauche si un bit vaut 0 pour retrouver le code ASCII souhaité.

    for(i = (unsigned long int)EndOfHeader; i < CompressedSize; i++) {

        // Récupération d'un octet

        Data = InputFileBuffer[i];

        // Décodage des caractères bit par bit

        for(k = 0; (k < 8) && (j < ExpandedSize); k++) {

             // on teste le bit de poids fort pour parcourir l'arbre

            if((Data & 0x80) == 0x80)

                htNodePointer = htNodePointer->Next;

            else

                htNodePointer = htNodePointer->Pred;

            if(htNodePointer == NULL) {

                // il n'y a qu'un seul type d'élément dans le fichier d'origine,

                // ou bien l'arbre a été généré de manière incorrecte

                if(NumberOfElements == 1) { // on pourrait traiter ce cas particulier autrement

                                OutputFileBuffer[j++] = (unsigned char)TreeRoot->Value;

                                // retour à la racine de l'arbre

                                htNodePointer = TreeRoot;

                }

                else {

                                ErrorCode = eBadTree;

                                ErrorString = ListOfErrorMessages[5];

                                Reset();

                                return false;

                }

            }

            if(!(htNodePointer->Next || htNodePointer->Pred)) {

                // Le noeud est une feuille - écriture de l'octet

                OutputFileBuffer[j++] = (unsigned char)htNodePointer->Value;

                // retour à la racine de l'arbre

                htNodePointer = TreeRoot;

            }

            Data <<= 1; // on passe au bit suivant

        }

    }

6. Comparaison entre HCD et PowerArchiver 2000 version 6

En dehors du fait que PowerArchiver (idem WinZip) est un outil très professionnel au niveau de l’interface et des fonctionnalités, il est aussi extrèmement performant comme le montrent les exemples arbitraires et non exhaustifs suivants :

Le cas n°1 s’explique par le fait que l’entête de PA est plus longue que celle de HCD.

Le cas n°4 est celui d’un fichier PDF (qui utilise déjà un type de compression).

PowerArchiver est donc en général bien plus efficace que HCD, sans doute parce qu’il emploie une compression de type Liv, Zempel et Welsh (LZW) qui fera l’objet d’un autre utlitaire.

7. Conclusions

HCD reprend les principes d’HVO en apportant plusieurs améliorations techniques. Par rapport à HVO qui démontre le concept Huffman de manière très pédagogique, HCD offre un gain de vitesse pouvant atteindre un rapport 100 sur certains fichiers.

Dans l’absolu, HCD n’atteint pas les taux de compression des standards du marché comme PowerArchiver ou WinZip. Cet utilitaire n’a qu’un but pédagogique et permet une discussion sur des choix possibles de codage. D’autres options sont possibles pour optimiser encore la vitesse de compression. Certaines se feront cependant au détriment de la lisibilité du code.

Pour une meilleure compréhension de la problématique de la compression de données numériques, il est intéressant de considérer d’autres méthodes :

-         Run Length Encoding (RLE) utilisée, par exemple, dans les formats BMP, TIFF et PDF ;

-         Liv, Zempel et Welch (LZW) utilisée, par exemple, dans les formats GIF et TIFF (attention aux aspects liés à la propriété intellectuelle) - cf. autre source ;

-         Joint Photographic Expert Group (JPEG) utilisée dans les formats JFIF, PDF, EPS ;

-         etc.