सबसे लंबा सामान्य उपअनुक्रम: Python, C++ उदाहरण
सारा चेन
⚡ स्मार्ट सारांश
सबसे लंबी सामान्य अनुक्रम (Longest Common Subsequence) दो स्ट्रिंग्स द्वारा साझा किए गए सबसे लंबे क्रमबद्ध तत्व पैटर्न की पहचान करता है, जिसके लिए लगातार वर्णों की आवश्यकता नहीं होती है। यह डायनेमिक प्रोग्रामिंग की क्लासिक विधि बहुपद समय में अनुक्रमों की कुशलतापूर्वक तुलना करके डिफरेंस यूटिलिटीज, डीएनए अलाइनमेंट और वर्जन कंट्रोल का आधार बनती है।
सबसे लम्बा उभयनिष्ठ उपअनुक्रम क्या है?
सबसे लंबी सामान्य अनुक्रम (LCS) का अर्थ है कि आपको दो स्ट्रिंग, पैटर्न या वस्तुओं के अनुक्रम दिए जाएंगे। इन दो अनुक्रमों या स्ट्रिंग में से, आपको उन तत्वों का सबसे लंबा अनुक्रम खोजना होगा जो दोनों स्ट्रिंग या पैटर्न में समान क्रम में मौजूद हों।
उदाहरण
उदाहरण के लिए, दो स्ट्रिंग दी गई हैं। मान लीजिए कि:
पैटर्न_1 = “RGBGARGA”
पैटर्न_2 = “BGRARG”
- pattern_1 से “RGB”, “RGGA”, “RGAR” जैसी अनुक्रम संरचनाएँ बनाई जा सकती हैं। अनुक्रम संरचना बनाने के लिए, स्ट्रिंग में प्रत्येक वर्ण की सापेक्ष स्थिति का ध्यान रखना आवश्यक है।
- पैटर्न_2 से, हम "BGR", "BRAG", "RARG" जैसी अनुक्रम उत्पन्न कर सकते हैं। अनुक्रम तब तक उत्पन्न किए जा सकते हैं जब तक वे मूल स्ट्रिंग की सापेक्ष स्थिति को बनाए रखते हैं।
सापेक्ष स्थिति शब्द का अर्थ है क्रम।
उदाहरण के लिए, "BRG" एक वैध अनुक्रम है क्योंकि मूल स्ट्रिंग पैटर्न_2 में "B" पहले, फिर "R" और फिर "G" आया है। हालांकि, यदि कोई अनुक्रम "RBRG" है, तो वह वैध नहीं है, क्योंकि मूल स्ट्रिंग (पैटर्न_2) में "B" पहले आता है।
दिए गए दो अनुक्रमों या सारणी से सबसे लंबा सामान्य उपअनुक्रम खोजने के लिए हमारे पास दो विकल्प हैं।
- सरल विधि
- डायनेमिक प्रोग्रामिंग समाधान: सबसे लंबा कॉमन सबसीक्वेंस को LCS के रूप में भी जाना जाता है।
सरल समाधान की समय जटिलता अधिक होती है और यह सर्वोत्तम समाधान नहीं है। डायनामिक प्रोग्रामिंग सॉल्यूशन (डीपी) का उपयोग करके, हम जटिलता की समस्या को दूर करते हैं।
सरल विधि
सरल विधि समस्या के लिए एक सरल दृष्टिकोण है, चाहे समय जटिलता और अन्य अनुकूलन कारक कुछ भी हों। इसमें अधिकतर मामलों में "ब्रूट फोर्स", कई लूप और रिकर्सिव कॉल शामिल होते हैं। ब्रूट फोर्स का अर्थ है किसी दी गई समस्या के लिए सभी संभावित पैटर्न को आजमाना।
उदाहरण
पैटर्न1 और पैटर्न2 के उपरोक्त उदाहरण से, मान लें कि पैटर्न1 की लंबाई m है और पैटर्न2 की लंबाई n है। हर संभावित मामले की जाँच करने के लिए, हमें पैटर्न1 के साथ पैटर्न2 के हर संभावित उप-अनुक्रम का मूल्यांकन करने की आवश्यकता है।
यहां एक सरल चार अक्षरों वाली स्ट्रिंग "ABCD" है। उदाहरण के लिए, हमें "ABCD" से एक अनुक्रम बनाना है। हम चाहें तो एक अक्षर ले सकते हैं या नहीं। इसका मतलब है कि प्रत्येक अक्षर के लिए हमारे पास दो विकल्प हैं:
- वर्ण को उपअनुक्रम में जोड़ दिया जाएगा।
- वर्ण को उपअनुक्रम में नहीं जोड़ा जाएगा।
यहां, चित्र उन सभी अनुक्रमों को दर्शाते हैं जिन्हें हम स्ट्रिंग “ABCD” से बना सकते हैं।
1 वर्ण वाला अनुक्रम:
2 वर्णों वाले अनुक्रम:
3 वर्णों वाले अनुक्रम:
ऊपर दिए गए चित्र से 14 अनुक्रम प्राप्त होते हैं। यदि हम कोई अक्षर न लें, यानी एक खाली स्ट्रिंग लें, तो कुल अनुक्रम 15 होंगे। इसके अलावा, स्ट्रिंग "ABCD" स्वयं एक अनुक्रम है। अतः, कुल अनुक्रम 16 हो जाते हैं।
अतः, “ABCD” से 2^4 या 16 अनुक्रम उत्पन्न करना संभव है। फिर, एक स्ट्रिंग जिसकी लंबाई है m कुल अनुक्रम 2^m होगा।
प्रत्येक उप-अनुक्रम के लिए, हमें पूरे पैटर्न2 की जाँच करनी होगी। इसमें O(n) समय लगेगा। O(n) का अर्थ है वह जटिलता फ़ंक्शन जो निष्पादन में लगने वाले समय की गणना करता है।
तो, कुल समय जटिलता बन जाती है O(n*2^m). ऊपर दिए गए उदाहरण में, m का मान 8 और n का मान 5 है।
नैवे विधि के चरण इस प्रकार हैं:
चरण 1) पैटर्न 1 से एक अनुक्रम लें।
चरण 2) चरण 1 के अनुक्रम को पैटर्न 2 से मिलाएँ।
चरण 3) यदि यह मेल खाता है, तो उपअनुक्रम को सहेजें।
चरण 4) यदि पैटर्न 1 में और भी अनुक्रम शेष हैं, तो चरण 1 पर फिर से जाएं।
चरण 5) सबसे लंबे उपअनुक्रम को प्रिंट करें.
इष्टतम निर्माण
इष्टतम उपसंरचना शब्द का अर्थ है कि उपसमस्याओं को हल करके एक इष्टतम समाधान प्राप्त किया जा सकता है। उदाहरण के लिए, उपरोक्त उदाहरण में, हमारे पास पैटर्न 1 और पैटर्न 2 हैं।
चरण 1) प्रत्येक पैटर्न से पहले दो अक्षर लें।
चरण 2) प्रत्येक पैटर्न से तीसरे से पांचवें अक्षर लें।
चरण 3) शेष वर्णों के साथ भी इसी प्रकार आगे बढ़ें।
एल.सी.एस. समस्या की पुनरावर्ती संरचना
हम सबस्ट्रिंग (मूल स्ट्रिंग से उत्पन्न स्ट्रिंग) पर एलसीएस ज्ञात करते हैं। फिर हम सबस्ट्रिंग के एलसीएस की लंबाई का रिकॉर्ड रखते हैं।
अब, यहाँ एक और दिलचस्प संपत्ति है जो ओवरलैपping उप समस्याओंकिसी समस्या में ओवरलैप होने की बात कही जाती है।ping यदि समस्या कथन को छोटी-छोटी उपसमस्याओं में तोड़ा जा सकता है और प्रोग्राम में कई बार उपयोग किया जा सकता है, तो उन्हें उप-समस्याओं में विभाजित किया जा सकता है।
नीचे दिया गया चित्र दर्शाता है कि पुनरावर्ती एल्गोरिथ्म ने समान पैरामीटर वाले फ़ंक्शन को कई बार कॉल किया।
उदाहरण के लिए, रिकर्सन ट्री को देखें। गहरे रंग के बॉक्स में, आप ओवरलैप देख सकते हैं।ping उप-समस्याएँ (“आरजी”, “आरए”), (“आरजी”, “आर”), और अन्य को कई बार कहा जाता है।
इसे अनुकूलित करने के लिए, हमारे पास निम्नलिखित दृष्टिकोण है: गतिशील प्रोग्रामिंग (डीपी)
सबसे लंबी सामान्य अनुक्रम की पुनरावर्ती विधि
ऊपर दर्शाया गया ग्राफ पुनरावर्ती विधि को दर्शाता है। प्रत्येक पुनरावर्ती फ़ंक्शन में पुनरावर्ती क्रिया को तोड़ने या अपने स्टैक से वापस लौटना शुरू करने के लिए एक आधार स्थिति होती है।
इस कार्यान्वयन के लिए, हम एक आधार स्थिति का उपयोग करेंगे। इसलिए, कलन विधि निम्नलिखित जैसा है:
- यदि अंतिम तत्व से पहले के सभी तत्वों का मिलान हो जाता है, तो लंबाई को एक से बढ़ाएँ और वापस लौटें।
- फंक्शन में दो पैटर्न पास करें और रिटर्न का अधिकतम मान लें।
- यदि एक पैटर्न की लंबाई शून्य है, तो हमारे पास तुलना करने के लिए कोई उप-अनुक्रम नहीं है। इस मामले में 0 लौटाएँ। यह रिकर्सन का आधार मामला है।
उपनाम Code:
def lcs: input: pattern_1, pattern_2, len_1, len_2 if len_1 or len_2 is zero: return 0 if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]: return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1) else: return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
कार्यान्वयन C++
#include<iostream> #include<bits/stdc++.h> using namespace std; int lcs(string pattern_1, string pattern_2, int len_1, int len_2) { if (len_1 == 0 || len_2 == 0) return 0; if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) { return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1); } else { return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1)); } } int main() { string pattern_1, pattern_2; pattern_1 = "RGBGARGA"; pattern_2 = "BGRARG"; cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl; }
आउटपुट:
Length of LCS is: 5
कार्यान्वयन Python
def lcs(pattern_1, pattern_2, len_1, len_2): if len_1 == 0 or len_2 == 0: return 0 if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]: return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1) else: return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1)) pattern_1 = "RGBGARGA" pattern_2 = "BGRARG" print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))
आउटपुट:
Length of LCS is: 5
सबसे लंबी सामान्य अनुक्रम (LCS) की गतिशील प्रोग्रामिंग विधि
डायनामिक प्रोग्रामिंग का अर्थ है सामान्य रिकर्सिव विधि को अनुकूलित करना। उदाहरण के लिए, यदि हम रिकर्सिव या सरल दृष्टिकोण ग्राफ को देखें, तो हम देख सकते हैं कि इसमें कई समान फ़ंक्शन कॉल हैं। डायनामिक प्रोग्रामिंग विधि सभी गणनाओं को एक ऐरे में रिकॉर्ड करती है और आवश्यकता पड़ने पर उनका पुनः उपयोग करती है।
हम mxn आयामों वाली एक 2D सरणी का उपयोग करेंगे, जहाँ m और n पैटर्न 1 और पैटर्न 2 की लंबाई हैं। 2डी सरणीहम लिस्ट डेटा संरचनाओं का उपयोग कर सकते हैं Python या वेक्टर/एरे डेटा संरचनाओं में C++.
उपनाम Code डीपी का उपयोग करके एलसीएस के लिए:
LCS(pattern_1, pattern_2): m = length of pattern_1 + 1 n = length of pattern_2 + 1 dp[n][m] for i in range 0 to n + 1: for j in range 0 to m + 1: if i or j equals to 0: dp[i][j] = 0 else if pattern_1[i] == pattern_2[j]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[n][m]
यहां एलसीएस टेबल है जिसका उपयोग डायनेमिक प्रोग्रामिंग दृष्टिकोण के लिए 2डी ऐरे डेटा संरचना के रूप में किया जाता है।
आइए, यहाँ हमने जिस तर्क का प्रयोग किया है, उस पर चर्चा करें। चरण इस प्रकार हैं:
चरण 1) यदि i या j शून्य है, तो हम दी गई दो स्ट्रिंग में से एक खाली स्ट्रिंग लेते हैं और उभयनिष्ठ उप-अनुक्रम खोजने का प्रयास करते हैं। हालाँकि, क्योंकि हम जो उप-स्ट्रिंग ले रहे हैं वह खाली है, इसलिए उप-अनुक्रम की लंबाई शून्य है।
चरण 2) यदि दो अक्षर मेल खाते हैं, तो हम (i-1,j-1) सूचकांक (पिछली पंक्ति से) में मौजूद पहले से गणना किए गए LCS को बढ़ाकर (i,j) सूचकांक को मान निर्दिष्ट करेंगे।
चरण 3) यदि यह मेल नहीं खाता है, तो हम दो आसन्न सूचकांकों का अधिकतम LCS मान लेंगे। इस प्रकार, हमें 2D ऐरे में सभी मान भरने होंगे।
चरण 4) अंत में, हम 2D सारणी के अंतिम सेल का मान लौटाएंगे।
मूलतः, 2D एरे में सभी मानों में उभयनिष्ठ अनुक्रमों की लंबाई होती है। इनमें से अंतिम सेल में सबसे लंबे उभयनिष्ठ अनुक्रम की लंबाई होती है।
कार्यान्वयन C++
#include<iostream> using namespace std; int lcs(string pattern_1, string pattern_2) { int m = pattern_1.size(); int n = pattern_2.size(); // dp will store solutions as the iteration goes on int dp[n + 1][m + 1]; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < m + 1; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (pattern_2[i - 1] == pattern_1[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][m]; } int main() { string pattern_1 = "RGBGARGA"; string pattern_2 = "BGRARG"; cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl; }
आउटपुट:
Length of LCS: 5
कार्यान्वयन Python
def lcs(pattern_1, pattern_2): m = len(pattern_1) n = len(pattern_2) # dp will store solutions as the iteration goes on dp = [[None] * (n + 1) for item in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: dp[i][j] = 0 elif pattern_1[i - 1] == pattern_2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n] pattern_1 = "RGBGARGA" pattern_2 = "BGRARG" print("Length of LCS: ", lcs(pattern_1, pattern_2))
आउटपुट:
Length of LCS: 5
अतः, दोनों स्ट्रिंग्स में सबसे लंबा सामान्य उपअनुक्रम 5 लंबाई का है।
संक्षेप में कहें तो, डीपी विधि में हम प्रत्येक कार्य की गणना केवल एक बार करते हैं। पुनरावर्ती विधि में, ओवरलैप हो सकता है।ping उपसमस्याएँ।
इस डायनेमिक प्रोग्रामिंग एल्गोरिथम में, हम 2D मैट्रिक्स का उपयोग कर रहे हैं। दो स्ट्रिंग दी जाएंगी (मान लें कि दोनों की लंबाई n है)। फिर सरणी में आवश्यक स्थान nx n है। यदि स्ट्रिंग्स काफी बड़ी हैं, तो हमें DP समाधान के मेमोरी-अनुकूलित संस्करण की आवश्यकता होगी।
कोड में लिया गया सरलीकृत तर्क इस प्रकार है:
- एक 2D ऐरे DP[m][n] घोषित करें.
- DP सारणी की पहली पंक्ति और पहले कॉलम को 0 से भरें।
- पुनरावृत्ति के लिए i और j लें।
- यदि pattern1[i] pattern2[j] के बराबर है, तो DP[i][j] = DP[i-1][j-1] + 1 को अपडेट करें।
- यदि pattern1[i] pattern2[j] के बराबर नहीं है, तो DP[i][j] DP[i-1][j] और DP[i][j-1] के बीच अधिकतम मान होगा।
- तब तक जारी रखें जब तक i और j, m और n तक न पहुंच जाएं।
- अंतिम तत्व, DP[m-1][n-1], में लंबाई होगी।
यहां, इसे DP[m-1][n-1] के रूप में संबोधित किया जाता है क्योंकि सरणी सूचकांक 0 से शुरू होता है।
