Wiki du LAMA (UMR 5127) - Contributions [fr]

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

2025-05-16T14:58:04Z

Bogdan : /* Tableau de suffixes */

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

<pre>
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
</pre>

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) ===

[[Fichier:Visi_201_trie_abracadabradad.png|200px|thumb|right|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 :

<pre>
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
</pre>

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 :

<pre>
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
</pre>

Cette structure présente plusieurs avantages :
* Facile à comprendre (construction et recherche)
* Facile à implémenter
* Recherche en <math>O(m)</math> (<math>m</math>: la longueur de la chaîne recherchée)

Cependant elle présente aussi plusieurs désavantages :
* Construction en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)
* Complexité spatiale en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)

=== Arbre de suffixes ===

[[Fichier:Visi_201_suffix_tree_abracadabradad_imp.png|400px|thumb|right|Arbre de suffixes de "abracadabradad" avec longueurs]]
[[Fichier:Visi_201_suffix_tree_abracadabradad.png|400px|thumb|right|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 :
<pre>
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)] = {}
</pre>

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 :
<pre>
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
</pre>

L'arbre de suffixes présente plusieurs avantages :
* Il a une taille réduite (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine
* Simple à comprendre
* Recherche rapide (<math>O(m)</math> avec <math>m</math> 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 <math>O(n)</math> au lieu de <math>O(n^2)</math> avec <math>n</math> la taille de la chaîne de caractères d'origine) en utilisant par exemple l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen].

=== Tableau de suffixes ===

[[Fichier:Visi_201_suffix_array_bananas.png||thumb|right|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 :
<pre>
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
</pre>

Le tableau de suffixes présente comme avantages : sa taille (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine) et sa rapidité de recherche (<math>mlog(n)</math> avec <math>m</math> la taille du patern et <math>n</math> la taille de la chaîne d'origine.
La ta construction du tableau de suffixes peut cependant être longue lorsque la chaîne est très répétitive (exemple : que des "a") ce qui augment fortement la complexité (<math>O(n^2)</math> avec <math>n</math> la taille de la chaîne d'origine).

Cependant bien que la construction et la recherche soient plus longues 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 ==

[[Fichier:Visi_201_transformee_bw_bananas.png||thumb|right|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 :
<pre>
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])
</pre>

La transformée est réversible en connaissant le dernier caractère de la chaîne d'origine.

Pour se faire, il faut suivre l'algorithme suivant :
<pre>
bw <- transformée de Burrows-Wheeler
triee <- bw trié dans l'ordre alphabétique
i <- indice du caractère de fin de chaîne dans la transformée
mot_origine <- ""

Tant triee[i] différent de caractère de fin de chaîne
mot_origine <- mot_origine + triee[i]
i <- indice de la lettre dans la transformée de Burrows-Wheeler (si 2eme "a" dans triee, alors prendre l'indice du 2eme "a" dans bw)
</pre>

Cet algorithme ne garde pas le cactère de fin de chaîne

Le code Python suivant permet de retrouver la chaîne d'origine à partir de la transformée (garde le caractère de fin de chaîne) :
<pre>
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
</pre>

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).
<pre>
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])
</pre>

Pour retrouver le tableau de suffixes à l'aide de la transformée de Burrows-Wheeler, il suffit d'appliquer l'algorithme suivant :
<pre>
sa <- tableau de la taille de la transformée - 1
bw <- transformée de Burrows-Wheeler
triee <- bw trié dans l'ordre alphabétique
i <- indice du caractère de fin de chaîne dans la transformée
mot_origine <- ""
j <- 0

Tant triee[i] différent de caractère de fin de chaîne
mot_origine <- mot_origine + triee[i]
sa[i] = j
i <- indice de la lettre dans la transformée de Burrows-Wheeler (si 2eme "a" dans triee, alors prendre l'indice du 2eme "a" dans bw)
j <- j + 1
</pre>

Cet algorithme ne garde pas le caractère de fin de chaîne.

Le passage de la transformée au tableau de suffixes se fait via le code suivant en Python (en gardant le caractère de fin de chaîne) :
<pre>
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)
</pre>

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.

== Comparaison ==

[[Fichier:Visi_201_temps_constructions_structures.png|500px|center|thumb|Graphique du temps de génération des structures en fonction de la taille de la chaîne transformée]]

Le graphique ci-dessus nous montre que poure des chaînes de caractères très grandes, il n'est pas avisé d'utiliser un Trie pour la recherche de patern, ni même un arbre de suffixes utilisant le Trie pour se générer. Le choix repose donc entre l'arbre de suffixe (générer sans Trie) et le tableau de suffixe, cependant nous pouvons voir sur le graphique que la tableau de suffixes tend à être plus efficace et rapide à construire que l'arbre de suffixes lorsque la chaîne de caractère est grandissante. Il peut donc être justicieux d'utiliser l'arbre de suffixes plutôt que le tableau de suffixes pour sa rapidité de construction et son stockage plus efficace bien qu'il soit un peu moins efficace pour rechercher un patern.

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

2025-05-15T21:30:13Z

Bogdan :

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

<pre>
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
</pre>

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) ===

[[Fichier:Visi_201_trie_abracadabradad.png|200px|thumb|right|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 :

<pre>
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
</pre>

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 :

<pre>
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
</pre>

Cette structure présente plusieurs avantages :
* Facile à comprendre (construction et recherche)
* Facile à implémenter
* Recherche en <math>O(m)</math> (<math>m</math>: la longueur de la chaîne recherchée)

Cependant elle présente aussi plusieurs désavantages :
* Construction en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)
* Complexité spatiale en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)

=== Arbre de suffixes ===

[[Fichier:Visi_201_suffix_tree_abracadabradad_imp.png|400px|thumb|right|Arbre de suffixes de "abracadabradad" avec longueurs]]
[[Fichier:Visi_201_suffix_tree_abracadabradad.png|400px|thumb|right|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 :
<pre>
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)] = {}
</pre>

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 :
<pre>
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
</pre>

L'arbre de suffixes présente plusieurs avantages :
* Il a une taille réduite (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine
* Simple à comprendre
* Recherche rapide (<math>O(m)</math> avec <math>m</math> 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 <math>O(n)</math> au lieu de <math>O(n^2)</math> avec <math>n</math> la taille de la chaîne de caractères d'origine) en utilisant par exemple l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen].

=== Tableau de suffixes ===

[[Fichier:Visi_201_suffix_array_bananas.png||thumb|right|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 :
<pre>
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
</pre>

Le tableau de suffixes présente comme avantages : sa taille (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine), sa rapidité de construction (<math>nlog(n)</math> avec <math>n</math> la taille de la chaîne d'origine) et sa rapidité de recherche (<math>mlog(n)</math> avec <math>m</math> la taille du patern et <math>n</math> 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 ==

[[Fichier:Visi_201_transformee_bw_bananas.png||thumb|right|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 :
<pre>
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])
</pre>

La transformée est réversible en connaissant le dernier caractère de la chaîne d'origine.

Pour se faire, il faut suivre l'algorithme suivant :
<pre>
bw <- transformée de Burrows-Wheeler
triee <- bw trié dans l'ordre alphabétique
i <- indice du caractère de fin de chaîne dans la transformée
mot_origine <- ""

Tant triee[i] différent de caractère de fin de chaîne
mot_origine <- mot_origine + triee[i]
i <- indice de la lettre dans la transformée de Burrows-Wheeler (si 2eme "a" dans triee, alors prendre l'indice du 2eme "a" dans bw)
</pre>

Cet algorithme ne garde pas le cactère de fin de chaîne

Le code Python suivant permet de retrouver la chaîne d'origine à partir de la transformée (garde le caractère de fin de chaîne) :
<pre>
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
</pre>

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).
<pre>
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])
</pre>

Pour retrouver le tableau de suffixes à l'aide de la transformée de Burrows-Wheeler, il suffit d'appliquer l'algorithme suivant :
<pre>
sa <- tableau de la taille de la transformée - 1
bw <- transformée de Burrows-Wheeler
triee <- bw trié dans l'ordre alphabétique
i <- indice du caractère de fin de chaîne dans la transformée
mot_origine <- ""
j <- 0

Tant triee[i] différent de caractère de fin de chaîne
mot_origine <- mot_origine + triee[i]
sa[i] = j
i <- indice de la lettre dans la transformée de Burrows-Wheeler (si 2eme "a" dans triee, alors prendre l'indice du 2eme "a" dans bw)
j <- j + 1
</pre>

Cet algorithme ne garde pas le caractère de fin de chaîne.

Le passage de la transformée au tableau de suffixes se fait via le code suivant en Python (en gardant le caractère de fin de chaîne) :
<pre>
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)
</pre>

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.

== Comparaison ==

[[Fichier:Visi_201_temps_constructions_structures.png|500px|center|thumb|Graphique du temps de génération des structures en fonction de la taille de la chaîne transformée]]

Le graphique ci-dessus nous montre que poure des chaînes de caractères très grandes, il n'est pas avisé d'utiliser un Trie pour la recherche de patern, ni même un arbre de suffixes utilisant le Trie pour se générer. Le choix repose donc entre l'arbre de suffixe (générer sans Trie) et le tableau de suffixe, cependant nous pouvons voir sur le graphique que la tableau de suffixes tend à être plus efficace et rapide à construire que l'arbre de suffixes lorsque la chaîne de caractère est grandissante. Il peut donc être justicieux d'utiliser l'arbre de suffixes plutôt que le tableau de suffixes pour sa rapidité de construction et son stockage plus efficace bien qu'il soit un peu moins efficace pour rechercher un patern.

Fichier:Visi 201 temps constructions structures.png

2025-05-15T21:02:32Z

Bogdan :

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

2025-05-15T14:23:54Z

Bogdan : /* Passage entre tableau de 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 :

<pre>
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
</pre>

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) ===

[[Fichier:Visi_201_trie_abracadabradad.png|200px|thumb|right|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 :

<pre>
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
</pre>

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 :

<pre>
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
</pre>

Cette structure présente plusieurs avantages :
* Facile à comprendre (construction et recherche)
* Facile à implémenter
* Recherche en <math>O(m)</math> (<math>m</math>: la longueur de la chaîne recherchée)

Cependant elle présente aussi plusieurs désavantages :
* Construction en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)
* Complexité spatiale en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)

=== Arbre de suffixes ===

[[Fichier:Visi_201_suffix_tree_abracadabradad_imp.png|400px|thumb|right|Arbre de suffixes de "abracadabradad" avec longueurs]]
[[Fichier:Visi_201_suffix_tree_abracadabradad.png|400px|thumb|right|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 :
<pre>
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)] = {}
</pre>

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 :
<pre>
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
</pre>

L'arbre de suffixes présente plusieurs avantages :
* Il a une taille réduite (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine
* Simple à comprendre
* Recherche rapide (<math>O(m)</math> avec <math>m</math> 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 <math>O(n)</math> au lieu de <math>O(n^2)</math> avec <math>n</math> la taille de la chaîne de caractères d'origine) en utilisant par exemple l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen].

=== Tableau de suffixes ===

[[Fichier:Visi_201_suffix_array_bananas.png||thumb|right|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 :
<pre>
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
</pre>

Le tableau de suffixes présente comme avantages : sa taille (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine), sa rapidité de construction (<math>nlog(n)</math> avec <math>n</math> la taille de la chaîne d'origine) et sa rapidité de recherche (<math>mlog(n)</math> avec <math>m</math> la taille du patern et <math>n</math> 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 ==

[[Fichier:Visi_201_transformee_bw_bananas.png||thumb|right|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 :
<pre>
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])
</pre>

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 :
<pre>
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
</pre>

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).
<pre>
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])
</pre>

Le passage de la transformée au tableau de suffixes se fait via le code suivant en Python :
<pre>
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)
</pre>

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.

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

2025-05-15T14:11:06Z

Bogdan : /* 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 :

<pre>
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
</pre>

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) ===

[[Fichier:Visi_201_trie_abracadabradad.png|200px|thumb|right|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 :

<pre>
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
</pre>

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 :

<pre>
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
</pre>

Cette structure présente plusieurs avantages :
* Facile à comprendre (construction et recherche)
* Facile à implémenter
* Recherche en <math>O(m)</math> (<math>m</math>: la longueur de la chaîne recherchée)

Cependant elle présente aussi plusieurs désavantages :
* Construction en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)
* Complexité spatiale en <math>O(n^2)</math> (<math>n</math>: la longueur de la chaîne qui génère l'arbre)

=== Arbre de suffixes ===

[[Fichier:Visi_201_suffix_tree_abracadabradad_imp.png|400px|thumb|right|Arbre de suffixes de "abracadabradad" avec longueurs]]
[[Fichier:Visi_201_suffix_tree_abracadabradad.png|400px|thumb|right|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 :
<pre>
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)] = {}
</pre>

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 :
<pre>
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
</pre>

L'arbre de suffixes présente plusieurs avantages :
* Il a une taille réduite (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine
* Simple à comprendre
* Recherche rapide (<math>O(m)</math> avec <math>m</math> 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 <math>O(n)</math> au lieu de <math>O(n^2)</math> avec <math>n</math> la taille de la chaîne de caractères d'origine) en utilisant par exemple l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen].

=== Tableau de suffixes ===

[[Fichier:Visi_201_suffix_array_bananas.png||thumb|right|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 :
<pre>
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
</pre>

Le tableau de suffixes présente comme avantages : sa taille (<math>O(n)</math> avec <math>n</math> la taille de la chaîne d'origine), sa rapidité de construction (<math>nlog(n)</math> avec <math>n</math> la taille de la chaîne d'origine) et sa rapidité de recherche (<math>mlog(n)</math> avec <math>m</math> la taille du patern et <math>n</math> 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 ==

[[Fichier:Visi_201_transformee_bw_bananas.png||thumb|right|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 :
<pre>
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])
</pre>

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 :
<pre>
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
</pre>

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 ==

Fichier:Visi 201 transformee bw bananas.png

2025-05-15T13:42:25Z

Bogdan : transformée de Burrows-Wheeler de "bananas$"

== Description ==
transformée de Burrows-Wheeler de "bananas$"

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

2025-05-15T13:34:57Z

Bogdan : /* Tableau de suffixes */

Fichier:Visi 201 suffix array bananas.png

2025-05-15T13:08:19Z

Bogdan : Tableau de suffixes de bananas

== Description ==
Tableau de suffixes de bananas

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

2025-05-15T12:37:41Z

Bogdan : /* Trie (Arbre de préfixes) */

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

2025-05-15T12:29:18Z

Bogdan : /* Arbre de suffixes */

Fichier:Visi 201 suffix tree abracadabradad imp.png

2025-05-15T09:59:38Z

Bogdan : Arbre de suffixes de "abracadabradad" avec les nombres

== Description ==
Arbre de suffixes de "abracadabradad" avec les nombres

Fichier:Visi 201 suffix tree abracadabradad.png

2025-05-15T09:42:11Z

Bogdan : Arbre de suffixes de "abracadabradad" avec les lettres

== Description ==
Arbre de suffixes de "abracadabradad" avec les lettres

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

2025-05-15T09:29:54Z

Bogdan : Réécriture introduction, recherche naïve, trie

Fichier:Visi 201 trie abracadabradad.png

2025-05-15T08:37:15Z

Bogdan : Trie (Arbre de Préfixes) de "abracadabradad"

== Description ==
Trie (Arbre de Préfixes) de "abracadabradad"

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

2025-05-05T20:45:51Z

Bogdan : /* Tableau de suffixes */

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

<pre>
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
</pre>

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 :
<pre>
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
</pre>

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 suffixes ===

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 ainsi que le nombre de lettre parcourue à 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 ou l'indice de fin de cette nouvelle branche. L'utilisation de l'indice de fin de la branche ou du nombre de lettres dans la branche est un choix qui doit être le même dans toutes les branches de l'arbre.

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 règle pas le problème de la construction longue lorsque les chaînes de caractère sont grandes. Il est cependant possible de régler ce problème en construisant l'arbre grâce à l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen], qui permet de construire l'arbre de suffixes avec une complexité linéaire.

Afin de rechercher dans l'arbre de suffixes la présence d'un paterne, il suffit de suivre le même algorithme que celui du Trie en remplaçant chaque indice par sa lettre à la position de l'indice dans le mot ainsi que de prendre en compte que la branche n'est pas forcément de longueur 1, mais peut être plus longue.

=== Tableau de suffixes ===

La tableau de suffixes est une structure prenant encore moins de place que l'arbre de suffixes et qui permet aussi une recherche plus rapide que celui-ci.

Le principe du tableau de suffixes est de stocker chaque suffixe d'une chaîne de caractère par l'indice de début du suffixe dans l'ordre alphabétique du suffixe (donc "abra" viendra avant "ada" car "b" vient avant "d"). Ainsi, une chaîne de <code>n</code> caractères produira un tableau de suffixes à <code>n</code> éléments.

Ainsi, pour un chaîne de caractère <code>c</code> de taille n, on génère le tableau <code>T=[0, 1, 2, ..., n-1]</code> et on trie chaque élément de <code>T</code> en mettant <code>T[a]</code> avant <code>T[b]</code> si et seulement si <code>c[T[a]:] < c[T[b]:]</code>, sinon <code>T[b]</code> viendra avant <code>T[a]</code>.

L'algorithme de trie choisit définira la complexité temporel de construction de la structure.

La recherche dans le tableau de suffixes est plus efficace que dans une autre des structures présentées car nous avons un tableau totalement trié, ce qui nous permet d'utiliser la dichotomie afin de rechercher un paterne dans la chaîne de caractère (complexité de <code>O(n)=nlog(n)</code>).

Voici, ci-dessous, l'algorithme de la recherche dans le tableau de suffixes
<pre>
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
</pre>

== Transformée de Burrows-Wheeler ==

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

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

2025-05-05T20:20:02Z

Bogdan : /* Arbre de suffixes */

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

<pre>
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
</pre>

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 :
<pre>
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
</pre>

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 suffixes ===

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 ainsi que le nombre de lettre parcourue à 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 ou l'indice de fin de cette nouvelle branche. L'utilisation de l'indice de fin de la branche ou du nombre de lettres dans la branche est un choix qui doit être le même dans toutes les branches de l'arbre.

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 règle pas le problème de la construction longue lorsque les chaînes de caractère sont grandes. Il est cependant possible de régler ce problème en construisant l'arbre grâce à l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen], qui permet de construire l'arbre de suffixes avec une complexité linéaire.

Afin de rechercher dans l'arbre de suffixes la présence d'un paterne, il suffit de suivre le même algorithme que celui du Trie en remplaçant chaque indice par sa lettre à la position de l'indice dans le mot ainsi que de prendre en compte que la branche n'est pas forcément de longueur 1, mais peut être plus longue.

=== Tableau de suffixe ===

== Transformée de Burrows-Wheeler ==

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

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

2025-05-05T20:15:12Z

Bogdan : /* Arbre de suffixe */

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

<pre>
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
</pre>

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 :
<pre>
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
</pre>

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 suffixes ===

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 ainsi que le nombre de lettre parcourue à 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 ou l'indice de fin de cette nouvelle branche. L'utilisation de l'indice de fin de la branche ou du nombre de lettres dans la branche est un choix qui doit être le même dans toutes les branches de l'arbre.

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 règle pas le problème de la construction longue lorsque les chaînes de caractère sont grandes. Il est cependant possible de régler ce problème en construisant l'arbre grâce à l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen], qui permet de construire l'arbre de suffixes avec une complexité linéaire.

=== Tableau de suffixe ===

== Transformée de Burrows-Wheeler ==

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

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

2025-05-05T20:15:05Z

Bogdan : /* Arbre de suffixe */

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

<pre>
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
</pre>

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 :
<pre>
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
</pre>

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 ainsi que le nombre de lettre parcourue à 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 ou l'indice de fin de cette nouvelle branche. L'utilisation de l'indice de fin de la branche ou du nombre de lettres dans la branche est un choix qui doit être le même dans toutes les branches de l'arbre.

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 règle pas le problème de la construction longue lorsque les chaînes de caractère sont grandes. Il est cependant possible de régler ce problème en construisant l'arbre grâce à l'[https://fr.wikipedia.org/wiki/Algorithme_d%27Ukkonen algorithme de Ukkonen], qui permet de construire l'arbre de suffixes avec une complexité linéaire.

=== Tableau de suffixe ===

== Transformée de Burrows-Wheeler ==

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

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

2025-04-14T07:55:54Z

Bogdan : /* Arbre de suffixe */

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

<pre>
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
</pre>

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 :
<pre>
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
</pre>

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

=== Tableau de suffixe ===

== Transformée de Burrows-Wheeler ==

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

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

2025-04-13T20:52:48Z

Bogdan : Introduction + Algorithme naïf + Trie

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

2025-03-09T13:25:23Z

Bogdan : Page créée avec « Étudiant: BOGDAN Benjamin Chercheur: TAVENAS Sébastien == Introduction == == Recherche dans une chaîne de caractères == === Trie === === Arbre de suffixe === === Tableau de suffixe === == Transformée de Burrows-Wheeler == == Passage entre tableau de suffixes et transformée de Burrows-Wheeler == »

Étudiant: BOGDAN Benjamin

Chercheur: TAVENAS Sébastien

== Introduction ==

== Recherche dans une chaîne de caractères ==

=== Trie ===
=== Arbre de suffixe ===
=== Tableau de suffixe ===

== Transformée de Burrows-Wheeler ==

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