PackBits
La compression PackBits est un schéma de compression de longueur d'exécution simple orienté octet ayant été initialement développé pour être utilisé dans le format de fichier image MacPaint et est l'un des nombreux schémas pris en charge par le format TIFF. L'algorithme PackBits code un flux d'octets en une série de paquets consistant en un octet d'index suivi d'un certain nombre d'octets de données. La façon la plus simple d'expliquer l'algorithme est de décrire le processus de décodage. Voici son algorithme :
|
BOUCLE JUSQU'A nombre d'octets souhaité a été décodé N ← octet suivant de l'entrée SI N < 0 ALORS Lisez l'octet suivant de l'entrée et répétez-le 1 à N fois. SINON Lire les N + 1 octets suivants de l'entrée. FIN SI FIN BOUCLE |
Voici quelques notes et règles concernant l'algorithme :
- Chaque ligne de numérisation d'une image doit être codée séparément. Ainsi, les paquets dans le flux de données compressé ne peuvent pas s'étendre sur les lignes de balayage.
- Notez que les valeurs d'index sont toujours incrémentées de 1 avant d'être utilisées dans le processus de décodage. Ainsi, un indice de 0 implique un décompte de 1, un indice de 1 implique un décompte de 2, un indice de -5 implique un décompte de 6,...
- Les valeurs d'index valides vont de -127 à 127. Cette situation donne des nombres compris entre 1 et 128. Notez que la valeur d'index -128 n'est jamais utilisée.
Dans la plupart des schémas de compression basés sur le RLE (Run-Length), la logique requise pour effectuer le codage est plus complexe que la logique de décodage. Le PackBits est typique à cet égard. Cette situation résulte principalement du fait qu'un flux de données spécifié produit rarement une représentation codée unique, quel que soit l'algorithme, de sorte qu'une prise de décision accompagne invariablement le processus de codage. Par exemple, considérons la séquence d'octets AAB. Cela pourrait être codé par l'algorithme PackBits de plusieurs manières différentes. Une façon serait que deux cycles répétitifs, deux comme suit un B. Un autre serait une séquence non répétitive unique de trois octets, AAB. Il s'avère que les deux formes en génèrent une est souhaitable. Il est possible avec un effort suffisant de déterminer le codage optimal pour une chaîne de données spécifiée, mais les résultats justifient rarement l'effort.