1

我已经实现了 CYK 解析算法，它使用自下而上的方法来构建解析树。当它遍历算法时，最终解决方案的路径存储在反向指针中。从反向指针，我们构造树。这最后一步是我遇到的问题。

这是我用来存储树的数据结构：

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)

以下是我构建树的方式，其中back存储了一个元组，其中split用于拆分树的索引是用于拆分树的索引，left_rule并且right_rule是由 int 表示的相应树的规则。如果到达叶节点，则没有元组，只有一个表示终端规则的 int。

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

问题是当功能完成构建树时，会添加额外的分支，即节点没有正确粘合在一起。

这是它的样子：

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

data树之间不应该有节点。

编辑：

问题不在于多了一个数据节点（上面的说法是错误的），而是在Lvl1之后，不是在Lvl2上添加新的分支，而是添加到L1.left/right和字段中。所以最终成为一棵树本身，并且没有被使用，因此。 R1.left/rightL1R1's dataL1/R1.dataL1.left/rightR1.left/rightNone

它应该如下所示：

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

这就是我所说的构建树：

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)
4

1 回答 1

0

问题出在类的insertLeft()和insertRight()方法中GrammarTree。你会看到我调用了GrammarTree构造函数，而不是简单地连接分支，所以我实际上是在将一棵树包裹在另一棵树中。

我通过删除对构造函数的调用解决了这个问题。 

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)
于 2017-06-10T19:28:45.970 回答