如何操作分析樹？

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

和（這是一個簡化的例子）：

1. 找到與標籤NP具有任何節點第一個標籤爲NP的孩子和一些名爲「銀行」的後代，第二個孩子的標籤爲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的東西，所以我不知道從哪裏開始。

什麼是描述模式的好方法？什麼是描述操作的好方法？想想這個問題的好方法是什麼？

Answer 1

這是一個使用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))))))))))) 

Answer 2

美在觀察者的眼中。但你永遠不會說如何 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中的其他樹，那麼歡迎您離開並執行此操作。

Answer 3

這是Common Lisp的第二個版本。這次我使用模式匹配器。

我正在使用匹配Lisp數據模式的函數。 PMATCH：MATCH是在Winston/Horn，Lisp第3版中找到的模式匹配的增強版本。有類似的模式匹配功能可用。

該數據與我的其他答案一樣。

將樹映射功能更改爲使用模式匹配器。如果匹配成功，則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))))) 

運行此代碼返回與我的其他答案相同的結果。