Des branches supplémentaires ajoutées à l'arbre lors de la génération

Question

J'ai implémenté l'algorithme d'analyse CYK qui utilise une approche bottom-up pour construire une arborescence d'analyse. En parcourant l'algorithme, le chemin vers la solution finale est stocké dans les backpointers. A partir des backpointers, nous construisons l'arbre. Cette dernière étape est ce que j'ai des problèmes avec.

C'est la structure de données que je utilise pour stocker l'arbre:

class GrammarTree(object): 
    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 

    def insertLeft(self, new_node): 
     self.left = GrammarTree(new_node) 

    def insertRight(self, new_node): 
     self.right = GrammarTree(new_node) 

Voici comment je construis l'arbre, où back stocke un tuple où split est l'index utilisé pour diviser l'arbre et left_rule et right_rule sont les règles pour l'arbre respectif représenté par int. Si un nœud feuille est atteint, il n'y a pas de tuple, juste un int représentant la règle du terminal.

def build_tree(start,end,idx,back): 
    tree = GrammarTree(idx) 
    node = back[start][end][idx] 
    if isinstance(node,tuple): 
     split,left_rule,right_rule = node 
     tree.insertLeft(build_tree(start,split,left_rule,back)) 
     tree.insertRight(build_tree(split,end,right_rule,back)) 
     return tree 
    else: 
     tree.insertLeft(GrammarTree(node)) 
     return tree 

Le problème est que lorsque la fonction est fait construire l'arbre, il y a des branches supplémentaires ajoutés, à savoir les noeuds ne sont pas correctement collés ensemble.

Voici ce qu'il ressemble à:

Lvl0        root 
         /       \ 
Lvl1      L1        R1 
       /  | \   /   |  \ 
       /  |  \   /   |  \ 
       /  |  \  /   |   \ 
      /  |  \  /   |   \ 
      /   |  \ /    |   \ 
Lvl2 L1.left=None L1.right=None L1.data R1.left=None R1.right=None R1.data 
           / \       / \ 
Lvl3        L2  R2       L3  R3 

Il ne devrait pas être un nœud data entre les arbres.

Edit:

Le problème est pas qu'il existe un nœud de données supplémentaires (déclaration ci-dessus est faux), il est qu'après LVL1, au lieu de nouvelles branches ajoutées à L1.left/right et R1.left/right sur LVL2, ils sont ajouté à L1 et R1'sdata champs. Donc L1/R1.data finit par être un arbre en soi et L1.left/right et R1.left/right ne sont pas utilisés et donc None.

Il devrait ressembler à ceci:

    root 
     /    \ 
     /    \ 
    L1=root.left   R1=root.right 
    / \    / \ 
    / \    / \ 
/  \   /  \ 
L2=L1.left R2=L1.right L3=R1.left R3=R1.right 

C'est là que j'appelle construire l'arbre:

back = [[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (1, 6, 7), 0, 3, 0, (1, 7, 7)], [0, 0, 0, (1, 6, 7), 0, (1, 7, 3), 0, (1, 7, 7)], [0, 0, 0, (1, 6, 7), 0, (2, 7, 3), 0, (1, 7, 7)]],\ 
     [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (2, 6, 7), 0, (2, 7, 3), 0, (2, 7, 7)], [0, 0, 0, (2, 6, 7), 0, (2, 7, 3), 0, (3, 7, 7)]],\ 
     [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (3, 6, 7), 0, 3, 0, (3, 7, 7)]],\ 
     [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2]],\ 
     [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]] 
build_tree(0,4,5,back) 

Answer 1

Le problème était dans les méthodes insertLeft() et insertRight() de la classe GrammarTree. Plutôt que de simplement connecter les branches, vous remarquerez que j'appelais le constructeur GrammarTree alors j'emballais essentiellement un arbre dans un autre arbre.

J'ai résolu le problème en supprimant l'appel au constructeur.

class GrammarTree(object): 
    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 

    def insertLeft(self, new_node): 
     self.left = new_node ## <- NOT GrammarTree(new_node) 

    def insertRight(self, new_node): 
     self.right = new_node ## <- NOT GrammarTree(new_node)