lisp - 解析ツリーを操作するにはどうすればよいですか?

Question

私は自然言語解析ツリーをいじり、さまざまな方法でそれらを操作してきました。私はスタンフォード大学の Tregex ツールと Tsurgeon ツールを使用してきましたが、コードがごちゃごちゃしていて、ほとんどが Python である私の環境にはうまく適合しません (これらのツールは Java であり、微調整には適していません)。より多くの機能が必要なときに簡単にハッキングできるツールセットが欲しいです。ツリーでパターンマッチングを実行し、一致したブランチを操作するのに適したツールは他にありますか?

たとえば、次のツリーを入力として使用したいと思います。

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

および (これは単純化された例です):

ラベル NP を持つ最初の子、"Bank" という名前のいくつかの子孫、およびラベル PP を持つ 2 番目の子を持つ、ラベル NP を持つ任意のノードを見つけます。
それが一致する場合、PP ノードのすべての子を取得し、それらを一致した NP の子の最後に移動します。

たとえば、ツリーの次の部分を見てください。

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

そしてそれをこれに変えます：

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

私の入力ツリーは S 式であるため、Lisp を使用することを検討しました (私の Python プログラムに組み込まれています)。

パターンを説明する良い方法は何でしょうか? 操作を説明する良い方法は何でしょうか? この問題について考える良い方法は何ですか?

score 11 · Accepted Answer

美しさは見る人の目にある。しかし、Tregex や Tsurgeon のコードがめちゃくちゃだとは決して言いません。Java やそれ以上の抽象化を扱うことができないため、Python で書かれた具体的なものを探しているようです。

手書きのツリーマッチングと変換関数に問題はありません。実際、私たちはいつもそうしていました。しかし、最初の 200 を超えると、もっと良い方法が必要であると思われたため、Tregex と Tsuurgeon のドメイン固有言語を使用することにしました。これは、一般的に賞賛に値するプログラミングスタイルと見なされます。ウィキペディアで参照してください。それらは、正確な構文仕様などを備えた明確に指定された言語です。これらを使用した例を次に示します。

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

ドメイン固有言語を使用しているため、Java コードは実際には Lisp コードよりも短いことに注意してください。パターンを指定し、操作を指定し、適用します。

しかし、ツリーのパターンに一致するメソッドを手書きで作成し、それらを Python の他のツリーに変更したい場合は、それを実行してもかまいません。

score 8 · Accepted Answer

これは Lisp を使用する典型的なケースです。ツリーに別の関数をマップする関数が必要になります。

以下は、Common Lisp を使用した手続き型マッチングの例です。Lisp には、代わりに使用できるリスト構造に対して機能するマッチャーがあります。リストマッチャーを使用すると、例が簡素化されます（パターンマッチャーを使用した例については、他の回答を参照してください）。

コード：

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

例：

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

例の実行:

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

score 5 · Accepted Answer

これは Common Lisp の 2 番目のバージョンです。今回はパターンマッチャーを使用しています。

Lisp データに対してパターンを照合する関数を使用しています。PMATCH:MATCH は、書籍 Winston/Horn, Lisp, 3rd Edition にあるパターンマッチャーの拡張バージョンです。同様のパターンマッチング関数が利用可能です。

データは私の他の回答と同じです。

ツリーマッピング関数は、パターンマッチャーを使用するように変更されます。PMATCH:MATCH 関数は、一致が成功した場合、T またはバインディングの関連リストを返します。一致しなかった場合は NIL を返します。PMATCH:INSTANTIATE-PATTERN は、パターンとバインディングのセットを取ります。パターン変数がバインディングに置き換えられた新しいリスト構造を返します。

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

この例では now パターンを使用しています。

パターンはリスト構造です。#?symbol は単一のアイテムに一致し、symbol のバインディングを作成します。#$symbol は項目のリストに一致し、symbol のバインディングを作成します。

トランスフォーマーは、バインディングでインスタンス化されるパターンです。

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

このコードを実行すると、他の回答と同じ結果が返されます。

lisp - 解析ツリーを操作するにはどうすればよいですか?

3 に答える 3

Related

Reference