Comment puis-je manipuler des arbres parse?

Question

Je joue autour des arbres d'analyse du langage naturel et de les manipuler de différentes façons. J'utilise les outils de Stanford Tregex et Tsurgeon mais le code est un gâchis et ne correspond pas bien avec mon environnement principalement Python (ces outils sont Java et ne sont pas idéales pour peaufinage). Je voudrais avoir un ensemble d'outils qui permettrait de piratage facile quand j'ai besoin de plus de fonctionnalités. Y at-il d'autres outils qui sont bien adaptés pour faire la recherche de motifs sur les arbres et la manipulation de ces branches adapté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 certains nom descendant « Banque », et un deuxième enfant avec l'étiquette PP.
2. Si cette allumettes, puis prendre tous les enfants du nœud de PP et de les déplacer pour mettre fin à des enfants du NP apparié.

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 envisagé d'utiliser Lisp (intégré dans mon programme Python) mais il a été si longtemps que j'ai écrit quelque chose d'important dans Lisp que je ne sais pas où commencer même.

Quelle serait une bonne façon de décrire les motifs? Quelle serait une bonne façon de décrire les manipulations? Ce qui est une bonne façon de penser à ce problème?

Answer 1

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

Voici un exemple de mise en correspondance de procédure utilisant Common Lisp. Il y a matchers dans Lisp que le travail sur les structures de la liste, qui pourrait être utilisé à la place. L'utilisation d'un matcher liste simplifierait l'exemple (voir mon autre réponse pour un exemple en utilisant un adaptateur de motif).

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

L'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 plus que vous ne pouvez pas traiter avec Java ou plus abstraction et que vous cherchez quelque chose de concret écrit en Python.

Il n'y a rien de mal avec les fonctions de correspondants et de transformation d'arbres écriture à la main. En effet, nous avons l'habitude de le faire tout le temps. Mais après les deux premières cent, il semblait qu'il devait y avoir une meilleure façon, et donc nous sommes passés à l'aide des langages spécifiques de domaine de Tregex et Tsurgeon. Ceci est généralement considéré comme un style de programmation louable. Voir Wikipedia . Ils sont des langues bien définies avec une spécification de syntaxe exacte, etc. Voici votre exemple les utiliser.

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 à domaine. Il est difficile de voir comment cela pourrait être plus simple. Spécifier motif, spécifiez l'opération, appliquez

Mais si vous préférez être des méthodes d'écriture main que les modèles de match sur les arbres et les changer dans d'autres arbres en Python, alors vous êtes les bienvenus pour partir et faire cela.

Answer 3

Voici une deuxième version en Common Lisp. Cette fois, je suis sur 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 matcher modèle dans le livre Winston / Horn, Lisp, 3e édition. Il y a des fonctions de correspondance de modèle similaires disponibles.

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

La fonction de mise en correspondance d'arborescence est modifié pour utiliser la configuration matcher. La pmatch: fonction MATCH retourne T ou une liste assoc des consolidations si le match est réussi. Il retourne NIL si le match n'a pas réussi. Le pmatch: instancier-PATTERN prend un modèle et un ensemble de fixations. Il renvoie une nouvelle structure de liste, où 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)))

L'exemple utilise maintenant des modèles.

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

Le transformateur est un motif qui sera instancié avec les fixations.

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