如何操作解析树？

Question

我一直在研究自然语言解析树并以各种方式对其进行操作。我一直在使用斯坦福的Tregex和Tsurgeon工具，但代码混乱且不适合我的大部分Python环境（这些工具使用Java，不太适合调整）。我想要一套工具集，可以轻松地进行hack以获得更多功能。是否有其他工具非常适合在树上进行模式匹配，然后操作这些匹配的分支？

例如，我想将以下树作为输入：

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

并（这只是一个简化的示例）：

1. 查找具有标签NP的任何节点，该节点具有具有标签NP的第一个子节点和名为“Bank”的某些后代，并具有具有标签PP的第二个子节点。
2. 如果匹配，则将PP节点的所有子节点取出并移动到匹配的NP节点的子节点的末尾。

例如，考虑以下树的一部分：

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

并将其转换为以下内容:

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

由于我的输入树是S表达式，我考虑使用Lisp（嵌入到我的Python程序中），但我已经很久没有用Lisp编写过任何重要的东西了，甚至不知道该从哪里开始。

如何描述这些模式？如何描述这些操作？如何思考这个问题？

- guidoism

Answer 1

“眼见为实”，但是您从未说明Tregex或Tsurgeon的代码有多混乱。听起来更像是您无法处理Java或更高层次抽象，因此您正在寻找用Python编写的具体内容。

手写树匹配和转换函数没有任何问题。事实上，我们以前经常这样做。但在写了几百个之后，似乎必须有更好的方法，因此我们开始使用Tregex和Tsurgeon的领域特定语言。这通常被视为一种值得称赞的编程风格。请参见Wikipedia。它们是具有精确语法规范等确切语法规范的规范化语言。以下是您可以使用它们的示例。

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中手写匹配树上的模式并将其转换为其他树的方法，那么您可以自行去做。

- Christopher Manning

---

使用SP树正则表达式的文档在哪里可以找到？或者目前只有JavaDocs是唯一的文档？ - sholsapp

啊，你好Manning教授，很抱歉我在没有提供具体原因的情况下批评了您的工作。我想对代码进行一些修改，但是对于仅添加一点抽象层而言，10万行代码有些令人望而生畏。我非常感激Tregex/Turgeon的存在。我只是好奇是否可以编写一个类似的DSL更加简洁。仍然存在Java<->Python交互的问题，我已经用一种不太令人满意的方式解决了这个问题，但它（有点）有效。 - guidoism

@gnucom：我承认文档可能需要更好/更详尽的说明。但是还有其他几个资源。ppt幻灯片http://nlp.stanford.edu/software/tregex/The_Wonderful_World_of_Tregex.ppt是介绍tregex模式的最佳选择。GUI应用程序中有有用的帮助屏幕。更多信息请参见：http://nlp.stanford.edu/software/tregex-faq.shtml#b。 - Christopher Manning

@guidoism: 顺便说一句，这不是我的工作。 DSL和大部分代码都是由Roger Levy和Galen Andrew编写的。 我相信在其他语言（如Scala或Clojure）中可以更简洁地编写DSL，这些语言更适合于编写DSL。 Java远非简洁，并且不特别针对编写DSL。但我认为你的主要观点是，如果您只想添加几个特殊情况，并且您对工具和代码不是很熟悉，则使用tree函数比使用DSL更容易实现，因为您需要更改标记器和解析器等内容。 - Christopher Manning

Answer 2

这是使用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)))))))))))

- Rainer Joswig

Answer 3

这是Common Lisp的第二个版本。这次我使用了一个模式匹配器。

我使用了一个函数来匹配Lisp数据与模式。PMATCH:MATCH是Winston/Horn的书中发现的模式匹配器的增强版本，有类似的模式匹配函数可用。

数据与我的其他答案相同。

树映射函数被更改为使用模式匹配器。如果匹配成功，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)))

这个示例现在使用模式。

该模式是一个列表结构。#?符号匹配单个项并为符号创建绑定。#$符号匹配一组项目并为符号创建绑定。

转换器是一个将使用这些绑定实例化的模式。

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

运行此代码将得到与我其他答案中相同的结果。

- Rainer Joswig

---

好的，treemapp可以适应使用optima lib（https://github.com/m2ym/optima），但仍存在一个限制，即转换仅在树的第一个匹配中完成。 - Alexandre Rademaker