1. Correction HC
2. Files d'attente
3. Files de priorité
4. La structure d'arbre
5. Optimalité du tri
6. Compression -- code de Huffman
7. Code de Huffman dynamique
8. Ziv-Lempel
9. Exercices

class FIFO {
  final static int  MaxF = 100;
  int               debut, fin;
  boolean           pleine, vide;
  int               contenu[];    

  FIFO () {
    debut = 0; fin = 0; pleine = false; vide = true;
    contenu = new int[MaxF];
  } 

  static void ajouter (int x, FIFO f) {
    if (f.pleine)
        erreur ("File Pleine.");
    f.contenu[f.fin] = x;
    f.fin = (f.fin + 1) % MaxF;
    f.vide = false; f.pleine = f.fin == f.debut;
  }

  static int supprimer (FIFO f) {
    if (f.vide)
        erreur ("File Vide.");
    int res = contenu[f.debut]
    f.debut =  (f.debut + 1) % MaxF;
    f.vide = f.fin == f.debut; f.pleine = false;
    return res;
  }

class FIFO {
        
  Liste debut, fin;

  FIFO (Liste a, Liste b)  {
    Liste garde = new Liste();   
    debut = fin = garde;
  }

  static void ajouter (int x, FIFO f) {
    Liste a = new Liste (x, null);
    f.fin.suivant = a;
    f.fin = a;
  }

  static int supprimer (FIFO f)  throws EmptyFifoException {   
    if (f.debut == f.fin)
        throw new EmptyFifoException();
    int res = f.debut.suivant.contenu;
    f.debut = f.debut.suivant;
    return res;
  }
}

class EmptyFifoException extends Exception {}

class FilePriorite {
  final static int  MaxF = 100;
  int               t[];
  int               nb;
  FilePriorite () { t = new int[MaxF]; nb = 0; }
  static void ajouter (FilePriorite f, int v)  {
    ++f.nb; int[] t = f.t; int n = f.nb; int i = n - 1;
    while( i > 0 && t[(i - 1)/2] <= v ) {
        t[i] = t[(i - 1)/2]; 
        i = (i - 1)/2;
    }
    t[i] = v;
  }
  static int premier (FilePriorite f) { return f.t[0]; }

static int supprimer (FilePriorite f) {
  int[] t = f.t; 
  int res = t[0]; 
  t[0] = t[f.nb - 1]; -- f.nb;
  int v = t[0]; 
  for (int i = 0; 2*i + 1 < f.nb; ) {
      int j = 2*i + 1;
      if (j + 1 < f.nb && t[j + 1] > t[j])   ++j;
      if (v >= t[j])  break;
      t[i] = t[j]; i = j;
  }
  t[i] = v;
  return res;
}

type 'a tas =  {mutable nb: int;  t: 'a array} ;;

let ajouter v f =
  f.nb <- f.nb + 1;
  let t = f.t in
  let n = f.nb in
  let i = ref (n - 1) in
  if !i >= Array.length t then failwith "file pleine" else
  while !i > 0 && t.((!i - 1) / 2) <= v do
    t.(!i) <- t.((!i - 1) / 2);
    i := (!i - 1) / 2
  done;
  t.(!i) <- v;;

let premier f = f.t(0);;

let new_tas n v = {nb = 0; t = Array.make n v} ;;

let supprimer f =
  if f.nb = 0 then failwith "file vide" else
  let t = f.t in
  let res = t.(0) in
  t.(0) <- t.(f.nb - 1); f.nb <- f.nb - 1;
  let v = t.(0) and i = ref 0 in
  begin try
      while 2 * !i + 1 < f.nb do
        let j = ref (2 * !i + 1) in
        if !j + 1 < f.nb && t.(!j + 1) > t.(!j) then incr j;
        if v >= t.(!j) then raise Exit;
        t.(!i) <- t.(!j);
        i := !j
      done
    with Exit -> () end;
  t.(!i) <- v;
  res;;

Théorème

1. Noter les répétitions et générer des escape-séquences avec le compte
   
   
2. Codes fixes ou de taille variable
3. Méthode Code Huffman
4. Méthodes adaptatives (Huffman dynamiques, Ziv Lempel)

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFACBABCBCCDCDDCCCDDDCDEDDCDDCDDCCCDDDCDDCDCCDDDCDDDDDCC\
CDCCCCBCCCCCDCCDDDDDDDDDDEEEDFFDEDFEFEFFDEFFEFFFFEEFFFFFFFFEFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBDCDDCCDDDDEDDDD\
DDDDDDEDDDEDEDEEDDDCDCDDCDDCDDDDDDDCDCDDDDDDDDCDCCCCCDDCDCDDDDD
DDDDDDEDDDDCDDDDDCDDCCBBCCCDCCCCCCDCCCCBBCACCBDCCCCEDDDDDEDCBCC\
BCCBBACBCBBCCCCCCBDDCCCCBBCBCCCBBCCDDDBDDACDBAABBADE9BDECADDCBCEF
DEEFDEFEEEFFEEEFEFEFEFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

• Code (préfixe) en taille variable. Chaque lettre est représentée par une suite de 0 et de 1, indiquant son chemin à partir de la racine dans l'arbre de Huffman.
  
  
• Deux passes. La première compte les occurrences de chaque lettre. La seconde construit l'arbre de Huffman, et traduit le texte.
  
  
• A chaque étape de la construction de l'arbre, on cherche les deux lettres les moins fréquentes parmi les 26 lettres de l'alphabet. Soient n₁ et n₂ leurs nombres d'occurences. On met ces deux lettres comme sous-arbres de gauche et de droite d'un nouveau caractère fictif dont le nombre d'occurence est n₁ + n₂. Et on recommence tant qu'il existe deux lettres différentes.
  
  
• Pour trouver rapidement les deux lettres les moins fréquentes, on gère une liste de priorité du nombre d'occurence des lettres (les 26 normales et les 26 autres fictives rajoutées par l'algorithme).

final static boolean GAUCHE = false, DROIT = true;
int[] occ = new int[256]        // nombre d'occurences
int[] pere = new int[256];      // indice du père
boolean[] sens = new int[256];  // fils gauche/droit
int[] code = new int[256];      // code de Huffman
int[] lcode = new int[256];     // longueur du code de Huffman

• L'encodeur et décodeur construisent dynamiquement les codes de Huffman en une seule passe. Ils suivent la même stratégie de construction de l'arbre de Huffman.
  
  
• Méthode FGK [Faller and Gallager 73; Knuth 85] Les noeuds de l'arbre de Huffman sont reliés par une liste triée en ordre croissant (au sens large) sur la valeur des noeuds, et telle que tout noeud (sauf la racine) est relié à son frère.
  
  
• Une feuille 0 représente tous les caractères non rencontrés. Lorsqu'un nouveau caractère est rencontré, on l'envoit et on remplace ce noeud par un nouveau noeud interne 1 dont les fils sont les feuilles 0 et 1 correspondant au nombre d'occurences du nouveau caractère. On va au cas suivant.
  
  
• Quand un caractère déja rencontré est à nouveau dans le fichier à coder. On échange sa position dans l'arbre de Huffman avec le plus loin dans la liste de même valeur. On augmente sa valeur de 1. Et on itère l'incrémentation sur son père.

• Codage de taille fixe par des triplets (a, l, c) où a est l'adresse dans la fenêtre, l la longueur, c caratère d'arrêt.
  
  
• example: alphabet {0, 1, 2}. La chaine
  
  
  001010210210212021021200...
  
  se code en (8,2,1), (7,3,2), (6,7,2), (2,8,0) soit en ternaire:
  
  
  22021 21102 20212 02220...
  
  avec un tampon de taille n=18 et la taille maximale des mots à coder L_s=9. La taille fixe de chaque mot de code est
  L_c = 1 + é log (n - L_s)ù + é log L_s ù
  
  
• On prend n º L_sa^{h L_s} où a est la cardinalité de l'alphabet, et 0 < h < 1.

• Au début on met n-L_s zéros devant la chaîne à coder.
  
  
• On cherche dans la partie droite la plus longue chaîne déjà rencontrée dans la fenêtre. On note son adresse a, sa longueur l et le caractère qui crée la différence c.
  
  
• On recentre la fenêtre sur le caractère c et on recommence à chercher une autre chaîne.

• Finir la recherche en table.
  
  
• Coder du texte avec des facteurs de répétitions.
  
  
• Faire des codes de Huffman statiques.
  
  
• Pour lire un fichier, utiliser la redirection de l'entrée standard, et on lit des lignes sur l'entrée standard. Pour rediriger l'entrée, on fait sous unix:
  % java Huffman < fichier_de_données
  
  De même pour créer un fichier, on peut rediriger la sortie standard et faire
  % java Huffman > fichier_résultat

This document was translated from L^AT_EX by H^EV^EA.