compression.theory.txt

Méthodes :
  - run-length encoding (RLE) :
    - lossless, symetric, physical, adaptive
    - high speed but low compression ratio
    - plus efficace sur les channels avec des répétitions consécutives de même valeur (moyenne de répétition consécutive doit être > 2)
    - Méthode :
       - chaque suite d'un ou plusieurs octets de même valeur est un "run"
       - un run est encodé avec d'abord un octet représentant sa taille, puis un second représentant sa valeur
       - peut aussi être au niveau du bit, du word, etc.
    - Pour une image :
       - pour une image, le processing peut aussi se faire de gauche à droite, de haut en bas, en zigzag, etc.
       - peut être lossy, en supprimant d'abord les LSB des pixels par exemple (supprime le bruit)
       - parfois un magic number à la fin de chaque ligne de pixels (pour éviter corruption de l'image si problème d'intégrité)
    - Alternative :
       - magic number précède chaque run si taille > 1 ; sinon, pas de magic number, et octet isolé (sans taille précisée)
    - exemple : .bmp, .tiff
  - Lempel-Ziv-Welch (LZW)
  - Huffman / entropy encoding :
    - années 50
    - caractère le plus fréquent : 0 ; celui d'après : 10 ; puis 110 ; etc. ; 111...10 ; 111...11 (le moins fréquent)
    - cas spéciaux :
      - CCITT
  - DCT (discrete cosine transform)
    - exemple : .jpg
  - JBIG
  - ART
  - Fractal

Raster vs vecto :
  - vecto : compression souvent inutile, car déjà compact, et implique overhead de la décompression
  - raster : plus utile

Codec vs container :
  - codec / compression algorithm :
    - effectue la compression
    - ex : JPEG
  - container / file format
    - encapsule datas compressées dans un format de fichier
    - rajoute par exemple un header, etc.
    - exemple : JFIF

Raw data : data not compressed
Compressed ratio : taille raw data / taille compressed data

Physical vs logical compression :
  - physical :
    - souvent output avec distribution aléatoire uniforme
    - majorité des cas
  - logical :
    - output compréhensible
    - substitution polyalphabétique
    - ex : United States of America -> USA, cannot -> can't

Symetric vs asym. compression :
  - symetric :
    - même algo pour compression et décompression
  - asym. :
    - algo différent pour compression et décompression
    - utile si on se soucie surtout du temps de décompression, et pas de compression (ou l'inverse)

Adaptive vs non-adaptive :
  - adaptive :
    - sur tout channel
  - non-adaptive :
    - sur channel précis (par exemple sur texte anglais avec CCITT)

Lossy vs lossless compression

Tradeoffs :
  - compression ratio
  - temps de compression
  - temps de décompression
  - mémoire utilisée
  - dégradation des data