Compression des informations

 

 

 

Les images les sons et les vidéos sont souvent compressés pour gagner de la place en mémoire.

Les textes peuvent l'être aussi.

L'algorithme de huffman permet de réaliser une des étapes de compression de texte.

​

I] Codage des caractères

​

ASCII code permettant sur 1octet(8bits) de représenter toutes les touches d'un clavier américain.

L'algorithme de Huffman permet de coder les caractères les plus fréquents avec moins de bits que les caractères les moins fréquents.

 

"C'est un texte"

​

 

 

(c;1)

(';1)

(e;3)

(s;1)

(t;3)

(  ;2)

(u;1)

(n;1)

(x;1)

 

 

​

 

Pour décoder il faut que l'arbre ait été enregistré avec le code.

 

Pour diminuer encore la taille du code il faut opérer des permutations circulaires.

 

II] Permutation de Burrows Wheeler

​

Des permutations circulaires sont appliqués aux textes de manière à décrire toutes les possibilités .On s'aperçoit que statistiquement en lisant la dernière colonne on trouve des groupes de lettres semblables

Les permutations de Burrows wheeler suivit d'une mise par ordre alphabétique et de la lecture de la dernière colonne permettent souvent de rassembler les lettres semblables.

 

III] Move to front(déplacer vers l'avant)

 

Le disctionnaire sera constitué d'un alphabée dont les lettres sont numérotés de 0 à 25, chaque fois qu'une lettre est codée , elle subit un move to front dans le dictionnaire elle passe en premiere place et prend le code 0.

​

(7,etttteeea)

a b c d e … t … z

0 1 2 3 4    19    25

e → 4

 

 

e a b c d … t … z

0 1 2 3 4    19    25

t → 19

 

t  e a b c … z

0 1 2 3 4      25

t → 0        t →0         t → 0

 

e  t a b c … z

0 1 2 3 4     25

e → 0        e → 0      e → 0

a → 2

 

4190000002

 

Pour une compression, burroz weeller, move to front puis huffman. Pour une décompression, l'inverse.