Ceci est la dernière séance de nos TP. Vous avez toujours des exercices qui n'ont pas été terminés. Je n'ai vi ni la compression Huffman, ni la césure des mots avec l'algorithme de Knuth/Liang. Je vous prie de travailler dessus ; dans ces circonstances je ne veux pas à ce que vous travaillez en TP sur votre devoir maison.
Uniquement pour la référence, et pour quelques uns vraiment très ambitieux, qui pourront résoudre l'exercice plus tard, je vous offre encore un exercice supplémentaire, mais j'insiste à ce que vous vous concentriez sur les précédants.
Lire l'article (Wikipédia et quelques tutoriels) sur les tableaux des suffixes (Suffix arrays). Un jour vous pourrez en avoir besoin.
Il existe une forte affinité conceptuelle entre cette technique de stockage des textes cherchés, et les tries. La recherche de toute sorte d'information séquentielle, par ex. textuelle, est accélérée, si on arrive a trier les séqences, ce qui facilite la recherche binaire, comme les mots dans un dictionnaire. Prenons un mot terminé par un symbole spécial, artificiel (ici : \$), par ex. "tarantella" → tarantella$.
Bien sûr, dans la réalité, c'est un texte considérablement plus long.
Construisons la liste de tous las suffixes du mot augmenté :
0 tarantella$ 1 arantella$ 2 rantella$ ... 8 la$ 9 a$ 10 $Ensuite trions cette liste lexicographiquement, ce qui donne, si on sauvegarde les indices d'origine : :
[('$', 10),
('a$', 9),
('antella$', 3),
('arantella$', 1),
('ella$', 6),
('la$', 8),
('lla$', 7),
('ntella$', 4),
('rantella$', 2),
('tarantella$', 0),
('tella$', 5)]
Les indices sont [10, 9, 3, 1, 6, 8, 7, 4, 2, 0, 5]. C'est le tableau de suffixes de notre mot. On n'a pas besoin de sauvegarder les textes eux-mêmes ! Ce sont des sous-chaînes de l'original, disponibles depuis la source. Donc, si la longueur du texte est 1000, on ne doit pas craindre que l'algorithme stockera un demi-million de caractères...
L'algorithme de recherche d'un pattern, par ex. "antel" dans le texte d'origine est binaire (dichotomique). On commence par le milieu, l'indice 5 du tableau, où on trouve "la$". Puisque "antel" le précède, on cherche à gauche entre les indices 0 et 4. Le milieu est 2, avec "antella$". Le mot a été trouvé ! L'indice dans l'original est 3, et c'est le résultat de la recherche.