Question L'algorithme de l'arbre des suffixes d'Ukkonen en anglais clair


Je me sens un peu épais à ce stade. J'ai passé des jours à essayer de comprendre comment construire des suffixes, mais comme je n'ai pas d'arrière-plan mathématique, beaucoup d'explications m'échappent au fur et à mesure qu'elles commencent à faire un usage excessif de la symbologie mathématique. Le plus proche d'une bonne explication que j'ai trouvé est Recherche de chaînes rapide avec des arbres Suffix, 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 à part 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:

  • J'ai besoin de 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'arbre, j'ai besoin de parcourir chaque caractère de S, avec les itérations consistant soit à descendre une branche existante qui commence par le même ensemble de caractères C dans S et à scinder potentiellement une arête 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 vers C, un nouveau bord de feuille est créé pour C.

L'algorithme de base semble être O (n2), comme cela est indiqué 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 cette est ce que j'ai de la difficulté à comprendre.

J'ai aussi du mal à comprendre:

  • exactement quand et comment le "point actif" est assigné, utilisé et changé
  • ce qui se passe avec l'aspect canonisation de l'algorithme
  • Pourquoi les implémentations que j'ai vues doivent "réparer" les variables de délimitation qu'elles utilisent

Voici le complété C # code source. Cela fonctionne non seulement correctement, mais prend en charge la canonisation automatique et rend un graphique de texte plus agréable de la sortie. Le code source et l'exemple de sortie sont à:

https://gist.github.com/2373868


Mise à jour 2017-11-04

Après de nombreuses années, j'ai trouvé une nouvelle utilisation pour les arborescences de suffixes, et j'ai implémenté l'algorithme dans JavaScript. Gist est ci-dessous. Cela devrait être sans bug. Déposez-le dans un fichier js, npm install chalk à partir du même emplacement, puis exécutez avec node.js pour voir une sortie colorée. Il y a une version dépouillée dans le même Gist, sans aucun code de débogage.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6


949
2018-02-26 11:30


origine


Réponses:


Ce qui suit est une tentative pour décrire l'algorithme d'Ukkonen en montrant d'abord ce qu'il fait quand la chaîne est simple (c'est-à-dire ne contient aucun caractère répété), puis en l'étendant à l'algorithme complet.

D'abord, quelques déclarations préliminaires.

  1. Ce que nous construisons, c'est fondamentalement comme une recherche trie. Donc là est un nœud racine, les arêtes qui en sortent conduisent à de nouveaux nœuds, et d'autres bords qui sortent de ceux-ci, et ainsi de suite

  2. Mais: Contrairement à une recherche trie, les étiquettes de bord ne sont pas simples personnages. Au lieu de cela, chaque bord est étiqueté en utilisant une paire d'entiers [from,to]. Ce sont des pointeurs dans le texte. En ce sens, chaque bord porte une étiquette de longueur arbitraire, mais ne prend que O (1) espace (deux pointeurs).

Principe de base

Je voudrais d'abord montrer comment créer l'arbre de suffixe d'un chaîne particulièrement simple, une chaîne sans caractères répétés:

abc

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 à partir du la gaucheet insérez d'abord uniquement le caractère unique a en créant une arête depuis le nœud racine (à gauche) jusqu'à une feuille, et l'étiqueter 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. je utilise le symbole # vouloir dire la fin actuelle, qui est en position 1 (juste après a).

Nous avons donc un arbre initial, qui ressemble à ceci:

Et ce que cela signifie est 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 faisons cela par

  • l'expansion de l'existant a-voiture à ab
  • insérer un nouveau bord pour b

Dans notre représentation, cela ressemble à

enter image description here

Et ce que cela signifie est:

Nous observons deux choses:

  • La représentation de bord pour ab est le même Comme c'était le cas dans l'arbre initial: [0,#]. Sa signification a changé automatiquement parce que nous avons mis à jour la position actuelle # de 1 à 2.
  • Chaque bord consomme O (1) espace, car il se compose de seulement deux pointeurs dans le texte, quel que soit le nombre de caractères représente.

Ensuite, nous incrémenter à nouveau la position et mettre à jour l'arbre en ajoutant une c à chaque bord existant et en insérant un nouveau bord pour le nouveau suffixe c.

Dans notre représentation, cela ressemble à

Et ce que cela signifie est:

Nous observons:

  • L'arbre est l'arbre de suffixe correct jusqu'à la position actuelle après chaque étape
  • Il y a autant d'étapes qu'il y a de caractères dans le texte
  • La quantité de travail dans chaque étape est O (1), car tous les bords existants sont mis à jour automatiquement en incrémentant #et en insérant le un nouveau bord pour le dernier caractère peut être fait dans O (1) temps. Donc, 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 fonctionne si bien seulement parce que notre chaîne ne contenir des répétitions. Nous regardons maintenant une chaîne plus réaliste:

abcabxabcd

Ça commence avec abc comme dans l'exemple précédent, alors ab est répété et suivi par x, et alors abc est répété suivi de d.

Étapes 1 à 3: Après les trois premières étapes, nous avons l'arbre de l'exemple précédent:

Étape 4: Nous déménageons # à la position 4. Cela met implicitement à jour tous les bords à ceci:

et nous devons insérer le suffixe final de l'étape en cours, a, à la racine.

Avant de faire cela, nous présentons deux autres variables (en plus de #), qui bien sûr ont été là tout le temps mais nous n'avons pas utilisé eux jusqu'à présent:

  • le point actif, qui est un triple (active_node,active_edge,active_length)
  • le remainder, qui est un nombre entier indiquant combien de nouveaux suffixes nous devons insérer

La signification exacte de ces deux deviendra bientôt clair, mais pour l'instant Disons simplement:

  • Dans le simple abc Par exemple, le point actif était toujours (root,'\0x',0), c'est à dire. active_node était le nœud racine, active_edge a été spécifié comme le caractère nul '\0x', et active_length était zéro. L'effet de ceci était que le nouveau bord nous avons inséré dans chaque étape a été insérée au noeud racine en tant que bord fraîchement créé. Nous verrons bientôt pourquoi un triple est nécessaire pour représenter cette information.
  • le remainder était toujours réglé sur 1 au début de chaque étape. La signification de ceci était que le nombre de suffixes nous devions insérer activement à la fin de chaque étape était 1 (toujours juste le caractère final).

Maintenant cela va changer. Lorsque nous insérons la finale en cours personnage a à la racine, nous remarquons qu'il y a déjà un sortant bord commençant par a, Plus précisément: abca. Voici ce que nous faisons un tel cas:

  • nous ne pas insérer un nouveau bord [4,#] au noeud racine. Au lieu de nous remarquez simplement que le suffixe a est déjà dans notre arbre. Il se termine au milieu d'un bord plus long, mais nous ne sommes pas dérangé par cela. Nous laissons les choses comme elles sont.
  • nous définir le point actif à (root,'a',1). Cela signifie que l'actif point est maintenant quelque part au milieu du bord sortant du nœud racine qui commence par a, spécifiquement, après la position 1 sur ce bord. nous notez que le bord est spécifié simplement par son premier personnage a. Cela suffit parce qu'il peut y avoir seulement un bord en commençant par un caractère particulier (confirmez que ceci est vrai après avoir lu toute la description).
  • Nous incrémentons également remainder, donc au début de la prochaine étape ce sera 2.

Observation: Quand la finale suffixe que nous devons insérer est trouvé à existe déjà dans l'arbre, l'arbre lui-même est inchangé du tout (nous mettons seulement à jour le point actif et remainder). L'arbre est alors pas une représentation précise de l'arbre de suffixe jusqu'à la position actuelle plus, mais contient tous les suffixes (parce que la finale suffixe a est contenu implicitement). Par conséquent, mis à part la mise à jour variables (qui sont tous de longueur fixe, donc c'est O (1)), il y avait pas de travail fait dans cette étape.

Étape 5: Nous mettons à jour la position actuelle # à 5. Ceci met automatiquement à jour l'arbre à ceci:

Et car remainder est 2, nous devons insérer deux derniers suffixes de la position actuelle: ab et b. C'est essentiellement parce que:

  • le a suffixe de l'étape précédente n'a jamais été correctement inséré. Donc, il a restéet depuis que nous avons progressé étape, il a maintenant grandi à partir de a à ab.
  • Et nous devons insérer le nouveau bord final b.

En pratique, cela signifie que nous allons au point actif (qui pointe vers derrière la a sur ce qui est maintenant le abcab bord), et insérez le caractère final actuel b. Mais: Encore une fois, il s'avère que b est également déjà présent sur ce même bord.

Donc, encore une fois, nous ne changeons pas l'arbre. Nous simplement:

  • Mettre à jour le point actif à (root,'a',2) (même noeud et bord comme avant, mais maintenant nous indiquons derrière le b)
  • Incrémenter le remainder à 3 parce que nous n'avons toujours pas correctement inséré le dernier bord de l'étape précédente, et nous n'insérons pas le dernier bord actuel soit.

Pour être clair: nous devions insérer ab et b dans l'étape actuelle, mais car ab a déjà été trouvé, nous avons mis à jour le point actif et fait même pas tenter d'insérer b. Pourquoi? Parce que si ab est dans l'arbre, chaque suffixe de celui-ci (y compris b) doit être dans l'arbre, aussi. Peut-être seulement implicitement, mais il doit être là, à cause du Nous avons construit l'arbre jusqu'à présent.

Nous procédons à étape 6 en incrémentant #. L'arbre est mis à jour automatiquement pour:

Car remainder est 3, nous devons insérer abx, bx et x. Le point actif nous dit où ab se termine, nous avons seulement besoin de sauter là et insérer le x. Effectivement, x n'est pas encore là, donc nous diviser le abcabx bord et insérez un nœud 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 O (1) temps.

Nous avons donc traité avec abx et décrémenter remainder à 2. Maintenant nous besoin d'insérer le suffixe restant suivant, bx. Mais avant de faire ça nous devons mettre à jour le point actif. La règle pour cela, après la séparation et en insérant un bord, sera appelé Règle 1 ci-dessous, et il s'applique chaque fois que le active_node est root (nous apprendrons la règle 3 pour d'autres cas plus loin au dessous de). Voici la règle 1:

Après une insertion de racine,

  • active_node reste racine
  • active_edge est réglé sur le premier caractère du nouveau suffixe nous   besoin d'insérer, c'est-à-dire b
  • active_length est réduit de 1

Par conséquent, le nouveau triple actif (root,'b',1) indique que le l'insertion suivante doit être faite au bcabx bord, derrière 1 caractère, c'est-à-dire derrière b. Nous pouvons identifier le point d'insertion en O (1) et vérifier si x est déjà présent ou non. Si c'était présent, nous mettrait fin à l'étape actuelle et laisserait tout comme il est. Mais x n'est pas présent, donc nous l'insérons en divisant le bord:

Encore une fois, cela a pris O (1) fois et nous mettons à jour remainder à 1 et le point actif à (root,'x',0) comme règle 1 états.

Mais il y a encore une chose à faire. Nous appellerons cela Règle 2:

Si nous divisons un bord et insérons un nouveau nœud, et si c'est pas le   premier noeud créé au cours de l'étape actuelle, nous connectons le précédemment   nœud inséré et le nouveau nœud à travers un pointeur spécial, un suffixe   lien. Nous verrons plus tard pourquoi cela est utile. Voici ce que nous obtenons, le   Le lien suffixe est représenté par un point en pointillé:

Nous devons toujours insérer le suffixe final de l'étape en cours, x. Depuis le active_length composant du noeud actif est tombé à 0, l'insertion finale est faite directement à la racine. Comme il n'y a pas bord sortant au noeud racine commençant par x, nous insérons un nouveau bord:

Comme nous pouvons le voir, dans l'étape actuelle, tous les inserts restants ont été faits.

Nous procédons à étape 7 en définissant #= 7, qui ajoute automatiquement le caractère suivant, a, à tous les bords de la feuille, comme toujours. Ensuite, nous essayons d'insérer la nouvelle finale caractère au point actif (la racine), et trouver qu'il est là déjà. Nous terminons donc l'étape actuelle sans rien insérer et mettre à jour le point actif (root,'a',1).

Dans étape 8, #= 8, nous ajoutons bet comme vu avant, ceci seulement signifie que nous mettons à jour le point actif à (root,'a',2) et incrémenter remainder sans faire rien d'autre, parce que b est déjà présent. cependant, on remarque (en O (1) temps) que le point actif est maintenant à la fin d'un bord. Nous reflétons cela en le redéfinissant à (node1,'\0x',0). Ici, j'utilise node1 se référer à nœud interne du ab le bord se termine à.

Puis dans étape #= 9, nous devons insérer 'c' et cela nous aidera à comprendre le dernier tour:

Deuxième extension: Utilisation de liens de suffixe

Comme toujours, le # mettre à jour les ajouts c automatiquement aux bords de la feuille et nous allons au point actif pour voir si nous pouvons insérer 'c'. Ça tourne out 'c' existe déjà à ce bord, donc nous définissons le point actif à (node1,'c',1), incrément remainder et ne fais rien d'autre.

Maintenant en étape #= 10, remainder is 4, et donc nous devons d'abord insérer abcd (qui reste d'il y a 3 étapes) en insérant d à l'actif point.

Tenter d'insérer d au point actif provoque une division de bord en O (1) temps:

le active_node, à partir de laquelle la scission a été initiée, est marquée rouge ci-dessus. Voici la règle finale, Règle 3:

Après avoir séparé un bord d'un active_node ce n'est pas la racine   noeud, nous suivons le lien suffixe sortant de ce noeud, s'il y a   tout, et réinitialiser le active_node au noeud, il pointe vers. S'il y a   pas de lien suffixe, nous avons mis le active_nodeà la racine. active_edge   et active_length restent inchangés.

Donc, le point actif est maintenant (node2,'c',1), et node2 est marqué dans rouge ci-dessous:

Depuis l'insertion de abcd est complet, nous décrémenterons remainder à 3 et considérons le 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 droits donc l'insertion bcd peut être fait en insérant simplement son dernier caractère d au point actif.

Cela provoque une autre division de bord, et à cause de la règle 2, nous doit créer un lien de suffixe entre le nœud précédemment inséré et le nouveau un:

Nous observons: Les liens de suffixe nous permettent de réinitialiser le point actif afin que nous   peut faire le prochain insert restant à O (1) effort. Regarde le   graphique ci-dessus pour confirmer que, en effet, le noeud à l'étiquette ab est lié à   le noeud à b (son suffixe), et le noeud à abc est lié à    bc.

L'étape en cours n'est pas encore terminée. remainder est maintenant 2, et nous besoin de suivre la règle 3 pour réinitialiser le point actif. Depuis le actuel active_node (rouge ci-dessus) n'a pas de lien de suffixe, nous réinitialisons à racine. Le point actif est maintenant (root,'c',1).

Par conséquent, l'insertion suivante se produit au niveau du premier noeud sortant du noeud racine. dont l'étiquette commence par c: cabxabcdderrière le premier personnage c'est-à-dire derrière c. Cela provoque une autre scission:

Et puisque cela implique la création d'un nouveau nœud interne, nous suivons règle 2 et définit un nouveau lien suffixe à partir de l'interne créé précédemment nœud:

(J'utilise Graphviz Dot pour ces petits graphiques. Le nouveau lien de suffixe a provoqué un réarrangement du point existant bords, alors vérifiez avec soin pour confirmer que la seule chose qui était inséré ci-dessus est un nouveau lien de suffixe.)

Avec ça, remainder peut être réglé sur 1 et depuis active_node est root, nous utilisons la règle 1 pour mettre à jour le point actif à (root,'d',0). Ce signifie que l'insertion finale de l'étape actuelle consiste à insérer un seul d à la racine:

C'était la dernière étape et nous avons terminé. Il y a un certain nombre de final observations, bien que:

  • Dans chaque étape, nous passons # avancer d'1 position. Ceci automatiquement met à jour tous les nœuds feuille en O (1) temps.

  • Mais cela ne concerne pas a) les suffixes restant de précédents étapes, et b) avec le dernier caractère de l'étape en cours.

  • remainder nous dit combien d'inserts supplémentaires nous devons faire. Ces inserts correspondent les uns aux autres aux suffixes finaux de la chaîne qui se termine à la position actuelle #. Nous considérons un après l'autre et faire l'insertion. Important: Chaque insert est fait en O (1) temps puisque le point actif nous dit exactement où aller, et nous devons ajouter un seul caractère à l'actif point. Pourquoi? Parce que les autres personnages sont contenue implicitement (sinon le point actif ne serait pas où il est).

  • Après chaque insertion, nous décrémenterons remainder et suivez le lien suffixe s'il y en a. Sinon, nous allons à la racine (règle 3). Si nous sont déjà à la racine, nous modifions le point actif en utilisant la règle 1. Dans Dans tous les cas, cela prend seulement O (1) temps.

  • Si, au cours de l'une de ces insertions, nous trouvons que le personnage que nous voulons insérer est déjà là, nous ne faisons rien et finissons étape actuelle, même si remainder> 0. La raison en est que tout les inserts qui restent seront des suffixes de celui que nous venons d'essayer de faire. D'où ils sont tous implicite dans l'arbre actuel. Le fait cette remainder> 0 s'assure que nous traitons les suffixes restants plus tard.

  • Que faire 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 avant. Dans ce cas, nous devons ajouter un caractère supplémentaire à la fin de la chaîne qui ne s'est pas produite avant. dans le littérature, généralement le signe dollar $ est utilisé comme un symbole pour cette. Pourquoi est-ce important? -> Si plus tard nous utilisons l'arborescence de suffixes complétée pour rechercher des suffixes, nous devons accepter des correspondances seulement si elles fin à une feuille. Sinon, nous aurions beaucoup de matches faux, car il y a beaucoup cordes implicitement contenu dans l'arborescence qui ne sont pas des suffixes réels de la chaîne principale. Forcer remainder ê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'arbre pour rechercher sous-chaînes générales, pas seulement suffixes de la chaîne principale, cette dernière étape n'est en effet pas requise, comme le suggère le commentaire du PO ci-dessous.

  • Alors, quelle est la complexité de l'ensemble de l'algorithme? Si le texte est n caractères de longueur, il y a évidemment n étapes (ou n + 1 si on ajoute le signe dollar). Dans chaque étape, nous ne faisons rien (autre que mettre à jour les variables), ou nous faisons remainder inserts, chacun prenant O (1) temps. Depuis remainder 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 que 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 bien expliqué: Il peut arriver que nous suivions un lien suffixe, mettre à jour l'actif point, puis constater que son active_length le composant ne fonctionne bien avec le nouveau active_node. Par exemple, considérez une situation comme ça:

(Les lignes pointillées indiquent le reste de l'arbre. lien suffixe.)

Maintenant, laissez le point actif être (red,'d',3), donc il pointe vers l'endroit derrière la f sur le defg bord. Supposons maintenant que nous avons fait le nécessaire mises à jour et maintenant suivre le lien suffixe pour mettre à jour le point actif selon la règle 3. Le nouveau point actif est (green,'d',3). cependant, la d-de sortir du noeud vert est de, donc il a seulement 2 personnages. Afin de trouver le bon point actif, nous avons évidemment besoin de suivre ce bord au nœud bleu et réinitialiser (blue,'f',1).

Dans un cas particulièrement grave, le active_length pourrait être aussi grand que remainder, qui peut être aussi grand que n. Et ça pourrait très bien arriver que pour trouver le bon point actif, nous devons non seulement sauter par-dessus un nœud interne, mais peut-être beaucoup, jusqu'à n dans le pire des cas. Est-ce que signifie que l'algorithme a un O caché2) complexité, parce que dans chaque étape remainder est généralement O (n), et les post-ajustements au nœud actif après avoir suivi un lien suffixe pourrait être O (n), aussi?

Non. La raison en 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 a son propre lien de suffixe, et active_length va être réduit. Comme nous suivons la chaîne de liens suffixe nous faisons les inserts restants, active_length peut seulement diminuer, et le nombre d'ajustements de point actif, nous pouvons faire sur le chemin ne peut pas être plus grand que active_length n'importe quand. Depuis active_length ne peut jamais être plus grand que remainder, et remainder est O (n) non seulement dans chaque étape, mais la somme totale des incréments jamais fait pour remainder au cours de l'ensemble du processus est O (n) aussi, le nombre d'ajustements de points actifs est également limité par Sur).


2164
2018-03-01 09:13



J'ai essayé d'implémenter l'Arbre Suffixe 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 vais aussi décrire le cas quand on oublie de créer important liens suffixes.

Variables supplémentaires utilisées

  1. point actif - un triplet (noeud_actif, actif_courant; longueur_active), indiquant d'où nous devons commencer à insérer un nouveau suffixe.
  2. reste - montre le nombre de suffixes que nous devons ajouter explicitement. Par exemple, si notre mot est 'abcaabca', et reste = 3, cela signifie que nous devons traiter 3 derniers suffixes: bca, Californie et une.

Utilisons un concept de noeud interne - tous les nœuds, sauf le racine et le leafs sont nœuds internes.

Observation 1

Lorsque le suffixe final que nous devons insérer est déjà présent dans l'arbre, l'arbre lui-même n'est pas modifié du tout (nous ne faisons que active point et remainder).

Observation 2

Si à un moment donné active_length est supérieur ou égal à la longueur du bord courant (edge_length), nous déplaçons notre active point jusqu'à ce que edge_length est strictement supérieur à active_length.

Maintenant, redéfinissons les règles:

Règle 1

Si après une insertion du noeud actif = racine, la longueur active est supérieur à 0, alors:

  1. noeud actif n'est pas changé
  2. longueur active est décrémenté
  3. bord actif est décalé vers la droite (au premier caractère du suffixe suivant nous devons insérer)

Règle 2

Si nous créons une nouvelle noeud interne  OU faire un inséreur d'un noeud interne, et ce n'est pas le premier TEL  noeud interne à l'étape actuelle, nous lions le précédent TEL noeud avec CE un à travers un lien suffixe.

Cette définition du Rule 2 est différent de jogojapan ', car ici nous prenons en compte non seulement nouvellement créé nœuds internes, mais aussi les nœuds internes, à partir de laquelle nous faisons une insertion.

Règle 3

Après un insert de la noeud actif ce qui n'est pas le racine nœud, nous devons suivre le lien suffixe et définir le noeud actif au noeud, il pointe vers. S'il n'y a pas de lien de suffixe, réglez le noeud actif au racine nœud. D'une manière ou d'une autre, bord actif et longueur active reste inchangé.

Dans cette définition de Rule 3 Nous considérons également les inserts des nœuds feuilles (pas seulement les nœuds dédoublés).

Et enfin, observation 3:

Lorsque le symbole que nous voulons ajouter à l'arbre est déjà sur le bord, nous, selon Observation 1, mise à jour uniquement active point et remainder, laissant l'arbre inchangé. MAIS s'il y a un noeud interne marqué comme avoir besoin du lien suffixe, nous devons connecter ce noeud avec notre courant active node à travers un lien suffixe.

Regardons l'exemple d'un arbre de suffixe pour cdddcdc si nous ajoutons un lien suffixe dans un tel cas et si nous ne le faisons pas:

  1. Si nous NE PAS connecter les nœuds via un lien de suffixe:

    • avant d'ajouter la dernière lettre c:

    • après avoir ajouté la dernière lettre c:

  2. Si nous FAIRE connecter les nœuds via un lien de suffixe:

    • avant d'ajouter la dernière lettre c:

    • après avoir ajouté la dernière lettre c:

On dirait qu'il n'y a pas de différence significative: dans le second cas, il y a deux autres liens suffixes. Mais ces liens de suffixe sont correctet l'un d'eux - du nœud bleu au rouge - est très important pour notre approche avec point actif. Le problème est que si nous ne mettons pas un lien 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, parce que, selon lui, s'il n'y a pas de lien suffixe, alors nous devons mettre le active_node à la racine.

Lorsque nous avons ajouté la dernière lettre à l'arbre, le nœud rouge avait déjà existé avant de faire un insert à partir du noeud bleu (le bord marqué 'c'). Comme il y avait un insert du nœud bleu, nous le marquons comme avoir besoin d'un lien suffixe. Ensuite, en s'appuyant sur le point actif approche, le active node a été réglé sur le nœud rouge. Mais nous ne faisons pas un insert du noeud rouge, comme 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 nœud rouge via un lien suffixe. Pourquoi est-ce correct? Parce que le point actif approche garantit que nous arrivons au bon endroit, c'est-à-dire à l'endroit suivant où nous devons traiter un encart d'un plus court suffixe.

Enfin, voici mes implémentations de l'arbre des suffixes:

  1. Java
  2. C ++

Espérons 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 suffixe.


112
2018-01-29 09:57



Merci pour le tutoriel bien expliqué par @jogojapan, J'ai implémenté l'algorithme en Python.

Un couple de problèmes mineurs mentionnés par @jogojapan s'avère être plus sophistiqué que ce à quoi je m'attendais, et j'ai besoin d'être traité très soigneusement. Cela m'a coûté plusieurs jours pour obtenir ma mise en œuvre assez robuste (Je suppose). Les problèmes et les solutions sont énumérés ci-dessous:

  1. Terminer par Remainder > 0 Il se trouve que cette situation peut aussi arriver pendant l'étape de déploiementet pas seulement la fin de tout l'algorithme. Quand cela arrive, nous pouvons laisser le reste, actnode, actedge, et actlength inchangé, terminez l'étape de dépliement en cours et démarrez une autre étape en gardant le pliage ou le dépliage suivant si le caractère suivant dans la chaîne d'origine est sur le chemin courant ou non.

  2. Bond sur les nœuds: Lorsque nous suivons un lien de suffixe, mettez à jour le point actif, puis trouvez que son composant active_length ne fonctionne pas correctement avec le nouveau nœud actif. Nous devons Avance au bon endroit pour diviser, ou insérer une feuille. Ce processus pourrait être pas si simple que ça parce que pendant le mouvement, la longueur et la durée de l'action changent tout le temps, quand vous devez revenir à la Noeud principal, la Acted et actlength pourrait être faux à cause de ces mouvements. Nous avons besoin de variables supplémentaires pour conserver cette information.

    enter image description here

Les deux autres problèmes ont été soulignés par @managonov

  1. Split pourrait dégénérer Lorsque vous essayez de diviser un tronçon, vous verrez parfois que l'opération de division est correcte sur un nœud. Dans ce cas, nous avons seulement besoin d'ajouter une nouvelle feuille à ce noeud, le prendre comme une opération de partage de bord standard, ce qui signifie que les liens de suffixe, s'il y en a, doivent être conservés en conséquence.

  2. Liens de suffixe caché Il y a un autre cas particulier qui est encouru par problème 1 et problème 2. Parfois, nous avons besoin de sauter sur plusieurs nœuds au bon endroit pour diviser, nous pourrions dépasser le bon point si l'on se déplace en comparant la chaîne restante et les étiquettes de chemin. Dans ce cas, le lien suffixe sera négligé involontairement, s'il y en aurait. Cela pourrait être évité par se souvenir du bon point quand aller de l'avant. Le lien de suffixe devrait être maintenu si le noeud de split existe déjà, ou même le problème 1 arrive pendant une étape de déploiement.

Enfin, ma mise en œuvre dans Python est comme suit:

Conseils:  Il comprend un naïf impression d'arbre fonction dans le code ci-dessus, ce qui est très important lors du débogage. Il m'a sauvé beaucoup de   temps et est pratique pour localiser des cas spéciaux.


7
2017-08-02 02:35



Mon intuition est la suivante:

Après k itérations de la boucle principale, vous avez construit un arbre de suffixes qui contient tous les suffixes de la chaîne complète commençant par les k premiers caractères.

Au début, cela signifie que l'arborescence de 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 (string), vous avez un arbre de suffixes qui contient tous les suffixes.

Pendant la boucle, la clé est le point actif. Ma conjecture est que ceci représente le point le plus profond dans l'arbre de suffixe 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 dans l'arborescence que vous obtenez en commençant à l'origine du nœud et en alimentant les caractères en chaîne [first: last]

Lorsque vous ajoutez un nouveau caractère, vous cherchez à 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 de suffixes au point actif, revenir à la correspondance la plus courte suivante et vérifier à nouveau.

Note 1: Les pointeurs de suffixe donnent un lien vers la correspondance la plus courte suivante pour chaque noeud.

Note 2: Lorsque vous ajoutez un nouveau noeud et une nouvelle version, vous ajoutez un nouveau pointeur de suffixe pour le nouveau noeud. La destination de ce pointeur de suffixe sera le noeud au point actif raccourci. Ce noeud existera déjà ou sera créé à l'itération suivante de cette boucle de repli.

Note 3: La partie canonisation permet simplement de gagner du temps en vérifiant le point actif. Par exemple, supposons que vous ayez toujours utilisé origine = 0, et que vous ayez juste changé le premier et le dernier. Pour vérifier le point actif, vous devez suivre l'arbre des suffixes à chaque fois le long des nœuds intermédiaires. Il est logique de mettre en cache le résultat de suivre ce chemin en enregistrant juste la distance du dernier nœud.

Pouvez-vous donner un exemple de code de ce que vous entendez par "fixer" des variables de délimitation?

Avertissement de santé: J'ai également trouvé cet algorithme particulièrement difficile à comprendre, alors s'il vous plaît se rendre compte que cette intuition est susceptible d'être incorrecte dans tous les détails importants ...


6
2018-02-26 20:16



Salut j'ai essayé de mettre en œuvre la mise en œuvre expliquée ci-dessus dans ruby, s'il vous plaît vérifier. Cela semble marcher correctement.

la seule différence dans l'implémentation est que j'ai essayé d'utiliser l'objet edge au lieu de simplement utiliser des symboles.

c'est aussi présent à https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry

3
2018-03-02 10:54



@jogojapan vous avez apporté une explication et une visualisation impressionnantes. Mais comme @makagonov mentionné il manque des règles concernant la définition des liens de suffixe. Il est visible de manière agréable en allant pas à pas sur http://brenden.github.io/ukkonen-animation/ à travers 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 de Java J'ai aussi essayé de suivre votre implémentation pour saisir le workflow de construction de ST, mais c'était dur pour moi à cause de:

  • combiner des arêtes avec des nœuds
  • utilisant des pointeurs d'index au lieu de références
  • casse les déclarations;
  • poursuivre les déclarations;

Je me suis donc retrouvé 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:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}

2
2018-04-21 14:22