Comment manipuler les arbres d'analyse?

Question

J'ai joué avec des arbres d'analyse en langage naturel et je les ai manipulés de diverses manières. J'ai utilisé les outils Tregex et Tsurgeon de Stanford, mais le code est en désordre et ne s'accorde pas bien avec mon environnement principalement Python (ces outils sont Java et ne sont pas idéaux pour le peaufinage). J'aimerais avoir un jeu d'outils qui permettrait un piratage facile lorsque j'ai besoin de plus de fonctionnalités. Y a-t-il d'autres outils qui sont bien adaptés pour faire un appariement de motifs sur des arbres et ensuite manipuler ces branches appariées?

Par exemple, je voudrais prendre l'arbre suivant en entrée:

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

et (ce qui est un exemple simplifié):

1. Trouver un nœud avec l'étiquette NP qui a un premier enfant avec l'étiquette NP et un descendant nommé "Banque", et un deuxième enfant avec l'étiquette PP.
2. Si cela correspond, alors prenez tous les enfants du nœud PP et déplacez-les à la fin des enfants de NP correspondants.

Par exemple, prenez cette partie de l'arbre:

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

et la transformer en ceci:

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

Depuis mes arbres d'entrée sont S-expressions que je l'ai pensé à utiliser Lisp (intégré dans mon programme Python) mais ça fait tellement longtemps que j'ai écrit quelque chose de significatif dans Lisp que je n'ai aucune idée par où commencer.

Quelle serait une bonne façon de décrire les motifs? Quel serait un bon moyen de décrire les manipulations? Quelle est une bonne façon de penser à ce problème?

Answer 1

Ceci est un cas typique d'utilisation de Lisp. Vous auriez besoin d'une fonction qui mappe une autre fonction sur l'arbre.

Voici un exemple de correspondance procédurale utilisant Common Lisp. Il y a des allumeurs dans Lisp qui fonctionnent sur des structures de liste, qui pourraient être utilisées à la place. L'utilisation d'un comparateur de liste simplifierait l'exemple (voir mon autre réponse pour un exemple utilisant un correcteur de modèle).

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

L'exemple:

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

Exécution de l'exemple:

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 beauté est dans l'oeil du spectateur. Mais vous ne dites jamais comment le code de Tregex ou Tsurgeon est un gâchis. Il semble que vous ne puissiez pas traiter avec Java ou une plus grande abstraction et que vous cherchez quelque chose de concret écrit en Python.

Il n'y a rien de mal avec les fonctions de correspondance et de transformation d'arbre à écriture manuelle. En effet, nous avions l'habitude de le faire tout le temps. Mais après les deux premiers cent, il semblait qu'il y avait une meilleure solution, et nous avons donc décidé d'utiliser les langages de Tregex et Tsurgeon spécifiques au domaine. Ceci est généralement considéré comme un style de programmation louable. Voir au Wikipedia.Ce sont des langages bien spécifiés avec une spécification de syntaxe exacte, etc. Voici votre exemple les utilisant.

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

Notez que le code Java est en fait plus court que le code Lisp, précisément en raison de l'utilisation de la langue spécifique au domaine. Il est difficile de voir comment cela pourrait être plus simple: spécifier un motif, spécifier une opération, appliquer. Mais si vous préférez utiliser des méthodes d'écriture manuscrites qui correspondent à des motifs sur des arbres et les changer dans d'autres arbres en Python, alors vous êtes le bienvenu pour le faire.

Answer 3

Voici une deuxième version en Common Lisp. Cette fois, j'utilise un modèle matcher. J'utilise une fonction qui correspond à un modèle par rapport aux données Lisp. PMATCH: MATCH est une version améliorée d'un modèle de correspondance trouvée dans le livre Winston/Horn, Lisp, 3rd Edition. Il existe des fonctions de correspondance de modèles similaires disponibles.

Les données sont comme dans mon autre réponse.

La fonction de mappage d'arborescence est modifiée pour utiliser l'outil de correspondance de modèles. La fonction PMATCH: MATCH renvoie T ou une liste assoc de liaisons si la correspondance est réussie. Il retourne NIL si la correspondance échoue. Le PMATCH: INSTANTIATE-PATTERN prend un motif et un ensemble de liaisons. Il renvoie une nouvelle structure de liste, dans laquelle les variables de modèle sont remplacées par les liaisons.

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

Le exemple utilise maintenant des modèles.

Le motif est une structure de liste. Le symbole #? correspond à un seul élément et crée une liaison pour le symbole. Le symbole # $ correspond à une liste d'éléments et crée une liaison pour le symbole.

Le transformateur est un modèle qui sera instancié avec les liaisons.

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

L'exécution de ce code renvoie le même résultat que dans mon autre réponse.