Làm cách nào để thao tác phân tích cú pháp cây?

Question

Tôi đã chơi xung quanh với ngôn ngữ tự nhiên phân tích các cây và thao tác chúng theo nhiều cách khác nhau. Tôi đã sử dụng các công cụ Tregex và Tsurgeon của Stanford nhưng mã là một mớ hỗn độn và không phù hợp với môi trường Python của tôi (những công cụ này là Java và không lý tưởng cho việc tinh chỉnh). Tôi muốn có một bộ công cụ cho phép hack dễ dàng khi tôi cần thêm chức năng. Có bất kỳ công cụ nào khác phù hợp để thực hiện đối sánh mẫu trên cây và sau đó thao tác với các nhánh phù hợp đó không?

Ví dụ, tôi muốn để có những cây sau đây như là đầu vào:

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

và (đây là một ví dụ đơn giản):

1. Tìm bất kỳ nút với nhãn NP có một đứa trẻ đầu tiên có nhãn NP và một số con cháu có tên là "Ngân hàng", và một đứa con thứ hai có nhãn PP.
2. Nếu điều đó phù hợp, sau đó đưa tất cả các trẻ em của nút PP và di chuyển chúng đến cuối của trẻ em NP của phù hợp.

Ví dụ, tham gia này của cây:

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

và biến nó thành này:

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

Kể từ cây đầu vào của tôi là S-biểu thức tôi đã xem xét sử dụng Lisp (nhúng vào chương trình Python của tôi) nhưng nó đã được quá lâu mà tôi đã viết bất cứ điều gì đáng kể trong Lisp mà tôi không có ý tưởng nơi để thậm chí bắt đầu.

Điều gì sẽ là cách hay để mô tả các mẫu? Điều gì sẽ là một cách hay để mô tả các thao tác? Một cách hay để suy nghĩ về vấn đề này là gì?

Answer 1

Đây là trường hợp điển hình khi sử dụng Lisp. Bạn sẽ cần một hàm ánh xạ một hàm khác trên cây.

Dưới đây là ví dụ về kết hợp thủ tục sử dụng Common Lisp. Có các matchers trong Lisp làm việc trên các cấu trúc danh sách, có thể được sử dụng thay thế. Việc sử dụng trình so khớp danh sách sẽ đơn giản hóa ví dụ (xem câu trả lời khác của tôi cho ví dụ bằng cách sử dụng trình ghép mẫu).

Mã:

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

Ví dụ:

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

Chạy ví dụ:

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

Beauty là trong mắt của kẻ si tình. Nhưng bạn không bao giờ nói cách mã của Tregex hoặc Tsurgeon là một mớ hỗn độn. Nghe có vẻ giống như bạn không thể đối phó với Java hoặc trừu tượng hơn và vì vậy bạn đang tìm kiếm một cái gì đó cụ thể bằng văn bản trong Python.

Không có gì sai với chức năng đối sánh và chuyển đổi cây viết tay. Thật vậy, chúng tôi thường làm như vậy. Nhưng sau vài trăm đầu tiên, có vẻ như phải có một cách tốt hơn, và do đó chúng tôi chuyển sang sử dụng các ngôn ngữ cụ thể của miền Tregex và Tsurgeon. Điều này thường được xem như là một phong cách lập trình đáng khen ngợi. Xem trong Wikipedia.Chúng là các ngôn ngữ được chỉ định rõ ràng với đặc tả cú pháp chính xác, v.v. Đây là ví dụ của bạn khi sử dụng chúng.

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

Lưu ý rằng mã Java thực sự là ngắn hơn mã Lisp, chính vì sử dụng các ngôn ngữ miền cụ thể. Thật khó để thấy cách này có thể đơn giản hơn: chỉ định mẫu, chỉ định hoạt động, áp dụng.

Nhưng nếu bạn thích các phương pháp viết tay phù hợp với các mẫu trên cây và thay đổi chúng thành các cây khác bằng Python, thì bạn được hoan nghênh nhất để thực hiện điều đó.

Answer 3

Đây là phiên bản thứ hai trong Common Lisp. Lần này, tôi đang sử dụng mẫu đối sánh mẫu.

Tôi đang sử dụng hàm phù hợp với mẫu chống lại dữ liệu Lisp. PMATCH: MATCH là một phiên bản nâng cao của một mẫu phù hợp được tìm thấy trong cuốn sách Winston/Horn, Lisp, 3rd Edition. Có sẵn các chức năng khớp mẫu tương tự.

Dữ liệu giống như câu trả lời khác của tôi.

Chức năng ánh xạ cây được thay đổi để sử dụng trình so khớp mẫu. Hàm PMATCH: MATCH trả về T hoặc danh sách kết hợp assoc nếu khớp thành công. Nó trả về NIL nếu trận đấu không thành công. PMATCH: INSTANTIATE-PATTERN có một mẫu và một tập hợp các ràng buộc. Nó trả về một cấu trúc danh sách mới, trong đó các biến mẫu được thay thế bằng các ràng buộc.

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

ví dụ hiện sử dụng mẫu.

Mẫu là cấu trúc danh sách. Biểu tượng #? khớp với một mục duy nhất và tạo một ràng buộc cho biểu tượng. Biểu tượng # $ khớp với một danh sách các mục và tạo ra một ràng buộc cho biểu tượng.

Biến áp là mẫu sẽ được khởi tạo với các ràng buộc.

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

Chạy mã này trả về kết quả tương tự như trong câu trả lời khác của tôi.