"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 :

1. 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.

2. 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.