Bzip2 utilise plusieurs couches de techniques de compression empilées les unes sur les autres, qui se produisent dans lordre suivant lors de la compression et dans lordre inverse lors de la décompression:
- Encodage de longueur dexécution (RLE) des données initiales.
- Transformation Burrows – Wheeler (BWT) ou tri par bloc.
- Transformation Move-to-front (MTF).
- Codage de longueur dexécution (RLE) du résultat MTF.
- Codage de Huffman.
- Sélection entre plusieurs tables de Huffman.
- Codage unaire base-1 de la sélection de la table de Huffman.
- Codage delta (Δ) des longueurs de bits du code Huffman.
- Tableau de bits épars montrant quels symboles sont utilisés.
Encodage de longueur dexécution initiale Modifier
Toute séquence de 4 à 255 symboles en double consécutifs est remplacée par les 4 premiers symboles et une longueur de répétition comprise entre 0 et 251. Ainsi la séquence AAAAAAABBBBCCCD est remplacé par AAAA\3BBBB\0CCCD, où \3 et \0 représente les valeurs doctet 3 et 0 respectivement. Les séries de symboles sont toujours transformées après 4 symboles consécutifs, même si la longueur de course est mise à zéro, pour garder la transformation réversible.
Dans le pire des cas, cela peut provoquer une expansion de 1,25, et dans le meilleur cas, une réduction à < 0,02. Alors que la spécification autorise théoriquement lencodage de séquences de longueur 256–259, lencodeur de référence ne produira pas une telle sortie.
Lauteur de bzip2 a déclaré que létape RLE était une erreur historique et quelle était uniquement destinée pour protéger limplémentation BWT dorigine des cas pathologiques.
TransformEdit de Burrows – Wheeler
Cest le tri par blocs réversible qui est au cœur de bzip2. Le bloc est entièrement autonome, les tampons dentrée et de sortie restant de la même taille – dans bzip2, la limite de fonctionnement pour cette étape est de 900 Ko. Pour le tri par bloc, une matrice (fictive) est créée, dans laquelle la ligne i contient la totalité du tampon, tournée pour commencer à partir du i-ème symbole. Après la rotation, les lignes de la matrice sont triées par ordre alphabétique (numérique). Un pointeur 24 bits est stocké marquant la position de départ lorsque le bloc nest pas transformé. En pratique, il nest pas nécessaire de construire la matrice complète; au contraire, le tri est effectué en utilisant des pointeurs pour chaque position dans le tampon. Le tampon de sortie est la dernière colonne de la matrice; celui-ci contient le tampon entier, mais réorganisé de manière à ce quil contienne probablement de grandes séries de symboles identiques.
Transformation Move-to-frontEdit
Encore une fois, cette transformation ne modifie pas la taille du bloc traité. Chacun des symboles utilisés dans le document est placé dans un tableau. Lorsquun symbole est traité, il est remplacé par son emplacement (index) dans le tableau et ce symbole est mélangé à lavant du tableau. Leffet est que les symboles immédiatement récurrents sont remplacés par des symboles zéro (les longues séries de nimporte quel symbole arbitraire deviennent ainsi des séries de symboles zéro), tandis que les autres symboles sont remappés en fonction de leur fréquence locale.
Beaucoup de données « naturelles » contient des symboles identiques qui se reproduisent dans une plage limitée (le texte est un bon exemple). Comme la transformation MTF attribue des valeurs faibles aux symboles qui réapparaissent fréquemment, il en résulte un flux de données contenant de nombreux symboles dans la plage dentiers inférieurs, beaucoup dentre eux étant identiques (différents symboles dentrée récurrents peuvent en fait mapper sur le même symbole de sortie). Ces données peuvent être très efficacement encodées par nimporte quelle méthode de compression héritée.
Encodage de longueur dexécution de MTF resultEdit
De longues chaînes de zéros dans la sortie de la transformation move-to-front ( qui proviennent de symboles répétés dans la sortie du BWT) sont remplacés par une séquence de deux codes spéciaux, RUNA et RUNB, qui représentent la longueur dexécution sous forme de nombre binaire. Les zéros réels ne sont jamais codés dans la sortie; un seul zéro devient RUNA. (Cette étape se fait en fait en même temps que MTF; chaque fois que MTF produirait zéro, il augmente à la place un compteur pour ensuite encoder avec RUNA et RUNB.)
La séquence 0, 0, 0, 0, 0, 1 serait représenté par RUNA, RUNB, 1; RUNA, RUNB représente la valeur 5 comme décrit ci-dessous. Le code de longueur dexécution se termine en atteignant un autre symbole normal. Ce processus RLE est plus flexible que létape RLE initiale, car il est capable de coder des entiers arbitrairement longs (en pratique, cela est généralement limité par la taille du bloc, de sorte que cette étape ne code pas une exécution de plus de 900000 octets). La longueur dexécution est codée de cette manière: en attribuant des valeurs de position de 1 au premier bit, de 2 au deuxième, de 4 au troisième, etc. dans la séquence, multipliez chaque valeur de position dans un point RUNB par 2, et ajoutez tout les valeurs de position résultantes (pour les valeurs RUNA et RUNB) ensemble. Ceci est similaire à la numération bijective en base 2.Ainsi, la séquence RUNA, RUNB donne la valeur (1 + 2 × 2) = 5. Comme exemple plus compliqué:
RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49
Huffman codingEdit
Ce processus remplace les symboles de longueur fixe compris entre 0 et 258 par des codes de longueur variable basés sur la fréquence dutilisation. Les codes les plus fréquemment utilisés finissent par être plus courts (2 à 3 bits), tandis que les codes rares peuvent être alloués jusquà 20 bits. Les codes sont soigneusement sélectionnés pour quaucune séquence de bits ne puisse être confondue avec un code différent.
Le code de fin de flux est particulièrement intéressant. Sil y a n octets (symboles) différents utilisés dans les données non compressées, alors le code Huffman se composera de deux codes RLE (RUNA et RUNB), n – 1 codes de symboles et un code de fin de flux. En raison du résultat combiné des codages MTF et RLE dans les deux étapes précédentes, il nest jamais nécessaire de référencer explicitement le premier symbole dans la table MTF (serait zéro dans le MTF ordinaire), économisant ainsi un symbole pour la fin. marqueur de flux (et expliquant pourquoi seuls n – 1 symboles sont codés dans larbre de Huffman). Dans le cas extrême où un seul symbole est utilisé dans les données non compressées, il ny aura aucun code de symbole dans larbre de Huffman, et le bloc entier sera composé de RUNA et RUNB (répétant implicitement loctet unique) et une fin de marqueur de flux avec la valeur 2.
0: RUNA, 1: RUNB, 2–257: valeurs doctet 0–255, 258: fin de flux, terminer le traitement (peut être aussi bas que 2).
Plusieurs tables HuffmanModifier
Plusieurs tables Huffman de taille identique peuvent être utilisées avec un bloc si le gain de leur utilisation est supérieur au coût dinclusion de la table supplémentaire. Au moins 2 et jusquà 6 tables peuvent être présentes, la table la plus appropriée étant resélectionnée tous les 50 symboles traités. Cela a lavantage davoir une dynamique de Huffman très réactive sans avoir à fournir en permanence de nouvelles tables, comme cela serait requis dans DEFLATE. Le codage de longueur dexécution à létape précédente est conçu pour prendre en charge les codes qui ont une probabilité dutilisation inverse supérieure au code le plus court du code Huffman utilisé.
Codage unaire de la sélection de table de HuffmanModifier
Si plusieurs tables de Huffman sont utilisées, la sélection de chaque table (numérotée de 0 à 5) se fait à partir dune liste par un bit terminé par zéro parcouru entre 1 et 6 bits de longueur. La sélection se fait dans une liste MTF des tables. Lutilisation de cette fonctionnalité entraîne une expansion maximale denviron 1,015, mais généralement moins. Cette expansion est susceptible dêtre largement occultée par lavantage de sélectionner des tables de Huffman plus appropriées, et le cas courant de continuer à utiliser la même table de Huffman est représenté comme un seul bit. Plutôt quun encodage unaire, il sagit en fait dune forme extrême darbre de Huffman, où chaque code a la moitié de la probabilité du code précédent.
Delta encodingEdit
Les longueurs de bits du code Huffman sont nécessaire pour reconstruire chacune des tables canoniques de Huffman utilisées. Chaque longueur de bit est stockée comme une différence codée par rapport à la longueur de bit du code précédent. Un bit zéro (0) signifie que la longueur de bit précédente doit être dupliquée pour le code actuel, tandis quun bit (1) signifie quun bit supplémentaire doit être lu et la longueur de bit incrémentée ou décrémentée en fonction de cette valeur.
Dans le cas courant, un seul bit est utilisé par symbole par table et le pire des cas – allant de la longueur 1 à la longueur 20 – nécessiterait environ 37 bits. En raison du codage MTF antérieur, les longueurs de code commenceraient à 2 à 3 bits (codes très fréquemment utilisés) et augmenteraient progressivement, ce qui signifie que le format delta est assez efficace, nécessitant environ 300 bits (38 octets) par table de Huffman complète .
Tableau de bits éparsEdit
Un bitmap est utilisé pour montrer quels symboles sont utilisés à lintérieur du bloc et doivent être inclus dans les arbres de Huffman. Les données binaires utiliseront probablement les 256 symboles représentables par un octet, tandis que les données textuelles ne peuvent utiliser quun petit sous-ensemble de valeurs disponibles, couvrant peut-être la plage ASCII entre 32 et 126. Le stockage de 256 bits à zéro serait inefficace sils étaient pour la plupart inutilisés. Une méthode creuse est utilisée: les 256 symboles sont divisés en 16 plages, et seulement si des symboles sont utilisés dans ce bloc, un tableau de 16 bits est inclus. La présence de chacune de ces 16 plages est indiquée par un tableau de 16 bits supplémentaire à lavant.
Le bitmap total utilise entre 32 et 272 bits de stockage (4 à 34 octets). Par contraste, lalgorithme DEFLATE montrerait labsence de symboles en codant les symboles comme ayant une longueur de bit de zéro avec un codage de longueur dexécution et un codage Huffman supplémentaire.