string suffix - Algoritmo dell'albero del suffisso di Ukkonen in inglese semplice




tree c++ (6)

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


Answers

Ciao ho provato a implementare l'implementazione spiegata sopra in ruby, per favore controlla. Sembra che funzioni bene.

l'unica differenza nell'implementazione è che, ho provato a usare l'oggetto edge invece di usare solo i simboli.

è anche presente su https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[[email protected]_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @[email protected]_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry

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. Questo processo potrebbe non essere così semplice perché durante lo spostamento l'actlength e l'actedge continuano a cambiare fino in fondo, quando si deve tornare al nodo radice , il recto e l' actlength potrebbero essere sbagliati a causa di quei movimenti. Abbiamo bisogno di variabili aggiuntive per mantenere tali informazioni.

Gli altri due problemi sono stati in qualche modo indicati da @managonov

  1. Dividi potrebbe degenerare Quando provi a dividere un bordo, a volte troverai che l'operazione di divisione è proprio su un nodo. In questo caso abbiamo solo bisogno di aggiungere una nuova foglia a quel nodo, prendila come operazione standard di divisione del bordo, il che significa che i collegamenti dei suffissi, se ce ne sono, dovrebbero essere mantenuti in modo corrispondente.

  2. Collegamenti a suffisso nascosto C'è un altro caso speciale che è dovuto al problema 1 e al problema 2 . A volte abbiamo bisogno di saltare su diversi nodi al punto giusto per la divisione, potremmo superare il punto giusto se ci muoviamo confrontando la stringa resto e le etichette del percorso. In tal caso il link del suffisso verrà ignorato involontariamente, se ce ne dovrebbe essere. Questo potrebbe essere evitato ricordando il punto giusto quando vai avanti. Il suffisso link dovrebbe essere mantenuto se il nodo split esiste già, o anche il problema 1 si verifica durante una fase di unfolding.

Infine, la mia implementazione in Python è la seguente:

Suggerimenti: include una funzione di stampa dell'albero naif nel codice sopra, che è molto importante durante il debug . Mi ha risparmiato un sacco di tempo ed è comodo per individuare casi speciali.


@jogojapan hai portato splendide spiegazioni e visualizzazioni. Ma come @makagonov ha menzionato che mancano alcune regole riguardanti l'impostazione dei collegamenti dei suffissi. È visibile in modo carino quando si procede passo dopo passo su http://brenden.github.io/ukkonen-animation/ attraverso la parola 'aabaaabb'. Quando si passa dal punto 10 al passaggio 11, non esiste alcun collegamento suffisso dal nodo 5 al nodo 2, ma il punto attivo si sposta improvvisamente lì.

@ Makagonov da quando vivo nel mondo di Java ho anche provato a seguire la tua implementazione per comprendere il flusso di lavoro ST building, ma è stato difficile per me a causa di:

  • combinando i bordi con i nodi
  • usando indici puntuali invece di riferimenti
  • rompe le dichiarazioni;
  • continuare le dichiarazioni;

Così ho finito con una tale implementazione in Java che spero rispecchi tutti i passaggi in modo più chiaro e ridurrà il tempo di apprendimento per altre persone 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);
        }
    });
  }
}

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, allora 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 inserto dal nodo rosso, poiché 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.


La mia intuizione è la seguente:

Dopo k iterazioni del ciclo principale hai costruito un albero suffisso che contiene tutti i suffissi della stringa completa che iniziano nei primi k caratteri.

All'inizio, ciò significa che l'albero del suffisso contiene un singolo nodo radice che rappresenta l'intera stringa (questo è l'unico suffisso che inizia da 0).

Dopo le iterazioni di len (stringa) hai un albero di suffisso che contiene tutti i suffissi.

Durante il ciclo il tasto è il punto attivo. La mia ipotesi è che questo rappresenti il ​​punto più profondo nell'albero del suffisso che corrisponde a un suffisso appropriato dei primi k caratteri della stringa. (Penso che sia corretto significa che il suffisso non può essere l'intera stringa.)

Ad esempio, supponi di aver visto i caratteri "abcabc". Il punto attivo rappresenterebbe il punto nell'albero corrispondente al suffisso 'abc'.

Il punto attivo è rappresentato da (origine, primo, ultimo). Ciò significa che ti trovi attualmente nel punto dell'albero che trovi iniziando dall'origine del nodo e quindi inserendo i caratteri nella stringa [first: last]

Quando aggiungi un nuovo personaggio, cerchi di vedere se il punto attivo si trova ancora nell'albero esistente. Se è così, hai finito. Altrimenti è necessario aggiungere un nuovo nodo all'albero del suffisso nel punto attivo, eseguire il fallback alla corrispondenza più breve successiva e ricontrollare.

Nota 1: i puntatori del suffisso forniscono un collegamento alla corrispondenza più breve successiva per ciascun nodo.

Nota 2: quando aggiungi un nuovo nodo e un fallback, aggiungi un nuovo puntatore del suffisso per il nuovo nodo. La destinazione di questo puntatore del suffisso sarà il nodo nel punto attivo abbreviato. Questo nodo sarà già esistente o creato alla successiva iterazione di questo ciclo di fallback.

Nota 3: la parte di canonizzazione consente semplicemente di risparmiare tempo nel controllo del punto attivo. Ad esempio, supponi di aver sempre usato origin = 0 e appena cambiato prima e ultima. Per controllare il punto attivo dovresti seguire l'albero del suffisso ogni volta lungo tutti i nodi intermedi. Ha senso memorizzare nella cache il risultato di seguire questo percorso registrando solo la distanza dall'ultimo nodo.

Puoi dare un esempio di codice di cosa intendi per "fissare" le variabili di delimitazione?

Avvertenza sulla salute: ho trovato anche questo algoritmo particolarmente difficile da capire, quindi ti prego di capire che questa intuizione potrebbe non essere corretta in tutti i dettagli importanti ...


Big O descrive la natura di ridimensionamento fondamentale di un algoritmo.

Ci sono molte informazioni che Big O non ti dice su un determinato algoritmo. Tocca all'osso e fornisce solo informazioni sulla natura di ridimensionamento di un algoritmo, in particolare su come l'utilizzo delle risorse (tempo di riflessione o memoria) di un algoritmo si ridimensiona in risposta alla "dimensione di input".

Considera la differenza tra un motore a vapore e un razzo. Non sono semplicemente diverse varietà della stessa cosa (come, diciamo, un motore Prius contro un motore Lamborghini), ma sono sistemi di propulsione radicalmente diversi, al loro centro. Un motore a vapore potrebbe essere più veloce di un razzo giocattolo, ma nessun motore a pistoni a vapore sarà in grado di raggiungere la velocità di un veicolo di lancio orbitale. Questo perché questi sistemi hanno caratteristiche di ridimensionamento differenti rispetto alla relazione del combustibile necessario ("uso delle risorse") per raggiungere una determinata velocità ("dimensione di input").

Perché è così importante? Perché il software si occupa di problemi che possono differire in termini di dimensioni da fattori fino a un trilione. Consideralo per un momento. Il rapporto tra la velocità necessaria per viaggiare sulla Luna e la velocità di camminata umana è inferiore a 10.000: 1, e questo è assolutamente minuscolo rispetto alla gamma in cui il software di dimensioni dell'input potrebbe trovarsi ad affrontare. E poiché il software può affrontare un intervallo astronomico in dimensioni di input, c'è il potenziale per la complessità Big O di un algoritmo, è la natura di ridimensionamento fondamentale, per superare qualsiasi dettaglio di implementazione.

Considera l'esempio di classificazione canonica. Bubble-sort è O (n 2 ) mentre merge-sort è O (n log n). Supponiamo che tu abbia due applicazioni di ordinamento, l'applicazione A che utilizza bubble-sort e l'applicazione B che usa merge-sort, e diciamo che per le dimensioni di input di circa 30 elementi l'applicazione A è 1.000 volte più veloce dell'applicazione B all'ordinamento. Se non devi mai ordinare più di 30 elementi, è ovvio che dovresti preferire l'applicazione A, poiché è molto più veloce con queste dimensioni di input. Tuttavia, se trovi che potresti dover ordinare dieci milioni di elementi, allora quello che ti aspetteresti è che l'applicazione B in realtà in questo caso sia migliaia di volte più veloce dell'applicazione A, interamente a causa del modo in cui ogni algoritmo scala.





string algorithm language-agnostic suffix-tree