Je me sens un peu épais à ce stade. J'ai passé des jours à essayer d'envelopper complètement ma tête autour de la construction d'arbres de suffixes, mais parce que je n'ai pas de formation mathématique, de nombreuses explications m'échappent alors qu'elles commencent à faire un usage excessif de la symbologie mathématique. La plus proche d'une bonne explication que j'ai trouvée est la recherche rapide de chaînes avec des arbres de suffixes , mais il passe en revue divers points et certains aspects de l'algorithme restent flous.
Une explication étape par étape de cet algorithme ici sur Stack Overflow serait inestimable pour beaucoup d'autres que moi, j'en suis sûr.
Pour référence, voici l'article d'Ukkonen sur l'algorithme: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
Ma compréhension de base, jusqu'à présent:
- Je dois parcourir chaque préfixe P d'une chaîne donnée T
- Je dois parcourir chaque suffixe S dans le préfixe P et l'ajouter à l'arbre
- Pour ajouter le suffixe S à l'arborescence, je dois parcourir chaque caractère de S, les itérations consistant soit à descendre une branche existante qui commence par le même ensemble de caractères C à S et à diviser potentiellement un bord en nœuds descendants lorsque je atteindre un caractère différent dans le suffixe, OU s'il n'y avait pas de bord correspondant à descendre. Lorsqu'aucun bord correspondant n'est trouvé pour descendre pour C, un nouveau bord de feuille est créé pour C.
L'algorithme de base semble être O (n 2 ), comme cela est souligné dans la plupart des explications, car nous devons parcourir tous les préfixes, puis nous devons parcourir chacun des suffixes pour chaque préfixe. L'algorithme d'Ukkonen est apparemment unique en raison de la technique de pointeur de suffixe qu'il utilise, bien que je pense que c'est ce que j'ai du mal à comprendre.
J'ai aussi du mal à comprendre:
- exactement quand et comment le "point actif" est attribué, utilisé et modifié
- ce qui se passe avec l'aspect canonisation de l'algorithme
- Pourquoi les implémentations que j'ai vues doivent "corriger" les variables de délimitation qu'elles utilisent
Voici le code source C # terminé . Il fonctionne non seulement correctement, mais prend en charge la canonisation automatique et rend un graphique de texte plus joli de la sortie. Le code source et l'exemple de sortie sont à:
Mise à jour 2017-11-04
Après de nombreuses années, j'ai trouvé une nouvelle utilisation des arbres de suffixes et j'ai implémenté l'algorithme en JavaScript . Gist est ci-dessous. Il devrait être exempt de bogues. Videz-le dans un fichier js, npm install chalk
du même emplacement, puis exécutez-le avec node.js pour voir une sortie colorée. Il y a une version allégée dans le même Gist, sans aucun code de débogage.
https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6
la source
Réponses:
Ce qui suit est une tentative de décrire l'algorithme Ukkonen en montrant d'abord ce qu'il fait lorsque la chaîne est simple (c'est-à-dire ne contient aucun caractère répété), puis en l'étendant à l'algorithme complet.
Tout d'abord, quelques déclarations préliminaires.
Ce que nous construisons, c'est essentiellement comme un trieur de recherche. Il y a donc un nœud racine, des bords en sortant menant à de nouveaux nœuds, et d'autres bords en sortant, etc.
Mais : contrairement à un tri de recherche, les étiquettes de bord ne sont pas des caractères uniques. Au lieu de cela, chaque bord est étiqueté à l'aide d'une paire d'entiers
[from,to]
. Ce sont des pointeurs dans le texte. Dans ce sens, chaque bord porte une étiquette de chaîne de longueur arbitraire, mais ne prend que l'espace O (1) (deux pointeurs).Principe de base
Je voudrais d'abord montrer comment créer l'arborescence des suffixes d'une chaîne particulièrement simple, une chaîne sans caractères répétés:
L'algorithme fonctionne par étapes, de gauche à droite . Il y a une étape pour chaque caractère de la chaîne . Chaque étape peut impliquer plus d'une opération individuelle, mais nous verrons (voir les observations finales à la fin) que le nombre total d'opérations est O (n).
Donc, nous commençons par la gauche et insérons d'abord uniquement le caractère unique
a
en créant un bord du nœud racine (à gauche) vers une feuille, et en l'étiquetant comme[0,#]
, ce qui signifie que le bord représente la sous-chaîne commençant à la position 0 et se terminant à la fin actuelle . J'utilise le symbole#
pour désigner la fin actuelle , qui est à la position 1 (juste aprèsa
).Nous avons donc un arbre initial, qui ressemble à ceci:
Et cela signifie ceci:
Nous passons maintenant à la position 2 (juste après
b
). Notre objectif à chaque étape est d'insérer tous les suffixes jusqu'à la position actuelle . Nous le faisons ena
portée existante àab
b
Dans notre représentation, cela ressemble à
Et cela signifie:
Nous observons deux choses:
ab
est le même que l'habitude d'être dans l'arbre initial:[0,#]
. Sa signification a changé automatiquement car nous avons mis à jour la position actuelle#
de 1 à 2.Ensuite, nous incrémentons à nouveau la position et mettons à jour l'arborescence en ajoutant un
c
à chaque bord existant et en insérant un nouveau bord pour le nouveau suffixec
.Dans notre représentation, cela ressemble à
Et cela signifie:
On observe:
#
, et l'insertion du seul nouveau bord pour le caractère final peut être effectuée en temps O (1). Par conséquent, pour une chaîne de longueur n, seul le temps O (n) est requis.Première extension: répétitions simples
Bien sûr, cela ne fonctionne si bien que parce que notre chaîne ne contient aucune répétition. Nous regardons maintenant une chaîne plus réaliste:
Il commence par
abc
comme dans l'exemple précédent, puisab
est répété et suivi dex
, puisabc
répété suivi ded
.Étapes 1 à 3: Après les 3 premières étapes, nous avons l'arborescence de l'exemple précédent:
Étape 4: Nous passons
#
à la position 4. Cela met implicitement à jour tous les bords existants en ceci:et nous devons insérer le suffixe final de l'étape en cours,,
a
à la racine.Avant de faire cela, nous introduisons deux autres variables (en plus de
#
), qui bien sûr ont été là tout le temps mais nous ne les avons pas utilisées jusqu'à présent:(active_node,active_edge,active_length)
remainder
, qui est un entier indiquant combien de nouveaux suffixes nous devons insérerLa signification exacte de ces deux éléments deviendra claire bientôt, mais pour l'instant disons simplement:
abc
exemple simple , le point actif était toujours(root,'\0x',0)
, c.-àactive_node
-d. Était le nœud racine,active_edge
était spécifié comme le caractère nul'\0x'
etactive_length
était zéro. L'effet de ceci était que le seul nouveau bord que nous avons inséré à chaque étape a été inséré au nœud racine en tant que bord fraîchement créé. Nous verrons bientôt pourquoi un triple est nécessaire pour représenter cette information.remainder
était toujours réglé sur 1 au début de chaque étape. Cela signifiait que le nombre de suffixes que nous devions insérer activement à la fin de chaque étape était de 1 (toujours juste le caractère final).Maintenant, cela va changer. Lorsque l' on insère la finale du caractère actuellement
a
à la racine, on constate qu'il existe déjà un bord sortant en commençant para
, en particulier:abca
. Voici ce que nous faisons dans un tel cas:[4,#]
au nœud racine. Au lieu de cela, nous remarquons simplement que le suffixea
est déjà dans notre arbre. Cela se termine au milieu d'un bord plus long, mais cela ne nous dérange pas. Nous laissons les choses telles qu'elles sont.(root,'a',1)
. Cela signifie que le point actif se trouve maintenant quelque part au milieu du bord sortant du nœud racine qui commencea
, spécifiquement, après la position 1 sur ce bord. On remarque que l'arête est spécifiée simplement par son premier caractèrea
. Cela suffit car il ne peut y avoir qu'un seul bord commençant par un caractère particulier (confirmez que c'est vrai après avoir lu toute la description).remainder
, donc au début de la prochaine étape ce sera 2.Observation: Lorsque le suffixe final que nous devons insérer existe déjà dans l'arbre , l'arbre lui-même n'est pas modifié du tout (nous ne mettons à jour que le point actif et
remainder
). L'arbre n'est alors plus une représentation précise de l'arbre des suffixes jusqu'à la position actuelle , mais il contient tous les suffixes (car le suffixe finala
est contenu implicitement ). Par conséquent, à part la mise à jour des variables (qui sont toutes de longueur fixe, il s'agit donc de O (1)), aucun travail n'a été effectué à cette étape.Étape 5: Nous mettons à jour la position actuelle
#
à 5. Cela met automatiquement à jour l'arborescence à ceci:Et parce que
remainder
vaut 2 , nous devons insérer deux suffixes finaux de la position actuelle:ab
etb
. C'est essentiellement parce que:a
suffixe de l'étape précédente n'a jamais été correctement inséré. Il est donc resté , et depuis que nous avons progressé d'une étape, il est maintenant passé dea
àab
.b
.En pratique, cela signifie que nous allons au point actif (qui pointe derrière derrière
a
sur ce qui est maintenant leabcab
bord) et insérons le caractère final actuelb
. Mais: Encore une fois, il s'avère qu'ilb
est également déjà présent sur ce même bord.Donc, encore une fois, nous ne changeons pas l'arbre. Nous simplement:
(root,'a',2)
(même nœud et bord que précédemment, mais maintenant nous pointons derrièreb
)remainder
à 3 car nous n'avons toujours pas inséré correctement le bord final de l'étape précédente, et nous n'insérons pas non plus le bord final actuel.Pour être clair: nous avons dû insérer
ab
etb
dans l'étape en cours, mais parce qu'ilab
était déjà trouvé, nous avons mis à jour le point actif et n'avons même pas tenté d'insérerb
. Pourquoi? Parce que si seab
trouve dans l'arborescence, chaque suffixe (y comprisb
) doit également être dans l'arborescence. Peut-être seulement implicitement , mais il doit être là, en raison de la façon dont nous avons construit l'arbre jusqu'à présent.Nous passons à l' étape 6 par incrémentation
#
. L'arbre est automatiquement mis à jour pour:Parce que
remainder
c'est 3 , nous devons insérerabx
,bx
etx
. Le point actif nous indique oùab
se termine, nous n'avons donc qu'à y sauter et insérer lex
. En effet,x
n'est pas encore là, donc on scinde leabcabx
bord et on insère un noeud interne:Les représentations de bord sont toujours des pointeurs dans le texte, donc la division et l'insertion d'un nœud interne peuvent être effectuées en temps O (1).
Nous avons donc traité
abx
et décrémentremainder
à 2. Maintenant , nous avons besoin d'insérer le prochain suffixe restantbx
. Mais avant de faire cela, nous devons mettre à jour le point actif. La règle pour cela, après avoir divisé et inséré une arête, sera appelée la règle 1 ci-dessous, et elle s'applique chaque fois que laactive_node
racine est (nous apprendrons la règle 3 pour les autres cas plus loin). Voici la règle 1:Par conséquent, le nouveau triple de point actif
(root,'b',1)
indique que l'insertion suivante doit être faite aubcabx
bord, derrière 1 caractère, c'est-à-dire derrièreb
. Nous pouvons identifier le point d'insertion en temps O (1) et vérifier s'ilx
est déjà présent ou non. S'il était présent, nous terminerions l'étape en cours et laisserions tout comme ça. Maisx
n'est pas présent, nous l'insérons donc en divisant le bord:Encore une fois, cela a pris du temps O (1) et nous mettons à jour
remainder
à 1 et le point actif à(root,'x',0)
comme règle 1 déclare.Mais il y a encore une chose que nous devons faire. Nous appellerons cette règle 2:
Nous avons quand même besoin d'insérer le suffixe final de l'étape en cours,
x
. Étant donné que leactive_length
composant du nœud actif est tombé à 0, l'insertion finale est effectuée directement à la racine. Puisqu'il n'y a pas de bord sortant au nœud racine commençant parx
, nous insérons un nouveau bord:Comme nous pouvons le voir, dans l'étape actuelle, tous les inserts restants ont été réalisés.
Nous passons à l' étape 7 en définissant
#
= 7, qui ajoute automatiquement le caractère suivanta
, à tous les bords des feuilles, comme toujours. Ensuite, nous essayons d'insérer le nouveau caractère final au point actif (la racine), et constatons qu'il est déjà là. Nous terminons donc l'étape en cours sans rien insérer et mettons à jour le point actif(root,'a',1)
.À l' étape 8 ,
#
= 8, nous ajoutonsb
, et comme vu précédemment, cela signifie uniquement que nous mettons à jour le point actif(root,'a',2)
et l'incrémentonsremainder
sans rien faire d'autre, car ilb
est déjà présent. Cependant, nous remarquons (en temps O (1)) que le point actif est maintenant à la fin d'une arête. Nous reflétons cela en le réinitialisant(node1,'\0x',0)
. Ici, j'utilisenode1
pour faire référence au nœud interne oùab
se termine le bord.Ensuite, à l' étape
#
= 9 , nous devons insérer «c» et cela nous aidera à comprendre l'astuce finale:Deuxième extension: utilisation de liens de suffixe
Comme toujours, la
#
mise à jour s'ajoutec
automatiquement aux bords des feuilles et nous allons au point actif pour voir si nous pouvons insérer «c». Il s'avère que «c» existe déjà à ce bord, nous avons donc défini le point actif sur(node1,'c',1)
, incrémenterremainder
et ne rien faire d'autre.Maintenant à l' étape
#
= 10 ,remainder
c'est 4, et donc nous devons d'abord insérerabcd
(qui reste d'il y a 3 étapes) en insérantd
au point actif.La tentative d'insertion
d
au point actif provoque une division des bords en temps O (1):Le
active_node
, à partir duquel la scission a été initiée, est marqué en rouge ci-dessus. Voici la règle finale, la règle 3:Donc, le point actif est maintenant
(node2,'c',1)
, etnode2
est marqué en rouge ci-dessous:Depuis l'insertion
abcd
est complète, nous décrémentonsremainder
à 3 et considérons le prochain suffixe restant de l'étape en cours,bcd
. La règle 3 a défini le point actif sur juste le nœud et le bord droit afin que l'insertionbcd
puisse être effectuée en insérant simplement son caractère finald
au point actif.Cela provoque une autre division des bords et, en raison de la règle 2 , nous devons créer un lien de suffixe du nœud précédemment inséré vers le nouveau:
Nous observons: Les liens de suffixe nous permettent de réinitialiser le point actif afin que nous puissions faire l' insertion restante suivante à l'effort O (1). Regardez le graphique ci-dessus pour confirmer qu'effectivement le nœud à l'étiquette
ab
est lié au nœud àb
(son suffixe), et le nœud àabc
est lié àbc
.L'étape en cours n'est pas encore terminée.
remainder
est maintenant 2, et nous devons suivre la règle 3 pour réinitialiser à nouveau le point actif. Puisque le courantactive_node
(rouge ci-dessus) n'a pas de lien de suffixe, nous réinitialisons à la racine. Le point actif est maintenant(root,'c',1)
.D' où l'insert suivant se produit à un bord de sortie du noeud racine dont le label commence par
c
:cabxabcd
, derrière le premier caractère, soit derrièrec
. Cela provoque une autre scission:Et comme cela implique la création d'un nouveau nœud interne, nous suivons la règle 2 et définissons un nouveau lien de suffixe à partir du nœud interne précédemment créé:
(J'utilise Graphviz Dot pour ces petits graphiques. Le nouveau lien de suffixe a amené le point à réorganiser les bords existants, alors vérifiez soigneusement pour confirmer que la seule chose qui a été insérée ci-dessus est un nouveau lien de suffixe.)
Avec cela,
remainder
peut être défini sur 1 et puisque laactive_node
racine est, nous utilisons la règle 1 pour mettre à jour le point actif vers(root,'d',0)
. Cela signifie que l'insertion finale de l'étape en cours consiste à insérer un seuld
à la racine:C'était la dernière étape et nous avons terminé. Il y a cependant un certain nombre d' observations finales :
À chaque étape, nous avançons
#
d'une position. Cela met automatiquement à jour tous les nœuds terminaux en temps O (1).Mais il ne traite pas a) des suffixes restants des étapes précédentes, et b) du dernier caractère de l'étape en cours.
remainder
nous indique combien d'insertions supplémentaires nous devons faire. Ces insertions correspondent un à un aux suffixes finaux de la chaîne qui se termine à la position actuelle#
. Nous considérons les uns après les autres et réalisons l'insert. Important: chaque insertion est effectuée en O (1), car le point actif nous indique exactement où aller, et nous devons ajouter un seul caractère au point actif. Pourquoi? Parce que les autres caractères sont contenus implicitement (sinon le point actif ne serait pas là où il est).Après chaque insertion, nous décrémentons
remainder
et suivons le lien de suffixe s'il y en a. Sinon, nous allons à la racine (règle 3). Si nous sommes déjà à la racine, nous modifions le point actif en utilisant la règle 1. Dans tous les cas, cela ne prend que O (1).Si, lors d'une de ces insertions, nous constatons que le caractère que nous voulons insérer est déjà là, nous ne faisons rien et terminons l'étape en cours, même si
remainder
> 0. La raison en est que les insertions restantes seront des suffixes de celui que nous venons d'essayer de faire. Par conséquent, ils sont tous implicites dans l'arbre actuel. Le fait queremainder
> 0 assure que nous traiterons les suffixes restants plus tard.Et si à la fin de l'algorithme
remainder
> 0? Ce sera le cas chaque fois que la fin du texte est une sous-chaîne qui s'est produite quelque part auparavant. Dans ce cas, nous devons ajouter un caractère supplémentaire à la fin de la chaîne qui ne s'est pas produite auparavant. Dans la littérature, le signe dollar$
est généralement utilisé comme symbole pour cela. Pourquoi est-ce important? -> Si plus tard nous utilisons l'arborescence des suffixes complétée pour rechercher les suffixes, nous ne devons accepter les correspondances que si elles se terminent par une feuille . Sinon, nous obtiendrions beaucoup de correspondances parasites, car il y a de nombreuses chaînes implicitement contenues dans l'arborescence qui ne sont pas des suffixes réels de la chaîne principale. Forcerremainder
être 0 à la fin est essentiellement un moyen de s'assurer que tous les suffixes se terminent à un nœud feuille. Cependant, si nous voulons utiliser l'arborescence pour rechercher des sous - chaînes générales , non seulement des suffixes de la chaîne principale, cette dernière étape n'est en effet pas requise, comme le suggère le commentaire de l'OP ci-dessous.Quelle est donc la complexité de l'ensemble de l'algorithme? Si le texte est de n caractères, il y a évidemment n étapes (ou n + 1 si l'on ajoute le signe dollar). À chaque étape, nous ne faisons rien (autre que la mise à jour des variables), ou nous faisons des
remainder
insertions, chacune prenant O (1) fois. Depuisremainder
indique combien de fois nous n'avons rien fait dans les étapes précédentes, et est décrémenté pour chaque insertion que nous faisons maintenant, le nombre total de fois où nous faisons quelque chose est exactement n (ou n + 1). Par conséquent, la complexité totale est O (n).Cependant, il y a une petite chose que je n'ai pas correctement expliquée: il peut arriver que nous suivions un lien de suffixe, mettons à jour le point actif, puis constations que son
active_length
composant ne fonctionne pas bien avec le nouveauactive_node
. Par exemple, considérons une situation comme celle-ci:(Les lignes pointillées indiquent le reste de l'arbre. La ligne pointillée est un lien suffixe.)
Maintenant, laissez le point actif être
(red,'d',3)
, de sorte qu'il pointe vers l'endroit derrièref
ledefg
bord. Supposons maintenant que nous avons effectué les mises à jour nécessaires et suivez maintenant le lien du suffixe pour mettre à jour le point actif conformément à la règle 3. Le nouveau point actif est(green,'d',3)
. Cependant, lad
bordure sortant du nœud vert l'estde
, donc elle n'a que 2 caractères. Afin de trouver le point actif correct, nous devons évidemment suivre ce bord jusqu'au nœud bleu et réinitialiser(blue,'f',1)
.Dans un cas particulièrement mauvais, le
active_length
pourrait être aussi grand queremainder
, ce qui peut être aussi grand que n. Et il pourrait très bien arriver que pour trouver le point actif correct, nous devons non seulement sauter par-dessus un nœud interne, mais peut-être plusieurs, jusqu'à n dans le pire des cas. Cela signifie-t-il que l'algorithme a une complexité O (n 2 ) cachée , car à chaque étaperemainder
est généralement O (n), et les post-ajustements du nœud actif après avoir suivi un lien de suffixe pourraient également être O (n)?Non. La raison est que si en effet nous devons ajuster le point actif (par exemple du vert au bleu comme ci-dessus), cela nous amène à un nouveau nœud qui a son propre lien de suffixe, et
active_length
sera réduit. Au fur et à mesure que nous suivons la chaîne de liens de suffixe, nous faisons les insertions restantes,active_length
ne pouvons que diminuer, et le nombre d'ajustements de points actifs que nous pouvons faire en cours de route ne peut pas être plus important qu'àactive_length
un moment donné. Puisqueactive_length
ne peut jamais être plus grande queremainder
, etremainder
est O (n) non seulement dans chaque étape, mais la somme totale des incréments jamais fait àremainder
au cours de l'ensemble du processus est O (n) aussi, le nombre d'ajustements de points actifs est également délimité par O (n).la source
abcdefabxybcdmnabcdex
. La partie initiale deabcd
est répétée dansabxy
(cela crée un nœud interne aprèsab
) et à nouveau dansabcdex
, et elle se termine parbcd
, qui apparaît non seulement dans lebcdex
contexte, mais aussi dans lebcdmn
contexte. Après avoirabcdex
inséré, nous suivons le lien du suffixe pour insérerbcdex
, et il y aura canonicize.J'ai essayé d'implémenter l'arborescence des suffixes avec l'approche donnée dans la réponse de jogojapan, mais cela n'a pas fonctionné dans certains cas en raison de la formulation utilisée pour les règles. De plus, j'ai mentionné que personne n'a réussi à implémenter un arbre de suffixes absolument correct en utilisant cette approche. Ci-dessous, je vais écrire un "aperçu" de la réponse de jogojapan avec quelques modifications aux règles. Je décrirai également le cas où nous oublions de créer des liens de suffixe importants .
Variables supplémentaires utilisées
Prenons le concept d'un nœud interne - tous les nœuds, à l'exception de la racine et des feuilles, sont des nœuds internes .
Observation 1
Lorsque le suffixe final que nous devons insérer existe déjà dans l'arbre, l'arbre lui-même n'est pas modifié du tout (nous mettons uniquement à jour le
active point
etremainder
).Observation 2
Si à un certain point
active_length
est supérieur ou égal à la longueur du bord actuel (edge_length
), nous déplaçons notreactive point
bas jusqu'à ce qu'iledge_length
soit strictement supérieur àactive_length
.Maintenant, redéfinissons les règles:
Règle 1
Règle 2
Cette définition de la
Rule 2
est différente de jogojapan ', car ici nous prenons en compte non seulement les nœuds internes nouvellement créés , mais aussi les nœuds internes, à partir desquels nous faisons une insertion.Règle 3
Dans cette définition de,
Rule 3
nous considérons également les insertions de nœuds foliaires (pas seulement les nœuds divisés).Et enfin, Observation 3:
Lorsque le symbole que nous voulons ajouter à l'arbre est déjà sur le bord, nous, selon, nous mettons à
Observation 1
jour uniquementactive point
etremainder
, en laissant l'arbre inchangé. MAIS s'il y a un nœud interne marqué comme ayant besoin d'un lien de suffixe , nous devons connecter ce nœud à notre courantactive node
via un lien de suffixe.Regardons l'exemple d'un arbre de suffixes pour cdddcdc si nous ajoutons un lien de suffixe dans ce cas et si nous ne le faisons pas:
Si nous NE connectons PAS les nœuds via un lien de suffixe:
Si nous FAISONS connecter les noeuds via un lien suffixe:
Il semble qu'il n'y ait pas de différence significative: dans le deuxième cas, il existe deux autres liens de suffixe. Mais ces liens de suffixe sont corrects , et l'un d'eux - du nœud bleu au nœud rouge - est très important pour notre approche avec le point actif . Le problème est que si nous ne mettons pas de lien de suffixe ici, plus tard, lorsque nous ajouterons de nouvelles lettres à l'arbre, nous pourrions omettre d'ajouter des nœuds à l'arbre en raison de la
Rule 3
, car, selon lui, s'il n'y a pas de lien suffixe, alors nous devons mettre leactive_node
à la racine.Lorsque nous ajoutions la dernière lettre à l'arbre, le nœud rouge avait déjà existé avant de faire une insertion à partir du nœud bleu (le bord marqué «c» ). Comme il y avait un insert du nœud bleu, nous le marquons comme nécessitant un lien de suffixe . Puis, en s'appuyant sur l' approche par point actif , le a
active node
été défini sur le nœud rouge. Mais nous ne faisons pas d'insertion à partir du nœud rouge, car la lettre «c» est déjà sur le bord. Cela signifie-t-il que le nœud bleu doit être laissé sans lien de suffixe? Non, nous devons connecter le nœud bleu avec le rouge via un lien suffixe. Pourquoi est-ce correct? Parce que le point actifapproche garantit que nous arrivons au bon endroit, c'est-à-dire au prochain endroit où nous devons traiter un insert d'un suffixe plus court .Enfin, voici mes implémentations de l'arbre des suffixes:
J'espère que cette "vue d'ensemble" combinée avec la réponse détaillée de jogojapan aidera quelqu'un à implémenter son propre arbre de suffixes.
la source
aabaacaad
est l'un des cas qui montre que l'ajout d'un lien de suffixe supplémentaire peut réduire les délais de mise à jour du triple. La conclusion des deux derniers paragraphes du post de jogojapan est fausse. Si nous n'ajoutons pas les liens de suffixe mentionnés dans ce post, la complexité temporelle moyenne devrait être O (nlong (n)) ou plus. Parce qu'il faut plus de temps pour parcourir l'arbre pour trouver le bonactive_node
.Merci pour le tutoriel bien expliqué de @jogojapan , j'ai implémenté l'algorithme en Python.
Quelques problèmes mineurs mentionnés par @jogojapan se révèlent être plus sophistiqués que ce à quoi je m'attendais et doivent être traités très soigneusement. Il m'a fallu plusieurs jours pour obtenir une implémentation suffisamment robuste (je suppose). Les problèmes et solutions sont répertoriés ci-dessous:
Fin avec
Remainder > 0
Il s'avère que cette situation peut également se produire pendant l'étape de dépliage , et pas seulement à la fin de l'algorithme entier. Lorsque cela se produit, nous pouvons laisser le reste, actnode, actedge et actlength inchangé , terminer l'étape de dépliage en cours et commencer une autre étape en continuant à plier ou à déplier selon que le caractère suivant de la chaîne d'origine se trouve sur le chemin actuel ou ne pas.Leap Over Nodes: lorsque nous suivons un lien de suffixe, mettons à jour le point actif, puis constatons que son composant active_length ne fonctionne pas correctement avec le nouveau noeud actif. Nous devons avancer au bon endroit pour diviser ou insérer une feuille. Ce processus peut ne pas être aussi simple car pendant le déplacement, la longueur d'acte et l'actedge changent constamment, lorsque vous devez revenir au nœud racine , l' actedge et la longueur d'acte peuvent être incorrects à cause de ces mouvements. Nous avons besoin de variables supplémentaires pour conserver ces informations.
@Managonov a en quelque sorte souligné les deux autres problèmes
Le fractionnement pourrait dégénérer Lorsque vous essayez de fractionner un bord, vous constaterez parfois que l'opération de fractionnement se situe directement sur un nœud. Dans ce cas, il suffit d'ajouter une nouvelle feuille à ce nœud, de la prendre comme une opération de division de bord standard, ce qui signifie que les liens de suffixe, s'il y en a, doivent être conservés en conséquence.
Liens de suffixe cachés Il existe un autre cas particulier qui est dû au problème 1 et au problème 2 . Parfois, nous devons sauter par-dessus plusieurs nœuds au bon point pour la division, nous pourrions dépasser le bon point si nous nous déplaçons en comparant la chaîne restante et les étiquettes de chemin. Dans ce cas, le lien de suffixe sera négligé involontairement, s'il en existe. Cela pourrait être évité en se souvenant du bon point lors de la progression. Le lien de suffixe doit être conservé si le nœud divisé existe déjà, ou même le problème 1 se produit pendant une étape de dépliage.
Enfin, mon implémentation en Python est la suivante:
la source
Toutes mes excuses si ma réponse semble redondante, mais j'ai récemment implémenté l'algorithme d'Ukkonen et je me suis retrouvé aux prises avec lui pendant des jours; J'ai dû lire plusieurs articles sur le sujet pour comprendre le pourquoi et le comment de certains aspects fondamentaux de l'algorithme.
J'ai trouvé l'approche «règles» des réponses précédentes inutile pour comprendre les raisons sous-jacentes , j'ai donc tout écrit ci-dessous en me concentrant uniquement sur la pragmatique. Si vous avez eu du mal à suivre d'autres explications, tout comme je l'ai fait, peut-être que mon explication supplémentaire le fera «cliquer» pour vous.
J'ai publié mon implémentation C # ici: https://github.com/baratgabor/SuffixTree
Veuillez noter que je ne suis pas un expert sur ce sujet, donc les sections suivantes peuvent contenir des inexactitudes (ou pire). Si vous en rencontrez, n'hésitez pas à le modifier.
Conditions préalables
Le point de départ de l'explication suivante suppose que vous êtes familier avec le contenu et l'utilisation des arborescences de suffixes et les caractéristiques de l'algorithme d'Ukkonen, par exemple comment vous étendez l'arborescence des suffixes caractère par caractère, du début à la fin. Fondamentalement, je suppose que vous avez déjà lu certaines des autres explications.
(Cependant, j'ai dû ajouter un récit de base pour le flux, donc le début pourrait en effet sembler redondant.)
La partie la plus intéressante est l' explication de la différence entre l'utilisation de liens de suffixe et la nouvelle analyse à partir de la racine . C'est ce qui m'a donné beaucoup de bugs et de maux de tête dans mon implémentation.
Nœuds foliaires ouverts et leurs limites
Je suis sûr que vous savez déjà que l'astuce la plus fondamentale consiste à réaliser que nous pouvons simplement laisser la fin des suffixes «ouverte», c'est-à-dire référencer la longueur actuelle de la chaîne au lieu de définir la fin sur une valeur statique. De cette façon, lorsque nous ajoutons des caractères supplémentaires, ces caractères seront implicitement ajoutés à toutes les étiquettes de suffixe, sans avoir à les visiter et à les mettre à jour tous.
Mais cette fin ouverte de suffixes - pour des raisons évidentes - ne fonctionne que pour les nœuds qui représentent la fin de la chaîne, c'est-à-dire les nœuds feuilles dans la structure arborescente. Les opérations de branchement que nous exécutons sur l'arborescence (l'ajout de nouveaux nœuds de branche et de nœuds terminaux) ne se propagent pas automatiquement partout où elles en ont besoin.
Il est probablement élémentaire, et ne nécessiterait pas de mention, que les sous-chaînes répétées n'apparaissent pas explicitement dans l'arbre, car l'arbre les contient déjà en raison de leur répétition; cependant, lorsque la sous-chaîne répétitive se termine en rencontrant un caractère non répétitif, nous devons créer une ramification à ce point pour représenter la divergence à partir de ce point.
Par exemple, dans le cas de la chaîne «ABCXABCY» (voir ci-dessous), une ramification vers X et Y doit être ajoutée à trois suffixes différents, ABC , BC et C ; sinon, ce ne serait pas un arbre de suffixes valide, et nous ne pourrions pas trouver toutes les sous-chaînes de la chaîne en faisant correspondre les caractères de la racine vers le bas.
Encore une fois, pour souligner - toute opération que nous exécutons sur un suffixe dans l'arborescence doit également être reflétée par ses suffixes consécutifs (par exemple ABC> BC> C), sinon ils cessent simplement d'être des suffixes valides.
Mais même si nous acceptons de devoir effectuer ces mises à jour manuelles, comment savoir combien de suffixes doivent être mis à jour? Puisque, lorsque nous ajoutons le caractère répété A (et le reste des caractères répétés successivement), nous n'avons pas encore d'idée quand / où devons-nous diviser le suffixe en deux branches. La nécessité de diviser n'est vérifiée que lorsque nous rencontrons le premier caractère non répétitif, dans ce cas Y (au lieu du X qui existe déjà dans l'arbre).
Ce que nous pouvons faire est de faire correspondre la chaîne répétée la plus longue possible et de compter le nombre de ses suffixes que nous devons mettre à jour plus tard. C'est ce que signifie le «reste» .
Le concept de «reste» et de «nouvelle numérisation»
La variable
remainder
nous indique combien de caractères répétés nous avons ajoutés implicitement, sans branchement; c'est-à-dire combien de suffixes nous devons visiter pour répéter l'opération de branchement une fois que nous avons trouvé le premier caractère que nous ne pouvons pas faire correspondre. Cela équivaut essentiellement au nombre de caractères `` profonds '' dans l'arbre depuis sa racine.Donc, en restant avec l'exemple précédent de la chaîne ABCXABCY , nous faisons correspondre la partie ABC répétée «implicitement», en incrémentant
remainder
chaque fois, ce qui donne un reste de 3. Ensuite, nous rencontrons le caractère non répétitif «Y» . Nous séparons ici le ajouté précédemment ABCX dans ABC -> X et ABC -> Y . Ensuite, nous décrémentonsremainder
de 3 à 2, car nous avons déjà pris en charge la ramification ABC . Maintenant, nous répétons l'opération en faisant correspondre les 2 derniers caractères - BC - de la racine pour atteindre le point où nous devons diviser, et nous divisons également BCX en BC-> X et BC -> Y . Encore une fois, nous décrémentonsremainder
à 1 et répétons l'opération; jusqu'à ce que leremainder
soit 0. Enfin, nous devons également ajouter le caractère actuel ( Y ) à la racine.Cette opération, suivant les suffixes consécutifs de la racine simplement pour atteindre le point où nous devons effectuer une opération, est ce qu'on appelle la `` nouvelle analyse '' dans l'algorithme d'Ukkonen, et généralement c'est la partie la plus coûteuse de l'algorithme. Imaginez une chaîne plus longue où vous devez `` réanalyser '' de longues sous-chaînes, sur plusieurs dizaines de nœuds (nous en discuterons plus tard), potentiellement des milliers de fois.
Comme solution, nous introduisons ce que nous appelons des «liens de suffixe» .
Le concept de «liens suffixes»
Les liens de suffixe pointent essentiellement vers les positions que nous devrions normalement `` réanalyser '' , donc au lieu de l'opération de réanalyse coûteuse, nous pouvons simplement passer à la position liée, faire notre travail, passer à la position liée suivante et répéter - jusqu'à ce qu'il y ait il n'y a plus de postes à mettre à jour.
Bien sûr, une grande question est de savoir comment ajouter ces liens. La réponse actuelle est que nous pouvons ajouter les liens lorsque nous insérons de nouveaux nœuds de branche, en utilisant le fait que, dans chaque extension de l'arbre, les nœuds de branche sont naturellement créés les uns après les autres dans l'ordre exact dont nous aurions besoin pour les lier ensemble . Cependant, nous devons établir une liaison entre le dernier nœud de branche créé (le suffixe le plus long) et le précédent, nous devons donc mettre en cache le dernier que nous créons, le lier au suivant que nous créons et mettre en cache le nouveau.
Une conséquence est que nous n'avons en fait souvent pas de liens de suffixe à suivre, car le nœud de branche donné vient d'être créé. Dans ces cas, nous devons toujours revenir à la «nouvelle analyse» susmentionnée de la racine. C'est pourquoi, après une insertion, vous êtes invité à utiliser le lien suffixe ou à passer à la racine.
(Ou bien, si vous stockez des pointeurs parents dans les nœuds, vous pouvez essayer de suivre les parents, vérifier s'ils ont un lien et l'utiliser. J'ai trouvé que cela est très rarement mentionné, mais l'utilisation du lien de suffixe n'est pas ensemble en pierres. Il y a plusieurs approches possibles, et si vous comprenez le mécanisme sous - jacent vous pouvez mettre en œuvre un qui correspond à vos besoins le meilleur.)
Le concept de «point actif»
Jusqu'à présent, nous avons discuté de plusieurs outils efficaces pour construire l'arbre, et nous avons vaguement fait référence à la traversée de plusieurs arêtes et nœuds, mais nous n'avons pas encore exploré les conséquences et les complexités correspondantes.
Le concept précédemment expliqué de «reste» est utile pour garder une trace de l'endroit où nous sommes dans l'arbre, mais nous devons réaliser qu'il ne stocke pas suffisamment d'informations.
Premièrement, nous résidons toujours sur un bord spécifique d'un nœud, nous devons donc stocker les informations sur le bord. Nous appellerons ce «bord actif» .
Deuxièmement, même après avoir ajouté les informations de bord, nous n'avons toujours aucun moyen d'identifier une position qui est plus bas dans l'arborescence et qui n'est pas directement connectée au nœud racine . Nous devons donc également stocker le nœud. Appelons ce «nœud actif» .
Enfin, nous pouvons remarquer que le «reste» est insuffisant pour identifier une position sur un bord qui n'est pas directement connecté à la racine, car le «reste» est la longueur de la route entière; et nous ne voulons probablement pas prendre la peine de se souvenir et de soustraire la longueur des bords précédents. Nous avons donc besoin d'une représentation qui est essentiellement le reste sur le bord actuel . C'est ce que nous appelons la «longueur active» .
Cela conduit à ce que nous appelons «point actif» - un ensemble de trois variables qui contiennent toutes les informations que nous devons conserver sur notre position dans l'arbre:
Active Point = (Active Node, Active Edge, Active Length)
Vous pouvez observer sur l'image suivante comment l'itinéraire correspondant d' ABCABD se compose de 2 caractères sur le bord AB (à partir de la racine ), plus 4 caractères sur le bord CABDABCABD (à partir du nœud 4) - résultant en un `` reste '' de 6 caractères. Ainsi, notre position actuelle peut être identifiée comme nœud actif 4, bord actif C, longueur active 4 .
Un autre rôle important du `` point actif '' est qu'il fournit une couche d'abstraction pour notre algorithme, ce qui signifie que des parties de notre algorithme peuvent faire leur travail sur le `` point actif '' , que ce point actif soit à la racine ou ailleurs . Cela facilite l'implémentation de l'utilisation de liens de suffixe dans notre algorithme de manière claire et simple.
Différences entre la nouvelle analyse et l'utilisation de liens de suffixe
Maintenant, la partie délicate, quelque chose qui - selon mon expérience - peut provoquer de nombreux bugs et maux de tête, et qui est mal expliquée dans la plupart des sources, est la différence dans le traitement des cas de lien de suffixe par rapport aux cas de nouvelle analyse.
Prenons l'exemple suivant de la chaîne «AAAABAAAABAAC» :
Vous pouvez observer ci-dessus comment le «reste» de 7 correspond à la somme totale des caractères de la racine, tandis que la «longueur active» de 4 correspond à la somme des caractères correspondants du bord actif du nœud actif.
Maintenant, après avoir exécuté une opération de branchement au point actif, notre nœud actif peut contenir ou non un lien suffixe.
Si un lien de suffixe est présent: nous avons seulement besoin de traiter la partie «longueur active» . Le «reste» n'est pas pertinent, car le nœud où nous sautons via le lien de suffixe code déjà implicitement le «reste» correct , simplement parce qu'il se trouve dans l'arbre où il se trouve.
Si un lien de suffixe N'EST PAS présent: nous devons «rescanner» à partir de zéro / root, ce qui signifie traiter l'intégralité du suffixe depuis le début. À cette fin, nous devons utiliser l'ensemble du «reste» comme base de la nouvelle analyse.
Exemple de comparaison de traitement avec et sans lien de suffixe
Considérez ce qui se passe à l'étape suivante de l'exemple ci-dessus. Comparons comment obtenir le même résultat - c'est-à-dire passer au suffixe suivant à traiter - avec et sans lien de suffixe.
Utilisation du «lien suffixe»
Notez que si nous utilisons un lien suffixe, nous sommes automatiquement «au bon endroit». Ce qui n'est souvent pas strictement vrai car la «longueur active» peut être «incompatible» avec la nouvelle position.
Dans le cas ci-dessus, puisque la «longueur active» est 4, nous travaillons avec le suffixe « ABAA» , en commençant par le nœud lié 4. Mais après avoir trouvé l'arête qui correspond au premier caractère du suffixe ( «A» ), on remarque que notre «longueur active» déborde ce bord de 3 caractères. Nous sautons donc sur le bord complet, au nœud suivant, et décrémentons la «longueur active» des caractères que nous avons consommés avec le saut.
Ensuite, après avoir trouvé le bord suivant `` B '' , correspondant au suffixe décrémenté `` BAA '', nous notons enfin que la longueur du bord est supérieure à la `` longueur active '' restante de 3, ce qui signifie que nous avons trouvé le bon endroit.
Veuillez noter qu'il semble que cette opération ne soit généralement pas appelée `` nouvelle analyse '', même si pour moi il semble que ce soit l'équivalent direct de la nouvelle analyse, juste avec une longueur raccourcie et un point de départ non racine.
Utilisation de «rescan»
Notez que si nous utilisons une opération de `` nouvelle analyse '' traditionnelle (prétendant ici que nous n'avions pas de lien de suffixe), nous commençons en haut de l'arborescence, à la racine, et nous devons redescendre au bon endroit, suivant sur toute la longueur du suffixe actuel.
La longueur de ce suffixe est le «reste» dont nous avons discuté auparavant. Nous devons consommer la totalité de ce reste, jusqu'à ce qu'il atteigne zéro. Cela pourrait (et le fait souvent) inclure le saut à travers plusieurs nœuds, à chaque saut, diminuant le reste de la longueur du bord que nous avons traversé. Enfin, nous atteignons un bord plus long que notre «reste» restant ; ici, nous définissons le bord actif sur le bord donné, définissons la «longueur active» sur le «reste » restant , et nous avons terminé.
Notez, cependant, que la variable «résiduelle» réelle doit être préservée et seulement décrémentée après chaque insertion de nœud. Donc, ce que j'ai décrit ci-dessus supposait l'utilisation d'une variable distincte initialisée à «reste» .
Remarques sur les liens de suffixe et les nouvelles analyses
1) Notez que les deux méthodes conduisent au même résultat. Le saut de lien de suffixe est cependant beaucoup plus rapide dans la plupart des cas; c'est toute la logique derrière les liens de suffixe.
2) Les implémentations algorithmiques réelles n'ont pas besoin de différer. Comme je l'ai mentionné ci-dessus, même dans le cas de l'utilisation du lien de suffixe, la «longueur active» n'est souvent pas compatible avec la position liée, car cette branche de l'arbre peut contenir des ramifications supplémentaires. Donc, essentiellement, il vous suffit d'utiliser la «longueur active» au lieu de «reste» et d'exécuter la même logique de nouvelle analyse jusqu'à ce que vous trouviez un bord plus court que la longueur de suffixe restante.
3) Une remarque importante concernant les performances est qu'il n'est pas nécessaire de vérifier chaque caractère lors de la nouvelle numérisation. En raison de la façon dont un arbre de suffixes valide est construit, nous pouvons supposer en toute sécurité que les caractères correspondent. Vous comptez donc principalement les longueurs, et le seul besoin de vérification de l'équivalence des caractères survient lorsque nous passons à un nouveau bord, car les bords sont identifiés par leur premier caractère (qui est toujours unique dans le contexte d'un nœud donné). Cela signifie que la logique de «nouvelle analyse» est différente de la logique de correspondance de chaîne complète (c'est-à-dire la recherche d'une sous-chaîne dans l'arborescence).
4) Le lien de suffixe original décrit ici n'est qu'une des approches possibles . Par exemple, NJ Larsson et al. nomme cette approche Node-Oriented Top-Down et la compare à Node-Oriented Bottom-Up et deux variétés Edge-Oriented . Les différentes approches ont des performances, des exigences, des limites, etc. typiques et pires, mais il semble généralement que les approches orientées sur les bords représentent une amélioration globale par rapport à l'original.
la source
@jogojapan vous avez apporté une explication et une visualisation impressionnantes. Mais comme @makagonov l'a mentionné, il manque certaines règles concernant la définition des liens de suffixe. Il est visible de manière agréable lorsque vous allez étape par étape sur http://brenden.github.io/ukkonen-animation/ via le mot «aabaaabb». Lorsque vous passez de l'étape 10 à l'étape 11, il n'y a pas de lien de suffixe entre le nœud 5 et le nœud 2 mais le point actif s'y déplace soudainement.
@makagonov depuis que je vis dans le monde Java, j'ai également essayé de suivre votre implémentation pour saisir le flux de travail du bâtiment ST mais cela a été difficile pour moi à cause de:
J'ai donc fini avec une telle implémentation en Java qui, je l'espère, reflète toutes les étapes de manière plus claire et réduira le temps d'apprentissage pour les autres personnes Java:
la source
Mon intuition est la suivante:
Après k itérations de la boucle principale, vous avez construit une arborescence de suffixes qui contient tous les suffixes de la chaîne complète qui commencent par les k premiers caractères.
Au début, cela signifie que l'arborescence des suffixes contient un seul nœud racine qui représente la chaîne entière (c'est le seul suffixe qui commence à 0).
Après les itérations len (chaîne), vous avez une arborescence de suffixes qui contient tous les suffixes.
Pendant la boucle, la clé est le point actif. Je suppose que cela représente le point le plus profond de l'arbre des suffixes qui correspond à un suffixe approprié des k premiers caractères de la chaîne. (Je pense que cela signifie que le suffixe ne peut pas être la chaîne entière.)
Par exemple, supposons que vous ayez vu des caractères «abcabc». Le point actif représenterait le point dans l'arbre correspondant au suffixe «abc».
Le point actif est représenté par (origine, premier, dernier). Cela signifie que vous êtes actuellement au point de l'arborescence auquel vous accédez en commençant à l'origine du nœud, puis en introduisant les caractères dans la chaîne [premier: dernier]
Lorsque vous ajoutez un nouveau caractère, vous regardez pour voir si le point actif est toujours dans l'arborescence existante. Si c'est le cas, vous avez terminé. Sinon, vous devez ajouter un nouveau nœud à l'arborescence des suffixes au point actif, revenir à la correspondance la plus courte suivante et vérifier à nouveau.
Remarque 1: les pointeurs de suffixe donnent un lien vers la correspondance la plus courte suivante pour chaque nœud.
Remarque 2: lorsque vous ajoutez un nouveau noeud et de secours, vous ajoutez un nouveau pointeur de suffixe pour le nouveau noeud. La destination de ce pointeur de suffixe sera le nœud au point actif raccourci. Ce nœud existera déjà ou sera créé lors de la prochaine itération de cette boucle de secours.
Remarque 3: La partie canonisation permet simplement de gagner du temps lors de la vérification du point actif. Par exemple, supposons que vous ayez toujours utilisé origin = 0 et que vous ayez juste changé en premier et en dernier. Pour vérifier le point actif, vous devez suivre l'arborescence des suffixes à chaque fois le long de tous les nœuds intermédiaires. Il est logique de mettre en cache le résultat du suivi de ce chemin en enregistrant uniquement la distance par rapport au dernier nœud.
Pouvez-vous donner un exemple de code de ce que vous entendez par des variables de délimitation «fixes»?
Avertissement de santé: j'ai également trouvé cet algorithme particulièrement difficile à comprendre, alors veuillez vous rendre compte que cette intuition est probablement incorrecte dans tous les détails importants ...
la source
Salut, j'ai essayé d'implémenter l'implémentation expliquée ci-dessus dans ruby, veuillez le vérifier. Cela semble marcher correctement.
la seule différence dans l'implémentation est que j'ai essayé d'utiliser l'objet bord au lieu d'utiliser simplement des symboles.
son également présent sur https://gist.github.com/suchitpuri/9304856
la source