Wie manipuliere ich Parse Bäume?

Question

Ich habe mit natürlichsprachigen Pars-Bäumen gespielt und sie auf verschiedene Arten manipuliert. Ich habe Stanfords Tregex- und Tsurgeon-Tools verwendet, aber der Code ist unordentlich und passt nicht gut in meine Python-Umgebung (diese Tools sind Java und eignen sich nicht zum Optimieren). Ich hätte gerne ein Toolset, das einfaches Hacken ermöglicht, wenn ich mehr Funktionalität brauche. Gibt es noch andere Werkzeuge, die sich gut für die Mustererkennung auf Bäumen und die Manipulation dieser Zweige eignen?

Zum Beispiel, würde Ich mag den folgenden Baum als Eingabe nehmen:

(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))))))))))) 

und (dies ist ein vereinfachtes Beispiel):

1. Angebote: Alle Knoten mit dem Label, das NP hat ein erstes Kind mit dem Label NP und ein Nachkomme namens "Bank", und ein zweites Kind mit dem Label PP.
2. Wenn dies zutrifft, dann nimm alle untergeordneten Elemente des PP-Knotens und verschiebe sie zum Ende der untergeordneten NPs.

Nehmen wir zum Beispiel diesen Teil des Baumes:

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

und in diese abbiegen:

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

Da meine Eingangs Bäume sind S-Ausdrücke, die ich in Betracht gezogen habe Lisp mit (eingebettet in mein Python-Programm), aber es ist so lange her, dass ich etwas Wesentliches in Lisp geschrieben habe, dass ich keine Ahnung habe, wo ich überhaupt anfangen soll.

Was wäre ein guter Weg, um die Muster zu beschreiben? Was wäre ein guter Weg, die Manipulationen zu beschreiben? Was ist eine gute Möglichkeit, über dieses Problem nachzudenken?

Answer 1

Dies ist ein typischer Fall der Verwendung von Lisp. Sie benötigen eine Funktion, die eine andere Funktion über den Baum abbildet.

Hier ist ein Beispiel für eine prozedurale Übereinstimmung mit Common Lisp. In Lisp gibt es Matcher, die über Listenstrukturen arbeiten, die stattdessen verwendet werden können. Die Verwendung eines Listen-Matcher würde das Beispiel vereinfachen (siehe meine andere Antwort für ein Beispiel, das einen Muster-Matcher verwendet).

Der Code:

(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)))) 

Das Beispiel:

(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))))))))) 

Ausführen des Beispiel:

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

Schönheit liegt im Auge des Betrachters. Aber Sie sagen nie wie der Code von Tregex oder Tsurgeon ist ein Durcheinander. Es klingt eher so, als könnten Sie nicht mit Java oder einer größeren Abstraktion umgehen, und Sie suchen nach etwas Konkretem, das in Python geschrieben wurde.

Es ist nichts falsch mit handschriftlichen Tree Matching und Transformationsfunktionen. Tatsächlich haben wir das die ganze Zeit gemacht. Aber nach den ersten paar hundert Jahren schien es, als müsste es einen besseren Weg geben, und deshalb sind wir dazu übergegangen, die domänenspezifischen Sprachen von Tregex und Tsurgeon zu verwenden. Dies wird allgemein als lobenswerter Programmierstil angesehen. Siehe in Wikipedia.Sie sind gut spezifizierte Sprachen mit einer genauen Syntaxspezifikation usw. Hier ist Ihr Beispiel, das sie verwendet.

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(); 

Beachten Sie, dass der Java-Code tatsächlich kürzer als der Lisp-Code ist, gerade wegen der Verwendung der domänenspezifischen Sprache. Es ist schwer zu sehen, wie dies einfacher sein könnte: Muster angeben, Operation angeben, anwenden.

Aber wenn Sie es vorziehen, Handschrift Methoden, um die Muster auf Bäumen entsprechen und sie in andere Bäume in Python ändern, dann sind Sie herzlich eingeladen zu gehen und das tun.

Answer 3

Hier ist eine zweite Version in Common Lisp. Dieses Mal verwende ich einen Mustervergleicher.

Ich verwende eine Funktion, die ein Muster gegen Lisp-Daten entspricht. PMATCH: MATCH ist eine erweiterte Version eines Pattern Matcher, der in dem Buch Winston/Horn, Lisp, 3rd Edition gefunden wurde. Es sind ähnliche Mustervergleichsfunktionen verfügbar.

Die Daten sind wie in meiner anderen Antwort.

Die Baum-Mapping-Funktion wurde geändert, um den Muster-Matcher zu verwenden. Die Funktion PMATCH: MATCH gibt T oder eine assoziierte Liste von Bindungen zurück, wenn die Übereinstimmung erfolgreich ist. Wenn die Übereinstimmung nicht erfolgreich ist, wird NIL zurückgegeben. Das PMATCH: INSTANTIATE-PATTERN nimmt ein Muster und eine Reihe von Bindungen. Sie gibt eine neue Listenstruktur zurück, in der die Mustervariablen durch die Bindungen ersetzt werden.

(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))) 

Das Beispiel verwendet nun Muster.

Das Muster ist eine Listenstruktur. #? Symbol entspricht einem einzelnen Objekt und erstellt eine Bindung für das Symbol. # $ symbol entspricht einer Liste von Elementen und erstellt eine Bindung für das Symbol.

Der Transformator ist ein Muster, das mit den Bindungen instanziiert wird.

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

Ausführen dieses Codes gibt das gleiche Ergebnis wie in meiner anderen Antwort.