सीके वाई पार्सिंग

CKY पार्सिंग (जिसे CYK भी कहा जाता है, Cocke-Younger-Kasami के लिए) संदर्भ-मुक्त व्याकरणों के लिए एक पार्सिंग एल्गोरिदम है जो बॉटम-अप पार्सिंग और डायनामिक प्रोग्रामिंग का उपयोग करता है। इसे पहली बार 1961 में Itiroo Sakai द्वारा प्रकाशित किया गया था और बाद में स्वतंत्र रूप से John Cocke, Daniel Younger, Tadao Kasami, और Jacob T. Schwartz द्वारा पुनः खोजा गया, जिनके नाम पर इसका नाम रखा गया है। एल्गोरिदम यह निर्धारित करता है कि क्या दिया गया स्ट्रिंग किसी व्याकरण द्वारा उत्पन्न किया जा सकता है और, यदि हाँ, तो उस स्ट्रिंग के लिए सभी संभावित पार्स ट्री का निर्माण कर सकता है।

CKY का मानक संस्करण केवल चॉम्स्की सामान्य रूप (CNF) में संदर्भ-मुक्त व्याकरणों पर कार्य करता है, जहाँ हर उत्पादन नियम या तो A → BC (दो गैर-टर्मिनल) या A → a (एक टर्मिनल) के रूप में होता है। कोई भी संदर्भ-मुक्त व्याकरण जो खाली स्ट्रिंग उत्पन्न नहीं करता है, उसे एल्गोरिदमिक रूप से समकक्ष CNF व्याकरण में बदला जा सकता है, इसलिए यह प्रतिबंध सिद्धांत रूप में एल्गोरिदम की प्रयोज्यता को सीमित नहीं करता है। खाली स्ट्रिंग उत्पन्न करने वाले व्याकरणों के लिए, कोई स्पष्ट रूप से नियम S → ε की अनुमति दे सकता है, जहाँ S प्रारंभ प्रतीक है।

CKY पार्सिंग का महत्व इसकी सबसे खराब स्थिति समय जटिलता O(n^3 · |G|) से उत्पन्न होता है, जहाँ n इनपुट स्ट्रिंग की लंबाई है और |G| CNF व्याकरण का आकार है। यह इसे स्पर्शोन्मुख सबसे खराब स्थिति व्यवहार के संदर्भ में सबसे कुशल पार्सिंग एल्गोरिदम में से एक बनाता है, हालाँकि व्यावहारिक परिदृश्यों में अन्य एल्गोरिदम के औसत चलने का समय बेहतर हो सकता है।

एल्गोरिदम अवलोकन

एल्गोरिदम एक त्रि-आयामी तालिका P[l, s, v] भरकर काम करता है, जहाँ प्रत्येक प्रविष्टि एक बूलियन मान है जो दर्शाती है कि क्या स्थिति s से शुरू होने वाली लंबाई l की उपस्ट्रिंग गैर-टर्मिनल R_v से उत्पन्न की जा सकती है। तालिका उपस्ट्रिंग की लंबाई के बढ़ते क्रम में भरी जाती है, जो लंबाई 1 की उपस्ट्रिंग से शुरू होती है।

इनपुट में प्रत्येक टर्मिनल प्रतीक के लिए, एल्गोरिदम R_v → a_s के रूप के सभी यूनिट उत्पादनों की जाँच करता है और संबंधित तालिका प्रविष्टियों को सत्य के रूप में चिह्नित करता है। लंबी उपस्ट्रिंग के लिए, यह उपस्ट्रिंग के हर संभावित विभाजन को दो भागों में मानता है और जाँचता है कि क्या कोई उत्पादन A → BC मौजूद है जैसे कि B पहला भाग उत्पन्न करता है और C दूसरा भाग उत्पन्न करता है। यदि ऐसा उत्पादन मौजूद है, तो A के लिए प्रविष्टि सत्य पर सेट की जाती है।

स्यूडोकोड

मान लें कि इनपुट एक स्ट्रिंग I है जिसमें n वर्ण हैं: a1 ... an।

मान लें कि व्याकरण में r गैर-टर्मिनल प्रतीक R1 ... Rr हैं, जिसमें प्रारंभ प्रतीक R1 है।

मान लें कि P[n,n,r] बूलियन की एक सरणी है। P के सभी तत्वों को false पर प्रारंभ करें।

मान लें कि back[n,n,r] बैकपॉइंटिंग ट्रिपल की सूचियों की एक सरणी है। back के सभी तत्वों को खाली सूची पर प्रारंभ करें।

प्रत्येक s = 1 से n के लिए

प्रत्येक यूनिट उत्पादन Rv → as के लिए

P[1,s,v] = true सेट करें

प्रत्येक l = 2 से n के लिए -- स्पैन की लंबाई

प्रत्येक s = 1 से n-l+1 के लिए -- स्पैन की शुरुआत

प्रत्येक p = 1 से l-1 के लिए -- स्पैन का विभाजन

प्रत्येक उत्पादन Ra → Rb Rc के लिए

यदि P[p,s,b] और P[l-p,s+p,c] तो

P[l,s,a] = true सेट करें,

<p,b,c> को back[l,s,a] में जोड़ें

यदि P[n,1,1] true है तो

I भाषा का सदस्य है

back लौटाएं -- back के माध्यम से चरणों को पुनः ट्रेस करके, स्ट्रिंग के सभी संभावित पार्स ट्री आसानी से बनाए जा सकते हैं।

अन्यथा

"भाषा का सदस्य नहीं है" लौटाएं

उदाहरण

CNF में निम्नलिखित व्याकरण पर विचार करें:

S → NP VP

VP → VP PP

VP → V NP

VP → eats

PP → P NP

NP → Det N

NP → she

V → eats

P → with

Det → the

N → fish

स्ट्रिंग "she eats the fish with the fish" को पार्स करने के लिए, एल्गोरिदम पहले सभी लंबाई-1 उपस्ट्रिंग को चिह्नित करता है। उदाहरण के लिए, P[1,1,NP] को true पर सेट किया जाता है क्योंकि NP → she, और P[1,2,VP] को true पर सेट किया जाता है क्योंकि VP → eats। फिर यह लंबाई-2 उपस्ट्रिंग को संसाधित करता है, जैसे "she eats", जिसे S → NP VP के रूप में व्युत्पन्न किया जा सकता है, इसलिए P[2,1,S] true हो जाता है। प्रक्रिया लंबी उपस्ट्रिंग के लिए जारी रहती है, सभी विभाजनों पर विचार करते हुए। अंत में, यदि P[n,1,S] true है, तो स्ट्रिंग को भाषा के भाग के रूप में पहचाना जाता है, और बैकपॉइंटर्स पार्स ट्री के पुनर्निर्माण की अनुमति देते हैं।

अनुप्रयोग और विविधताएँ

CKY पार्सिंग प्राकृतिक भाषा प्रसंस्करण और कम्प्यूटेशनल भाषाविज्ञान में व्यापक रूप से उपयोग की जाती है, विशेष रूप से संभाव्य संदर्भ-मुक्त व्याकरणों के साथ पार्सिंग के लिए। एल्गोरिदम की विविधताएँ भारित व्याकरणों को संभालने और औसत-स्थिति प्रदर्शन में सुधार करने के लिए विकसित की गई हैं। एल्गोरिदम का डायनामिक प्रोग्रामिंग दृष्टिकोण इसे अन्य पार्सिंग विधियों से भी जोड़ता है, जैसे कि Earley पार्सर, जो CNF रूपांतरण के बिना मनमाने संदर्भ-मुक्त व्याकरणों को संभालता है लेकिन समान सबसे खराब स्थिति जटिलता रखता है।

आधुनिक Artificial intelligence प्रणालियों में, CKY पार्सिंग को बड़े पैमाने पर Neural network आधारित दृष्टिकोणों द्वारा प्रतिस्थापित किया गया है, विशेष रूप से Large language model में उपयोग किए जाने वाले Transformer (architecture) मॉडल द्वारा। हालाँकि, एल्गोरिदम औपचारिक भाषा सिद्धांत में एक महत्वपूर्ण आधारभूत तकनीक बनी हुई है और कंप्यूटर विज्ञान पाठ्यक्रमों में अभी भी पढ़ाई जाती है। इसके डायनामिक प्रोग्रामिंग और बॉटम-अप विश्लेषण के सिद्धांत अन्य क्षेत्रों में भी दिखाई देते हैं, जैसे Sequence-to-Sequence (Seq2Seq) मॉडल और Beam Search डिकोडिंग।

एल्गोरिदम की दक्षता और स्पष्टता ने इसे पार्सिंग और Machine learning पर पाठ्यपुस्तकों में एक मानक उदाहरण बना दिया है। MIT CSAIL और Stanford AI Lab जैसे शोध संस्थानों ने इसके अध्ययन और अनुप्रयोग में योगदान दिया है, और यह उन क्षेत्रों में प्रासंगिक बना हुआ है जिन्हें संरचित डेटा की सटीक पार्सिंग की आवश्यकता होती है, जैसे बायोइन्फॉर्मेटिक्स और कंपाइलर डिज़ाइन।

सीमाएँ

CKY पार्सिंग के लिए व्याकरण को चॉम्स्की सामान्य रूप में होना आवश्यक है, जो उत्पादन नियमों की संख्या और व्याकरण के आकार को बढ़ा सकता है। O(n^3) सबसे खराब स्थिति समय जटिलता बहुत लंबे इनपुट स्ट्रिंग के लिए निषेधात्मक हो सकती है, विशेष रूप से वास्तविक समय अनुप्रयोगों में। इसके अतिरिक्त, एल्गोरिदम की स्थान जटिलता O(n^2 · r) है, जो कई गैर-टर्मिनलों वाले व्याकरणों के लिए बड़ी हो सकती है। इन सीमाओं के बावजूद, CKY पार्सिंग सटीक पार्सिंग एल्गोरिदम के लिए एक बेंचमार्क और संदर्भ-मुक्त भाषाओं के अध्ययन में एक प्रमुख अवधारणा बनी हुई है।