Come faccio a manipolare alberi di analisi?

Question

Ho suonato in giro con alberi di analisi del linguaggio naturale e la loro manipolazione in vari modi. Sto usando strumenti Tregex e Tsurgeon di Stanford, ma il codice è un casino e non si adatta bene con la mia gran parte dell'ambiente Python (questi strumenti sono Java e non sono ideali per tweaking). Mi piacerebbe avere un set di strumenti che consenta una facile pirateria informatica quando ho bisogno di più funzionalità. Ci sono altri strumenti che ben si adattano per fare pattern matching sugli alberi e poi la manipolazione di quei rami abbinati?

Per esempio, mi piacerebbe prendere il seguente albero come input:

(ROOT
  (S
    (NP
      (NP (NNP Bank))
      (PP (IN of)
        (NP (NNP America))))
    (VP (VBD used)
      (S
        (VP (TO to)
          (VP (VB be)
            (VP (VBN called)
              (NP
                (NP (NNP Bank))
                (PP (IN of)
                  (NP (NNP Italy)))))))))))

e (questo è un esempio semplificato):

1. : tutte le nodo con l'etichetta NP che ha un primo figlio con l'etichetta NP e alcuni discendente denominata "Banca", e un secondo figlio con il PP etichetta.
2. Se quello che soddisfa, poi prendere tutti i figli del nodo PP e spostarli alla fine dei figli del abbinato del NP.

Per esempio, prendi questo parte della struttura:

(NP
  (NP (NNP Bank))
  (PP (IN of)
    (NP (NNP America))))

e trasformarlo in questo:

(NP
  (NP (NNP Bank) (IN of) (NP (NNP America))))

Dato che i miei alberi di ingresso sono S-espressioni che ho pensato di utilizzare Lisp (incorporato nel mio programma Python), ma è passato così tanto tempo che ho scritto qualcosa di significativo in Lisp che non ho idea da dove cominciare anche.

Quale sarebbe un buon modo per descrivere i modelli? Quale sarebbe un buon modo per descrivere le manipolazioni? Che cosa è un buon modo di pensare a questo problema?

Answer 1

Questo è un tipico caso di utilizzo di Lisp. Si avrebbe bisogno di una funzione che mappa un'altra funzione sopra l'albero.

Ecco un esempio di corrispondenza procedurale utilizzando Common Lisp. Ci sono matchers in Lisp che lavoro sulle strutture della lista, che potrebbe essere utilizzato al posto. Utilizzando un elenco matcher semplificherebbe l'esempio (vedere la mia altra risposta per un esempio utilizzando un matcher modello).

Il codice:

(defun node-children (node)
  (rest node))

(defun node-name (node)
  (second node))

(defun node-type (node)
  (first node))


(defun treemap (tree matcher transformer)
  (cond ((null tree) nil)
        ((consp tree)
         (if (funcall matcher tree)
             (funcall transformer tree)
           (cons (node-type tree)
                 (mapcar (lambda (child)
                           (treemap child matcher transformer))
                         (node-children tree)))))
        (t tree))))

L'esempio:

(defvar *tree*
  '(ROOT
    (S
     (NP
      (NP (NNP Bank))
      (PP (IN of)
          (NP (NNP America))))
     (VP (VBD used)
         (S
          (VP (TO to)
              (VP (VB be)
                  (VP (VBN called)
                      (NP
                       (NP (NNP Bank))
                       (PP (IN of)
                           (NP (NNP Italy))))))))))))



(defun example ()
  (pprint
   (treemap *tree*
            (lambda (node)
              (and (= (length (node-children node)) 2)
                   (eq (node-type (first (node-children node))) 'np)
                   (some (lambda (node)
                           (eq (node-name node) 'bank))
                         (children (first (node-children node))))
                   (eq (first (second (node-children node))) 'pp)))
            (lambda (node)
              (list (node-type node)
                    (append (first (node-children node))
                            (node-children (second (node-children node)))))))))

L'esecuzione l'esempio:

CL-USER 75 > (example)

(ROOT
 (S
  (NP
   (NP (NNP BANK) (IN OF) (NP (NNP AMERICA))))
  (VP
   (VBD USED)
   (S
    (VP
     (TO TO)
     (VP
      (VB BE)
      (VP
       (VBN CALLED)
       (NP
        (NP
         (NNP BANK)
         (IN OF)
         (NP (NNP ITALY)))))))))))

Answer 2

La bellezza è negli occhi di chi guarda. Ma non avete mai dire come il codice di Tregex o Tsurgeon è un casino. Suona più come non si può fare con Java o maggiore astrazione e quindi siete alla ricerca di qualcosa di concreto scritto in Python.

Non c'è niente di sbagliato con le funzioni di scrittura a mano albero di corrispondenza e di trasformazione. In effetti, abbiamo usato per fare che tutto il tempo. Ma dopo il primo paio di centinaia, sembrava che ci doveva essere un modo migliore, e quindi ci siamo trasferiti a utilizzando i linguaggi di dominio-specifici di Tregex e Tsurgeon. Questo è generalmente visto come uno stile di programmazione lodevole. Vedere in Wikipedia . Stanno lingue ben specificati, con una specifica sintassi esatta, ecc Ecco il tuo esempio li utilizzano.

Tree t = Tree.valueOf("(ROOT (S (NP (NP (NNP Bank)) (PP (IN of) (NP (NNP America)))) (VP (VBD used) (S (VP (TO to) (VP (VB be) (VP (VBN called) (NP (NP (NNP Bank)) (PP (IN of) (NP (NNP Italy)))))))))))");
TregexPattern pat = TregexPattern.compile("NP <1 (NP << Bank) <2 PP=remove");
TsurgeonPattern surgery = Tsurgeon.parseOperation("excise remove remove");
Tsurgeon.processPattern(pat, surgery, t).pennPrint();

Si noti che il codice Java è in realtà più breve che il codice Lisp, proprio a causa dell'uso del linguaggio dominio-specifica. E 'difficile vedere come questo potrebbe essere più semplice:. Specificare modello, specificare il funzionamento, applicare

Ma se si preferisce essere i metodi di scrittura a mano che corrispondono modelli su alberi e li trasformano in altri alberi in Python, allora siete i benvenuti a andare fuori e farlo.

Answer 3

Ecco una seconda versione in Common Lisp. Questa volta sto usando un modello di abbinamento .

Sto usando una funzione che corrisponde a un modello con i dati Lisp. PMATCH: MATCH è una versione migliorata di un matcher modello trovato nel libro di Winston / Horn, Lisp, 3rd Edition. Ci sono simili funzioni di pattern matching disponibili.

I dati sono come nella mia altra risposta.

La funzione di mappatura albero viene modificata per utilizzare il matcher modello. La PMATCH: funzione match ritorna T o un elenco assoc di attacchi se la partita è successo. Si ritorna NIL se la partita non è successo. Il PMATCH: istanziare-modello prende un modello e una serie di attacchi. Si restituisce una nuova struttura della lista, in cui le variabili del modello vengono sostituiti con le associazioni.

(defun treemapp (tree pattern transformer)
  (cond ((null tree) nil)
        ((consp tree)
         (let ((bindings (pmatch:match pattern tree)))
           (if bindings
               (pmatch:instantiate-pattern transformer bindings)
             (cons (node-type tree)
                   (mapcar (lambda (child)
                             (treemapp child pattern transformer))
                           (node-children tree))))))
        (t tree)))

Il Esempio usi ora i modelli.

Lo schema è una struttura lista. #? Simbolo corrisponde a un singolo elemento e crea un binding per simbolo. # $ Simbolo corrisponde a un elenco di elementi e crea un binding per simbolo.

Il trasformatore è un motivo che sarà istanziata con le associazioni.

(defun example1 ()
  (pprint (treemapp *tree*
                    '(NP (NP (#?type bank)) (PP #$children))
                    '(NP (NP (#?type bank) #$children)))))

L'esecuzione di questo codice restituisce lo stesso risultato nella mia altra risposta.