[javascript] Algoritmo dell'albero del suffisso di Ukkonen in inglese semplice


Answers

Ho cercato di implementare l'albero del suffisso con l'approccio dato nella risposta di jogojapan, ma per alcuni casi non ha funzionato a causa del testo usato per le regole. Inoltre, ho menzionato che nessuno è riuscito a implementare un albero di suffisso assolutamente corretto utilizzando questo approccio. Di seguito scriverò una "panoramica" della risposta di jogojapan con alcune modifiche alle regole. Descriverò anche il caso in cui dimentichiamo di creare collegamenti suffisso importanti .

Altre variabili utilizzate

  1. punto attivo : una tripla (active_node; active_edge; active_length), che mostra da dove dobbiamo iniziare a inserire un nuovo suffisso.
  2. resto - mostra il numero di suffissi che dobbiamo aggiungere esplicitamente . Ad esempio, se la nostra parola è "abcaabca" e resto = 3, significa che dobbiamo elaborare 3 ultimi suffissi: bca , ca e a .

Usiamo un concetto di nodo interno : tutti i nodi, eccetto la radice e le foglie sono nodi interni .

Osservazione 1

Quando il suffisso finale che dobbiamo inserire è già presente nell'albero, l'albero stesso non viene affatto modificato (aggiorniamo solo il active point e il remainder ).

Osservazione 2

Se ad un certo punto active_length è maggiore o uguale alla lunghezza del bordo corrente ( edge_length ), spostiamo il nostro active point verso il basso finché edge_length è strettamente maggiore di active_length .

Ora, ridefiniamo le regole:

Regola 1

Se dopo un inserimento dal nodo attivo = root , la lunghezza attiva è maggiore di 0, quindi:

  1. il nodo attivo non è cambiato
  2. la lunghezza attiva è decrementata
  3. il bordo attivo è spostato a destra (al primo carattere del suffisso successivo che dobbiamo inserire)

Regola 2

Se creiamo un nuovo nodo interno OPPURE facciamo un inseritore da un nodo interno , e questo non è il primo nodo interno SUCH al passo corrente, quindi colleghiamo il precedente nodo SUCH con QUESTO attraverso un collegamento suffisso .

Questa definizione della Rule 2 è diversa da jogojapan ', in quanto qui prendiamo in considerazione non solo i nodi interni appena creati , ma anche i nodi interni, dai quali facciamo un inserimento.

Regola 3

Dopo un inserimento dal nodo attivo che non è il nodo radice , dobbiamo seguire il link suffisso e impostare il nodo attivo sul nodo a cui punta. Se non esiste un collegamento suffisso, impostare il nodo attivo sul nodo radice . In entrambi i casi, il fronte attivo e la lunghezza attiva rimangono invariati.

In questa definizione della Rule 3 consideriamo anche gli inserti dei nodi foglia (non solo i nodi split).

E infine, l'osservazione 3:

Quando il simbolo che vogliamo aggiungere all'albero è già sul bordo, noi, secondo l' Observation 1 , aggiorniamo solo il active point e il remainder , lasciando l'albero invariato. MA se c'è un nodo interno contrassegnato come bisessante , è necessario connettere quel nodo con il nostro active node corrente tramite un collegamento suffisso.

Diamo un'occhiata all'esempio di un albero di suffisso per cdddcdc se aggiungiamo un suffisso in questo caso e se non lo facciamo:

  1. Se NON connettiamo i nodi tramite un suffisso link:

    • prima di aggiungere l'ultima lettera c :

    • dopo aver aggiunto l'ultima lettera c :

  2. Se colleghiamo i nodi tramite un suffisso link:

    • prima di aggiungere l'ultima lettera c :

    • dopo aver aggiunto l'ultima lettera c :

Sembra che non ci siano differenze significative: nel secondo caso ci sono altri due link suffix. Ma questi collegamenti suffisso sono corretti , e uno di loro - dal nodo blu a quello rosso - è molto importante per il nostro approccio con il punto attivo . Il problema è che se non inseriamo qui un link suffisso, più tardi, quando aggiungiamo alcune nuove lettere all'albero, potremmo omettere di aggiungere alcuni nodi all'albero a causa della Rule 3 , perché, secondo esso, se c'è nessun link suffisso, quindi dobbiamo inserire il active_node nella root.

Quando stavamo aggiungendo l'ultima lettera all'albero, il nodo rosso esisteva già prima di creare un inserto dal nodo blu (il bordo etichettato 'c' ). Dato che c'era un inserto dal nodo blu, lo contrassegniamo come se avessimo bisogno di un suffisso link . Quindi, basandosi sull'approccio a punto attivo , il active node stato impostato sul nodo rosso. Ma non facciamo un inserimento dal nodo rosso, dato che la lettera "c" è già sul bordo. Significa che il nodo blu deve essere lasciato senza un suffisso link? No, dobbiamo collegare il nodo blu con quello rosso attraverso un link suffisso. Perché è corretto? Perché l'approccio punto attivo garantisce che arriviamo al posto giusto, cioè al prossimo posto in cui dobbiamo elaborare un inserto di un suffisso più corto .

Infine, ecco le mie implementazioni dell'albero del suffisso:

  1. Java
  2. C++

Spero che questa "panoramica" combinata con la risposta dettagliata di jogojapan aiuterà qualcuno a implementare il proprio Suffix Tree.

Question

Mi sento un po 'grosso a questo punto. Ho passato giorni a cercare di avvolgere completamente la mia testa attorno alla costruzione dell'albero del suffisso, ma poiché non ho uno sfondo matematico, molte delle spiegazioni mi sfuggono mentre iniziano a fare un uso eccessivo della simbologia matematica. Il più vicino ad una buona spiegazione che ho trovato è Fast String Searching With Suffix Trees , ma egli glossa su vari punti e alcuni aspetti dell'algoritmo rimangono poco chiari.

Una spiegazione dettagliata di questo algoritmo qui su sarebbe inestimabile per molti altri oltre a me, ne sono sicuro.

Per riferimento, ecco il documento di Ukkonen sull'algoritmo: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

La mia comprensione di base, finora:

  • Ho bisogno di scorrere ogni prefisso P di una data stringa T
  • Ho bisogno di scorrere ogni suffisso S nel prefisso P e aggiungerlo all'albero
  • Per aggiungere il suffisso S all'albero, ho bisogno di scorrere ogni carattere in S, con le iterazioni consistenti nel camminare su un ramo esistente che inizia con lo stesso set di caratteri C in S e potenzialmente dividere un bordo in nodi discendenti quando io raggiungere un carattere diverso nel suffisso, OPPURE se non vi era alcun bordo corrispondente da calpestare. Quando non viene trovato alcun bordo corrispondente che cammina per C, viene creato un nuovo bordo foglia per C.

L'algoritmo di base sembra essere O (n 2 ), come indicato nella maggior parte delle spiegazioni, poiché è necessario scorrere tutti i prefissi, quindi è necessario scorrere ciascuno dei suffissi per ciascun prefisso. L'algoritmo di Ukkonen è apparentemente unico a causa della tecnica del puntatore suffisso che usa, anche se penso che sia quello che ho difficoltà a capire.

Ho anche difficoltà a capire:

  • esattamente quando e come il "punto attivo" è assegnato, utilizzato e modificato
  • cosa sta succedendo con l'aspetto della canonizzazione dell'algoritmo
  • Perché le implementazioni che ho visto devono "aggiustare" le variabili che stanno usando

Ecco il codice sorgente C # completo. Funziona non solo correttamente, ma supporta la canonizzazione automatica e rende un grafico di testo dall'aspetto più gradevole all'output. Il codice sorgente e l'output del campione sono a:

https://gist.github.com/2373868

Aggiornamento 2017-11-04

Dopo molti anni ho trovato un nuovo uso per gli alberi dei suffissi e ho implementato l'algoritmo in JavaScript . Gist è sotto. Dovrebbe essere privo di bug. npm install chalk in un file js, npm install chalk dalla stessa posizione, quindi esegui node.js per vedere un po 'di output colorato. C'è una versione ridotta nello stesso Gist, senza alcun codice di debug.

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




Grazie per il tutorial ben spiegato da @jogojapan , ho implementato l'algoritmo in Python.

Un paio di problemi minori menzionati da @jogojapan si rivelano più sofisticati di quanto mi aspettassi e devono essere trattati con molta attenzione. Mi è costato diversi giorni per avere la mia implementazione abbastanza robusta (suppongo). I problemi e le soluzioni sono elencati di seguito:

  1. End with Remainder > 0 Risulta che questa situazione può verificarsi anche durante la fase di unfolding , non solo alla fine dell'intero algoritmo. Quando ciò accade, possiamo lasciare il resto, actnode, actedge e actlength immutati , terminare il passaggio di unfolding corrente e iniziare un altro passo continuando a piegare o spiegare a seconda se il prossimo char nella stringa originale si trova sul percorso corrente o non.

  2. Salta i nodi: quando seguiamo un collegamento suffisso, aggiorna il punto attivo e poi scopri che il suo componente active_length non funziona bene con il nuovo active_node. Dobbiamo andare avanti nel posto giusto per dividere o inserire una foglia. 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