Index des articles > Documentations > La compression de données - Compression sans perte AFE

La compression de données - Compression sans perte AFE

Article posté par serioussam

La compression AFE (Adaptative Frequence Encoding) Codage adaptatif des fréquences :


1-Principe et méthode :

La méthode consiste à ajuster la taille des caractères en fonction de leur fréquence d?apparition. Nous allons donc essayer d?attribuer un code ASCII plus court aux caractères les plus redondants.

Tous les caractères sont codés en ASCII 8 bits, l?idée est donc de coder sur le moins de bits possible un caractère. Une compression particulière sera appliquée permettant ainsi de distinguer un caractère dont sa taille variera entre 2 et 11 bits.

Le nouveau code d?un caractère est décomposé en 2 parties, l?en-tête de 3 bits et un corps variant de 1 à 7 bits.

-L?en-tête détermine la taille du corps, c?est à dire le nombre de bits à lire après celui-ci pour reconstituer le code complet du caractère (par exemple si nous rencontrons une en-tête « 111 », le corps est alors long de 7 bits car 111 en binaire donne 7 en base 10).

-Le corps du code représente le caractère codé.

Exemple d?un code : 100 0111

L?en-tête est « 100 » ce qui nous donne en base 10 4 car 2^2=4, ainsi notre corps aura une longueur de 4 bits soit dans notre exemple « 0111 ».

Pour coder un caractère nous aurons besoin d?une table nous donnant des informations sur le code ASCII du caractère, son en-tête de 3 bits, sa fréquence d?apparition et enfin son corps.

L?algorithme de compression commence par un dictionnaire ou table de transcription initiale, les caractères sont rangé suivant leur code ASCII. (Voir fichier table initiale AFE).

2-Algorithme de compression :

Ce nouveau codage permet finalement le codage de la moitié des caractères sur moins de 8 bits (4 minimums) mais d?autres seront en contrepartie codés sur plus de 8 bits ? Le but de l'algorithme est maintenant d?attribuer les codes les plus courts aux caractères les plus fréquents, pour gagner de la place.

Lors de la compression, le compresseur va lire les caractères et les ranger dans le dictionnaire en fonction de leurs fréquences et ce, au fur et à mesure de la lecture.

La fréquence d?un caractère augmente alors de 1 à chaque fois qu?il est rencontré lors de la lecture, le caractère est reclassé dans la table en fonction de sa nouvelle fréquence. Il prend généralement la place d?un autre caractère et décale tous ceux situés en dessous d?un cran vers le bas. On dit que le dictionnaire est dynamique, il change en effet à chaque caractère lu.

Les fréquences hautes se trouveront finalement au début de la table avec un code plus court.

Le principe est simple, si les caractères les plus redondants sont codés sur 4 bits, ils prendront alors moins de place que s?ils étaient codés sur 8 bits ! ! Logiquement d?autres caractères devront être codés sur 8, 9, 10 ou 11 bits?mais ils sont beaucoup moins fréquents d?où un gain logique de place.

On obtient finalement une table de référence avec les nouveaux codages de tous les caractères.

L?ensemble du texte compressé comprendra une table de codage suivie de l?information.

Supposons que nous sommes en pleine compression et que l'on arrive au stade ci-dessous :

Caractère en-tête corps fréquence
'A' 000 0 27
'Z' 000 1 27
... ... ... ...
'E' 100 1110 26
'C' 100 1111 5
'B' 101 00000 2

Si le prochain caractère lu est un 'E' : on écrira '100 1110', sa fréquence sera de 27 et il se placera au tout début de la table :

Caractère en-tête corps fréquence
'E' 000 0 27
'A' 000 1 27
'Z' 001 0 27
... ... ... ...
'C' 100 1111 5
'B' 101 00000 2

On remarquera que les caractères allant de l'ancienne position de 'E' à sa nouvelle position (du caractère 'A' inclu au caractère 'C' exclu) ont changé de code


3-Algorithme de décompression :

La compression et la décompression sont symétriques. Pour que la décompression fonctionne bien, elle doit suivre le même parcours que la compression avec la même table de codage.

Elle commence par la lecture des 3 premiers bits de l?information ( l?en tête ) qui permet de connaître le nombre de bits à lire pour reconstituer le code au complet d?un élément. Il faut ensuite utiliser la table de référence obtenue lors de la compression pour trouver le caractère attribué à ce code.

Tous les bits de l?information vont être décodés ainsi de suite jusqu?à la fin?
Les caractères reconstitués seront reclassés dans la table avec une nouvelle fréquence d?apparition.


4-Avantages et inconvénients :

Cette méthode de compression est très rapide et peu coûteuse en mémoire, malheureusement elle permet dans les meilleurs cas d?obtenir un taux de compression de 50% soit diviser par 2 la taille d?un fichier et dans les pires cas, on obtient une perte d?environ ?28%. En général le AFE donne des taux de compression entre ?20% et 2%.
Un grand avantage de cette méthode de compression c?est que les données sont reconstituées au fur et à mesure de la lecture du fichier compressé, ainsi l?application dans le transfert de données est possible, de plus cette méthode de compression est très performante dans le cas de format de fichiers n?utilisant pas tous les caractères de la table ASCII. La compression AFE n?est pas utilisée de nos jours à cause de ses faibles taux de compression.

>> Vos commentaires [0]

Pas de commentaires

Poster un commentaire


Seuls les membres peuvent poster des commentaires