Domaine d'int‚rˆt et contenu de la disquette -------------------------------------------- Elle pr‚sente des classes r‚alisant la compression et d‚compression LZW en Borland C++ version 3.1. Voici l'inventaire des fichiers : compr.exe, dcompr.exe ex‚cutables (rŠgles d'usage expliqu‚es plus bas) compr.cpp, dcompr.cpp programmes principaux traite.inc source compl‚mentaire inclu dans compr.cpp et dcompr.cpp lzw.h, lzw.cpp classe LZW lzwdico.h, lzwdico.cpp classe du dictionnaire sp‚cifique de l'algorythme crc32.h crc32.cpp classe de calcul de crc pour les v‚rifications Remarque : tous les sources cit‚s furent ‚dit‚s dans l'EDI Borland avec des tabulations r‚gl‚es … 3. Installation ------------ C'est un bien grand mot : il suffit de copier les fichiers dans l'un de vos r‚pertoires consacr‚s aux applications compilables sous Borland C++. Les 2 ex‚cutables sont … copier dans l'un des r‚pertoires de votre path. Origine du projet ----------------- La r‚alisation de ces programmes ne r‚pondait pas alors … un besoin imm‚diat. En fait j'avais ‚t‚ frapp‚ par un article sur les m‚thodes de compression, paru dans PC Expert. La pauvret‚ de l'expos‚, l'‚tran- get‚ des commentaires, montraient … l'‚vidence que l'auteur de cet ar- ticle ne comprenait pas lui-mˆme les petits morceaux de programmes qu'il avait hƒtivement recopi‚s Dieu sait o—. Mais, du coup, moi je ne com- prenais pas non plus, et je d‚teste cela...ce qui m'a d‚cid‚ … prendre le taureau par les cornes ! (cf bibliographie, un peu plus loin) Usage des ex‚cutables compr.exe et dcompr.exe --------------------------------------------- Donnons l'exemple pour la compression : - comprimer 1 fichier : compr source cible o— source et cible sont les noms ou les chemins du fichier existant … comprimer et du nouveau fichier comprim‚ (avec leurs extensions). - comprimer plusieurs fichiers : cr‚er un fichier d'ordres dont le nom commence par un @, et contenant des lignes : source1 cible1 (s‚parateurs espaces source2 cible2 ou tabulations) ... (les lignes vides sont admises) sp‚cifier ensuite : compr @ordres (nom du fichier d'ordres) La d‚compression s'effectue de fa‡on analogue. Exemple fourni : le fichier batch exemple.bat enchaine 2 fichiers d'ordres qui compriment, puis d‚compriment … nouveau 2 fichiers du r‚pertoire, puis comparent le r‚sultat aux fichiers de d‚part. Voir @ex_comp et @ex_decom. Remarques importantes : - il n'est pas int‚ressant de comprimer des fichiers log‚s sur une unit‚ comprim‚e, car cela n'amŠne qu'une ex‚cution sensiblement plus lente : malgr‚ l'affichage de dir (qui donne la taille originale), les fichiers sont en fait d‚j… comprim‚s par dblspace ! - ne pas s'‚tonner du facteur de compression d‚cevant obtenu sur ces fi- chiers d'exemple : ils sont trop petits ; les performances s'am‚liorent pour de grands fichiers (de texte), car le dictionnaire s'enrichit alors de chaŒnes redondantes de plus en plus nombreuses. Les fichiers .exe, en revanche, sont moins bien comprimables (par toutes les m‚thodes). Bibliographie ------------- Le livre fondamental de Mark Nelson : "La compression de donn‚es" (Dunod) m'a tout appris, y compris la programmation d‚taill‚e en C ANSI de l'al- gorythme LZW. Je n'ai fait qu'encapsuler tout cela dans des classes plus agr‚ables et plus s–res. Etant donn‚ que ce livre explique patiemment le fonctionnement de l'algo- rythme sur des exemples, je ne pense pas que vous pourrez vous en passer si vous avez un int‚rˆt s‚rieux pour le sujet. Examen des sources fournis -------------------------- Des commentaires de programmation d‚taill‚s figurent dans les sources. Cela serait une mauvaise id‚e de commencer par les programmes princi- paux puisque, comme d'habitude, ils ne contiennent rien d'autre qu'une analyse succinte de la ligne de commande, et le lancement du traitement. Au contraire, voici l'ordre d'examen conseill‚ : lzw.h commentaire abondant sur la m‚thode LZW lzw.cpp commentaires sur les d‚tails de programmation lzwdico.h, lzwdico.cpp commentaires sur la classe repr‚sentant le dictionnaire utilis‚ dans la m‚thode LZW crc32.h, crc32.cpp calcul de crc (… sauter en premiŠre lecture) traite.inc compl‚ments de source inclus dans les pro- grammes principaux compr.cpp, dcompr.cpp programmes principaux Attention : la compr‚hension du code n‚cessite une bonne connaissance de C++, il ne s'agit certes pas d'une introduction. Sont notamments utilis‚s : - fonctions virtuelles ; - h‚ritage multiple avec d‚rivations virtuelles ; - classes template ; - une pile de la librairie CLASSLIB version template ; - type et variable pointeur sur fonction membre. Une partie du source manque --------------------------- La m‚thode LZW (comme les autres) doit, … un moment donn‚, ‚changer avec le disque des "rafales" de bits, et non des octets, car la codification du fichier comprim‚ est con‡ue pour ˆtre la plus courte possible. Mark Nelson donne dans son livre des fonctions d'entr‚es-sorties de bits sur disque ; mais j'ai pr‚f‚r‚ construire des classes faisant ce travail : - elles sont greff‚es sur les classes de flux d'octets de C++ (iostream) ; - elles sont utilisables simultan‚ment avec celles-ci (elles en h‚ritent) ; - elles sont con‡ues de fa‡on trŠs analogue aux classes de flux d'octets, y compris pour la gestion interne des tampons de bits. Cet exercice m'a appris beaucoup sur la conception de la librairie de flux de C++, forc‚ que j'‚tais de l'‚tudier pour atteindre mon but... Les fichiers suppl‚mentaires (non fournis) qui impl‚mentent cette librairie d'E/S de bits sont les suivants : bits.h manipulations ‚l‚mentaires de bits dans un mot bitsbuf.h tampon de bits, trŠs analogue … streambuf iosbit.h racine de la hi‚rarchie des classes de bits (cf ios) fbitbase.h, fbitbase.cpp ce qui est commun aux entr‚es et aux sorties de bits fbits.h, fbits.cpp classes d'entr‚e, de sortie et d'entr‚e-sortie AprŠs obtention de ces fichiers (cf ci-dessous), vous serez en possession de programmes source complets, compilables sous BC++ 3.1. Une alternative serait de r‚aliser vous-mˆme ces classes (bon exercice !). Remarque importante : ces programmes ne sont pas imm‚diatement transposables sous compilateur Microsoft, car celui-ci ne connait pas les template (hou !). Comment obtenir ces fichiers ---------------------------- L'‚tude et l'utilisation des fichiers fournis est absolument libre de droits, vis … vis de moi s'entend (attention, certaines parties de l'algorythme LZW seraient brevet‚es, comme je le rappelle dans un commentaire de lzw.h). En revanche, pour obtenir le source complet des entr‚es-sorties de bits, je vous demande une petite contribution de...55F ! Pour cette somme, vous obte- nez un "insight" trŠs int‚ressant sur le fonctionnement d'un tampon streambuf (car notre tampon de bits lui ressemble), et sur la fa‡on de "greffer" des fonctionnalit‚s suppl‚mentaires … une hi‚rarchie existante (classes de flux d'octets C++) … l'aide de l'h‚ritage multiple. Permettez-moi de souligner qu'il ne s'agit pas de pures sp‚culations : la va- lidit‚ du travail est confirm‚e par le fonctionnement correct de ces classes contribuant aux programmes ex‚cutables fournis. Pour terminer, je fais les r‚serves d'usage : malgr‚ les assurances donn‚es il y a un instant, on ne peut exclure que telle ou telle fonction, dans tel ou tel cas particulier, soit d‚faillante. Vous acceptez par avance l'id‚e que les fichiers fournis constituent pour vous une simple base de d‚part, et que vous ˆtes seul responsable de leur mise en oeuvre si vous jugez qu'ils peuvent convenir … vos buts... Je suis ‚videmment int‚ress‚ par toute remarque ou suggestion ! Voici mon adresse pour ces remarques...et le petit chŠque : ---------------------------- Alain NAIGEON 39, boulevard de la victoire 67000 Strasbourg ----------------------------