使用过滤器检索图形最低高度节点

Question

给定一个树 T，有时是二进制的，有时不是二进制的，我需要检索每个分支中符合条件的最低节点。

所以，我需要检索那些标记为红色的节点的列表（数组），其中它们 label 等于 "NP" node.label() == 'NP'.

其实我用的是NLTK Tree (nltk.tree.Tree)数据结构，不过你可以post只用伪代码，我可以实现。

这是我试过的代码：

def traverseTree(tree):
  if not isinstance(tree, nltk.Tree): return []
  h = []
  for subtree in tree:
    if type(subtree) == nltk.tree.Tree:
      t = traverseTree(subtree)
      if subtree.label() == 'NP' and len(t) == 0: h.append(subtree)
  return h

Answer 1

你有一个条件，如果你的规范没有更好的候选者，那么追加子树，但是如果 len(t)>0 呢？在这种情况下，您希望保留在子调用中找到的节点：

def traverseTree(tree):
  if not isinstance(tree, nltk.Tree): return []
  h = []
  for subtree in tree:
    if type(subtree) == nltk.tree.Tree:
      t = traverseTree(subtree)
      #RIGHT HERE!! need to extend by t or the other found nodes are thrown out
      h.extend(t)

      if subtree.label() == 'NP' and len(t) == 0:
          h.append(subtree)

  return h

请记住，如果 t 始终为空，您将在下一级追加所有有效节点，但任何分支结束 "NP" 节点都将在 t 所以你想在递归中将它们向上传递一个级别。

编辑：唯一会失败的情况是顶级节点是 "NP" 并且没有 "NP" 的子节点，在这种情况下应该添加 tree到 h:

#after for loop has finished
if len(h) == 0 and tree.label() == "NP":
    h.append(tree)
return h

edit2：如果你将 tree 添加到 h 那么子树的检查将永远不会真正实现，因为它们只是在不同的递归级别检查具有相同条件的相同节点，所以你实际上可以像这样编写函数：

def traverseTree(tree):
  if not isinstance(tree, nltk.Tree): return []
  h = []
  for subtree in tree:
      #no need to check here as well as right inside the call
      h.extend(traverseTree(subtree))
  if tree.label() == 'NP' and len(h) == 0:
      h.append(tree)
  return h

使用过滤器检索图形最低高度节点

Retrieve Graph Lowest Height Node with Filter

python

algorithm

tree

graph

nltk