Come analizzare alberi genealogici in python?

Question

Ho bisogno di aiuto per sviluppare questo algoritmo su cui sto lavorando. Ho un un ingresso di un albero nel seguente formato:

(Root (AB (ABC) (CBA)) (CD (CDE) (FGH)))

Questo sembra questo il seguente albero.

    Root 
        | 
       ____________ 
       AB   CD 
       |    | 
     __________   ___________ 
     ABC  CBA  CDE  FGH 

Che l'algoritmo è supponiamo di è leggere il formato di parentesi e dare il seguente output:

Root -> AB CD 
AB -> ABC CBA 
CD -> CDE FGH 

il filone della radice e dei suoi figli e tutti gli altri genitori che hanno figli. Non riesco a capire come avviarlo, Qualcuno può aiutarmi a suggerire o dare qualche riferimento o link?

Answer 1

Una discesa parser ricorsiva è una semplice forma di parser in grado di analizzare molte grammatiche. Mentre l'intera teoria dell'analisi è troppo grande per una risposta di overflow dello stack, l'approccio più comune all'analisi consiste in due passaggi: in primo luogo, la tokenizzazione, che estrae le sottocomponenti della stringa (qui, probabilmente parole come "Root" e "ABC" , o parentesi come '(' e ')'), e quindi l'analisi utilizzando le funzioni ricorsive.

Questo codice analizza l'input (come il tuo esempio), producendo un cosiddetto albero di analisi e ha anche una funzione 'show_children' che prende l'albero di analisi e produce la visualizzazione figli dell'espressione come la tua domanda.

import re 

class ParseError(Exception): 
    pass 

# Tokenize a string. 
# Tokens yielded are of the form (type, string) 
# Possible values for 'type' are '(', ')' and 'WORD' 
def tokenize(s): 
    toks = re.compile(' +|[A-Za-z]+|[()]') 
    for match in toks.finditer(s): 
     s = match.group(0) 
     if s[0] == ' ': 
      continue 
     if s[0] in '()': 
      yield (s, s) 
     else: 
      yield ('WORD', s) 


# Parse once we're inside an opening bracket. 
def parse_inner(toks): 
    ty, name = next(toks) 
    if ty != 'WORD': raise ParseError 
    children = [] 
    while True: 
     ty, s = next(toks) 
     if ty == '(': 
      children.append(parse_inner(toks)) 
     elif ty == ')': 
      return (name, children) 

# Parse this grammar: 
# ROOT ::= '(' INNER 
# INNER ::= WORD ROOT* ')' 
# WORD ::= [A-Za-z]+ 
def parse_root(toks): 
    ty, _ = next(toks) 
    if ty != '(': raise ParseError 
    return parse_inner(toks) 

def show_children(tree): 
    name, children = tree 
    if not children: return 
    print '%s -> %s' % (name, ' '.join(child[0] for child in children)) 
    for child in children: 
     show_children(child) 

example = '(Root (AB (ABC) (CBA)) (CD (CDE) (FGH)))' 
show_children(parse_root(tokenize(example))) 

Answer 2

Penso che la soluzione più popolare per l'analisi in Python sia PyParsing. PyParsing è dotato di una grammatica per analizzare le espressioni S e dovresti essere in grado di usarlo. Discusso in questa risposta StackOverflow:

Parsing S-Expressions in Python

Answer 3

Prova questo:

def toTree(expression): 
    tree = dict() 
    msg ="" 
    stack = list() 
    for char in expression: 
     if(char == '('): 
      stack.append(msg) 
      msg = "" 
     elif char == ')': 
      parent = stack.pop() 
      if parent not in tree: 
       tree[parent] = list() 
      tree[parent].append(msg) 
      msg = parent 
     else: 
      msg += char 
    return tree 

expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))" 
print toTree(expression) 

restituisce un dizionario, dove la radice si può accedere con il tasto ''. È quindi possibile eseguire un semplice BFS per stampare l'output.

USCITA:

{ 
'' : ['Root'], 
'AB' : ['ABC', 'CBA'], 
'Root': ['AB', 'CD'], 
'CD' : ['CDE', 'FGH'] 
} 

Si dovrà eliminare tutti gli spazi bianchi nell'espressione prima di iniziare, o ignorare le charaters inrrelevant nell'espressione aggiungendo quanto segue come la prima linea nella per -loop:

if char == <IRRELEVANT CHARACTER>: 
    continue 

il codice precedente verrà eseguito in tempo O (n), dove n è la lunghezza dell'espressione.

EDIT

Ecco la funzione di stampa:

def printTree(tree, node): 
    if node not in tree: 
     return 
    print '%s -> %s' % (node, ' '.join(child for child in tree[node])) 
    for child in tree[node]: 
     printTree(tree, child) 

L'uscita desiderata può essere ottenuta dalla seguente:

expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))" 
tree = toTree(expression) 
printTree(tree, tree[''][0]) 

uscita

Root -> AB CD 
AB -> ABC CBA 
CD -> CDE FGH 

EDIT

Supponendo che i nomi dei nodi non sono unici, non ci resta che dare nuovi nomi ai nodi. Questo può essere fatto utilizzando:

def parseExpression(expression): 
    nodeMap = dict() 
    counter = 1 
    node = "" 
    retExp ="" 
    for char in expression: 
     if char == '(' or char == ')' : 
      if (len(node) > 0): 
       nodeMap[str(counter)] = node; 
       retExp += str(counter) 
       counter +=1 
      retExp += char 
      node ="" 
     elif char == ' ': continue 
     else : 
      node += char 
    return retExp,nodeMap 

la funzione di stampa ora cambierà in:

def printTree(tree, node, nodeMap): 
    if node not in tree: 
     return 
    print '%s -> %s' % (nodeMap[node], ' '.join(nodeMap[child] for child in tree[node])) 
    for child in tree[node]: 
     printTree(tree, child, nodeMap) 

L'uscita può essere ottenuto utilizzando:

expression = " (Root(SQ (VBZ) (NP (DT) (NN)) (VP (VB) (NP (NN)))))" 
expression, nodeMap = parseExpression(expression) 
tree = toTree(expression) 
printTree(tree, tree[''][0], nodeMap) 

uscita:

Root -> SQ 
SQ -> VBZ NP VP 
NP -> DT NN 
VP -> VB NP 
NP -> NN