Support des tabulations en début de ligne. * * Par Haypo - 23 février 2003 */ //---------------------------------------------------------------------------- function StrInsert ($txt,$pos,$insert) { global $i; // Partage i pour pouvoir le modifier par d'autres fonctions $i += strlen($insert); if (strlen($txt)<$pos) return $txt.$insert; return substr($txt,0,$pos).$insert.substr($txt,$pos); } //---------------------------------------------------------------------------- function ChercheMotCle ($up) { if ($i==strlen($up)-1) return 0; global $i; $SauveI = $i++; // Cherche la fin du mot while (($i"; if ($telechargement) { // Affiche un lien pour télécharger le code echo " \n"; printf ("Télécharger ".basename($NomFich).", %.1f Ko)\n",filesize($NomFich) / 1024); echo " \n"; } // Ouvre le paragraphe de code echo "

";
 
  // Affiche le fichier ligne/ligne
  for ($ligne=0; $ligne");
          $i = strlen($txt);
          if ($tmp=="/*")
	    $CommentMultiLigne = true;
          else
            $txt .= "";
	}
      }

      if ($txt[$i]=="\"")
      {
        // CHAINE DE CARACTERE
        // Insere la balise de fin ou début de chaîne
        $txt = StrInsert ($txt,$i,"");
        $i++;
        while (($i");
        $LongTxt = strlen($txt);
      } else if (('a'<=$txt[$i]) && ($txt[$i]<='z'))
	{
        // MOT CLE
        $SauveI = $i;
        $long = ChercheMotCle ($txt);

        if ($long)
        {
          $tmptxt = "";
          $NouveauI = $i+strlen($tmptxt);
          $txt = StrInsert($txt,$SauveI,$tmptxt);
          $i = $NouveauI;
          $txt = StrInsert($txt,$NouveauI,"");
          $LongTxt = strlen($txt);
        }
      }
    }

    // Affiche une ligne de code
    AfficheLigneCodeC ($txt);
  }

  // Ferme le paragraphe de code
  echo "

\n"; // Ferme le tableau echo "\n"; } //---------------------------------------------------------------------------- ?>

Algorithme de compression de Huffman en C++

Par gRRosminet

Introduction

Si le principe de la compression de Huffman peut paraitre simple, sa mise en oeuvre n'en n'est pas moins une aventure périlleuse. C'est ce que nous allons voir dans cet aricle. Je tiens a préciser que mon objectif premier à été de réaliser une solution fonctionnelle et qu'elle n'est absolument pas optimisée. Avant de vous plonger dans cet exemple, je vous conseille fortement de jetter un oeil à l'explication de l'algorithme.

Je tiens à préciser que la mise en forme automatique du code de cet article est l'oeuvre de Haypo, un de nos valeureux rédacteurs qui nous éclaire régulièrement sur le forum.

Vous pouvez télécharger le code source complet ici

I. Outils nécessaires

Tout d'abord, essayons d'envisager tous ce dont nous aurrons besoin pour ce développement.

a) Statistiques

Nous aurrons besoin d'une liste de fréquence d'apparition des fragments. Dans notre cas, le fragment est un octet et on peut donc faire un tableau de 256 statistiques sans avoir a se soucier de l'espace mémoire que cela représente puisque c'est plutot restreint.

Le format d'une statistique :
     - On a besoin de savoir quel est l'élément : son indice dans le tableau l'indiquera, il n'est donc pas nécessaire de le stocker.
     - On a besoin de connaitre la fréquence d'apparition du fragment : les fichiers pouvant faire jusqu'à 4Go, il faut dont utiliser un usigned long int pour compter le nombre d'apparition. La fréquence d'apparition n'est pas nécessaire, on ne la stockera donc pas.
     - Finalemment, on aurra besoin de stocker le code de Huffman associé au fragment. J'ai fais le choix d'une chaine de caractères qui a l'avantage de simplifier le débuggage. Mais le désavantage d'etre plutot lent :-(

Pour calculer les tatistiques, nous aurront besoin d'une fonction qui parcours tous le fichier d'entrée et incrémente les compteurs des fragments.

b) arbre de Huffman

Nous aurrons besoin d'une structue d'arbre binaire dont les noeux prennent n charge la comparaison. nous aurrons également besoin d'une liste triée pour ordonner les noeuds et les morceaux d'arbre je propose d'utiliser la file de priorité de la librairie de templates standards du C++. Le probleme est qu'en général, on utilise des liste de pointeurs pour éviter d'avoir des temps de recopie des éléments trop importants. Je propose donc de faire un objet template qui propose les opérateurs de comparaison et un pointeur vers un type d'objet.

Nous aurrons également besoin d'une fonction qui associe les éléments les plus légers 2 à 2 jusqu'a ce que la liste n'en contienne plus qu'un et une qui détermine le code de huffman de chaque élément.

c) compression/décompression

Nous aurrons besoin d'une fonction qui permette d'écrire l'entete de compression associé au fichier et qui effectue la compression. Cette dernière devra s'assurer que les étapes d'analyse et d'écriture de l'entete ont été réalisées correctement avant de réaliser la compression.

Finallement nous aurrons également besoin de fonctions réalisant l'opération inverse : lecture de l'entete de compression, reconstruction de l'arbre puis décompression.

II. Implémentation de l'objet

Pour des raison de clarté du point de vue du compilateur et afin d'éviter tout enchevêtrement possible, tous les développements seront fait dans le namespace Huffman qui contiendra donc tous les outils nécessaires à ce développement et dont l'utilisation d'ans d'autres projets n'est pas envisageable.

a) Définition de la classe

La classe contiendre des informations sur les fichiers mis en jeux, ainsi que des pointeurs vers les éléments de compression qui seront eux alloués dynamiquement. J'ai également inclu des pointeurs de fonctions permettant de faire communiquer l'objet avec l'application principale et que celle ci puisse afficher des information à l'utilisateur final. Toutes les fonctions nécessaires dont nous avons énoncé les propriétés ci-avant ont été prévues et elles sont acompagnées des fonctions nécessaires à la gestion des messages utilisateurs.

J'ajouterai que si vous pretez un peu attention au code, vous remarquerez que le type chois pour le stockage du nombre d'éléments est un unsigned short int et non pas un unsigned char alors qu'on va compter des éléments de type char. Cela est du au fait qu'on peut n'avoir aucun élément ou n ou 256 et que 256 est strictement égal à 0 par le système d'overflow ce qui pose quelques problèmes par la suite :-(