Получить граф Самый низкий узел высоты с фильтром

Question

Учитывая дерево T, иногда двоичное или нет, мне нужно получить самый низкий узел, который соответствует критериям в каждой ветви.

Итак, мне нужно получить список (массив) этих красных отмеченных узлов, где они label равно «NP» node.label() == 'NP'.

На самом деле я использую дерево NLTK (nltk.tree.Tree), но вы можете публиковать только псевдокод, и я могу его реализовать.

Вот код, который я пытался:

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