Извлечь родительский и дочерний узел из представления дерева питона

Question

[Tree('ROOT', [Tree('S', [Tree('INTJ', [Tree('UH', ['Hello'])]), Tree(',', [',']), Tree('NP', [Tree('PRP$', ['My']), Tree('NN', ['name'])]), Tree('VP', [Tree('VBZ', ['is']), Tree('ADJP', [Tree('JJ', ['Melroy'])])]), Tree('.', ['.'])])]), Tree('ROOT', [Tree('SBARQ', [Tree('WHNP', [Tree('WP', ['What'])]), Tree('SQ', [Tree('VBZ', ['is']), Tree('NP', [Tree('PRP$', ['your']), Tree('NN', ['name'])])]), Tree('.', ['?'])])])] 

У меня есть много из этих строк, доступных в Python, которые на самом деле представляют собой представления деревьев. Я хочу извлечь родительский и дочерний узел для каждого слова, например. для 'Hello' Я хочу (INTJ, UH), а для 'My' это (NP, PRP$).

Это результат я хочу:

(INTJ, UH) , (NP, PRP$), (NP, NN) , (VP, VBZ) , (VP , VPZ) , (ADJP, JJ) , (WHNP, WP), (SQ, VBZ), (NP, PRP$), (NP, NN) 

Как я могу это сделать?

Answer 1

Ваша строка, очевидно, представляет собой список из Tree объектов. Было бы намного лучше, если бы вы имели доступ или могли бы восстановить каким-то другим способом этот список - если нет, самым простым способом создания структуры данных, с которой вы можете работать, является eval() (со всеми usual caveats о вызове eval() на пользователе -пользуемые данные).

Поскольку вы ничего о вашем Tree классе не говорить, что я напишу простой, который достаточно для целей этого вопроса:

class Tree: 

    def __init__(self, name, branches): 
     self.name = name 
     self.branches = branches 

Теперь мы можем воссоздать структуру данных:

data = eval("""[Tree('ROOT', [Tree('S', [Tree('INTJ', [Tree('UH', ['Hello'])]), Tree(',', [',']), Tree('NP', [Tree('PRP$', ['My']), Tree('NN', ['name'])]), Tree('VP', [Tree('VBZ', ['is']), Tree('ADJP', [Tree('JJ', ['Melroy'])])]), Tree('.', ['.'])])]), Tree('ROOT', [Tree('SBARQ', [Tree('WHNP', [Tree('WP', ['What'])]), Tree('SQ', [Tree('VBZ', ['is']), Tree('NP', [Tree('PRP$', ['your']), Tree('NN', ['name'])])]), Tree('.', ['?'])])])]""") 

После того, как мы есть, что мы можем написать функцию, которая производит список 2-кортежей вы хотите:

def tails(items, path=()): 
    for item in items: 
     if isinstance(item, Tree): 
      if item.name in {".", ","}: # ignore punctuation 
       continue 
      for result in tails(item.branches, path + (item.name,)): 
       yield result 
     else: 
      yield path[-2:] 

Эта функция спускается рекурсивно в дерево, получая последние два имени Tree каждый раз, когда он попадает на соответствующий листовой узел.

Пример использования:

>>> list(tails(data)) 
[('INTJ', 'UH'), ('NP', 'PRP$'), ('NP', 'NN'), ('VP', 'VBZ'), ('ADJP', 'JJ'), ('WHNP', 'WP'), ('SQ', 'VBZ'), ('NP', 'PRP$'), ('NP', 'NN')]