en langage pur

Question

Je me sens un peu d'épaisseur à ce point. J'ai passé des jours à essayer de complètement envelopper ma tête autour de suffixe de la construction de l'arbre, mais parce que je n'ai pas de connaissances en mathématiques, de nombreuses explications échapper à moi comme ils commencent à faire usage excessif de la mathématique, de la symbologie. Le plus proche d'une bonne explication que j'ai trouvé est Rapide de Chaîne de Recherche Avec le Suffixe Arbres, mais il glisse sur divers points et certains aspects de l'algorithme restent floues.

Une étape-par-étape de l'explication de cet algorithme, ici, sur un Débordement de Pile serait inestimable pour beaucoup d'autres d'ailleurs moi, j'en suis sûr.

Pour référence, voici Ukkonen du papier sur l'algorithme: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Mon idée de base, jusqu'à présent:

• J'ai besoin pour itérer sur chaque préfixe P d'une chaîne de T
• J'ai besoin pour itérer sur chaque suffixe S en préfixe P et l'ajouter à l'arbre
• Pour ajouter le suffixe S de l'arbre, j'ai besoin d'itérer sur chaque personnage en S, avec les itérations consistant, soit en marchant vers le bas une branche qui commence avec le même jeu de caractères C à S et, potentiellement, le fractionnement d'un bord en descendant les nœuds quand j'atteins un caractère différent dans le suffixe, OU si il n'y a pas de correspondance bord de marcher vers le bas. Lorsque l'absence de correspondance bord est trouvé à pied vers le bas pour le C, une nouvelle feuille de bord est créé pour C.

L'algorithme de base semble être en O(n²), comme il est indiqué dans la plupart des explications, que nous avons besoin de tous les préfixes, nous avons besoin à l'étape par le biais de chacun des suffixes pour chaque préfixe. L'algorithme d'Ukkonen, apparemment, est unique en raison de l'suffixe pointeur de la technique qu'il utilise, mais je pense que c' est ce que je vais avoir du mal à comprendre.

Je suis aussi de la difficulté à comprendre:

• exactement quand et comment le "point actif" est attribué, utilisés et modifiés
• ce qui se passe avec la canonisation aspect de l'algorithme
• Pourquoi les implémentations j'ai vu le besoin de "fixer" la délimitation des variables qu'ils sont à l'aide de

---

EDIT (13 avril 2012)

Ici est le code source que j'ai écrit et de sortie sur la base jogojapan la réponse ci-dessous. Le code affiche une description détaillée et basée sur le texte diagramme des étapes nécessaires, car il s'inspire de l'arbre. C'est une première version et pourrait probablement le faire avec l'optimisation et ainsi de suite, mais cela fonctionne, ce qui est la chose principale.

[Edite URL, voir mise à jour du lien ci-dessous]

EDIT (15 avril 2012)

Le code source a été complètement réécrit à partir de zéro et maintenant, non seulement fonctionne correctement, mais il prend en charge automatique de la canonisation, ce qui le rend plus agréable à la recherche de texte graphique de la sortie. Le code Source et l'échantillon de sortie:

https://gist.github.com/2373868

Answer 1

J'ai essayé de mettre en œuvre le Suffixe de l'Arbre avec l'approche adoptée dans jogojapan réponse, mais il ne fonctionne pas pour certains cas, en raison de la formulation utilisée pour les règles. En outre, j'ai mentionné que personne n'a réussi à mettre en œuvre absolument correcte, suffixe de l'arbre à l'aide de cette approche. Ci-dessous, je vais écrire une "vue d'ensemble" de jogojapan réponse avec quelques modifications aux règles. Je décrirai également le cas lorsque nous oubliez pas de créer d'importantes suffixe liens.

L'ajout des variables utilisées

1. point actif - une chambre triple (active_node; active_edge; active_length), démontrant par là que nous devons commencer à insérer un nouveau suffixe.
2. reste - indique le nombre de suffixes nous devons ajouter explicitement. Par exemple, si notre parole est "abcaabca', et le reste = 3, cela signifie que nous devons processus 3 derniers suffixes: bca, ca et un.

Nous allons utiliser un concept d'un noeud interne - tous les nœuds, à l'exception de la racine et les feuilles sont les nœuds internes.

Observation 1

Lors de la finale de suffixe, nous avons besoin d'insérer existe dans l'arbre, l'arbre lui-même n'est pas du tout changé (nous n'mise à jour de l' active point et remainder).

Observation 2

Si à un certain moment, active_length est supérieure ou égale à la longueur de bord (edge_length), nous passons notre active point à la baisse jusqu' edge_length n'est pas strictement supérieur active_length.

Maintenant, nous allons redéfinir les règles:

Règle 1

Si, après l'insertion du nœud actif = racine, la longueur est supérieure à 0, puis:

1. nœud actif n'est pas modifié
2. longueur active est décrémenté
3. active bord est décalé à droite (le premier caractère de la prochaine suffixe que l'on doit insérer)

Règle 2

Si nous créons un nouveau noeud interne OU de faire une insertion d'un noeud interne, et ce n'est pas le premier EXEMPLE noeud interne à l'étape en cours, puis nous le lien de la précédente TEL noeud avec CE un par un suffixe lien.

Cette définition de l' Rule 2 est différent de jogojapan", comme ici, nous prenons en compte non seulement le nouvellement créé nœuds internes, mais aussi les noeuds internes, à partir de laquelle nous faire une insertion.

Règle 3

Après une insertion à partir du nœud actif qui n'est pas la racine de nœud, nous devons suivre le suffixe de lien et de définir le nœud actif pour le nœud points. Si il n'est pas un suffixe lien, définir le nœud actif de la racine au nœud. De toute façon, active bord et de la longueur active rester inchangé.

Dans cette définition de la Rule 3 nous considérons également les inserts de nœuds feuilles (pas seulement split-nœuds).

Et enfin, l'Observation 3:

Lorsque le symbole nous voulons ajouter à l'arbre est déjà sur le bord, nous avons, selon Observation 1, mise à jour uniquement active point et remainder, laissant l'arbre inchangé. MAIS si il y a un noeud interne marqué comme ayant besoin d'suffixe lien, il faut brancher le nœud avec notre active node par le biais d'un suffixe lien.

Regardons l'exemple d'un suffixe de l'arbre pour cdddcdc si l'on ajoute un suffixe lien dans un tel cas, et si nous n'avons pas:

1. Si nous NE PAS connecter les nœuds grâce à un suffixe lien:

   • avant l'ajout de la dernière lettre c:

   

   • après l'ajout de la dernière lettre c:

   

2. Si nous NE connecter les nœuds grâce à un suffixe lien:

   • avant l'ajout de la dernière lettre c:

   

   • après l'ajout de la dernière lettre c:

   

Semble comme il n'y a pas de différence significative: dans le second cas, il y a plus de deux suffixe liens. Mais ces suffixe liens sont corrects, et l'un d'eux - à partir du noeud bleu-rouge - est très important pour notre approche avec le point actif. Le problème est que si nous ne mettons pas un suffixe lien ici, plus tard, quand on ajoute quelques nouvelles lettres de l'arbre, on peut omettre l'ajout de certains nœuds de l'arbre en raison de l' Rule 3, parce que, selon elle, si il n'y a pas un suffixe lien, puis on doit mettre de l' active_node à la racine.

Lorsque nous avons ajouté la dernière lettre de l'arbre, le nœud rouge avait déjà existé avant nous avons fait une insertion à partir du noeud bleu (le bord intitulée "c"). Comme il y avait un encart de la couleur bleue du nœud, nous le marquer comme ayant besoin d'un suffixe lien. Puis, en s'appuyant sur le point actif approche, l' active node a été fixé pour le nœud rouge. Mais nous n'en faisons pas une plaquette rouge nœud, la lettre "c" est déjà sur le bord. Signifie que le noeud bleu doit être laissé sans un suffixe lien? Non, il faut brancher le noeud bleu avec le rouge par le biais d'un suffixe lien. Pourquoi est-il correct? Parce que le point actif approche garantit que nous arrivons à un bon endroit, c'est à dire, pour le prochain endroit où l'on doit traiter d'une insertion plus courte suffixe.

Enfin, voici mes implémentations de le Suffixe de l'Arbre:

1. Java
2. C++

Espérons que cette "vue d'ensemble" combiné avec jogojapan détaillées de réponse sera aider quelqu'un à mettre en œuvre son propre Suffixe de l'Arbre.

Answer 2

J'ai eu beaucoup de problèmes pour mettre en œuvre cette structure de données moi-même. En fin de compte j'ai trouvé cet article et a réussi à la mettre en œuvre. Un grand plus pour le il est que vous avez une étape-par-étape de l'exemple d'une très longue chaîne de sorte que vous obtenez de voir ce que vous devriez faire. Veuillez prendre un coup d'oeil à l'article et je serai plus heureux de donner des conseils en cas de besoin. J'hésite à gove encore une autre de plein fouet l'explication qu'il y a déjà quelques tour de l'internet.

Answer 3

Mon intuition est comme suit:

Après k itérations de la boucle principale, vous avez construit un suffixe arbre qui contient tous les suffixes de la chaîne complète qui commencent dans les k premiers caractères.

Au début, cela signifie que le suffixe de l'arbre contient un seul nœud racine qui représente l'ensemble de la chaîne (c'est le seul suffixe qui commence à 0).

Après len(chaîne) d'itérations que vous avez un suffixe arbre qui contient tous les suffixes.

Au cours de la boucle, la clé est le point actif. Ma conjecture est que cela représente le point le plus profond dans le suffixe arbre qui correspond à un suffixe de la k premiers caractères de la chaîne. (Je pense que les moyens appropriés que le suffixe ne peut pas être l'ensemble de la chaîne).

Par exemple, supposons que vous avez vu des personnages abcabc'. Le point actif représentent le point de l'arbre correspondant au suffixe "abc".

Le point actif est représenté par (origine,premier,dernier). Cela signifie que vous sont actuellement à la point de l'arbre que vous obtenez en commençant au niveau du nœud de l'origine et de l'alimentation dans les caractères de la chaîne[premier:dernier]

Lorsque vous ajoutez un nouveau personnage que vous regardez pour voir si le point actif est encore dans les arbres existants. Si c'est pour que vous vous êtes fait. Sinon, vous devez ajouter un nouveau nœud pour le suffixe de l'arbre au point actif, repli à la prochaine correspondance la plus courte, et vérifiez de nouveau.

Note 1: Le suffixe des pointeurs de donner un lien vers le côté le plus court de match pour chaque nœud.

Note 2: Lorsque vous ajoutez un nouveau nœud et de secours vous ajoutez un nouveau suffixe pointeur pour le nouveau nœud. La destination de ce suffixe pointeur sera le nœud à la réduction de l'actif point. Ce nœud ne soit existent déjà, ou être créé sur la prochaine itération de cette boucle de secours.

Note 3: La canonisation de la partie tout simplement de sauver du temps, de vérifier le point actif. Par exemple, supposons que vous avez toujours utilisé l'origine=0, et juste changé premier et le dernier. Pour vérifier le point actif que vous auriez à suivre le suffixe de l'arbre à chaque fois le long de tous les nœuds intermédiaires. Il est logique de mettre en cache le résultat de ce chemin par l'enregistrement, la distance entre le dernier nœud.

Pouvez-vous donner un exemple de code de ce que tu veux dire par "fix" de délimitation des variables?

Avertissement de santé: j'ai aussi trouvé cet algorithme particulièrement difficile à comprendre merci donc de réaliser que cette intuition est susceptible d'être incorrecte dans tous les détails importants...

Answer 4

Salut j'ai essayé de mettre en œuvre l'ai expliqué plus haut la mise en œuvre en ruby , s'il vous plaît vérifier. il semble bien fonctionner.

la seule différence dans la mise en œuvre, c'est que , j'ai essayé d'utiliser le bord de l'objet au lieu de simplement en utilisant des symboles.

il est aussi présent à 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[active_length..@active_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 @last_split_edge.data.end_with?@active_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