सीवाईके एल्गोरिथ्म

कॉक-यंगर-कसामी एल्गोरिथ्म (CYK, या CKY) कंप्यूटर विज्ञान में संदर्भ-मुक्त व्याकरणों के लिए एक पार्सिंग एल्गोरिथ्म है। इसे पहली बार 1961 में इतिरू सकाई द्वारा प्रकाशित किया गया था और बाद में जॉन कॉक, डैनियल यंगर, तादाओ कसामी और जैकब टी. श्वार्ट्ज द्वारा पुनः खोजा गया, जिनके नाम पर इसका नाम रखा गया है। यह एल्गोरिथ्म नीचे-से-ऊपर पार्सिंग और गतिशील प्रोग्रामिंग का उपयोग करता है ताकि यह निर्धारित किया जा सके कि दिया गया स्ट्रिंग किसी दिए गए व्याकरण द्वारा उत्पन्न किया जा सकता है, और यह पार्स ट्री भी बना सकता है। इसका सबसे खराब स्थिति में चलने का समय O(n^3 · |G|) है, जहाँ n इनपुट स्ट्रिंग की लंबाई है और |G| चॉम्स्की सामान्य रूप में व्याकरण का आकार है, जो इसे असिम्प्टोटिक सबसे खराब जटिलता के संदर्भ में सबसे कुशल पार्सिंग एल्गोरिथ्मों में से एक बनाता है, हालाँकि व्यवहार में अन्य एल्गोरिथ्मों का औसत प्रदर्शन बेहतर हो सकता है।

CYK एल्गोरिथ्म व्यापक रूप से प्राकृतिक भाषा प्रसंस्करण और कंपाइलर डिज़ाइन में उपयोग किया जाता है, जहाँ पार्सिंग एक मौलिक चरण है। यह विशेष रूप से इसकी सरलता और गारंटीकृत बहुपद समय के लिए मूल्यवान है, यहाँ तक कि अस्पष्ट व्याकरणों के लिए भी। एल्गोरिथ्म की गतिशील प्रोग्रामिंग पर निर्भरता इसे सभी संभावित पार्स को व्यवस्थित रूप से संभालने की अनुमति देती है, जो प्रोग्रामिंग भाषाओं में वाक्यविन्यास विश्लेषण और कृत्रिम बुद्धिमत्ता प्रणालियों में वाक्यविन्यास पार्सिंग जैसे अनुप्रयोगों में उपयोगी है।

ऐतिहासिक पृष्ठभूमि

यह एल्गोरिथ्म पहली बार 1961 में इतिरू सकाई द्वारा वर्णित किया गया था, लेकिन 1960 के दशक के अंत में जॉन कॉक, डैनियल यंगर और तादाओ कसामी द्वारा स्वतंत्र पुनः खोजों के माध्यम से प्रमुखता प्राप्त की। जैकब टी. श्वार्ट्ज ने भी इसके विकास में योगदान दिया। एल्गोरिथ्म का नाम इन पुनः खोजों को दर्शाता है, जिसमें CYK संक्षिप्त नाम कॉक, यंगर और कसामी से लिया गया है। यह एल्गोरिथ्म कंप्यूटर विज्ञान शिक्षा में एक मानक विषय बन गया, विशेष रूप से औपचारिक भाषाओं और ऑटोमेटा सिद्धांत के पाठ्यक्रमों में। इसका विकास आधुनिक मशीन लर्निंग और तंत्रिका नेटवर्क पार्सिंग दृष्टिकोणों से पहले हुआ था, लेकिन यह एक मौलिक तकनीक के रूप में प्रासंगिक बना हुआ है।

मानक रूप: चॉम्स्की सामान्य रूप

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

एल्गोरिथ्म विवरण

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

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

अंत में, इनपुट स्ट्रिंग को भाषा के सदस्य के रूप में पहचाना जाता है यदि P[n, 1, 1] सत्य है, जिसका अर्थ है कि प्रारंभ प्रतीक R_1 पूरे स्ट्रिंग को व्युत्पन्न कर सकता है। फिर बैकपॉइंटर्स का उपयोग सभी संभावित पार्स ट्री बनाने के लिए किया जा सकता है।

उदाहरण

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

• S → NP VP
• VP → VP PP
• VP → V NP
• VP → eats
• PP → P NP
• NP → Det N
• NP → she
• V → eats
• P → with
• N → fish
• Det → the

यह व्याकरण "she eats the fish with the fork" जैसे वाक्यों को पार्स कर सकता है। CYK एल्गोरिथ्म पहले एक-शब्द सबस्ट्रिंग को चिह्नित करके तालिका भरेगा: "she" को NP के रूप में, "eats" को VP या V के रूप में, "the" को Det के रूप में, "fish" को N के रूप में, "with" को P के रूप में, और "fork" को N के रूप में। फिर यह सबस्ट्रिंग को जोड़ता है: "the fish" को NP (Det N) के रूप में, "eats the fish" को VP (V NP) के रूप में, और इसी तरह। अंततः, यह निर्धारित करता है कि पूरा वाक्य S से व्युत्पन्न किया जा सकता है, और बैकपॉइंटर्स पार्स ट्री संरचना को प्रकट करते हैं।

अनुप्रयोग और महत्व

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

सीमाएँ और विस्तार

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