[javascript] Algoritmo del árbol de sufijos de Ukkonen en inglés sencillo


Answers

Traté de implementar el Suffix Tree con el enfoque dado en la respuesta de jogojapan, pero no funcionó en algunos casos debido a la redacción utilizada para las reglas. Además, he mencionado que nadie logró implementar un árbol de sufijos absolutamente correcto usando este enfoque. A continuación escribiré un "resumen" de la respuesta de jogojapan con algunas modificaciones a las reglas. También describiré el caso cuando olvidemos crear enlaces de sufijo importantes .

Variables adicionales utilizadas

  1. punto activo - un triple (active_node; active_edge; active_length), que muestra desde donde debemos comenzar a insertar un nuevo sufijo.
  2. resto - muestra el número de sufijos que debemos agregar explícitamente . Por ejemplo, si nuestra palabra es 'abcaabca', y remainder = 3, significa que debemos procesar 3 últimos sufijos: bca , ca y a .

Usemos un concepto de nodo interno : todos los nodos, excepto la raíz y las hojas, son nodos internos .

Observación 1

Cuando se encuentra que el sufijo final que necesitamos insertar ya existe en el árbol, el árbol en sí mismo no se modifica en absoluto (solo actualizamos el active point y el remainder ).

Observación 2

Si en algún momento active_length es mayor o igual a la longitud del borde actual ( edge_length ), movemos nuestro active point hacia abajo hasta que edge_length es estrictamente mayor que active_length .

Ahora, redefinamos las reglas:

Regla 1

Si después de una inserción del nodo activo = raíz , la longitud activa es mayor que 0, entonces:

  1. nodo activo no se cambia
  2. la longitud activa se disminuye
  3. el borde activo se desplaza hacia la derecha (al primer carácter del siguiente sufijo debemos insertarlo)

Regla 2

Si creamos un nuevo nodo interno O hacemos un insertador desde un nodo interno , y este no es el primer nodo interno TAL en el paso actual, entonces vinculamos el anterior SUCHO con ESTO a través de un enlace de sufijo .

Esta definición de la Rule 2 es diferente de jogojapan ', ya que aquí tenemos en cuenta no solo los nodos internos recién creados , sino también los nodos internos, desde los cuales hacemos una inserción.

Regla 3

Después de una inserción desde el nodo activo que no es el nodo raíz , debemos seguir el enlace del sufijo y establecer el nodo activo al nodo al que apunta. Si no hay un enlace de sufijo, configure el nodo activo en el nodo raíz . De cualquier forma, el borde activo y la longitud activa permanecen sin cambios.

En esta definición de la Rule 3 también consideramos los insertos de los nodos de las hojas (no solo los nodos divididos).

Y finalmente, Observación 3:

Cuando el símbolo que queremos agregar al árbol ya está en el borde, nosotros, de acuerdo con la Observation 1 , actualizamos solo active point y el remainder , sin modificar el árbol. PERO si hay un nodo interno marcado como que necesita un enlace de sufijo , debemos conectar ese nodo con nuestro active node actual a través de un enlace de sufijo.

Miremos el ejemplo de un árbol de sufijo para cdddcdc si agregamos un enlace de sufijo en tal caso y si no lo hacemos:

  1. Si NO conectamos los nodos a través de un enlace de sufijo:

    • antes de agregar la última letra c :

    • después de agregar la última letra c :

  2. Si HACEMOS conectar los nodos a través de un enlace de sufijo:

    • antes de agregar la última letra c :

    • después de agregar la última letra c :

Parece que no hay una diferencia significativa: en el segundo caso, hay dos enlaces de sufijo más. Pero estos enlaces de sufijo son correctos , y uno de ellos, desde el nodo azul hasta el rojo, es muy importante para nuestro enfoque con el punto activo . El problema es que si no ponemos un enlace de sufijo aquí, más adelante, cuando agreguemos algunas letras nuevas al árbol, podríamos omitir agregar algunos nodos al árbol debido a la Rule 3 , porque, de acuerdo con esto, si hay no hay un sufijo, entonces debemos poner el active_node en la raíz.

Cuando estábamos agregando la última letra al árbol, el nodo rojo ya existía antes de que hiciéramos una inserción desde el nodo azul (el borde etiquetado como 'c' ). Como había un inserto del nodo azul, lo marcamos como necesitar un enlace de sufijo . Luego, dependiendo del enfoque del punto activo , el active node se estableció en el nodo rojo. Pero no hacemos una inserción desde el nodo rojo, ya que la letra 'c' ya está en el borde. ¿Significa que el nodo azul debe quedar sin un sufijo? No, debemos conectar el nodo azul con el rojo a través de un enlace de sufijo. ¿Por qué es correcto? Porque el enfoque del punto activo garantiza que lleguemos a un lugar correcto, es decir, al siguiente lugar donde debemos procesar un inserto de un sufijo más corto .

Finalmente, aquí están mis implementaciones del Suffix Tree:

  1. Java
  2. C++

Espero que este "resumen" combinado con la respuesta detallada de jogojapan ayude a alguien a implementar su propio Árbol de sufijos.

Question

Me siento un poco grueso en este punto. He pasado varios días tratando de entender completamente la construcción del árbol de sufijos, pero debido a que no tengo conocimientos matemáticos, muchas de las explicaciones me eluden cuando empiezan a hacer un uso excesivo de la simbología matemática. Lo más parecido a una buena explicación que he encontrado es Fast String Searching With Suffix Trees , pero pasa por alto varios puntos y algunos aspectos del algoritmo siguen sin estar claros.

Una explicación paso a paso de este algoritmo aquí en sería invaluable para muchos otros además de mí, estoy seguro.

Como referencia, aquí está el artículo de Ukkonen sobre el algoritmo: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Mi entendimiento básico, hasta ahora:

  • Necesito iterar a través de cada prefijo P de una cadena dada T
  • Necesito iterar a través de cada sufijo S en el prefijo P y agregar eso al árbol
  • Para agregar el sufijo S al árbol, necesito iterar a través de cada carácter en S, con las iteraciones que consisten en caminar por una rama existente que comienza con el mismo conjunto de caracteres C en S y potencialmente dividir un borde en nodos descendientes cuando alcanzar un carácter diferente en el sufijo, O si no había un borde coincidente para caminar hacia abajo. Cuando no se encuentra un borde coincidente para bajar hacia C, se crea un nuevo borde de hoja para C.

El algoritmo básico parece ser O (n 2 ), como se señala en la mayoría de las explicaciones, ya que necesitamos pasar por todos los prefijos, luego tenemos que pasar por cada sufijo para cada prefijo. El algoritmo de Ukkonen es aparentemente único debido a la técnica de puntero de sufijo que usa, aunque creo que eso es lo que tengo problemas para entender.

También estoy teniendo problemas para entender:

  • exactamente cuándo y cómo se asigna, usa y cambia el "punto activo"
  • qué está pasando con el aspecto de canonización del algoritmo
  • Por qué las implementaciones que he visto necesitan para "arreglar" las variables de delimitación que están utilizando

Aquí está el código fuente completo de C # . No solo funciona correctamente, sino que también admite la canonización automática y ofrece un gráfico de texto de aspecto más agradable de la salida. El código fuente y el resultado de la muestra están en:

https://gist.github.com/2373868

Actualización 2017-11-04

Después de muchos años, he encontrado un nuevo uso para árboles de sufijos y he implementado el algoritmo en JavaScript . Gist está abajo. Debería estar libre de errores. Viértalo en un archivo js, npm install chalk en la misma ubicación y luego ejecútelo con node.js para ver resultados coloridos. Hay una versión simplificada en el mismo Gist, sin ningún código de depuración.

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




Gracias por el tutorial bien explicado por @jogojapan , implementé el algoritmo en Python.

Un par de problemas menores mencionados por @jogojapan resultan ser más sofisticados de lo que esperaba, y deben ser tratados con mucho cuidado. Me costó varios días lograr que mi implementación fuera lo suficientemente robusta (supongo). Los problemas y las soluciones se enumeran a continuación:

  1. End with Remainder > 0 Resulta que esta situación también puede ocurrir durante el paso de despliegue , no solo al final de todo el algoritmo. Cuando eso sucede, podemos dejar el resto, actnode, actedge, y actlength sin cambios , finalizar el paso de despliegue actual y comenzar otro paso manteniendo plegado o desplegado dependiendo de si el siguiente carácter en la cadena original está en la ruta actual o no.

  2. Salto sobre nodos: cuando seguimos un enlace de sufijo, actualizamos el punto activo y luego descubrimos que su componente active_length no funciona bien con el nuevo active_node. Tenemos que avanzar hacia el lugar correcto para dividir o insertar una hoja. 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