Quels sont les techniques de compression ?
La compression optimise les performances du stockage de sauvegarde et commence à être utilisée pour réduire le volume de données du stockage primaire.
Alors que la croissance des données est aujourd'hui exponentielle, la compression jouera un rôle de plus en plus important dans leur réduction.Quel est le rôle de la compression ?
Les méthodes les plus importantes de compression d'image sans perte sont : la méthode du codage des répétitions, utilisée sur les premiers scanners et télécopieurs ; le codage entropique ; les algorithmes à dictionnaire adaptable tels que LZW, davantage adaptés à l'information de type texte.
4-CS-4pdf
Mémoire de master Méthode de compression de données sans
Présentation de la compression de données
Architecture et construction
NEUFERTpdf
La construction la norme et l'architecte
GUIDE ARCHITECTE
CHAPITRE 2 : LECTURE DE PLAN BATIMENT
ARCHITECTURE INGENIERIE CONSTRUCTION URBANISME
VINCENT BEAUDOINDeveloppement de nouvelles techniques decompression de donnees sans perteMemoire presentea la Faculte des etudes superieures de l'Universite Lavaldans le cadre du programme de ma^trise Informatiquepour l'obtention du grade de ma^tre es sciences (M.Sc.)Sciences et genieUNIVERSITE LAVALQUEBEC2008cVincent Beaudoin, 2008ResumeL'objectif de ce memoire est d'introduire le lecteur a la compression de donneesgenerale et sans perte et de presenter deux nouvelles techniques que nous avons develop-pees et implantees an de contribuer au domaine.La premiere technique que nous avons developpee est le recyclage de bits et elle apour objectif de reduire la taille des chiers compresses en protant du fait que plusieurstechniques de compression de donnees ont la particularite de pouvoir produire plusieurschiers compresses dierents a partir d'un m^eme document original.
La multiplicite desencodages possibles pour un m^eme chier compresse cause de la redondance.Nousallons demontrer qu'il est possible d'utiliser cette redondance pour diminuer la tailledes chiers compresses.La deuxieme technique que nous avons developpee est en fait une methode qui reposesur l'enumeration des sous-cha^nes d'un chier a compresser.
La methode est inspireede la famille des methodes PPM (prediction by partial matching).Nous allons montrercomment la methode fonctionne sur un chier a compresser et nous allons analyser lesresultats que nous avons obtenus empiriquement.A mes parents, Christiane et Beno^t,pour leur soutien durant toutes ces anneesTable des matieresResume iiTable des matieres ivListe des tableaux viiTable des gures viii1 Introduction 12 Compression de donnees 32.
1) Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 2.1. 1) Compression de donnees sans perte . . . . . . . . . . . . . . . .3 2.1. 2) Compression de donnees avec perte . . . . . . . . . . . . . . . .4 2. 2) Concepts generaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 2.2. 1) Precisions sur les mathematiques employes . . . . . . . . . . . .4 2.2. 2) Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 2.2. 3) Redondance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 3 Codage 63. 1) Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 3. 2) Concepts generaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 3.2. 1) Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 3.2. 2) Code prexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 3.2. 3) Code complet . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 3.3) Technique de codage et algorithme de compression . . . . . . . . . . . .7 4 Techniques de codage 84.
1) Codage de Shannon-Fano . . . . . . . . . . . . . . . . . . . . . . . . . .8 4. 2) Codage de Human . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 4.2. 1) Codage de Human adaptatif . . . . . . . . . . . . . . . . . . .12 4. 3) Codage arithmetique . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 4.4) Code universel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 Table des matieresv4.4.
1) Elias gamma . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 4.4.2) Levenshtein . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 5 Algorithmes de compression 195.
1) Run-length encoding (RLE) . . . . . . . . . . . . . . . . . . . . . . . .19 5. 2) Algorithmes a base de dictionnaires . . . . . . . . . . . . . . . . . . . .19 5.2. 1) LZ77 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 5.2. 2) LZ78 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 5. 3) Burrows-Wheeler transform (BWT) . . . . . . . . . . . . . . . . . . . .21 5.3. 1) Move-to-front (MTF) . . . . . . . . . . . . . . . . . . . . . . . .23 5.4) Prediction by Partial Matching (PPM) . . . . . . . . . . . . . . . . . .24 6 Recyclage de bits 266.
1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26 6. 2) Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 6. 3) Possibilites d'encodages multiples . . . . . . . . . . . . . . . . . . . . .27 6.3. 1) Encodages multiples et consequences . . . . . . . . . . . . . . .27 6.3. 2) Messages equivalents . . . . . . . . . . . . . . . . . . . . . . . .28 6.3. 3) Messages non-equivalents . . . . . . . . . . . . . . . . . . . . . .28 6.3. 4) Lien avec les encodages multiples de chiers . . . . . . . . . . .29 6. 4) Recyclage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29 6.4. 1) Idee generale de message cache . . . . . . . . . . . . . . . . . .29 6.4.2) Idee de transmission de parties de chier compresse dans les mes-sages caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 6.4.
3) Recyclage plat . . . . . . . . . . . . . . . . . . . . . . . . . . . .31 6.4. 4) Recyclage proportionnel . . . . . . . . . . . . . . . . . . . . . .31 6.4. 5) Capacite du canal auxiliaire . . . . . . . . . . . . . . . . . . . .32 6. 5) LZ77 et recyclage de bits . . . . . . . . . . . . . . . . . . . . . . . . . .32 6.5. 1) LZ77 conventionnel . . . . . . . . . . . . . . . . . . . . . . . . .32 6.5. 2) LZ77 et recyclage de bits . . . . . . . . . . . . . . . . . . . . . .34 6.6) Resultats experimentaux . . . . . . . . . . . . . . . . . . . . . . . . . .35 6.6.1 gzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 6.6.
2) Experience 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 6.6. 3) Experience 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 6.6. 4) Experience 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 6.6. 5) Experience 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42 6.6. 6) Experience 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43 6.6. 7) Experience 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44 6.6. 8) Experience 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45 6.6.9) Recyclage proportionnel optimal . . . . . . . . . . . . . . . . . .47 6.6.10 Experience 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55 Table des matieresvi6.6.11 Experience 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56 6.
7) Travaux futurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62 6.8) Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62 7 Methode des papillons 647.
1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64 7. 2) Fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64 7.2. 1) Etape 1 :Enumeration des sous-cha^nes . . . . . . . . . . . . . .65 7.2. 2) Etape 2 : Transmission de l'enumeration au decompresseur . . .68 7.2. 3) Etape 3 : Identication de la cha^ne de bits originale . . . . . .72 7. 3) Developpement du prototype . . . . . . . . . . . . . . . . . . . . . . . .72 7. 4) Mesures empiriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74 7. 5) Analyse des resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . .74 7.6) Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74 A Corpus 76Bibliographie 77Liste des tableaux4.
1) Frequences d'apparition des symboles de l'alphabet . . . . . . . . . .9 4. 2) Code de Shannon-Fano pour l'alphabet . . . . . . . . . . . . . . . . .9 4. 3) Code de Human pour l'alphabet . . . . . . . . . . . . . . . . . . . .11 4. 4) Frequences d'apparition des symboles de l'alphabet . . . . . . . . . .13 4. 5) Premiere division de l'intervalle pour l'alphabet . . . . . . . . . . . .15 4. 6) Procedure de renormalisation pour l'alphabet . . . . . . . . . . . . .15 4. 7) Exemples de mots de code Elias gamma . . . . . . . . . . . . . . . . .16 4. 8) Exemples de mots de code de Levenshtein . . . . . . . . . . . . . . . .17 5. 1) LZ78 sur la cha^ne d'octetsABBCBCABA. . . . . . . . . . . . . . . .21 5. 2) Exemple de transformation BWT . . . . . . . . . . . . . . . . . . . . .22 5. 3) Exemple de transformation MTF . . . . . . . . . . . . . . . . . . . . .24 6. 1) Resultats des experiences 1 a 6 . . . . . . . . . . . . . . . . . . . . . .37 6. 2) Resultats des experiences 7 a 9 . . . . . . . . . . . . . . . . . . . . . .45 7. 1) Liste desnrotations triees . . . . . . . . . . . . . . . . . . . . . . . . .65 7. 2) Enumeration des sous-cha^nes . . . . . . . . . . . . . . . . . . . . . . .66 7. 3) Parametres du papillon . . . . . . . . . . . . . . . . . . . . . . . . . . .69 7. 4) Resultats du prototype . . . . . . . . . . . . . . . . . . . . . . . . . . .73 Table des gures4. 1) Algorithme de Shannon-Fano sur l'alphabet . . . . . . . . . . . . . .9 4. 2) Arbre de Human pour l'alphabet . . . . . . . . . . . . . . . . . . .11 4. 3) Codage arithmetique pour le messageA-C-EOF. . . . . . . . . . . . .13 5. 1) Exemple LZ77 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 6. 1) Exemple de messages equivalents . . . . . . . . . . . . . . . . . . . . .28 6. 2) Algorithmes LZ77 conventionnel . . . . . . . . . . . . . . . . . . . . . .33 6. 3) Algorithmes LZ77 avec recyclage de bits . . . . . . . . . . . . . . . . .34 6. 4) Exemples de chiers avec les dierentes traversees possibles . . . . . . .57 6. 5) Algorithmes pour le recyclage de bits avec tous les messages . . . . . .60 7. 1) Arbre des sous-cha^nes . . . . . . . . . . . . . . . . . . . . . . . . . . .66 7. 2) Arbre compact des sous-cha^nes . . . . . . . . . . . . . . . . . . . . . .67 7. 3) Arbre des sous-cha^nes inniment profond . . . . . . . . . . . . . . . .68 7. 4) Un papillon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69 7.5) Exemples de papillons . . . . . . . . . . . . . . . . . . . . . . . . . . .70 Chapitre 1IntroductionL'informatique fut creee an d'automatiser le traitement de l'information.
D'ailleurs,cette discipline scientique tire son nom du terme \information" lui-m^eme.Depuis les debuts de l'informatique, nous avons ete confrontes a la limite des ordi-nateurs a memoriser et a transmettre l'information.
Tirant parti de l'observation que lapresque totalite de l'information que nous manipulons n'est pas aleatoire, des methodesde compression de donnees ont ete elaborees.
Ces methodes visent a transformer desdonnees en une forme plus compacte (compression), quitte a ce que celles-ci soientinintelligibles, et a les recuperer plus tard sous leur forme originale (decompression).La representation plus compacte permet d'utiliser moins d'espace lors du stockage oumoins de bande passante lors de la transmission via un que