Methode
de
compression

•  
  • + - Les implémentations
    • + - 7-ZIP
      • + - LZMA

        • abreviation pour Lempel-Ziv-Markov chain-Algorithm,

          en développement jusqu'en 2001

          utilisé dans le format 7z des archiveurs 7-Zip et StuffitX

          méthode de compression à base de dictionnaire (jusqu'à 4GB)
          similaire à LZ77 permettant un taux de compression plus important que Bzip2

    • + - A
      • Bibliotèque UNIX
      • ~ Fichier Archive Pascal pour Linux ou DOS.
    • + - ACE

      • + - Format propriétaire d'archivage et de compression.
        permet le morcellement en fragments,
        rassemblés lors de la compression. Idem Arj

        • taux de compression supérieur à celui de ZIP
          au prix d'une vitesse de moindre.
          

          type MIME, application/x-ace-compressed.
          

          WinAce, maintenu et développé par e-merge GmbH,  pour Windows

          unace,sous licence GPL, décompresse les fichiers compressés
          par des versions antérieures où égale à la v2.0.

    • + - ARC
      • Ancien nom de LH ARC
      • format de fichier de SEA (System Enhancement Associates)
        
      • trés populaire avant l'introduction du format zip
        
      • compresse de nombreux fichier en un seul - mais pas l'arborescence totale
    • + - ARJ

      • crée des fichiers d'archives compressés.

        inventé par Robert K. Jung.
        ARJ veut dire probablement Archiver Robert Jung.
        peu utilisé actuellement.

        compression du même type que PKZIP 1.02. L'U.S. Patent 5140321
        

        était disponible pour licence dans des termes plus sympatique que PKZIP.
        

        + - jours de gloire à l'époque des BBS
        

        • permettait de créer des archives multi-volumes.
          

          permettait à l'utilisateur de modifier le degré de compression utilisé,
          fonctionnalité qui l'a rendu populaire chez les utilisateurs de "small packet mail networks"
          tel que WWIVNet et HOGnet, qui avaient tendance à utiliser des compression plus faible de manière à profiter au maximum des modes de compression des modem (MNP or v.42bis) pour minimiser les couts des communications longues distances.
          

        ARJ a céder une grande partie de son marché en faveur de RAR et d'autres formats;
        le manque d'intreface graphique a aussi contribué grandement a sa mise à l'ecart.

        ~ arjsoftware.com

        ~ http://arj.sourceforge.net

        ~ datacompression.info > LHA

    • + - BH
      • ~ BlackHole Archive Format File
    • + - Bzip2
      • + - BZ2
        • méthode de compression de données gratuite
        • + - résultats

          • 10 à 15% meilleurs que
            les meilleures techniques disponibles
            (the PPM family of statistical compressors)

            2 fois plus rapide à la compression

            6 fois plus rapide à la décompression.

        • utilise la Transformation de Burrows-Wheeler au lieu de LZW comme la plupart des autres formats...
        • ~ sources.redhat.com > Bzip2
      • BZ
      • + - TBZ
        • + - ~ BZIP2 Compressed TAR
          • L'archive faite tout en utilisant tar puis compressée par BZIP2.
    • + - BZA
      • + - BZA Compressed Archive
        • Aussi appelé BGA archives ????
    • + - GZA
      • Aussi appelé BGA archives ????
    • + - B64
      • + - Base 64 MIME-encoded File

        • Type de fichier non souvent trouvé sur PC.

          Note: The virus W32/MyWife.d@MM!M24 discovered 1/17/06 uses this file extension to send itself to others. Be careful if you have received a file of this type in the mail.

    • + - CAB

      • Extension : .cab ou .xx_ (le dernier caractère de l'extension du fichier initial est remplacé par un souligné).

        Format de Microsoft,

        Les fichiers commencent par la chaîne de caractères "MSCF".

        Fichiers compressés soit par la méthode MS ZIP (variante du zip)
        soit par la méthode LZX (méthode issue de l'ordinateur Amiga et rachetée par Microsoft).
        

    • + - CPIO
      • UNIX CPIO Archive
    • + - DEB
      • Debian package management system.
      • + - Links
        • ~ Debian
        • ~ package management system
    • + - ENC
      • UUENCODE Encoded File
    • + - GCA
      • ~ G Compression Archiver Compressed File
      • freeware compression utility --> DGCA
    • + - Gzip
      • + - GZ
        • Équivalent LIBRE de compress
        • DEFLATE
        • ~ gzip.org > Index-1
      • + - TGZ
        • + - UNIX Tar File Gzipped
          • Short for .tar.gz
    • + - HA
      • Compressed Archive ???
    • + - IMP
      • IMP Archive
      • ~ WinIMP Archive
    • + - LZH
      • LHA
      • + - LZH
        • + - LHa est un outil de compression et d'archivage
          pour le format LHarc (extension : .lhz).

          • LHA est un format et un outil de compression de données gratuit.
            A été créé en 1988 par Haruyasu Yoshizaki, et originellement appelé LHarc.
            Une réécriture compléte de LHarc, appelé LHx, fut diffusé sous le nom de LH.
            puis renommé LHA pour éviter le conflit avec l'appellation de MS-DOS 5.0 LH ("load high").
            Quoique plus beaucoup utilisé à l'Ouest, LHA reste populaire au Japon.
            Il fut utilisé par id Software pour compresser les fichiers d'installation de ces premiers jeux tel que Doom. LHA a été porté sur de nombreux operating system et est le principal format d'archivage de l'Amiga.

    • + - LIB
      • Library Used by an Application
    • + - MBF
      • ~ Money Backup File
      • Corel Visual DTD Document Type Definition for SGML ???
    • + - MIM
      • Multi-Purpose Internet Mail Extensions (MIME) File
    • + - PAK

      • Compressed Archive File

        Un fichier PAK est fait de la meme manière qu'une archive ZIP.
        Il regroupe plusieurs fichiers différents qui peuvent être accédés par le jeu auxquel il est associé.
        Les fichiers dans l'archive sont souvent en lecture seule.  
        Note: .Les fichiers PAK sont utilisés avec plusieurs jeux utilisant le moteur Quake.

    • + - PK3
      • conteneur de fichier 3D dans certain jeux comme Jedi Knight.
    • + - RAR

      • Extensions : rar ou rnn (nn=00,..99)

        la décompression des fichiers RAR est gratuite, la compression est payante.

        Le nom vient de Roshal Archive, d'après le nom du créateur

        Format propriétaire efficace pour l'archivage et la compression de très gros fichiers.
        Il permet le morcellement en fragments rassemblés lors de la décompression

    • + - RPM
      • Red Hat Package Manager
    • + - SQX

      • ~ SQX Archiver Compressed Archive

        Le principal compresseur est une variante du LZH utilisant plusieurs extension
        pour le Multimedia et d'autres type de fichiers.
        L'encodage 128-bit AES peut être utilisé.
        Full support pour les systèmes de fichiers de 64-bit
        (la taille des archives et des volumes est uniquement limitée par l'OS).
        modules SFX pour DOS (32bit PMode) et Win32.

    • + - SIT
      • + - StuffIt archives
        • + - Format propriétaire de Alladin Systems
          • Macintosh
    • + - SEA
      • + - self-extracting archives
        • + - Format propriétaire de Alladin Systems
          • Macintosh
    • + - TAR
      • Archivage de fichiers pour UNIX, sans compression
    • + - TAZ
      • + - Compressed File
        • Raccourci pour .TAR.Z
          consiste en un fichier .TAR compressé en utilisant Gzip.
    • + - TZ
      • + - Compressed File
        • (raccourci pour .tar.z)
          fichier TAR.Z compressé en utilisant compress
          (TAR and Compress)
    • + - YZ1
      • + - ~ DeepFreezer Compressed Archive

        • DeepFreezer crée rapidement des archives compactes.     
          mode opératoire convivial.
          taux de compression très bon pour les fichiers TEXT.      
          possibilité de locker les fichiers par mot de passe.     
          possibilité d'extraire des archives LZH , ZIP , RAR et CAB.(en fournissant les DLL)

    • + - z
      • Standard UNIX
        
      • Utilise le codage de Huffman
      • Généré par l'utilitaire pack
    • + - Z
      • Standard UNIX. A fait l'objet d'un brevet (patent en anglais) de la société UNISYS.
      • Généré par l'utilitaire compress
    • + - ZIP

      • Format de compression le plus répandu.

        ~ faqs.org > Rfcs > Rfc1951

        Défini en 1989 par Phil (Phillip W.) Katz (3 Novembre 1962 - 14 Avril 2000) pour succéder au format "arc".

        + - utilise l'algorithme 'deflate'.

        • DEFLATE est un algorithme de compression de données qui utilise une conbinaison de l'algorithme LZ77 et de codage de Huffman. Il fut originellement définit par  Phil Katz  pour la version 2 de son outil PKZIP, et fut plus tard spécifié dans la RFC 1951.
          DEFLATE est libre de toute patente,
          DEFLATE est largement pensé pour être exempt de tous brevets, et avant que le brevet sur LZW (qui est employé dans le format de dossier de GIF) expire, cela a mené à son utilisation dans GZIP et PNG, en plus du format de dossier ZIP pour lequel Katz l'a à l'origine conçu.
          Le code source de DEFLATE (compression et décompression) peut être trouvé dans la bibliotheque libre zlib.
          AdvanceComp utilise une implémentation de DEFLATE qui permet la recompression de Gzip, PNG, MNG et ZIP afin d'obtenir des taille de fichier plus petite qu'avec zlib. Bien plus efficace (mais également plus exigeant au niveau utilisateur) la routine DEFLATE est utilisé par KZIP et PNGOUT de Ken Silverman.

        Format de compression et d'archivage très commun dans Internet,
        développé pour DOS et Windows.

        + - Certain logiciel utilise le format ZIP pour archiver,
        à la manière de tar, un nombre important de petit fichier.
        Généralement, dans ce cas,
        une extension de fichier différente est utilisée.
        

        • + - Exemples
          
          • Java JAR files,
            
          • id Software .pk3/.pk4 files,
            
          • package files for StepMania and Winamp,
            
          • XPInstall, and
            
          • some OpenOffice.org document formats
    • + - ZOO

      • méthode de compression basé sur l'algorithme LZW .
        

        développé par Rahul Dhesi dans le milieu des années 1980.
        

        format n'est plus très répandu.
        

        Originellement les sources du programme ont été publiés sur le newsgroup comp.sources.misc.
        compatibles avec une grande variété d'OS de type Unix.
        binaires aussi diffusés pour la communauté d'utilisateurs MS-DOS.
        Un petit programme appelé booz, fut aussi développé
        pour assurer uniquement la fonction de décompression.

    • + - Messagerie Internet
      • + - B64
        • Fichier compressé (Stuffit Encoded)
      • + - HQX
        • + - BinHex
          • Encodage ASCII de fichiers binaires.
          • Très commun dans Internet pour les fichiers destinés au Macintosh
          • Macintosh BinHex 4 Compressed Archive
      • + - UUE
        • + - UUencoding

          • Encodage ASCII (7 bits) de fichiers binaires. Très commun pour le transfert de fichiers par courrier électronique et dans les forums Usenet

      • XXE
    • + - + image CD/DVD
      • BIN
      • C2D
      • CDI
      • ISO
      • IMG
      • MDF
      • NRG
      • PDI
    • + - Archive JAVA
      • + - EAr
        • ~ Java Enterprise Application Packaging Unit
      • + - JAR

        • Identique au format ZIP.

          On peut renommer les fichiers .jar en .zip.
          Un fichier jar peut contenir un fichier spécial, "MANIFEST.MF".
          Un fichier jar sert à distribuer un logiciel écrit en JAVA.
          Pour l'exécuter, il faut entrer la ligne de commande : java -jar <nom_du_fichier_jar>  
          Pour les programmeurs  JAVA: la classe JAVA JarFile du package java.util.jar hérite de ZipFile

      • + - WAR
        • ~ Java Web Archive
  • + - Les principales méthodes
    • + - Codage RLE
      • Codage le plus simple.
        
      • Surtout utilisé pour compresser des images noir et blanc, utilisé pour le fax donc...
        
      • + - Exemple

        • Au lieu de répéter les lettres identiques,
          on indique combien de fois elles se répètent,
          le mot "yahooooo!!!!!!!!"  est codé selon cette méthode en "yah6o8!"
          Pour décoder, si on voit un chiffre devant une lettre,
          on répète celle-ci autant de fois que l'indique le chiffre, c'est simple !

      • http://fr.wikipedia.org/wiki/RLE
    • + - Codage LZW
      • + - initiales des inventeurs :
        
        • Lempel Abraham et
          Ziv Jakob (1977) et
          Welch Terry qui a perfectionné la méthode en 1984.
      • + - Méthode

        • + - algorithmes simples

          • groupes de lettres sont remplacés par des codes.
            

          Définition d'un groupe de lettres (g) vide, qui a pour code 0.  
          Puis le texte est analysé caractère par caractère.  
          Pour chaque caractère C lu, le caractère C est ajouté à la fin du groupe de lettres courant ici g (gC).
          Si gC n'existe pas dans le dictionnaire,
          le code du groupe de caractères g est écrit dans le dictionnaire,
          le nouveau groupe de caractères (gC) est ajouté au dictionnaire avec le code suivant et
          le groupe en cours devient le caractère C
          sinon, le groupe en cours devient gC.   
          
          

      • + - Exemple :
        

        • que de querelles de queues
           dic c g         gc   code
           00: q []        [q]     q
           01: u [q]      [qu]   u
           02: e [u]      [ue]   e
           03:    [e]      [e ]      
           04: d [ ]       [ d]     d
           05: e [d]      [de]   e
           06>   [e]      [e ]
           06: q [e ]     [e q]  3  
           07> u [q]     [qu]
           07: e [qu]    [que] 1
           08: r [e]       [er]     r
           09: e [r]       [re]     e
           10: l [e]       [el]      l
           11: l [l]         [ll]       l
           12: e [l]       [le]      e
           13: s [e]      [es]    s
           14:   [s]       [s ]      
           15> d [ ]      [ d]
           15: e [ d]     [ de]   4
           16>   [e]      [e ]
           16> q [e ]    [e q]
           16: u [e q]   [e qu]  6
           [...]
           12345678901234567890123456
          --------------------------
          que de querelles de queues : (26 caractères)  
           1234567890123456789
          -------------------
          que d31erelles4622s : (19 caractères)   
          Le principe pour la décompression est symétrique et permet de retrouver le texte initial.

    • + - Codage de Huffman
      • + - Méthode

        • chercher le codage de longueur variable optimal.
          Un "bit" (contraction de BInary digiT) peut prendre deux valeurs
          (0 ou 1 par exemple, mais aussi vrai ou faux, noir ou blanc, homme ou femme, etc...).  
          
          

      • Voir : http://cermics.enpc.fr/polys/oap/node49.html   
        
        
      • + - Exemple

        • Dans la phrase "bal baba cool" qui comporte 13 caractères (en comptant les espaces), il y a 7 caractères différents (en comptant l'espace).
          
          

          Tandis que le code ASCII utilise 8 bits par caractère,
          on peut utiliser 3 bits seulement, comme ceci : ....
          : 000, a : 001, b : 010, c : 011, o : 100, l : 101
          La fréquence des lettres est : b:3, a:3, l:2, :2, c:1, o:2  
          On prend les deux lettres de plus petites fréquences.
          La plus forte à gauche, la plus faible à droite.
          On obtient un "noeud" (père) dont la fréquence est leur somme.
          On recommence en enlevant les deux lettres et en les remplaçant par le noeud,
          jusqu'à ce qu'il ne reste plus qu'un noeud.
            _3_
             |   |
            o   c
          
            _4_
            |     |
              ....   l
            _6_
            |     |
            b   a
              __7__
               |       |
            _4_   _3_
             |    | |    |
             l     .  o   c
                 ____13____
                   |                |    
              __7__       _6_
                |       |        |    |
            _4_   _3_    b  a
          |      | |    |
          l       .  o   c  
          
          Le code à utiliser pour chaque caractère s'obtient en suivant
          le chemin du noeud du sommet vers le caractère :
          on ajoute un 0 si on va à gauche et un 1 si on va à droite.   
          
          b:10
          a:11
          l:000
          ....:001
          o:010
          c:011  
          règle (x10)              1         2         3
          règle    123456789012345678901234567890123
          codage huffman  101100000110111011001011010010000
          lettres         b a l  .  b a b a .  c  o  o  l  
          33 bits au lieu de 39 !
          

    • + - Transformation de Burrow-Wheeler

      • Burrows-Wheeler Transforma (BWT), "Block Sorting Lossless Compression Algorithm".
        Michael Burrows, professeur à l'université de Cambridge (Angleterre)
        David J. Wheeler. publié en Mai 1994.  
        L'idée est de trouver une transformation favorable à la compression
        (ce n'est pas difficile: il suffit par exemple de trier les octets) ET
        qui soit réversible (ce qui n'est pas évident).   

        http://en.wikipedia.org/wiki/Burrows-Wheeler_transform  

        ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-124.pdf  

        http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124.html  

        http://www.datacompression.info/BWT.shtml  

        http://www.faqs.org/faqs/compression-faq/part2/section-9.html