Vous savez déjà tout, ou vous voulez simplement un lexique pour vous rappeler des définitions ? Dans ce cas, commencez ici.
Lexique des techniques de compression
Delta encoding
Encodage par rapport à la valeur précédente (soustraction). On ne stocke plus des valeurs mais des différences. Se retrouve souvent dans les formats multimédias.
RLE = Run-length encoding
Désigne le fait de préfixer une valeur littérale (qui n’est pas un code) par sa taille.
Code
Valeur faisant référence à d’autres valeurs déjà connues, en général plus longues.
Dictionnaire
Ensemble de codes.
Sliding window = fenêtre glissante
Le contenu déjà décodé, auquel il peut être fait référence pour demander de le reproduire.
Arbre binaire
Structure par arbre où chaque nœud peut avoir deux branches. La valeur d’un bit (0 ou 1) détermine séquentiellement quelle branche suivre. Utilisé dans les indexes de bases de donées et certains algorithmes de compression, très rapide à parcourir.
BWT = Burrows-Wheeler transform
Riante astuce qui consiste à grouper les octets suivant couramment un autre octet entre eux, mais sans perdre de place puisque les octets précédents sont re-trouvables en utilisant un algorithme de tri (qui permet de reconstituer des paires d’octets, dont la première est à préciser explictement).
DCT = Discrete cosine transform
Pour les images, méthode consistant à décomposer un bloc de pixels en stries de différentes tailles, les stries les plus fines contenant le moins de détails et admettant donc de pouvoir perdre le plus en précision.
Plus généralement, son principe est de décomposer un bloc de données (il peut s’agit d’une partie d’une image, d’un son, etc.) en des stries, plus ou moins précises, qui recouvrent de parties plus ou moins importantes du bloc, qu’on peut obtenir via des opérations trigonométriques, et sur lesquelles on effectuera des moyennes des valeurs. Avec le son, cela isolera les fréquences (aigus, graves, ultrasons…).
On pourra ensuite rendre moins précises ces moyennes (selon leur importance), afin de perdre intelligemment en taille. Cette étape est appelée quantification. Cette méthode dégrade la qualité mais est très utile pour les données multimédia, où on la retrouve partout : MP3, JPEG, MPEG, AAC, etc.
Chroma subsampling = sous-échantillonage de la chrominance (ouf !)
Fait d’étaler les pixels de couleurs de l’image afin d’avoir moins d’information à stocker, lorsque les pixels d’intensité (qui eux, ne sont pas stockés de la même façon) sont stockés séparément.
Se base sur l’idée que dans une image, les variations de contours sont plus visibles que les variations de teintes, qui peuvent être diluées.
Lexique des algorithmes de compression
LZ77
Algorithme à fenêtre glissante : on compresse en disant de reproduire des parties du flux qui ont déjà été produites en sortie.
Envoie des tuples (taille, distance, prochain caractère) en boucle en sortie.
- "prochain caractère" s’ajoute systématique à la fenêtre glissante.
- "taille", "distance" correspondent soit à une part de la fenêtre glissante à reproduire avant "prochain caractère", sinon ils sont à zéro.
LZSS
Comme LZ77 mais ajoute en plus un flag d’1 bit qui dit si ce qui suit est une référence à la fenêtre glissante ou bien une chaîne brute (comme ça il n’envoie pas des tuples à chaque nouvelle paire de caractères).
A plus d’applications concrètes que LZ77 (utilisé dans des packers, etc.)
RLE
Run-length encoding : désigne le fait de préfixer un symbole unique à répéter par le nombre de ces répétitions.
LZMA (.lzma, .7z, .xz)
S’inspire de LZ77 mais beaucoup plus puissant : fenêtre glissante de taille variable. Instructions de décodages à taille variable (range coding), s’optimisant à la volée en fonction des motifs rencontrés, et à plusieurs bits qui peuvent dire de reproduire une précédente instruction, donner des offsets complexes, etc. Et ainsi de constituer un dictionnaire de très grande taille.
Aujourd’hui très utilisé et second de GZip en popularité.
Rapide à décompresser et lent à compresser. Très bon ratio.
LZ78
Algorithme « par avalanche » : chaque nouveau caractère créé un code. Chaque nouvelle paire de caractères créé un code. Chaque nouveau triplet de caractères dont les deux premiers caractères constituent une paire de caractères déjà connue créé un nouveau code. Chaque nouveau quadruplet etc. Les codes ne sont plus ajoutés quand le dictionnaire est plein.
LZW (.Z)
Amélioration de LZ88 où le dictionnaire est pré-rempli avec tous les caractères possibles. Les codes font par défaut 12 bits (il nous reste donc plus de 11 bits de positions). Il peut y avoir des codes spéciaux : vider le dictionnaire, finir le flux, etc.
A plus d’applications concrètes que LZ88 (utilisé dans GIF, MOD, etc.)
DEFLATE (.zip, .gz, .zlib…)
Combinaison de Huffman et de LZ77. Grand concurrent de LZMA aujourd’hui. Dans l’idée, assez semblable au final : faire référence à des extraits déjà passés de la sortie, puis créer de nouvelles références courtes à ces répétitions elles-mêmes. Se retrouve dans les pages web, les .PNG, les .ZIP, les paquets logiciels… Autant dire partout. PNG l’optimise en ajoutant une seconde couche de filtres : un pixel peut être une répétition d’un pixel situé à gauche ou au-dessus, et un delta, par exemple.
BZ2
Patchwork d’algorithmes différents (BWT, qui est un filtre qui effectue du réarrangement d’octets, RLE, Huffman, delta encoding…).
Utilisé souvent dans le monde Linux.
Se situe entre DEFLATE et LZMA en efficacité.
LZ4, LZO, Snappy/Zippy
Algorithmes récents semblables à LZ77, taillés pour la performance
BCJ2
Filtre optionnel de LZMA conçu pour optimiser le compression d’instructions x86, conçu uniquement pour le format 7-Zip
Zopfli
Compresseur DEFLATE lent mais plus efficace, et plus récent que Zlib, conçu par Google.
Brotli
Algorithme à fenêtre glissante récent, conçu par Google, semblable à DEFLATE dans l’idée mis à part que de nombreux codes Huffman différents sont utilisés selon le contexte (en cela il est semblable à LZMA, même s’il n’utilise pas de range encoding)
Range encoding, arithmetic encoding
Techniques consistant à encoder des informations dans un grand nombre volumineux, en découpant successivement ce nombre en plusieurs parties, afin d’attribuer une valeur de bit (ou de symbole) donnée à chaque partie, puis sous-partie, puis sous-sous-partie… et on pondérant la taille des parties concernées à la probabilité de la valeur correspondante
Les termes « range coding » et « arithmetic coding » désignent deux manières sensiblement différentes d’expliquer le même concept.
Avec le « range coding », on vous parlera de « plage d’entiers », « taille de la plage » et « partie de la plage », alors qu’avec l’« arithmetic coding », on vous parlera de « fraction », « dénominateur » et « numérateur ». Il s’agit d’une simple différence de vocabulaire, les octets résultant seront codés pareil.
Le terme « arithmetic coding » est plus employé, mais le créateur de LZMA avait cœur à parler de « range coding ». Le range coding et le codage Huffman sont les deux grandes techniques de ce que l’on appelle le « codage entropique » (le fait de faire tenir un ensemble de codes dans le moins de bits possibles, où les codes plus fréquents prennent moins de place).
Huffman coding
Technique consistant à remplacer des symboles par des codes d’un nombre de bits variable, les codes les plus courts correspondant aux symboles les plus fréquents. Deux codes ne peuvent pas commencer pareil (on parle de « codes préfixes »), leurs tailles étant variables, ils ne peuvent ainsi pas être confondus.
S3TC, DXTC
Ensemble d’algorithmes de compression de textures populaires, créés à la fin des années 1990. Ils sont faits pour être lus matériellement (par une carte graphique) et créent une palette de 4 couleurs à partir de 2 couleurs explicitement mentionnées, pour chaque bloc de 8x8 pixels. Ils permettent aussi d’exprimer de la transparence (en fonction de la variante) et tronquent les couleurs à 16 bits.