Compression de données

Compression de données
Algorithme de LEMPEL-ZIV

Introduction :

La compression permet d'optimiser la place utilsée par des données et permet aussi de crypter des fichiers.
Le programme réalisé en C++ est un codeur utilisant cet algorithme, il a été réalisé sous Borland C++ Builder 3.
La premiere partie explique le fonctionnement de l'algorithme et la deuxieme partie explique le programme "Snarf Codeur 2.0" utlisant cet algorithme pour coder des fichiers.

Sommaire :

I Presentation de l'algorithme

II Exemple de realisation de l'algorithme en C++
.... A Généralités
.... B Programmation de l'algorithme

I Presentation de l'algorithme

Le codage utilise l'algorithme de LEMPEL-ZIV qui est en fait un algorithme de compression de donnée.
Cette technique permet d'optimiser la place utilisée par les données et accessoirement de les crypter.
C'est pour cette dernière possibilité que l'algorithme est utilisé en raison de sa lenteur et de son faible taux de compression par rapport aux compresseurs existants, comme par exemple WinZip.
L'idée générale est de coder une chaîne de caractère sur un nombre inférieur de bits. On crée un nouvel "alphabet " contenant les caractères standards, codés sur 8 bits, et des chaînes de caractères codées sur 9 bits ou plus. Par exemple, le nouvel alphabet pourra ętre le suivant :

Code Chaîne
00 00h
01 01h
... ...
65 A
66 B
... ...
255 FFh
256 BA
257 ON
258 ONJ
... ...

L'un des intéręts de l'algorithme de LEMPEL-ZIV est qu'il ne nécessite pas d'avoir une connaissance préalable des données à compresser et que le nouvel alphabet n'a pas à ętre transmis dans le fichier.
Pour cela if faut que la suite des codes écrits puisse permettre de reconstituer le nouvel alphabet. Par conséquent il faut que les codes déjà lus permettent de créer les nouveaux codes et que chaque lu doit déjà ętre décodé.
La solution adoptée par LEMPEL-ZIV consiste à décaler l'écriture d'un code et son ajout dans l'alphabet : au moment du codage, le code émis est toujours un code figurant déjà dans l'alphabet et le code qui est placé dans la table(ou l'alphabet) peut ętre reconstruit à partir des codes émis précédemment.
La construction de l'alphabet est simple : on construit une chaîne, en vérifiant à chaque ajout de caractère si cette chaîne est dans la table.
Si elle y est déjà on ajoute un nouveau caractère, sinon on ajoute la nouvelle chaîne à l'alphabet, et on recommence avec une nouvelle chaîne vide. Pour décaler l'écriture du code avec son codage, il suffit d'écrire le code correspondant à la chaîne actuelle moins son dernier caractère. Ce code est forcément déjà dans l'alphabet car chaque nouvelle chaîne est l'ajout d'une chaîne déjà existante et d'un nouveau caractère.
L'algorithme de compression est donc le suivant :

Initialiser la table avec les caractères du code ASCII et la chaîne à vide
Tant Que des caractères sont lus
Ajouter le nouveau caractère à la chaîne
Si la chaîne n'est pas dans la table
Ajouter la chaîne à la table
Ecrire le code correspondant à la chaîne moins son dernier caractère
Initialiser la chaîne au dernier caractère de celle-ci
Ecrire le code correspondant à la chaîne

voici un exemple de codage d'un texte comportant un alphabet de deux lettres :

Message Chaîne Chaîne ajoutée à la table Code émis
A A
A AA->A 2=AA 0=A
B AB->B 3=AB 0=A
A BA->A 4=BA 1=B
B AB
B ABB->B 5=ABB 3=AB
A BA
B BAB->B 6=BAB 4=BA
A BA
A BAA 7=BAA 4=BA
B AB
A ABA->A 8=ABA 3=AB
B AB
B ABB 5=ABB
fin de fichier

Le nombre de caractère au départ est de 14. Le nombre de code du fichier compressé est de 8.
L'alphabet de départ est constitué de 2 caractères donc est codé sur 1 bit.
La taille du message codé en bit est :
Code : 0 0 1 3 4 4 3 5
Taille en bit : 1 + 1 + 1 + 2 + 3 + 3 + 2 +3 = 16 bits !

La taille du fichier compressé est supérieure à celle du fichier original.
Cela vient du fait que le gain apporté en codant une chaîne de plusieurs caractères sur un seul est petit du au codage de l'alphabet de départ sur 1 bit.
Une chaîne de 2 caractères a un code au minimum égal à 3 donc est codé sur 2 bits. Le gain est donc nul.
Si l'alphabet de départ comporte 8 bits comme c'est le cas normalement, le codage de 2 caractères, c'est à dire 16 bits, s'écrit sur 9 bits.
On a donc un gain de 7 bits.
Dans l'exemple ci-dessus, la taille du message original est de 14*8 = 112 bits et celle du fichier codé est de 3*8 + 5*9 = 69 bits ce qui correspond à 9 caractères écrits (on ne peut écrire que par paquets de 8 bits). On a donc gagné 5 octets.

En ce qui concerne la décompression, l'algorithme est le suivant :

Initialiser la table avec les caractères du code ASCII
Lire et décoder le premier caractère
Tant Que des caractères sont lus
Si le code n'est pas dans la table
Alors écrire la chaîne formée par la chaîne précédente plus son premier caractère
Sinon écrire la chaîne correspondante au code
Ajouter à la table le code formé par la chaîne précédente plus le premier caractère de la chaîne actuelle

Voici la décompression de l'exemple précédent :

Message codé chaîne décodée chaîne ajoutée à la table
0 A
0 A 2 = A + A
1 B 3 = A + B
3 AB 4 = B + A
4 BA 5 = AB + B
4 BA 6 = BA + B
3 AB 7 = BA + A
5 ABB 8 = AB + A

II Exemple de realisation de l'algorithme en C++

A Généralités :

Le programme se décompose en 2 parties.
La première est la partie graphique, c'est à dire la feuille principale avec les labels et les dialogues.
La deuxième partie est la traduction de l'algorithme de codage.
Ces deux parties sont contenues dans deux unités différentes :
unit1.cpp, unit1.h et unit1.dfm (pour la fiche)
fonctions.cpp et fonctions.h

La feuille principale appelle deux fonctions de l'unité "fonctions". Ces deux fonctions sont définies comme suit :

void Codage(char *source, char *dest);
void DeCodage(char *source, char *dest);

La première fonction sert, comme son nom l'indique, à coder un fichier. Le premier paramètre est le nom du fichier original, le deuxième est le nom du fichier de destination, c'est à dire le fichier codé. Ces deux fonctions sont appelées lors du click sur les labels "...Coder..." et "...Décoder...".

B Programmation de l'algorithme :

L'algorithme nécessite que l'on puisse écrire des codes sur 9 bits et plus.
Or on ne peut écrire que des octets, c'est à dire 8 bits.
La solution choisie consiste à imposer le nombre de bits des codes et à écrire les codes 8 par 8.
Le nombre de bits des codes est fixé à 11, c'est à dire que tous les codes ont une taille de 11 bits.
Par exemple, le code 16 devient 000 00010000, le code 2047 devient 111 11111111
Il y a donc une perte de place pour les codes inférieurs à 11 bits mais il est nécessaire de savoir combien de code on doit lire de bits pour pouvoir décoder.
En le fixant à 11, le nombre de bits à lire pour le décodage est toujours le męme. De plus cette solution permet une écriture plus facile des codes.
En effet, si on regroupe les codes par paquets de 8, on obtient un total de 88 bits.
On peut donc écrire 11 caractères de 8 bits chacun.
Par exemple :
Les 8 codes (en binaires) : 011101011011 11100011010 11000011001...
Les 11 codes après découpage : 01110101 10111100 01101011 00001100 1...

Les 8 codes de 11 bits et les 11 codes de 8 bits sont stockés dans deux tableaux
différents définis comme suit :

unsigned char bufByte[11]; // 11*8 bits avant d'écrire
int bufCode[8]; // les 8 codes à écrire de 11 bits chacun

Le passage d'un tableau à l'autre est réalisé par les deux fonctions suivantes :

void CodeToByte();
void ByteToCode();

Ces conversions sont réalisées par décalage binaire réalisé dans les deux
fonctions :

//-----------------------------------------------------------------
void CodeToByte()
{
// on a bufCode[8] de 11 bits et on veut bufByte[11] de 8 bits
for(i=0;i<11;i++) bufByte[i] = 0;
bufByte[0] = (bufCode[0] >> 3);
bufByte[1] = (bufCode[0] << 5) | (bufCode[1] >> 6);
bufByte[2] = (bufCode[1] << 2) | (bufCode[2] >> 9);
bufByte[3] = (bufCode[2] >> 1);
bufByte[4] = (bufCode[2] << 7) | (bufCode[3] >> 4);
bufByte[5] = (bufCode[3] << 4) | (bufCode[4] >> 7);
bufByte[6] = (bufCode[4] << 1) | (bufCode[5] >> 10);
bufByte[7] = (bufCode[5] >> 2);
bufByte[8] = (bufCode[5] << 6) | (bufCode[6] >> 5);
bufByte[9] = (bufCode[6] << 3) | (bufCode[7] >> 8);
bufByte[10]= (bufCode[7]); // >> 0)
}
//-----------------------------------------------------------------

//-----------------------------------------------------------------
void ByteToCode()
{
static short iBTC;
for(i=0;i<8;i++) bufCode[i] = 0;
bufCode[0] = (bufByte[0] << 3) | (bufByte[1] >> 5);
bufCode[1] = (bufByte[1] << 6) | (bufByte[2] >> 2);
bufCode[2] = (bufByte[2] << 9) | (bufByte[3] << 1) | (bufByte[4] >> 7);
bufCode[3] = (bufByte[4] << 4) | (bufByte[5] >> 4);
bufCode[4] = (bufByte[5] << 7) | (bufByte[6] >> 1);
bufCode[5] = (bufByte[6] << 10) | (bufByte[7] << 2) | (bufByte[8] >> 6);
bufCode[6] = (bufByte[8] << 5) | (bufByte[9] >> 3);
bufCode[7] = (bufByte[9] << 8) | (bufByte[10]);

//met à 0 les bytes en trop (les 5 de gauche)
// 0000 0111 1111 1111 --> le filtre = 2047
//&1011 1001 0110 1010 --> le code sur 16 bits
// -------------------
// 0000 0001 0110 1010 --> résultat sur 11 bits
for(iBTC=0;iBTC<8;iBTC++) bufCode[iBTC] &= 2047;
}
//-----------------------------------------------------------------

La définition de la variable "int i" est en globale car elle est utilisée pour d'autres fonctions.
La variable "iBTC" est définie en static pour éviter d'avoir à la recréer à chaque appelle de la fonction.
Lors de l'écriture du dernier paquet de 8 codes lors du codage, il y a risque d'écrire des codes en trop si le nombre total de code n'est pas un multiple de 8.
Lors du décodage, ces codes seront lus et décoder comme des codes normaux.
Le fichier restitué sera alors différent de l'original.
Il faut donc stocker la taille du fichier original pour pouvoir supprimer les caractères en trop lors du décodage. Le stockage s'effectue en convertissant la taille en chaîne de caractère de 50 octets puis en effectuant une rotation binaire de chaques caractères pour éviter de pouvoir lire facilement la taille du fichier. Lors du codage une rotation à gauche est effectuée et lors du décodage, une à droite.
La suppression de caractère en fin de fichier n'est pas prévue par le C++.
Il faut donc créer un fichier temporaire contenant le fichier décodé avec les caractères en trop et ne copier que le bon nombre de caractères dans le fichier de destination choisi par l'utilisateur.

Le stockage de l'alphabet est réalisé dans un tableau de chaînes de caractères. La taille maximale d'un tableau étant limitée à un segment, c'est à dire 65536 octets, le nombre maximum de code étant 2048 (211) , la longueur des chaînes de caractère est donc limitée à 20 (20 * 2048 = 40960 < 65536).
Le nombre maximal de caractère aurait pu ętre plus élevé mais les chaînes de plus de 20 caractères sont très rares.
Il faut aussi un tableau contenant la taille des chaînes. En effet ici les chaînes ne sont pas des chaînes AZT.
La détermination de leur taille est donc impossible, il faut donc la stocker.
Il faut aussi stocker le nombre total de chaînes que comporte l'alphabet :

unsigned char Table[2048][20]; // l'alphabet
short TbTaille[2048];
short nbChaine;

Au moment de l'initialisation, la variable nbChaine a pour valeur 256. En effet,
les chaînes de 0 à 255 sont déjà utilisées pour les caractères standards.

Il faut aussi une chaîne pour permettre le codage et le décodage.
Pour le décodage il faut aussi avoir en mémoire la chaîne précédente.
On utilise deux variables :

unsigned char SousChaine[20]; short Taille ;
unsigned char PSousChaine[20]; short Ptaille ; // la chaîne précédente

Il faut aussi créer une fonction transférant une chaîne dans une autre car la fonction strcpy est inutilisable (ce ne sont pas des chaînes AZT).
Elle est définie comme suit :

void CopyChaine(unsigned char* dest,unsigned char* source);

Lors d'un click sur le label "Annuler", il faut pouvoir arręter le codage ou le décodage.
Une variable "stop" de type bool est mise à true lors de l'appelle de la fonction StopCodage.
Avant chaque lecture dans le fichier à coder (ou à décoder), les fonctions Codage et Decodage vérifient si la variable StopCodage
est à true. Si tel est le cas, la fonction s'arręte.

bool stop;
void StopCodage(void);

L'algorithme de codage est donc devenu le suivant :

Ouvrir le fichier source
Créer le fichier destination
Lire la taille du fichier source et la transformer en chaîne de caractère
Effectuer la rotation de la taille et l'écrire dans le fichier destination
Mettre à jour la barre de progression
Initialiser la table
Tant que des caractères sont lus
Si stop=true arręter le codage
Si la taille de la chaîne est inférieure à 20
Ajouter le nouveau caractère
Si la chaîne n'est pas dans la table
Ajouter la chaîne
Mettre dans bufCode la code correspondant à la chaîne moins son dernier caractère
Si le nombre de code est 8, convertir bufCode en bufByte et l'écrire dans le fichier
Initialiser la chaîne au dernier caractère de celle-ci
Si la taille est égale à 20
Mettre dans bufCode la code correspondant à la chaîne moins son dernier caractère
Si le nombre de code est 8, convertir bufCode en bufByte et l'écrire dans le fichier
Initialiser la chaîne au dernier caractère de celle-ci
Actualiser la barre de progression
Mettre dans bufCode la code correspondant à la chaîne
Convertir bufCode en bufByte et l'écrire dans le fichier
Fermer les 2 fichiers
Envoyer le message de fin de codage

L'algorithme de décodage est devenu :

Ouvrir le fichier source
Créer le fichier temporaire (oů seront écrites les chaînes)
Créer le fichier destination
Lire la taille dans le fichier source et effectuer la rotation
Mettre à jour la barre de progression
Initialiser la table
Tant que des paquets de 11 caractères sont lus
Si stop=true arręter le codage
Convertir les caractères lus en code de 11 bits
Pour chaque code faire
Si le code est dans la table, écrire la chaîne correspondant au code
Sinon écrire la sous chaîne formée par celle précédente plus son premier
caractère
Ajouter à la table le code formé par la chaîne précédente plus le premier
caractère de la chaîne actuelle
Actualiser la barre de progression
Copier dans le fichier destination le bon nombre de caractère
Fermer les 3 fichiers
Effacer le fichier temporaire
Envoyer le message de fin de codage

i-jeune