मैं पार्स पेड़ों में हेरफेर कैसे करूं?

Question

मैं प्राकृतिक भाषा पार्स पेड़ों के साथ खेल रहा हूं और उन्हें विभिन्न तरीकों से जोड़ रहा हूं। मैं स्टैनफोर्ड के ट्रेगेक्स और Tsurgeon उपकरण का उपयोग कर रहा हूं, लेकिन कोड एक गड़बड़ है और मेरे ज्यादातर पायथन पर्यावरण के साथ फिट नहीं है (वे उपकरण जावा हैं और tweaking के लिए आदर्श नहीं हैं)। मैं एक टूलसेट चाहता हूं जो मुझे अधिक कार्यक्षमता की आवश्यकता होने पर आसान हैकिंग की अनुमति देगा। क्या ऐसे कोई अन्य उपकरण हैं जो पेड़ों पर पैटर्न पैटर्न करने के लिए उपयुक्त हैं और फिर उन मिलान वाली शाखाओं में हेरफेर करते हैं?

उदाहरण के लिए, मैं इनपुट के रूप में निम्नलिखित पेड़ उठाना चाहते हैं:

(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. लेबल एनपी है के साथ किसी भी नोड का पता लगाएं लेबल एनपी और कुछ वंशज "बैंक" नामक पहला बच्चा, और लेबल पीपी वाला दूसरा बच्चा।
2. यदि वह मेल खाता है, तो पीपी नोड के सभी बच्चों को ले जाएं और उन्हें मिलान किए गए एनपी के बच्चों के अंत में ले जाएं।

उदाहरण के लिए, पेड़ के इस भाग लेते हैं:

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

और यह इस में बदल जाते हैं:

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

चूंकि मेरे इनपुट पेड़ एस भाव मैं लिस्प का उपयोग कर रहे हैं पर विचार किया है (मेरे पायथन कार्यक्रम में एम्बेडेड) लेकिन यह इतना लंबा रहा है कि मैंने लिस्प में कुछ भी महत्वपूर्ण लिखा है कि मुझे नहीं पता कि कहां से शुरू करना है।

पैटर्न का वर्णन करने का एक अच्छा तरीका क्या होगा? हेरफेर का वर्णन करने का एक अच्छा तरीका क्या होगा? इस समस्या के बारे में सोचने का एक अच्छा तरीका क्या है?

Answer 1

यह लिस्प का उपयोग करने का एक सामान्य मामला है। आपको एक ऐसे फ़ंक्शन की आवश्यकता होगी जो पेड़ पर एक और फ़ंक्शन को मानचित्र करे।

यहां सामान्य लिस्प का उपयोग करके एक प्रक्रियात्मक मिलान उदाहरण है। लिस्प में matchhers हैं जो सूची संरचनाओं पर काम करते हैं, जिसका उपयोग इसके बजाय किया जा सकता है। एक सूची मैचर का उपयोग उदाहरण को सरल बना देगा (पैटर्न मैचर का उपयोग करके उदाहरण के लिए मेरा दूसरा उत्तर देखें)।

कोड:

(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

सौंदर्य देखने वाले की आंखों में है। लेकिन आप कभी भी कैसे कहते हैं ट्रेगेक्स या 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(); 

ध्यान दें कि जावा कोड ठीक डोमेन विशिष्ट भाषा के प्रयोग की वजह, वास्तव में कम लिस्प कोड से है। यह देखना मुश्किल है कि यह कैसे आसान हो सकता है: पैटर्न निर्दिष्ट करें, ऑपरेशन निर्दिष्ट करें, लागू करें।

लेकिन यदि आप पेड़ पर पैटर्न से मेल खाने और पाइथन में अन्य पेड़ों में बदलने के लिए हाथ-लेखन विधियों को पसंद करना चाहते हैं, तो आप जाने और ऐसा करने के लिए आपका स्वागत है।

Answer 3

यहां सामान्य लिस्प में दूसरा संस्करण है। इस बार मैं पैटर्न मैचर का उपयोग कर रहा हूं।

मैं ऐसे फ़ंक्शन का उपयोग कर रहा हूं जो लिस्प डेटा के विरुद्ध पैटर्न से मेल खाता है। पीएमएटीएचएच: MATCH विंस्टन/हॉर्न, लिस्प, तीसरी संस्करण पुस्तक में पाए गए पैटर्न मैचर का एक उन्नत संस्करण है। समान पैटर्न मिलान कार्य उपलब्ध हैं।

डेटा मेरे अन्य उत्तर में है।

पेड़ मैपिंग फ़ंक्शन पैटर्न मैचर का उपयोग करने के लिए बदला जाता है। पीएमएटीएचएच: मैच सफल होने पर MATCH फ़ंक्शन बाइंडिंग की टी या एक आक्रमण सूची देता है। यदि मैच सफल नहीं होता है तो यह शून्य वापस आता है। पीएमएटीएचएच: इंस्टीट्यूट-पटरटन एक पैटर्न और बाइंडिंग का एक सेट लेता है। यह एक नई सूची संरचना देता है, जहां पैटर्न चर को बाइंडिंग के साथ बदल दिया जाता है।

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

इस कोड को चलाने से मेरा अन्य उत्तर जैसा ही परिणाम मिलता है।