"tableau des suffixes" et transformée de Burrows-Wheeler
Étudiant: BOGDAN Benjamin
Chercheur: TAVENAS Sébastien
Introduction
La recherche de paterne dans une chaîne de caractère est un problème récurrent qui peut rapidement poser problème lorsque la taille de la chaîne augmente.
Recherche dans une chaîne de caractères
Recherche naïve
L'algorithme naïf dans la recherche d'un paterne dans une chaîne de caractère consiste à regarder et à comparer successivement les lettres du paternes et de la chaîne. Si les caractères ne sont pas égaux, alors on avance d'un caractère dans la chaîne et on recommence jusqu'à la fin de la chaîne de caractère si on ne trouve pas le paterne.
L'avantage de cet algorithme est qu'il est facile à comprendre et à implémenter. Cependant il est très lent à l'exécution car il est de complexité quadratique, impliquant donc que cet algorithme n'est pas efficaces sur de très grandes chaînes.
Afin de palier à ce problème, il est possible de créer des structures de données complexes créée de façon à représenter tous les suffixes existant d'une chaîne de caractère de façon unique. Cette condition implique que tous les paternes existant dans une chaîne seront représentés, en effet chaque paterne de la chaîne est le préfixe d'au moins un suffixe.
Trie
Le Trie est un structure complexe permettant de représenter tous les suffixes d'une chaîne de caractère qui est simple.
On peut le représenter comme un arbre pour lequel chaque branche est une lettre. En partant de la racine et en allant jusqu'à n'importe quelle feuille de cet arbre, on obtient un suffixe de la chaîne d'origine.
La façon simple de le construire est d'ajouter successivement les suffixes de la chaîne dans le Trie.
Algorithme :
- On parcourt chaque lettre du suffixe.
- Si dans la position courante il existe un chemin qui a pour clef à cette lettre, on change la position courante en allant dans ce chemin.
- Sinon on créé un chemin qui a pour clef la lettre, puis on change la position courante en allant dans ce chemin.
- On retourne à la racine du Trie.
def tries(mot: str) -> dict:
"""Transforme une chaîne de caractère en tries"""
res = {}
for i in range(len(mot)):
actuel = res
for n in range(i, len(mot)):
actuel[mot[n]] = actuel.get(mot[n], {})
actuel = actuel[mot[n]]
return res
Afin de chercher un paterne dans la structure, il suffit de suivre le même principe que pour la création du Trie mise à part pour la création d'un chemin s'il n'existe pas et le retour à la racine (qui est inutile dans le cas présent).
On considère qu'un paterne est présent dans la structure (et donc dans la chaîne) si la suite de chemins demandée existe dans l'ordre.
On obtient donc l'algorithme suivant :
def est_dans_tries(tries: dict, mot: str) -> bool:
"""Renvoie si une chaîne de caractère est décomposée dans le tries"""
res = True
i = 0
actuel = tries
while i < len(mot) and res:
prochain = actuel.get(mot[i], None)
if prochain != None:
actuel = prochain
else:
res = False
i += 1
return res
L'avantage de cette structure complexe est qu'elle est simple à construire, à implémenter, à comprendre et que la recherche de paterne est rapide.
Cependant, celle-ci a un défaut : sa construction. En effet, bien que la recherche de paterne soit de complexité linéaire (O(m) avec m la longueur du paterne), la construction du Trie est, quant à elle, de complexité quadratique impliquant à nouveau que lorsqu'une chaîne de caractère est très grande, il faille du temps afin d'effectuer la recherche dans la chaîne. De plus, la structure prend beaucoup de place : il est fréquent de voir des branches avec un seul enfant qui pourraient pourtant être regroupés mais qui ne le sont pas.
Arbre de suffixe
L'arbre de suffixes est un structure proche du Trie mais qui règle le problème de la taille de la structure.
Pour réduire la taille du Tries, il faut considérer chaque lettre par son plus petit indice dans la chaîne de caractère en avançant à chaque fois l'indice.
Donc en reprenant le Trie de "abracadabradad" et en transformant chaque lettre par son plus petit indice dans la chaîne ansi que le nombre de lettre parcouru à cet endroit (soit toujours 1 actuellement), on obtient l'arbre suivant : TRIE MAIS AVEC INDICES ET LONGUEURS
Ensuite, on vérifie pour chaque branche le nombre de sous-branches. S'il n'y a pas de sous-branche, on ne fait rien car c'est une feuille. Si une branche n'a qu'une sous branche, on les combine en précisant d'où l'on part (indice de la branche) et le nombre de lettres contenues dans cette nouvelle branche.
En suivant de principe, on obtient l'arbre suivant pour la chaîne "abracadabradad" : TREE
On peut constater que l'arbre est plus petit que le Trie, mais que cependant il est plus compliqué à comprendre. De plus, pour le construire, on utilise le Trie ce qui implique que la construction de la structure est d'une complexité au moins quadratique, ce qui ne nous convient pas.
Il faut donc trouver un moyen de construire l'arbre de suffixes sans utiliser le Trie afin de réduire le temps de construction.
Pour cela, on peut se pencher sur l'algorithme de Ukkonen. Celui-ci consiste à ajouter chaque lettre dans la structure une à une au lieu d'ajouter un suffixe complet d'un coup. Ceci permet de créer tous les suffixes existant de la chaîne dans un arbre de suffixes, et ce de façon linéaire.
L'algorithme de Ukkonen est le suivant:
- À chaque feuille de l'arbre on ajoute la lettre actuelle
- À la racine :
- Si la lettre est la première lettre d'une des branches, on notifie que la branche peut être scindée
- Si la lettre n'est la première lettre d'aucune des branches, crée une nouvelle branche avec cette lettre