string El algoritmo del árbol de sufijos de Ukkonen en inglés simple





3 Answers

Intenté implementar el Árbol de sufijos 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 utilizando este enfoque. A continuación escribiré una "descripción general" de la respuesta de jogojapan con algunas modificaciones a las reglas. También describiré el caso cuando olvidemos crear enlaces con sufijos 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 el resto = 3, significa que debemos procesar 3 últimos sufijos: bca , ca y a .

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

Observación 1

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

Observación 2

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

Ahora, vamos a redefinir las reglas:

Regla 1

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

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

Regla 2

Si creamos un nuevo nodo interno O creamos un insertador desde un nodo interno , y este no es el primer nodo interno de TAL en el paso actual, entonces vinculamos el nodo TAL anterior con ESTE 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 en el nodo al que apunta. Si no hay un enlace de sufijo, establezca el nodo activo en el nodo raíz . De cualquier manera, el borde activo y la longitud activa permanecen sin cambios.

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

Y finalmente, la 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 enlace de sufijo , debemos conectar ese nodo con nuestro active node actual a través de un enlace de sufijo.

Veamos el ejemplo de un árbol de sufijos 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 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 :

Parece que no hay una diferencia significativa: en el segundo caso hay dos enlaces de sufijo más. Pero estos enlaces de sufijos son correctos , y uno de ellos, desde el nodo azul al 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, según este, si hay no hay un enlace de sufijo, entonces debemos poner el active_node a 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 marcado como 'c' ). Como había una inserción del nodo azul, lo marcamos como que necesita un enlace de sufijo . Luego, confiando en el enfoque de 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 enlace de sufijo? No, debemos conectar el nodo azul con el rojo a través de un enlace de sufijo. ¿Por qué es correcto? Debido a que el enfoque de punto activo garantiza que lleguemos al lugar correcto, es decir, al siguiente lugar donde debemos procesar una inserción de un sufijo más corto .

Finalmente, aquí están mis implementaciones del Árbol de Sufijo:

  1. Java
  2. C++

Espero que esta "visión general" combinada con la respuesta detallada de jogojapan ayude a alguien a implementar su propio árbol de sufijos.

string algorithm language-agnostic suffix-tree

Me siento un poco grueso en este punto. He pasado días tratando de envolver por completo mi cabeza alrededor de la construcción del árbol de sufijos, pero debido a que no tengo una base matemática, muchas de las explicaciones se me escapan cuando comienzan a usar la simbología matemática en forma excesiva. Lo más cercano a una buena explicación que he encontrado es la búsqueda rápida de cadenas con árboles de sufijos , pero él 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.

Para 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 recorrer cada prefijo P de una cadena dada T
  • Necesito iterar a través de cada sufijo S en el prefijo P y agregarlo al árbol
  • Para agregar el sufijo S al árbol, debo recorrer 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 descendentes cuando yo 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 debemos pasar por cada uno de los sufijos para cada prefijo. El algoritmo de Ukkonen es aparentemente único debido a la técnica de puntero de sufijo que utiliza, aunque creo que eso es lo que me cuesta entender.

También estoy teniendo problemas para entender:

  • exactamente cuándo y cómo se asigna, utiliza y cambia el "punto activo"
  • ¿Qué está pasando con el aspecto de canonización del algoritmo?
  • Por qué las implementaciones que he visto necesitan "arreglar" las variables de límite que están usando

Aquí está el código fuente de C # completado. 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. El código fuente y la salida de 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 los árboles de sufijos y he implementado el algoritmo en JavaScript . La esencia está abajo. Debe estar libre de errores. Volcarlo en un archivo js, npm install chalk desde la misma ubicación, y luego ejecuta con node.js para ver algunos 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




Mi intuición es la siguiente:

Después de k iteraciones del bucle principal, ha construido un árbol de sufijos que contiene todos los sufijos de la cadena completa que comienzan en los primeros k caracteres.

Al principio, esto significa que el árbol de sufijos contiene un solo nodo raíz que representa la cadena completa (este es el único sufijo que comienza en 0).

Después de las iteraciones len (cadena), tiene un árbol de sufijos que contiene todos los sufijos.

Durante el bucle la clave es el punto activo. Supongo que esto representa el punto más profundo en el árbol de sufijos que corresponde a un sufijo adecuado de los primeros k caracteres de la cadena. (Creo que correcto significa que el sufijo no puede ser la cadena completa).

Por ejemplo, supongamos que has visto los caracteres 'abcabc'. El punto activo representaría el punto en el árbol correspondiente al sufijo 'abc'.

El punto activo está representado por (origen, primero, último). Esto significa que se encuentra actualmente en el punto del árbol al que comienza al iniciar el origen del nodo y luego ingresando los caracteres en la cadena [primero: último]

Cuando agrega un nuevo carácter, observa si el punto activo todavía está en el árbol existente. Si es así, has terminado. De lo contrario, debe agregar un nuevo nodo al árbol de sufijos en el punto activo, retroceder a la siguiente coincidencia más corta y volver a verificar.

Nota 1: Los punteros de sufijo proporcionan un enlace a la siguiente coincidencia más corta para cada nodo.

Nota 2: cuando agrega un nuevo nodo y retrocede, agrega un nuevo puntero de sufijo para el nuevo nodo. El destino para este puntero de sufijo será el nodo en el punto activo acortado. Este nodo ya existirá o se creará en la próxima iteración de este bucle de reserva.

Nota 3: La parte de canonización simplemente ahorra tiempo al verificar el punto activo. Por ejemplo, supongamos que siempre ha utilizado origin = 0 y que acaba de cambiar primero y último. Para verificar el punto activo, tendría que seguir el árbol de sufijos cada vez a lo largo de todos los nodos intermedios. Tiene sentido almacenar en caché el resultado de seguir esta ruta al registrar solo la distancia desde el último nodo.

¿Puede dar un ejemplo de código de lo que quiere decir con "arreglar" las variables de límite?

Advertencia de salud: también encontré este algoritmo particularmente difícil de entender, así que tenga en cuenta que es probable que esta intuición sea incorrecta en todos los detalles importantes ...




@jogojapan trajiste asombrosa explicación y visualización. Pero, como mencionó @makagonov, faltan algunas reglas con respecto a la configuración de enlaces de sufijo. Es visible de una manera agradable al pasar paso a paso en http://brenden.github.io/ukkonen-animation/ través de la palabra 'aabaaabb'. Cuando se pasa del paso 10 al paso 11, no hay un vínculo de sufijo del nodo 5 al nodo 2, pero el punto activo se mueve de repente allí.

@makagonov ya que vivo en el mundo de Java, también intenté seguir su implementación para comprender el flujo de trabajo de construcción de ST, pero fue difícil para mí debido a:

  • combinando aristas con nodos
  • utilizando punteros de índice en lugar de referencias
  • rompe declaraciones;
  • continuar las declaraciones;

Así que terminé con una implementación en Java que espero que refleje todos los pasos de manera más clara y reduzca el tiempo de aprendizaje para otras personas 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);
        }
    });
  }
}



Related