L'ALGORITHME DE HUFFMAN

       Lorsque des textes se retrouvent dans des dossier compressés (.zip par exemple) ils seront compressés sans pertes d'informations.

I.Codage des caractères

      Code ASCII sur 1octet permet de coder les caractères américains du clavier.

      Tous les caractères sont codés sur le même nombre de bit. Pour compresser il faut coder les caractères les plus fréquents sur un plus petit nombre de bit.

Il faut enregistrer le code et l'arbre car il existe une infinité d'arbre pour un code.

II.Permutation circulaire de Wheeler

« tete a tete » → On permutte les lettres en enlevant la première et la mettant à la fin.

→ tete a tete 7)

ete a tetet 3)

te a tetete 6)

e a tetetet 2)

a tetetete 10)

a tetetete 1)

tetetete a 11)

tetetete a 9)

etetete a t 5)

tetete a te 8)

etete a tet 4)

tete a tete

   → Maintenant on trie les lignes par ordre alphabétique.

a tetetete

e a tetetet

ete a tetet

etete a tet

etetete a t

te a tetete

tete a tete

tetete a te

tetetete a

a tetetete

tetetete a

Après avoir réalisé toutes les permutations circulaires et les avoir classées par ordre alphabétique on relève la dernière colonne et la position du texte de départ. Souvent des lettres semblables se trouvent associés. → Ici c'est la ligne 7(numéro du texte de départ après permutation plus classement par alphabétique) , etttteeea (les lettres de la dernière colonne). 

III.Move to front

Dictionnaire :

• 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,d......z
  

           0,1,2,3,4,5....25

t → 0 t → 0 t → 0

• e → 1 e,t,a,b,c,d......z
  

            0,1,2,3,4,5....25

e → 0 e → 0

a → 2

=> 4,19,0,0,0,1,0,0,2

  Ces 3 méthodes sont associées pour crée des fichiers zip :

• Wheelers

• Move to front

• Huffman

  Pour décoder on fait dans l'autre sens.