😡 👩🏻‍⚕️ 〽️ अधिकतम समग्रता का पता लगाना 🕴🏽 🙏🏿 🥩

इस लेख में, मैं अधिकतम सामान्य अनुवर्ती या LCS (सबसे लंबे समय तक सामान्य अनुक्रम) की समस्या को हल करने के लिए लोकप्रिय एल्गोरिदम की समीक्षा करना चाहूंगा। चूंकि जोर सीखने पर है, और वास्तविक उपयोग पर नहीं है, इसलिए पायथन को कार्यान्वयन के लिए भाषा के रूप में चुना जाता है, जिससे कोड की मात्रा कम हो जाएगी और मुख्य विचारों पर ध्यान केंद्रित किया जाएगा।

परिभाषित

एक अनुक्रम तत्वों का एक क्रमबद्ध सेट है। एक स्ट्रिंग एक अनुक्रम का एक विशेष मामला है, आगे के उदाहरणों को केवल सादगी के तार के लिए माना जाएगा, लेकिन बदलाव के बिना उन्हें मनमाना पाठ या किसी अन्य चीज़ के लिए उपयोग किया जा सकता है।
आज्ञा देना एक अनुक्रम x होता है जिसमें तत्व x ₁ x ₂ ... x _m और एक अनुक्रम y होता है जिसमें तत्व y ₁ y ₂ ... y _{n होता है} । z , x का एक परिणाम है यदि वहाँ तत्व x के कड़ाई से बढ़ते सेट मौजूद है जिसमें से z प्राप्त किया गया है।
X और y के लिए एक सामान्य क्रम एक अनुक्रम z है जो कि x और उसके बाद y की एक अनुक्रिया दोनों है।
अधिकतम कुल लंबाई अधिकतम लंबाई के साथ कुल परिणाम है। पाठ में आगे हम संक्षिप्त नाम LCS का उपयोग करेंगे।
एक उदाहरण के रूप में, x = HA B R AHA BR , y = HARB OU R , इस मामले में LCS (x, y) = HARBR । आप पहले से ही एलसीएस गणना एल्गोरिदम पर सीधे जा सकते हैं, लेकिन यह समझना अच्छा होगा कि हमें इसकी आवश्यकता क्यों हो सकती है।

व्यावहारिक अनुप्रयोग

फ़ाइल तुलना कार्यक्रमों में सबसे आम उपयोग है, जैसे कि GNU भिन्न। एलसीएस को दो ग्रंथों के लिए पाया गया है, प्रारंभिक परिवर्तनों की सूची को x में बदलने के लिए या इसके विपरीत एक तुच्छ कार्य है। समग्र क्रमिकता के आधार पर एक बोनस के रूप में, आप दो अनुक्रमों की समानता निर्धारित करने के लिए एक मीट्रिक निर्दिष्ट कर सकते हैं। यही है, अब आप निश्चित रूप से व्यवसाय के लिए नीचे उतर सकते हैं।

पहला दृष्टिकोण या लोक कला

कुछ टिप्पणियों को शुरू करने के लिए:

यदि अनुक्रम x और y के लिए हमने पहले से ही LCS (x, y) = z की गणना की है, तो समान तत्व जोड़कर x और y से प्राप्त अनुक्रमों के लिए LCS z और इस जोड़े गए तत्व से मिलकर बनेगा
यदि हम अनुक्रम x और y में एक अलग तत्व जोड़ते हैं, तो प्राप्त xa और yb के लिए, LCS दो में से बड़ा होना चाहिए: LCS (x, yb) या LCS (xa, y)

ये अवलोकन पहले से ही पुनरावर्तन को लागू करने के लिए पर्याप्त हैं:

def LCS_RECURSIVE(x, y): if len(x) == 0 or len(y) == 0: return [] if x[-1] == y[-1]: return LCS_RECURSIVE(x[:-1], y[:-1]) + [x[-1]] else: left = LCS_RECURSIVE(x[:-1], y) right = LCS_RECURSIVE(x, y[:-1]) return left if len(left) > len(right) else right

अब आप सोच सकते हैं कि इस कार्यान्वयन के मामले में ऐसा नहीं है। सबसे खराब स्थिति में, जब x और y के बीच समान समान LCS_RECURSIVE तत्व नहीं होते हैं, तो 2 लेयन ^{(x) + लेन (y)} बार को रिकर्सन लेवल लेन (x) + लेन (y) पर बुलाया जाएगा। यहां तक कि अगर आप प्रदर्शन के लिए अपनी आँखें बंद करते हैं, तो कोड:

 from uuid import uuid4 x = [uuid4().hex for _ in xrange(500)] y = [uuid4().hex for _ in xrange(500)] print LCS_RECURSIVE(x,y)

अतिरिक्त कॉल के बिना, sys.setrecursionlimit विफल हो जाएगा। सबसे सफल कार्यान्वयन नहीं।

डायनेमिक प्रोग्रामिंग या 64 केबी सभी के लिए पर्याप्त है

प्रश्न में एल्गोरिथ्म को नीडलमैन-वून्श एल्गोरिथ्म के रूप में भी जाना जाता है।
पूरा दृष्टिकोण मैट्रिक्स में चरणबद्ध तरीके से उबलता है, जहां पंक्तियाँ x तत्व हैं और स्तंभ y तत्व हैं। भरते समय, पहले से किए गए अवलोकनों से उत्पन्न दो नियम लागू होते हैं:
1. यदि तत्व x _i , y _{j के} बराबर है तो सेल में (i, j) सेल का मान (i-1, j-1) एक के जोड़ के साथ लिखा जाता है
2. यदि तत्व x _i _, y _{j के} बराबर नहीं है _, तो मानों की अधिकतम (i-1, j) और (i, j-1) सेल (i, j) में दर्ज की जाती है।
फिलिंग में आई और जे को एक से बढ़कर एक दोहरे चक्र में जगह मिलती है, इसलिए प्रत्येक पुनरावृत्ति पर इस चरण में आवश्यक सेल मानों की गणना पहले से की जाती है:

 def fill_dyn_matrix(x, y): L = [[0]*(len(y)+1) for _ in xrange(len(x)+1)] for x_i,x_elem in enumerate(x): for y_i,y_elem in enumerate(y): if x_elem == y_elem: L[x_i][y_i] = L[x_i-1][y_i-1] + 1 else: L[x_i][y_i] = max((L[x_i][y_i-1],L[x_i-1][y_i])) return L

क्या हो रहा है इसका चित्रण:

कोशिकाएँ जिनमें सीधे वृद्धि हुई है, पर प्रकाश डाला गया है। मैट्रिक्स में भरने के बाद, इन कोशिकाओं को जोड़ने पर, हमें वांछित LCS मिलता है। इस मामले में, आपको अधिकतम से न्यूनतम सूचकांकों तक ले जाते समय कनेक्ट करना होगा, यदि सेल हाइलाइट किया गया है, तो एलसीएस में संबंधित तत्व जोड़ें, यदि नहीं, तो ऊपर या बाईं ओर आगे बढ़ें, इस पर निर्भर करता है कि मैट्रिक्स में बड़ा मूल्य कहां है:

 def LCS_DYN(x, y): L = fill_dyn_matrix(x, y) LCS = [] x_i,y_i = len(x)-1,len(y)-1 while x_i >= 0 and y_i >= 0: if x[x_i] == y[y_i]: LCS.append(x[x_i]) x_i, y_i = x_i-1, y_i-1 elif L[x_i-1][y_i] > L[x_i][y_i-1]: x_i -= 1 else: y_i -= 1 LCS.reverse() return LCS

एल्गोरिथ्म की जटिलता हे (len (x) * len (y)), वही मेमोरी स्कोर। इस प्रकार, अगर मैं लाइन की तुलना 100,000 लाइनों की दो फाइलों से करना चाहता हूं, तो मुझे मेमोरी में 10 ¹⁰ तत्वों के मैट्रिक्स को स्टोर करने की आवश्यकता होगी। यानी वास्तविक उपयोग के बारे में एक स्मृतिError प्राप्त करने की धमकी देता है नीले रंग से लगभग। अगले एल्गोरिथ्म पर आगे बढ़ने से पहले, हम ध्यान दें कि तत्वों x पर प्रत्येक पुनरावृत्ति में मैट्रिक्स एल में भरने पर, हमें पिछले चाल में प्राप्त केवल पंक्ति की आवश्यकता है। यानी यदि कार्य केवल LCS की गणना की आवश्यकता के बिना LCS की लंबाई खोजने के लिए सीमित था, तो यह O (len (y)) के लिए मेमोरी उपयोग को कम करना संभव होगा, मैट्रिक्स L की केवल दो पंक्तियों को बचाएगा।

एक जगह या हिर्शबर्ग एल्गोरिथम के लिए लड़ना

इस एल्गोरिथ्म के पीछे का विचार सरल है: यदि आप इनपुट अनुक्रम x = x ₁ x ₂ ... x _m को किसी भी सीमा सूचकांक i के लिए xb = x ₁ x ₂ ... x _i और xe = x _{i + 1} से दो मनमाने भागों में विभाजित करते हैं _। x _{i + 2} ... x _m , तो इसी तरह से विभाजन y का एक तरीका है (y में = y ₁ y ₂ ... y _j और ye = y _{j + 1} y _{j + 2} ... y _n ) जैसे कि LCS (x, y) = LCS (xb, yb) + LCS (xe, ye)।
इस विभाजन को खोजने के लिए y प्रस्तावित है:

X और y के लिए fill_dyn_matrix के साथ डायनामिक मैट्रिक्स L भरें। L1 हम गणना की गई मैट्रिक्स L की अंतिम पंक्ति की बराबरी करते हैं
* * Xe और * y के लिए मैट्रिक्स L में भरें (Pyeon के संदर्भ में xe और y के लिए व्युत्क्रम क्रम): सूची (उलट (x)), सूची (उलट (y)))। हम गणना की गई मैट्रिक्स एल की अंतिम पंक्ति को * L2 के बराबर करते हैं, L2 * L2 से नदी है
इंडेक्स के बराबर j ले लो जिसके लिए L1 [j] + L2 [j] का योग अधिकतम हो

इसे मैट्रिक्स L को दो विपरीत छोरों से भरने के रूप में दर्शाया जा सकता है:

ध्यान दें कि चूंकि मैट्रिक्स एल की अंतिम पंक्ति में केवल एक आवश्यकता है, तो गणना के दौरान पूरे मैट्रिक्स को संग्रहीत करना आवश्यक नहीं है। हमारे द्वारा मिलने वाले fill_dyn_matrix के कार्यान्वयन में थोड़ा बदलाव आया है:

 def lcs_length(x, y): curr = [0]*(1 + len(y)) for x_elem in x: prev = curr[:] for y_i, y_elem in enumerate(y): if x_elem == y_elem: curr[y_i + 1] = prev[y_i] + 1 else: curr[y_i + 1] = max(curr[y_i], prev[y_i + 1]) return curr

अब सीधे, एल्गोरिथ्म के बारे में ही। यह एक क्लासिक विभाजन है और जीतता है: जबकि अनुक्रम x में तत्व हैं, हम x को आधे में विभाजित करते हैं, y के लिए उपयुक्त विभाजन पाते हैं और अनुक्रमों (xb, yb) और (xe, ye) के जोड़े के लिए पुनरावर्ती कॉल का योग लौटाते हैं। ध्यान दें कि तुच्छ मामले में, यदि x में एक तत्व होता है और y में होता है, तो हम बस इस एकल तत्व x से एक अनुक्रम लौटाते हैं।

 def LCS_HIRSHBERG(x, y): x_len = len(x) if x_len == 0: return [] elif x_len == 1: if x[0] in y: return [x[0]] else: return [] else: i = x_len // 2 xb, xe = x[:i], x[i:] L1 = lcs_length(xb, y) L2 = reversed(lcs_length(xe[::-1], y[::-1])) SUM = (l1 + l2 for l1,l2 in itertools.izip(L1, L2)) _, j = max((sum_val, sum_i) for sum_i, sum_val in enumerate(SUM)) yb, ye = y[:j], y[j:] return LCS_HIRSHBERG(xb, yb) + LCS_HIRSHBERG(xe, ye)

अब हमारे पास O (len (y)) मेमोरी आवश्यकताएं हैं, गणना के लिए आवश्यक समय दोगुना हो गया है, लेकिन O (len (x) len (y)) अभी भी asymptotically है।

हंट-सिजमेंस्की एल्गोरिदम

पहली चीज जो हमें चाहिए वह है माचिस की मेज का हैश बनाना, जिसमें दूसरे क्रम के तत्वों के सूचक होंगे। इसके लिए आवश्यक समय O (len (y)) है। निम्नलिखित अजगर कोड यह करता है:

 y_matchlist = {} for index, elem in enumerate(y): indexes = y_matchlist.setdefault(elem, []) indexes.append(index) y_matchlist[elem] = indexes

HARBOR अनुक्रम के लिए, हैश निम्नानुसार होगा {'ए': [1], 'बी': [3], 'एच': [0], 'ओ': [4], 'आर': [2, 6] , 'U': [5]}।

अगला, अनुक्रम x के तत्वों को छांटता है, तैयार की गई सूची से संबंधित सूचकांकों के साथ THRESH सरणी भरें, ताकि THRESH के k-th तत्व का मान सूचकांक y_index होना चाहिए, बशर्ते कि THESESH [k-1] <y_index और y_index <THRESH [k]। इस प्रकार, किसी भी समय, THRESH सरणी को क्रमबद्ध किया जाता है और हम उपयुक्त k को खोजने के लिए बाइनरी खोज का उपयोग कर सकते हैं। THRESH तत्व को अपडेट करते समय, हम अपने LCS में y_index इंडेक्स के अनुरूप अनुक्रम तत्व भी जोड़ते हैं। निम्नलिखित कोड स्पष्ट कर सकते हैं:

 x_length, y_length = len(x), len(y) min_length = min(x_length, y_length) THRESH = list(itertools.repeat(y_length, min_length+1)) LINK_s1 = list(itertools.repeat(None, min_length+1)) LINK_s2 = list(itertools.repeat(None, min_length+1)) THRESH[0], t = -1, 0 for x_index,x_elem in enumerate(x): y_indexes = y_matchlist.get(x_elem, []) for y_index in reversed(y_indexes): k_start = bisect.bisect_left(THRESH, y_index, 1, t) k_end = bisect.bisect_right(THRESH, y_index, k_start, t) for k in xrange(k_start, k_end+2): if THRESH[k-1] < y_index and y_index < THRESH[k]: THRESH[k] = y_index LINK_x[k] = (x_index, LINK_x[k-1]) if k > t: t = k

उसके बाद, हम केवल LINK_x से ही अनुक्रम एकत्र कर सकते हैं।
इस एल्गोरिथ्म का रनिंग टाइम O ((r + n) लॉग एन) है, जहां n बड़े अनुक्रम की लंबाई है और r मैचों की संख्या है, सबसे खराब स्थिति में, जब r = n * n होता है, तो हमें पिछले समाधान की तुलना में एक खराब चल रहा समय मिलता है। स्मृति आवश्यकताएं O (r + n) के क्रम की रहती हैं।

कुल मिलाकर

बहुत सारे एल्गोरिदम हैं जो इस समस्या को हल करते हैं, asymptotically, सबसे कुशल एल्गोरिथ्म (Masek और Paterson) में O (n * n / log n) समय का अनुमान है। एलसीएस गणना में समग्र छोटी दक्षता को देखते हुए, व्यवहार में, एल्गोरिथम रन से पहले सबसे सरल तैयारी की जाती है, जैसे कि शुरुआत में और अनुक्रमों के अंत में समान तत्वों को छोड़ना और अनुक्रमों के बीच तुच्छ अंतर की खोज करना। इसके अलावा, बिट ऑपरेशंस का उपयोग करने वाले कुछ अनुकूलन हैं जो ऑपरेटिंग समय के स्पर्शोन्मुख व्यवहार को प्रभावित नहीं करते हैं।
उदाहरणों के साथ सभी कोड डाउनलोड करें

अधिकतम समग्रता का पता लगाना