[javascript] L'algorithme de l'arbre des suffixes d'Ukkonen en anglais clair



Answers

J'ai essayé de mettre en œuvre 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 du libellé utilisé 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 lorsque nous oublions de créer des liens de suffixes importants .

Variables supplémentaires utilisées

  1. point actif - un triple (noeud_actif; actif_libre; longueur_active), indiquant 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 traiter 3 derniers suffixes: bca , ca et a .

Utilisons un concept de nœud interne - tous les nœuds, sauf la racine et les leafs sont des 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 changé du tout (nous mettons seulement à jour le active point et le remainder ).

Observation 2

Si à un certain point active_length est supérieur ou égal à la longueur du front courant ( edge_length ), nous déplaçons notre active point 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 depuis le noeud actif = root , la longueur active est supérieure à 0, alors:

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

Règle 2

Si nous créons un nouveau noeud interne OU que nous faisons un inserteur à partir d'un noeud interne , et que ce n'est pas le premier noeud interne SUCH à l'étape actuelle, nous lions le noeud SUCH précédent avec celui-ci via un lien suffixe .

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 effectuons une insertion.

Règle 3

Après une insertion depuis le noeud actif qui n'est pas le noeud racine , nous devons suivre le lien du suffixe et définir le noeud actif sur le noeud vers lequel il pointe. S'il n'y a pas de lien de suffixe, définissez le noeud actif sur le noeud racine . Dans tous les cas, le bord actif et la longueur active restent inchangés.

Dans cette définition de la Rule 3 nous considérons également les insertions 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 l' Observation 1 , ne mettons à jour que active point et le remainder , laissant l'arbre inchangé. MAIS s'il y a un nœud interne marqué comme nécessitant un lien suffixe , nous devons connecter ce nœud avec notre active node actuel via un lien 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 connectons pas 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 connectons 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 corrects , et 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 , car, selon lui, s'il y a pas de lien suffixe, alors nous devons mettre le active_node à la racine.

Lorsque nous étions en train d'ajouter la dernière lettre à l'arbre, le nœud rouge existait déjà avant que nous n'effectuions une insertion depuis le nœud bleu (le bord 'c' ). Comme il y avait un insert du noeud bleu, nous le marquons comme ayant besoin d'un lien suffixe . Ensuite, en s'appuyant sur l'approche du point actif , le 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 nœud rouge via un lien suffixe. Pourquoi est-ce correct? Parce que l'approche du point actif 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:

  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.

Question

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 la recherche rapide de chaîne avec des arbres de suffixe , mais il glose sur divers points et certains aspects de l'algorithme restent peu clairs.

Une explication étape par étape de cet algorithme ici sur 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 (n 2 ), 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 du pointeur de suffixe qu'il utilise, bien que je pense que c'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 code source C # complété. 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 en JavaScript . Gist est ci-dessous. Cela devrait être sans bug. Videz-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




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és que ce à quoi je m'attendais et doivent être traités très soigneusement. Cela m'a coûté plusieurs jours pour que ma mise en œuvre soit assez robuste (je suppose). Les problèmes et les solutions sont énumérés ci-dessous:

  1. End with Remainder > 0 Il s'avère que cette situation peut également se produire pendant l'étape de déploiement , et pas seulement la fin de l'algorithme entier. Lorsque cela arrive, nous pouvons laisser le reste, actnode, actted et actlength inchangé , terminer l'étape de dépliement en cours, et commencer une autre étape en gardant le pliage ou le dépliage selon que le prochain caractère de la chaîne d'origine est sur le chemin courant ou ne pas.

  2. Leap Over Nodes: Lorsque nous suivons un lien de suffixe, mettez à jour le point actif, puis trouvez que son composant active_length ne fonctionne pas bien avec le nouveau noeud actif. Nous devons avancer au bon endroit pour diviser, ou insérer une feuille. This process might be not that straightforward because during the moving the actlength and actedge keep changing all the way, when you have to move back to the root node , the actedge and actlength could be wrong because of those moves. We need additional variable(s) to keep that information.

The other two problems have somehow been pointed out by @managonov

  1. Split Could Degenerate When trying to split an edge, sometime you'll find the split operation is right on a node. That case we only need add a new leaf to that node, take it as a standard edge split operation, which means the suffix links if there's any, should be maintained correspondingly.

  2. Hidden Suffix Links There is another special case which is incurred by problem 1 and problem 2 . Sometimes we need to hop over several nodes to the right point for split, we might surpass the right point if we move by comparing the remainder string and the path labels. That case the suffix link will be neglected unintentionally, if there should be any. This could be avoided by remembering the right point when moving forward. The suffix link should be maintained if the split node already exists, or even the problem 1 happens during a unfolding step.

Finally, my implementation in Python is as follows:

Tips: It includes a naive tree printing function in the code above, which is very important while debugging . It saved me a lot of time and is convenient for locating special cases.




@jogojapan you brought awesome explanation and visualisation. But as @makagonov mentioned it's missing some rules regarding setting suffix links. It's visible in nice way when going step by step on http://brenden.github.io/ukkonen-animation/ through word 'aabaaabb'. When you go from step 10 to step 11, there is no suffix link from node 5 to node 2 but active point suddenly moves there.

@makagonov since I live in Java world I also tried to follow your implementation to grasp ST building workflow but it was hard to me because of:

  • combining edges with nodes
  • using index pointers instead of references
  • breaks statements;
  • continue statements;

So I ended up with such implementation in Java which I hope reflects all steps in clearer way and will reduce learning time for other Java people:

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);
        }
    });
  }
}





Related