----------------- -- Compression -- -- topographique -- ----------------- ---------------------------------------------------------------------------- X.L. (toujours très occupé !) m'a demandé de préparer un petit article résumant la méthode de compression de données topographique... C'est fait mais ce ne fut pas simple ! Le listing C qu'il m'a fourni et que vous pouvez trouver sur ce disk n'est pas vraiment pour le débutant... Mais si vous adorez ce genre de problème , vous apprécierez ce passage de la théorie pure à la pratique ! P.A.I. Mr. S.M. 7 rue des Archers B-7000 MONS BELGIQUE & XAVIER LECLERCQ Vieux Chemin d'Ath n°12 B-7548 Warchin BELGIQUE Bibliographie: ~~~~~~~~~~~~~~ "La compression topographique" par X.L. AMIGA-NEWS N° 35 (MAI 91) "Compression des données" par G.Held ( Edit.MASSON ) "Analysis of Some Redudancy Removal Bandwidth Compression Techniques" Proc IEEE , 55 , n°3 ---------------------------------------------------------------------------- - Qu'est-ce que la compression de données ? ° C'est réduire un volume d'informations à l'aide d'un algorithme approprié. - Quel est l'intérêt de la compression de données ? ° Prendre moins de place sur disque. ° Le temps de chargement du fichier comprimé est moindre. ° "time is money" dans le cas de télétransmissions. ---------------------------------------------------------------------------- 1. Bref rappel théorique : ~~~~~~~~~~~~~~~~~~~~~ A. Méthode topographique simple. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Immaginez une suite d'octets formant le contenu d'un fichier "A" : EDF { 10 , 9 , 8 , 8 , 8 , 0 , 7 , 8} EOF Le fichier est lu octet par octet . Pour communiquer à une tierce personne cette série d'information vous déclarez chaque valeur successive puis sa position par rapport à son EDF (étiquette de début de fichier). Soit : {10,1 ; 9,2 ; 8,3 ; 8,4 ; 8,5 ; 0,6 ; 7,7 ; 8,8} On peut à partir de cette liste dresser un schéma global de la "topographie des positions" de chaque octet par rapport à EDF. pour l'octet 10 : (se retrouve une seule fois au début du fichier) Topographie octet 10 { 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } pour l'octet 9 : (se retrouve une seule fois en deuxième position) Topographie octet 9 { 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 } pour l'octet 8 : (se retrouve 4 fois dans le fichier) Topographie octet 8 { 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 } pour l'octet 0 : (se retrouve une seule fois) Topographie octet 0 { 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 } pour l'octet 7 : (se retrouve une seule fois) Topographie octet 0 { 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 } Par convention on peut décider que l'on va transmettre l'octet le plus fréquent dans le fichier puis sa carte topographique et enfin les données restant. Ici c'est le byte 8 qui revient 4 fois dans le fichier qui est donc le plus fréquent. Ce qui donne : Octet le plus fréquent = {8} + sa carte Topographie = { 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 } + la description des octets restants = { 10 , 9 , 0 , 7 } Comment l'interlocuteur peut-il reconstruire les données initiales ? Simplement il prend la première information {8} et ensuite il lira sa topographie et reconstruira le fichier à l'aide de la description des octets restants : 0 donc pas de 8 mais un 10 { 10 , ... } 0 donc pas de 8 mais un 9 { 10 , 9 , ... } 1 donc on place 8 { 10 , 9 , 8 , ... } 1 donc on place 8 { 10 , 9 , 8 , 8 , ... } 1 donc on place 8 { 10 , 9 , 8 , 8 , 8 , ... } 0 donc on place 0 { 10 , 9 , 8 , 8 , 8 , 0 , ... } 0 donc on place 7 { 10 , 9 , 8 , 8 , 8 , 0 , 7 } Remarquons que la carte topographique est une suite de 0 et de 1. C'est à dire une suite d'informations élémentaires (bits) qui peuvent être regrouper par paquets de 8 en octets !! Donc connaissant la taille du fichier intitial on peut connaître la taille de la table topographique de l'octet le plus fréquent qui sera toujours (taille du fichier initial / 8 ). Ce qui donne : Octet le plus fréquent = {8} 1 octet + sa carte Topographie = {57} 1 octet + la description des octets restants = { 10 , 9 , 0 , 7 } 4 octets En effet 57 en décimal donne 0x39 en hexa et %00111001 en binaire... La taille initiale du fichier est : EDF { 10 , 9 , 8 , 8 , 8 , 0 , 7 , 8} EOF ==> 8 octets La taille finale du fichier est : EDF { 8 , 57 , 10 , 0 , 7 } EOF ==> 6 octets Et comme 6 < 8 il y a bien compression de données !! Cette méthode porte le nom de compression topographique. B. Méthode topographique avec différence. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Il s'agit de pratiquer un traitement supplémentaire avant d'éffectuer une deuxième compression topographique simple sur un jeu de données. Je vais d'abord introduire en préambule une notion de compression relative. Lorsqu'un satellite météorologique relève les températures en plein soleil d' une région telle que le désert Saoudien il pourrait par exemple retransmettre à ses stations relais sur terre des chiffres comme ceux-ci : 50° , 50° , 50° , 52, 53° , 54° , 54° Mais au lieu de simplement transmettre les températures en valeurs absolues il peut très bien transmettre les variations relatives des températures par rapport à une température initiale par exemple 55° : -5 , -5 , -5 , -3 , -2 , -1 , -1 ce qui permet de coder les informations sur un nombre de bits moindre. Il s'agit d'une méthode de compression relative qui est utilisée lors de transmissions de données aux valeurs relativement proches les unes des autres. Maintenant observons ce que deviennnent les températures si je prend comme valeur intermédiaire de comparaison non pas une valeur fixe initiale fixée plus ou moins abitrairement mais une valeur de référence correspondant à l'avant dernière température. On part toujours de la 1ière valeur (50°) en calculant "ce qui manque" à la cette 1ère température pour atteindre la valeur de la 2ième température (50°) et ainsi de suite. En codage sur 8 bits formant un octet il faut rajouter 0 à 50 pour obtenir 50. Les données prennent donc l'aspect suivant : 50 , 0 , 0 , 2 , 1 , 1 , 0 Vous constatez sans doute l'utilité de la chose... Chaque groupement de n bytes consécutifs semblables se transforment en n-1 zéros consécutifs!! C'est même tout simplement génial lorsqu'on applique consécutivement à ces différences de bytes de rang m à chaque byte de rang m-1 une compression globale par topographie... La démarche inverse ,c'est à dire une complémentation au lieu d'une différence , permettra de rendre l'aspect d'origine aux données. 2. Le programme source : ~~~~~~~~~~~~~~~~~~~ Le coeur du source est formé par les fonctions suivantes : Frequence() ==> Permet de connaître l'octet le plus fréquent dans ~~~~~~~~~~~ le fichier. Topographie() ==> Elle parcourt le fichier et à chaque rencontre ~~~~~~~~~~~~~ de l'octet le plus fréquent fixe un bit dans l'octet topographique. Construit() ==> La démarche inverse est éffectuée : à partir de ~~~~~~~~~~~ la table topographique et de la description des octets restants on reconstruit les données initiales. Différence() ==> Applique une différence par rapport à l'avant dernière ~~~~~~~~~~~~ valeur pour metrre en évidence de plus nombreux 0. Complement() ==> Démarche inverse qui applique une complémentation ~~~~~~~~~~~~ aux données pour retrouver le flot initial. Compress() ==> Entrées/sorties pour une compression. ~~~~~~~~~~ Decompress() ==> Entrées/sorties pour une décompression. ~~~~~~~~~~~~ ----------------------------------------------------------------------------