Algorithmique des textes

On précalcule, pour chaque lettre $c$ de l'alphabet, sa dernière position dans le motif — ou $-1$ si elle n'y figure pas. En cas d'échec en position $j$ du motif sur la lettre $c$ du texte, on décale de $j-\text{derniere}[c]$, en s'assurant d'avancer d'au moins un cran.

#define ALPHABET 256

/* Affiche les positions où p apparaît dans t (Boyer-Moore, mauvais caractère).
   Préconditions : n >= m >= 1. */
void boyer_moore(const char t[], int n, const char p[], int m) {
    int derniere[ALPHABET];
    for (int c = 0; c < ALPHABET; c = c + 1) { derniere[c] = -1; }
    for (int j = 0; j < m; j = j + 1) { derniere[(unsigned char) p[j]] = j; }

    int i = 0;
    while (i + m <= n) {
        int j = m - 1;
        while (j >= 0 && p[j] == t[i + j]) { j = j - 1; }   /* de DROITE à gauche */
        if (j < 0) {
            printf("%d ", i);
            i = i + 1;
        } else {
            int saut = j - derniere[(unsigned char) t[i + j]];
            i = i + (saut > 1 ? saut : 1);      /* JAMAIS moins d'un cran */
        }
    }
}

Pour un seul motif, Boyer-Moore est généralement plus rapide. Mais Rabin-Karp cherche $k$ motifs de même longueur pour presque le même prix : on range leurs $k$ empreintes dans une table de hachage, et chaque fenêtre du texte se teste en $O(1)$. C'est ainsi que fonctionnent les détecteurs de plagiat et les antivirus par signatures.

On descend dans l'arbre au rythme des bits — $0$ à gauche, $1$ à droite — et l'on émet un caractère chaque fois qu'on atteint une feuille, en repartant de la racine.

(* Décode la suite de bits selon l'arbre de Huffman a.
   Précondition : bits est le codage d'un texte par CE MÊME arbre. *)
let decoder a bits =
  let sortie = Buffer.create 256 in
  let rec descendre n = function
    | [] -> ()
    | b :: reste ->
        match n with
        | Feuille (c, _) -> Buffer.add_char sortie c; descendre a (b :: reste)
        | Interne (g, d, _) -> descendre (if b = 0 then g else d) reste
  in
  descendre a bits;
  (match a with Feuille (c, _) -> Buffer.add_char sortie c | _ -> ());
  Buffer.contents sortie

Pourquoi cela marche sans ambiguïté : parce que le code est préfixe. Aucun mot de code n'étant préfixe d'un autre, atteindre une feuille signifie que le caractère est complet — il n'y a jamais à hésiter, ni à revenir en arrière. C'est toute la raison d'être de la structure d'arbre.

Le dictionnaire contient au départ les caractères seuls, numérotés. Puis :

• lire la plus longue séquence $S$ déjà présente dans le dictionnaire ;
• émettre son numéro ;
• ajouter au dictionnaire $S$ suivi du caractère suivant ;
• reprendre à ce caractère.

Le décodeur reconstruit le dictionnaire en appliquant la même règle avec un temps de retard : à la réception du code $k$, il émet la séquence associée, puis ajoute au dictionnaire la séquence précédente suivie du premier caractère de la nouvelle.

Le cas particulier, celui qui fait échouer les mises en œuvre naïves : il arrive que le code reçu ne soit pas encore dans le dictionnaire du décodeur — car le compresseur vient tout juste de l'y ajouter. Cela se produit exactement quand la séquence est de la forme $S+\text{premier}(S)$. Le décodeur la reconstitue alors lui-même :

let sequence =
  match Hashtbl.find_opt dico code with
  | Some s -> s
  | None -> precedente ^ String.make 1 precedente.[0]   (* LE CAS QUI PIÈGE *)

Dans l'exemple ci-dessus, le code $5$ est émis alors que le décodeur n'a encore que $1$ à $4$ : il doit deviner ABA en recollant AB et son premier caractère. C'est une reconstitution, pas une convention arbitraire — et elle est toujours correcte, parce que le compresseur ne peut émettre un code neuf que dans cette configuration précise.