Algorithme de l'arbre de suffixe d'Ukkonen en anglais simple

j'ai essayé de mettre en œuvre l'Arbre de Suffixe avec l'approche donnée dans la réponse de jogojapan, mais cela n'a pas fonctionné pour 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 suffixe 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 également décrire le cas lorsque nous oublions de créer important suffixe des liens.

variables supplémentaires utilisées

1. active point - un triple (active_node; active_edge; active_length), montrant d'où nous devons commencer à insérer un nouveau suffixe.
2. reste - indique le nombre de suffixes que nous devons ajouter explicitement . Par exemple, si notre mot est "abcaabca", et reste = 3, cela signifie que nous devons processus 3 derniers suffixes: bca , ca et un .

utilisons le concept d'un noeud interne - tous les noeuds, sauf le racine et le leafs sont noeuds internes .

Observation 1

lorsque le suffixe final que nous devons insérer se trouve déjà exister dans l'arbre, l'arbre lui-même n'est pas changé du tout (nous ne mettons à jour que les active point et remainder ).

Observation 2

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

maintenant, redéfinissons les règles:

Règle 1

si après une insertion à partir du noeud actif = root , la longueur active est supérieure à 0, alors:

1. nœud actif n'est pas modifiée
2. longueur active est décrémenté
3. Active edge est décalé à droite (au premier caractère du suffixe suivant il faut insérer)

règle 2

Si nous créons un nouveau noeud interne OU faire une insertion d'un noeud interne , et ce n'est pas le d'abord tel noeud interne à l'étape actuelle, puis nous relions le précédent tel noeud avec ce un à travers un lien suffixe .

cette définition du Rule 2 est différente de jogojapan', car ici nous prenons en compte non seulement le nouvellement créé noeuds internes, mais aussi les noeuds internes, à partir de laquelle nous faire une insertion.

Règle 3

après un insert du noeud actif qui n'est pas le root noeud, nous devons suivre le lien de suffixe et mettre le noeud actif au noeud qu'il pointe. S'il n'y a pas de lien de suffixe, définissez le noeud actif au noeud racine . De toute façon, active bord et longueur restent inchangées.

dans cette définition de Rule 3 nous considérons également les inserts de noeuds foliaires (pas seulement Split-nodes).

et enfin, Observation 3:

lorsque le symbole que nous voulons ajouter à l'arbre est déjà sur le bord, nous , selon Observation 1 , mettre à jour seulement active point et remainder , laissant l'arbre inchangé. mais s'il y a un noeud interne marqué comme ayant besoin d'une liaison de suffixe , nous devons connecter ce noeud avec notre active node actuel par une liaison de suffixe.

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

1. Si nous NE PAS connecter les nœuds grâce à un suffixe lien:

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

   

   • après l'ajout de la dernière lettre c :

   

2. Si nous FAIRE connecter les nœuds grâce à un suffixe lien:

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

   

   • après l'ajout de la dernière lettre c :

   

semble comme il n'y a pas de différence significative: dans le deuxième cas il y a deux liens de suffixe supplémentaires. Mais ces liens de suffixe sont correct , et l'un d'eux - du noeud bleu au noeud rouge - est très important pour notre approche avec point actif . Le problème est que si nous ne mettons pas de lien de suffixe ici, plus tard, quand nous ajoutons de nouvelles lettres à l'arbre, nous pourrions omettre d'ajouter des noeuds à l'arbre en raison de le Rule 3 , parce que, selon lui, s'il n'y a pas de lien de suffixe, alors nous devons mettre le active_node à la racine.

lorsque nous avons ajouté la dernière lettre à l'arbre, le noeud rouge avait déjà existé avant que nous avons fait un insert à partir du noeud bleu (le bord a câblé 'c' ). Comme il y avait un insert du noeud bleu, nous le marquons comme nécessitant un lien de suffixe . Puis, en s'appuyant sur la point actif approche, le active node a été placé sur le nœud rouge. Mais nous ne faisons pas un insert à partir du noeud rouge, comme la lettre 'c' est déjà sur le bord. Signifie que le noeud bleu doit être laissé sans un suffixe lien? Non, nous devons connecter le noeud bleu avec le noeud rouge à travers un lien de suffixe. Pourquoi est-il correct? Parce que l'approche point actif garantit que nous arrivons à un bon endroit, i.e., à la place suivante où nous devons traiter un insert d'un suffixe plus court .

enfin, voici mes implémentations de L'Arbre de suffixe:

1. Java
2. C++

espère que cette" vue d'ensemble " combinée avec la réponse détaillée de jogojapan aidera quelqu'un à mettre en œuvre son propre arbre de suffixe.

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

quelques problèmes mineurs mentionnés par @jogojapan s'avèrent être plus sophistiqué que je ne m'y attendais, et doivent être traités avec beaucoup de soin. Il m'a fallu plusieurs jours pour obtenir mon implémentation assez robuste (je suppose). Les problèmes et les solutions sont énumérés ci-dessous:

1. fin avec Remainder > 0 il s'avère que cette situation peut également se produire pendant l'étape de déploiement , pas seulement la fin de l'algorithme entier. Lorsque cela se produit, nous pouvons laisser le reste, actnode, actedge, et actlength inchangé , mettre fin à l'étape de déploiement en cours, et commencer une autre étape en continuant à se plier ou à se déployer en fonction de si le prochain char dans la chaîne d'origine est sur le chemin d'accès actuel ou pas.

2. sautez au-dessus des Noeuds: lorsque nous suivons un lien de suffixe, mettez à jour le point actif, puis découvrez que son composant active_length ne fonctionne pas bien avec le nouveau code active_node. Nous devons aller de l'avant au bon endroit pour fendre, ou insérer une feuille. Ce processus pourrait être pas si simple parce que pendant le déplacement l'actlength et actedge garder en changeant tout le chemin, quand vous devez revenir au noeud de racine , le actedge et actlength pourrait être faux en raison de ces mouvements. Nous avons besoin de variables supplémentaires pour conserver cette information.

   

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

3. Split pourrait dégénérer en essayant de diviser un bord, parfois vous trouverez l'opération de split est juste sur un noeud. Dans ce cas, nous avons seulement besoin d'ajouter une nouvelle feuille à ce noeud, prenez-le comme une opération standard edge split, ce qui signifie que les liens de suffixe s'il y en a, doivent être maintenus en conséquence.

4. Liens De Suffixe Cachés 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 noeuds au bon point pour split, nous pourrions surpasser le bon point si nous nous déplaçons en comparant la chaîne du reste et les étiquettes de chemin. Dans ce cas, la liaison de suffixe sera négligée involontairement, s'il y en a une. Cela pourrait être évité en en se rappelant le bon point en avançant. Le lien de suffixe doit être maintenu si le noeud divisé existe déjà, ou même le problème 1 se produit pendant une étape de déploiement.

enfin, mon implémentation dans Python est la suivante:

• Python

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

mon intuition est la suivante:

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

au début, cela signifie que l'arbre de suffixe contient un seul noeud 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 suffixe qui contient tous les suffixes.

pendant la boucle la clé est le point actif. À mon avis, cela représente le point le plus profond de l'arbre des suffixe qui correspond à un suffixe correct des premiers caractères k de la chaîne. (Je pense qu'être correct signifie que le suffixe ne peut pas être la chaîne entière.)

par exemple, supposons que vous ayez vu les caractères 'abcabc'. Le point actif représentent le point de 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'arbre où vous arrivez en commençant à l'origine du noeud et puis en vous alimentant dans les caractères dans la chaîne [premier: dernier]

quand vous ajoutez un nouveau caractère, vous regardez pour voir si le point actif est toujours dans l'arbre existant. Si c'est pour que vous vous êtes fait. Sinon, vous devez ajouter un nouveau noeud à l'arbre de suffixe au point actif, repli à la prochaine correspondance la plus courte, et vérifier de 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 nœud et de secours vous ajoutez un nouveau suffixe pointeur pour le nouveau nœud. La destination de ce pointeur de suffixe sera le noeud au point actif raccourci. Ce noeud existera déjà, ou sera créé lors de la prochaine itération de cette boucle de repli.

Note 3: la partie de canonisation sauve simplement il est temps de vérifier le point actif. Par exemple, supposons que vous utilisiez toujours origin=0, et que vous changiez juste le premier et le dernier. Pour vérifier le point actif, vous devez suivre l'arbre de suffixe à chaque fois le long de tous les noeuds intermédiaires. Il est logique de mettre en cache le résultat de suivre ce chemin en n'enregistrant que la distance du dernier noeud.

pouvez-vous donner un exemple de code de ce que vous entendez par" corriger " les variables limitatives?

mise en garde: j'ai aussi trouvé ceci algorithme particulièrement difficile à comprendre merci donc de réaliser que cette intuition est susceptible d'être incorrecte dans tous les détails importants...

Salut j'ai essayé de mettre en œuvre l'implémentation expliquée ci-dessus dans ruby , s'il vous plaît vérifier. il semble bien fonctionner.

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.

il est aussi présent au 151960920" 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

@jogojapan vous avez apporté des explications impressionnantes et la visualisation. Mais comme @makagonov mentionné il manque quelques règles concernant le suffixe de liens. Il est visible de manière agréable en allant pas à pas sur http://brenden.github.io/ukkonen-animation / par le mot "aabaaabb". Lorsque vous passez de l'étape 10 à l'étape 11, Il n'y a pas de lien de suffixe du noeud 5 au noeud 2 mais le point actif se déplace soudainement là.

@makagonov depuis que je vis à Java world I j'ai aussi essayé de suivre votre implémentation pour saisir le flux de travail du bâtiment ST, mais c'était difficile pour moi à cause de:

• combinaison d'arêtes et de noeuds
• utilisant des pointeurs d'index au lieu de références
• pauses consolidés;
• suite déclarations;

donc j'ai fini avec une telle implémentation en Java qui, je l'espère, reflète toutes les étapes d'une manière plus claire et permettra de réduire le temps d'apprentissage pour les autres habitants de 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);
        }
    });
  }
}