Documents sur la compression

 AIDE AU PROJET COMPRESSION

         by SICO

1)Introduction:

   La compression est un processus magique ;), mysterieux, reduire la taille d'un fichier sans perte est un acte purement jouissif.... qd c'est vous qui l'avait coder (utiliser winzip n'a (heureusement) jamais provoqué ca). On peut qd meme s'interroger de nos jours sur le bien fondé de compresser des fichiers. S'il n'y avait pas ces putains de disquettes de 1.44 qui  perdurent, internet par le telephone... alors la compression (sans perte)  n'aurait peut etre plus lieu d'exister.
   Alors prq compresser????
   Ca fait technique ;)
Avant de vous lancé dans la compression, sachez qqe petites choses:
   -Si en essayant un de vos algorithme, et que le taux de compression est mieux que rar, verifié que vous avez pris le meme fichier ou que l'algo n'est pas destructif ;)

   -Ne vous faites pas d'illusion sur le taux de compression
   -Lors de la compression ne regardez pas le taux de compression sinon il aura tendance a baisser
   -Compresser c'est bien mais decompresser cest encore mieux
   -Si le maniement des bits vous fiche de l'urticaire passez votre chemin

2) Le basique: La compression RLE

   RLE pour Run Lenght Encoding, la plus basique des compression utilise principalement pour les images '.pcx'.
   Le principe:
 En entrée: aaaaaaaaaaaaaeeee
 En sortie: 12a4e
   Où 12 et 4 tiennent par exemple sur un octet chacun.
Puissant non??, je pense pas qu'elle necessite de plus ample

   explication.

3) La Huffman compression

   Plus elaboré, avec un taux de compression superieur. Le principe est de calculer pour chaque byte son nombre d'occurence dans un fichier donnée. On obtient ainsi une probabilite d'apparition d'un caractere donnée. Ainsi plus un caractere a une probabilie grde, plus le nombre de bits pour  le coder sera petit
   Ex:
     ahhhhhhhhhh!!!
   Calcul des proba:
      a: 1
      h: 10
      !: 3
   il est evident que rien ne sert de coder a,h,! sur 8bits

   Calcul les codes:
      a: 001
      !: 01
      h: 1
   Notre ahhhhhhhhhh!!! tiendra maintenant sur 3*1+1*10+2*3=19bits
   Le calcul des codes peut se faire de plusieurs manieres, celle que je viens de faire est la moins efficace.
   La plus efficiente est la creation des codes par un arbre .
   On tri les proba et on decoupe le tableau des proba en deux sous tableau où le cumul des proba du sous tableau haut doit etre superieur a celui du bas.On ajoute ensuite 1 au codes dans le sous tableau haut et 0 dans l'autre, et on recommence l'op pour chq sous tableau jusqua ce que les bornes d'un sous tableau donné soit confondu.

     h: ---------- 0
                   |_____
      !: ----- 0   |1
              |----
      a: ----- 1

      h: 0
      !: 10
      a: 11

     Pas tres probant l'arbre a 3 branches
      a: 20
      b: 10
      c: 10
      d: 5
      e: 5

      a:------ 0
                   |---------
      b:------ 1            |0
                                 |______ Tronc
      c:--------- 0          |
                       | _____|1
      d:------ 0     |
                    |-- 1
      e:------ 1

     Un peu mieux
   Il existe des variantes: ou on calcule les proba dans l'autre sens, on part avec une probabilite de 1 pour chaque caractere de la table ASCII dans le tableau et on incremente la proba du caractere rencontré puis on recalcule les codes. On est pas obligé a chaque fois de trié le tableau en entier et de calculer les codes.
  

   A chq codeur de crée sa variante.

4) LZW and Co
   Ou la compressions par dictionnaires. Cad qu'on remplace un mot dans un fichier par le code de l'index de ce mot dans le dictionnaire.
   Ex: 'brownie'
     ->654  (Si brownie est dans le dictionnaire)

   Si brownie n'y est pas, on met le dictionnaire a jour en le rajoutant, et a la prochaine occurence de brownie, il sera remplacé par son index.

   Il existe deux grand type de LZ:
 -Le LZ77
 -Le LZ78

   *Le LZ77

 Ce type de compression est base sur un dictionnaire qui est constitué des données  precedement compressé. Le dictionnaire est une fenetre sur un nombre n de bytes qui se trouve juste avant la position courante dans le fichier a compressé.
        On cherche dans ses n bytes si la chaine a partir de la position courante s'y trouve Si elle y est on remplace la chaine par l'offset relatif de la chaine
dans la fenetre  avec sa longueur.

        Ex: "il dit: |court |cousine"       (exemple a la con)

        Ici la taille de notre fenetre est de 6 bytes et la position courante se trouve au 'c' de 'cousine'

        1)On cherche 'c' dans la fenetre, il y en a un a la position relative 0
        2)On cherche co, il existe
        3)cou idem
        4) cous, n'existe pas
        5)On remplace 'cou' de cousine par l'offset et la longueur trouvé dans la fenetre: (0,3)

        Et on remet a jour la position courante et donc la fenetre:  "il dit: cou|rt cou|sine"

        Le choix du nombre de bits de l'offset et de la longueur vous appartient, il peut evoluer au cours du processus.

 Ce type de compression est generalement utilisé en parallele avec une compression  Huffman sur le tableau des offsets et des longueurs. La plupart des compresseurs utilise cette technique.

   *Le LZ78

 Ce type de compression est basé sur un dictionnaire qui est constitué des données precedement compressé (bis repetita).Cette methode est notamment utilisé pour la compression .GIF.
        Il s'agit ici d'un vrai dico, qui est constitué ts au long du processus. Ce dico possede un certain nombre n d'entré où chacune d'entre elle pointe vers une chaine bien precise. Lors du processus on cherche la plus grande chaine courante du fichier a compresse appartenant au dico jusqu'a ce que cette chaine n'appartienne plus au dico. On remplace alors l'ancienne chaine par l'index du dico qui lui correspondait et on rajoute la chaine courante au dico.
        Au depart du processus, notre dico est constitue des 256 caracteres de la table ASCII.  Sa taille est donc de 8bits.
        ex: 'coco est cocu' (re exemple a la con)

        chaine lut     chaine rajoute au dico         index ecrit
           'c'
           'co'             'co':256                      'c':99
           'o'
           'oc'             'oc':257                      'o':111
           'c'
           'co'
           'co '            'co ':258                     'co':256
           ' '
           ' e'             ' e':259                      ' ':32
           'e'
           'es'             'es':260                      'e':101
           's'
           'st'             'st':261                      's':115
           't'
           etc
           etc

       A la fin du processus la taille du dico sera de 9bits.

       Le dico ne pouvant allez qu'en grossissant, avec lui la taille en bits de l'index,  il deviendra necessaire de le purger un coup a un moment ou a un autre, par exemple qd le % de compression commence a baisser....
       On peut le baisser de plusieurs facon:
       -on vire ts de 256 a 2^n-1 ;) methode barbare
       -on vire intelligement, en introduisant pour chaque index le nombre de fois qu'il a été utilisé
       -on vire les plus grandes chaines, on vire les fils des chaines peres

       Mais dans ts les cas où la purge depend du taux de compression, cette purge necessite un code special a emettre dans le fichier à l'encontre du decompresseur.

5)L'arithmetique.... (a faire)

6)La NACA (Nithril ACiX compression algorithm)

   Prq pas crée son propre algo de compression....Tout le temps des Lempel des Ziv des Welch et j'en passe..... Cette methode tres perfectionné utilise le fait que danns un fichier image ,par exemple, TRES filtré chaque composante du pixel successif est proche de leurs voisins
   ex d'une image 24b:
   (100,100,100) (110,115,95) (120,130,80)
   Prq coder chaque composante par sa valeur alors qu'on peut le coder par la difference
   (10,15,-5) (10,15,-15)
   On va donc coder ces differences sur 5bits d'où un total de 5*6=30/8=4 bytes au lieux des 9, il faut aussi ajouter au debut la composantes initiales, ce qui fait 3 bytes supplementaires pour ts le fichier.
   On peut faire une adaptative NACA et d'autres ameliorations.....

7)La multimedia compression

   La pas de mystere, il s'agit pas d'un type de compression geniale, mais de simple constation comme la NACA, de la, a vous de modifier le LZ, ou autres, pour qu'il
s'adapte a un type de fichier donné, il doit cependant exister des algo qui verifie si un fichier donné a le profil d'un type de multimedia compression.
   Je vais pas m'aventurer sur ce sujet car je n'y connait pas grand chose, mais ca vaudrait le coup d'y reflechir.....