"tableau des suffixes" et transformée de Burrows-Wheeler

Étudiant : BOGDAN Benjamin

Tuteur : TAVENAS Sébastien

Introduction

La recherche de patern dans une chaîne de caractères est un problème récurrent qui peut rapidement poser problème lorsque l'on cherche plusieurs fois dans une chaîne de caractères de grande taille.

Un patern est aussi une chaîne de caractères.

Recherche dans une chaîne de caractères

Recherche naïve

L'algorithme naïf pour rechercher une chaîne de caractères dans une autre consiste à regarder dans l'ordre la chaîne de caractères dans laquelle on cherche la sous-chaîne et de vérifier si les caractères correspondent ou non.

Nous pouvons l'implémenter comme suivant en Python :

def est_dans(sous_chaine: str, chaine: str) -> bool:
    """Renvoie si la sous chaîne est dans la chaîne"""
    dedans = False
    i = 0
    while i < len(chaine) and not dedans:
        offset = 0
        stop = False
        while i + offset < len(chaine) and offset < len(sous_chaine) and not stop:
            if sous_chaine[offset] != chaine[i+offset]:
                stop = True
            offset += 1
        if not stop:
            dedans = True
        i += 1
    return dedans

L'avantage de cet algorithme est qu'il est facile à comprendre et à implémenter. Cependant, bien qu'il puisse être optimisé et évitant certaines comparaisons, il est très lent à l'exécution car il est de complexité quadratique, impliquant donc qu'il n'est pas efficace sur de très grandes chaînes.

Afin de palier à ce problème, il est possible de créer des structures de données différentes qui ont pour but de représenter tous les suffixes existant d'une chaîne de caractère et qui permet de les identifier de manière unique. Ces conditions impliquent que toutes les sous-chaînes de la chaîne décomposée seront représenté à l'intérieur de la structure et seront plus facilement extrayables.

Pour effectuer la recherche du patern dans notre chaîne de caractère grâce aux différentes structures, il faut partir du principe que chaque sous-chaîne dans la chaîne d'origine est toujours préfixe d'un suffixe.

Trie (Arbre de préfixes)

Trie de "abracadabradad"

Le Trie est un structure permettant de représenter tous les suffixes d'une chaîne de caractères sous la forme d'un arbre. Chaque chemin allant de la racine de l'arbre à une de ses feuilles représente un suffixe différent. Chaque branche de l'arbre est une lettre et mène soit à une feuille soit à un sous Trie qui permet la représentation de la suite du suffixe.

Il est possible de créer le Trie en ajoutant successivement chaque suffixe de la chaîne de caractère à la racine de l'arbre en respectant les règles suivantes :

• Si une branche de l'arbre correspond à la première lettre du suffixe à ajouter, il faut ajouter la suite du suffixe dans le sous-arbre de cette branche
• Sinon créer une branche correspondant à la première lettre du suffixe à ajouter et ajouter la suite du suffixe dans le sous-arbre de cette nouvelle branche

Cela nous donne le code python suivant :

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

La recherche dans le Trie consiste à regarder s'il existe un chemin pour lequel chaque valeur des branches dans l'ordre correspond à chaque lettre du patern recherché.

On suit donc les règles suivantes:

• Si une branche du Trie correspond à la première lettre du patern, chercher le patern dans le sous-Trie correspondant de la branche
• Sinon, le patern n'est pas dans la chaîne

Cet algorithme donne le code Python 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

Cette structure présente plusieurs avantages :

• Facile à comprendre (construction et recherche)
• Facile à implémenter
• Recherche en $O(m)$ ($m$: la longueur de la chaîne recherchée)

Cependant elle présente aussi plusieurs désavantages :

• Construction en $O(n^{2})$ ($n$: la longueur de la chaîne qui génère l'arbre)
• Complexité spatiale en $O(n^{2})$ ($n$: la longueur de la chaîne qui génère l'arbre)

Arbre de suffixes

Arbre de suffixes de "abracadabradad" avec longueurs

Arbre de suffixes de "abracadabradad" pour lecture

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 Trie, il faut réduire les chemins uniques (ceux pour lesquels les noeuds successifs n'ont qu'un unique enfant) en les rassemblant en un unique noeud (dans "panpan", on regrouperait, entre autres, "pan", "an" et "npan"). Cependant, la même quantité d'information est toujours stockée mais d'une façon différente. Pour résoudre ce problème, il faut faut considérer chaque noeud comme une information de 2 nombres sur la chaîne d'origine : l'indice de début de la sous-chaîne et la longueur ou l'indice de fin de celle-ci. L'indice de début doit toujours être supérieur à l'indice auquel se fini la sous-chaîne représenté sur la branche parente (à la racine, c'est l'indice 0) et il doit être le plus petit possible en même temps.

Il est aussi possible de générer cette arbre d'autre manière telle que la suivante en Python qui utilise en clef l'indice du début du suffixe et sa taille :

def convertion_tree(mot: str) -> tuple:
    """Transforme une chaîne de caractères en arbre de suffixe"""
    arbre = {}
    for i in range(len(mot)):
        ajouter_tree(arbre, mot, i)
    return (mot, arbre)

def ajouter_tree(branche: dict, mot: str, offset: int):
    """Ajouter une chaîne de caractères dans un arbre"""
    keys = list(branche.keys())
    nb_total_keys = len(keys)
    nb_key = 0
    est_dedans = mot[offset:] == ""
    longueur_mot_a_placer = len(mot) - offset

    while nb_key < nb_total_keys and not est_dedans:
        key = keys[nb_key]

        if mot[key[0]] == mot[offset]:
            nb_egaux = 1
            stop = False
            while nb_egaux < min(key[1], longueur_mot_a_placer) and not stop:
                if mot[key[0] + nb_egaux] != mot[offset + nb_egaux]:
                    stop = True
                else:
                    nb_egaux += 1
            
            if nb_egaux != longueur_mot_a_placer:
                if nb_egaux == key[1]:
                    ajouter_tree(branche[key], mot, offset + nb_egaux)
                else:
                    branche[(key[0], nb_egaux)] = {
                        (key[0] + nb_egaux, key[1] - nb_egaux): branche[key],
                        (offset + nb_egaux, longueur_mot_a_placer - nb_egaux): {}
                    }
                    branche.pop(key)
            est_dedans = True

        nb_key += 1
    
    if not est_dedans:
        branche[(offset, len(mot) - offset)] = {}

L'arbre de suffixes, tout comme le Trie, créé des chemins uniques pour chaque suffixe de la chaîne d'origine. En utilisant ce principe, il est possible d'effectuer une recherche dans la structure en suivant les règles suivantes :

• S'il existe une branche dont la lettre à l'indice du début du suffixe dans la chaîne d'origine correspond à la première lettre du patern :
  • Si le patern est inclus dans la sous-chaîne, le patern est dans la chaîne d'origine
  • Si la sous chaîne est incluse dans le patern, cherche la suite du patern dans le sous-arbre correspondant à la branche
  • Sinon, le patern n'est pas dans la chaîne d'origine
• Sinon, le patern n'est pas dans la chaîne d'origine

Ce qui nous donne le code Python suivant :

def est_dans_tree(arbre: tuple, mot: str) -> bool:
    """Renvoie si la chaîne de caractères est contenue dans l'arbre"""
    return est_dans_branche(arbre[1], arbre[0], mot)

def est_dans_branche(branche: dict, mot_origine: str, mot: str) -> bool:
    """Renvoie si la chaîne de caractères est contenue dans la branche"""
    est_dedans = mot == ""
    fin = False
    keys = list(branche.keys())
    nb_key = 0
    longueur_mot = len(mot)
    while nb_key < len(keys) and not fin and not est_dedans:
        key = keys[nb_key]
        if mot_origine[key[0]] == mot[0]:
            if key[1] == longueur_mot:
                est_dedans = mot_origine[key[0] : key[0] + key[1]] == mot
            elif longueur_mot < key[1]:
                est_dedans = mot_origine[key[0] : key[0] + longueur_mot] == mot
            else:
                est_dedans = est_dans_branche(branche[key], mot_origine, mot[key[1]:])
            fin = True
        nb_key += 1
    return est_dedans

L'arbre de suffixes présente plusieurs avantages :

• Il a une taille réduite ($O(n)$ avec $n$ la taille de la chaîne d'origine
• Simple à comprendre
• Recherche rapide ($O(m)$ avec $m$ la taille du patern)
• Peut être construit grâce au Trie

Mais celui-ci présente aussi des désavantages :

• Plus complexe à implémenter
• Sa taille reste grande : la structure est lourde, surtout pour de grandes chaînes de caractères

Il est aussi possible de construire l'arbre de suffixes de manière plus efficace (construction en $O(n)$ au lieu de $O(n^{2})$ avec $n$ la taille de la chaîne de caractères d'origine) en utilisant par exemple l'algorithme de Ukkonen.

Tableau de suffixes

Tableau de suffixes de "bananas$"

Le tableau de suffixes est une structure légère qui représente indirectement tous les suffixes d'une chaîne de caractères.

Il stocke chaque indice de début de suffixe dans l'ordre alphabétique des suffixes.

Ainsi, pour le créer, il suffit de créer un tableau contenant tous les indices de la chaîne d'origine et de trier la liste suivant les suffixes commençant aux l'indices.

Afin de rechercher dans le tableau de suffixes, il suffit d'utiliser la recherche dichotomique, ce qui donne le code Python suivant :

def est_dans_suffix_array(suffix_array: tuple, mot: str) -> bool:
    res = False
    mot_origine = suffix_array[0]
    array = suffix_array[1]
    longueur_mot_origine = len(mot_origine)
    longueur_mot = len(mot)
    debut = 0
    fin = len(array) - 1
    while debut <= fin and not res:
        mil = (debut + fin) // 2
        val_mil = array[mil]
        sous_mot = mot_origine[val_mil: min(val_mil + longueur_mot, longueur_mot_origine)]
        if mot == sous_mot:
            res = True
        elif mot < sous_mot:
            fin = mil - 1
        else:
            debut = mil + 1
    return res

Le tableau de suffixes présente comme avantages : sa taille ($O(n)$ avec $n$ la taille de la chaîne d'origine), sa rapidité de construction ($nlog(n)$ avec $n$ la taille de la chaîne d'origine) et sa rapidité de recherche ($mlog(n)$ avec $m$ la taille du patern et $n$ la taille de la chaîne d'origine.

Cependant bien que la recherche est plus longue dans de très longues chaînes de caractères avec le tableau de suffixe qu'avec le Trie ou l'arbre de suffixe, la taille de la structure est un aspect non-négligeable pour la recherche de patern.

Transformée de Burrows-Wheeler

Transformée de Burrows-Wheeler de "bananas$"

La transformée de Burrows-Wheeler permet de transformer une chaîne de caractère en une autre ayant pour propriété que les caractères semblables éloignés dans la chaîne d'origine se retrouvent plus fréquemment collés (par exemple, la transformée de Burrows-Wheeler de "bananas$" est "sbnn$aaa"). Cette propriété permet de faciliter la compression de la chaîne grâce aux répétitions de caractères.

Pour faire la transformée d'une chaîne, il faut prendre chaque suffixe de la chaîne d'origine, recommencer à la fin de ceux-ci la chaîne jusqu'à ce qu'il y ait le même nombre de caractère dans la chaîne d'origine et dans celle-ci, trier les chaînes dans l'ordre alphabétique, récupérer la dernière lettre de chaque chaîne dans l'ordre.

Le code Python suivant permet de générer la transformée de Burrows-Wheeler :

EOS = chr(28)
def convertion_bw(mot: str) -> str:
    mot = mot + EOS
    taille_mot = len(mot)
    tab = [mot[i:] + mot[:i] for i in range(taille_mot)]
    tab.sort()
    return "".join([ligne[taille_mot - 1] for ligne in tab])

La transformée est réversible en connaissant le dernier caractère de la chaîne d'origine. Le code Python suivant permet de retrouver la chaîne d'origine à partir de la transformée :

def deconvertion_bw(bw: str) -> str:
    chaine_triee = list(enumerate(list(bw)))
    chaine_triee.sort(key=lambda e: e[1]) 
    indice = bw.find(EOS)
    mot = ""
    i = 0
    for j in range(len(bw)):
        caractere = chaine_triee[indice][1]
        mot += caractere
        i += 1
        indice = chaine_triee[indice][0]
    return mot

Il est donc possible de transformer une chaîne de caractères en une autre qui peut être facilement compressée et de faire le chemin inverse.

Passage entre tableau de suffixes et transformée de Burrows-Wheeler

Il est possible de passer du tableau de suffixes à la transformée de Burrows-Wheeler et inversement car les deux commencent de la même manière : prendre les suffixes d'une chaîne et les trier dans l'ordre alphabétique. Le tableau de suffixes stocke ensuite l'information sous la forme d'un tableau d'indices tandis que la transformée de Burrows-Wheeler sous la forme d'une chaîne de caractère.

La passage de tableau de suffixes à transformée de Burrows-Wheeler est simple. Il suffit de prendre la lettre à l'indice précédant le début du suffixe dans l'ordre du tableau de suffixe (si l'indice du suffixe est 0, alors il faut prendre la dernière lettre de la chaîne).

def sa_en_bw(suffix_array: tuple) -> str:
    """Transforme le suffix array en transformé de Burrows Wheeler"""
    mot = suffix_array[0]
    array = suffix_array[1]
    taille_mot = len(mot)
    return "".join([mot[(i-1) % taille_mot] for i in array])

Le passage de la transformée au tableau de suffixes se fait via le code suivant en Python :

def bw_en_sa(bw: str) -> tuple:
    """Transforme le transformé de Burrows Wheeler en suffix array"""
    taille = len(bw)
    chaine_triee = list(enumerate(list(bw)))
    chaine_triee.sort(key=lambda e: e[1])
    indice = bw.find(EOS)
    mot = ""
    sa = [0 for j in range(taille)]
    i = 0
    for j in range(taille):
        caractere = chaine_triee[indice][1]
        mot += caractere
        sa[indice] = i
        i += 1
        indice = chaine_triee[indice][0]
    return (mot, sa)

On a donc la possibilité de transformer une chaîne de caractère afin de faire qu'elle prenne moins de place et avec la chaîne transformée, générer une structure permettant de faire efficacement une recherche de patern dans une chaîne de caractère.