संपादकीय दूरी की गणना

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

थोड़ा औपचारिकता

आज्ञा देना दो लाइनें S ₁ और S _{2 हैं} । हम एक को दूसरे में स्थानांतरित करना चाहते हैं (पहले को दूसरे में दें, यह दिखाना आसान है कि निम्नलिखित कार्यों का उपयोग करके ऑपरेशन सममित हैं):

• I: एक चरित्र को एक मनमाना स्थान में सम्मिलित करें;
• डी: एक चरित्र को मनमाने स्थान से हटाना;
• R: एक चरित्र को दूसरे के साथ बदलना।

फिर d (S ₁ , S ₂ ) S ₁ को S _{2 में} स्थानांतरित करने के लिए I / D / R संचालन की न्यूनतम संख्या है, और संपादकीय निर्देश उनके मापदंडों के साथ अनुवाद के लिए संचालन की एक सूची है।

वैगनर - फिशर एल्गोरिदम द्वारा समस्या का आसानी से हल किया जाता है, हालांकि, O (| S ₁ | * | S | S) संपादकीय नुस्खे को बहाल करने के लिए मेमोरी सेल्स की आवश्यकता होगी। मैं एल्गोरिथ्म को संक्षेप में बताता हूं, क्योंकि "अनुकूलन" इस पर आधारित है।

वैगनर-फिशर एल्गोरिथम

वांछित दूरी सहायक फ़ंक्शन डी (एम, एन) के माध्यम से बनाई जाती है, जो सब्सट्रिंग्स एस ₁ [0..M] और एस ₂ [0..N] के लिए संपादकीय दूरी पाता है। फिर कुल संपादकीय दूरी पूर्ण लंबाई के सबस्ट्रिंग के लिए दूरी के बराबर होगी: d (S ₁ , S ₂ ) = D _{S 1 , S 2} (M, N)।

स्वयं स्पष्ट तथ्य यह है कि:

डी (0,0) = 0।

दरअसल, खाली रेखाएं समान होती हैं।

इसके अलावा, अर्थ के लिए स्पष्ट है:

डी (i, 0) = i;
डी (0, जे) = जे।

वास्तव में, कोई भी रेखा खाली हो सकती है, सही संख्या में वर्ण जोड़कर, कोई भी अन्य ऑपरेशन केवल स्कोर बढ़ाएगा।

सामान्य मामले में, थोड़ा और अधिक जटिल:

D (i, j) = D (i-1, j-1) यदि S ₁ [i] = S ₂ [j,
अन्यथा, D (i, j) = min (D (i-1, j), D (i, j-1), D (i-1, j-1)) + 1।

इस मामले में, हम चुनते हैं कि कौन अधिक लाभदायक है: चरित्र (D (i-1, j)), जोड़ें (D (i, j-1)), या प्रतिस्थापित करें (D (i-1, j-1))।

यह समझना आसान है कि अनुमान प्राप्त करने के लिए एल्गोरिथ्म को दो से अधिक कॉलम, वर्तमान (डी (आई, *)) और पिछले (डी (आई -1, *)) की स्मृति की आवश्यकता नहीं है। हालांकि, संपादकीय पर्चे को बहाल करने के लिए पूर्ण मैट्रिक्स की आवश्यकता है। मैट्रिक्स के निचले दाएं कोने से शुरू होकर (M, N), हम प्रत्येक ऊपरी चरण पर जाते हैं, प्रत्येक चरण में न्यूनतम तीन संकेतों की तलाश करते हैं:

• यदि न्यूनतम (D (i-1, j) + 1), वर्ण S ₁ [i] का विलोपन जोड़ें और (i-1, j) पर जाएं;
• यदि न्यूनतम (D (i, j-1) + 1), प्रतीक S ₁ [i] का सम्मिलन जोड़ें और (i, j-1) पर जाएं;
• यदि न्यूनतम (D (i-1, j-1) + m), जहाँ m = 1, यदि S ₁ [i]! = S ₂ [j], अन्यथा m = 0; जिसके बाद हम (i-1, j-1) पर जाते हैं और यदि m = 1 है तो एक प्रतिस्थापन जोड़ें।

यहां (i, j) मैट्रिक्स की कोशिका है जिसमें हम इस कदम पर हैं। यदि तीन में से दो मान न्यूनतम हैं (या सभी तीन समान हैं), इसका मतलब है कि 2 या 3 बराबर संपादकीय नुस्खे हैं।

परिणामस्वरूप, O (| S ₁ | * | S ₂ |) समय और O (| S ₁ | * | | S ₂ |) मेमोरी आवश्यक है।

सामान्य तर्क

इस पद्धति के निर्माण के लिए एक शर्त एक साधारण तथ्य है: वास्तविक प्रणालियों में, स्मृति समय की तुलना में अधिक महंगा है। दरअसल, लंबाई में 2 ¹⁶ वर्णों के तार के लिए, लगभग 2 ³² कम्प्यूटेशनल ऑपरेशन (जो आधुनिक क्षमताओं के साथ गणना के दस सेकंड के भीतर गिर जाएंगे) और 2 ³² मेमोरी की आवश्यकता होती है, जो ज्यादातर मामलों में मशीन की भौतिक मेमोरी से पहले से ही बड़ा है।

सतह पर दूरी का अनुमान लगाने के लिए स्मृति की रैखिक राशि (2 * | एस ₁ |) का उपयोग कैसे करें, इसका विचार संपादकीय पर्चे की गणना में इसे सही ढंग से स्थानांतरित करने के लिए रहता है।

काउंटर गणना विधि (हिर्शबर्ग एल्गोरिथ्म)

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

S ₁ = ACGTACGTACGT,
S ₂ = AGTACCTACCGT।

लगता है? लेकिन एक "आंख से" दूसरे में फिर से लिखना इतना स्पष्ट नहीं है। पत्र, वैसे, संयोग से नहीं चुने गए थे - ये नाइट्रोजनस आधार (ए, टी, जी, सी), डीएनए घटक हैं: संपादकीय दूरी अनुमान पद्धति का उपयोग जीव विज्ञान में म्यूटेशन का मूल्यांकन करने के लिए सक्रिय रूप से किया जाता है।

तब मूल अनफिल्ड मैट्रिक्स दिखेगा (यह बिल्कुल दिखेगा, हम केवल आवश्यक डेटा स्टोर करेंगे) निम्नानुसार है:



प्रत्येक सेल में संपादकीय दूरी का मान होना चाहिए।

हम मूल कार्य को एक उप-भाग में विभाजित करते हैं, दूसरी पंक्ति को दो समान (या लगभग बराबर) भागों में विभाजित करते हैं, विभाजन की जगह को याद करते हैं, और मैट्रिक्स को ठीक उसी तरह से भरना शुरू करते हैं, जैसा कि हमने वैगनर-फिशर में किया था:



अंदर भरने पर, हम पिछले कॉलम को स्टोर नहीं करेंगे, बाएं से दाएं, ऊपर से नीचे तक, क्योंकि हम D (i, j) के मूल्यों की गणना करते हैं, D (i-1, j) के मूल्यों को हटाया जा सकता है:



इसी तरह, विभाजन के दाईं ओर भरें। यहां हम दाएं से बाएं, ऊपर से नीचे की ओर जाएंगे:



तो हम मिले। अब आप कोटियों के संयोजन से सामान्य समस्या के समाधान का हिस्सा प्राप्त कर सकते हैं। बाएं और दाएं कॉलम में प्राप्त मानों को संक्षेप करें और न्यूनतम चुनें।



इस संयोजन का क्या अर्थ है? हमने पहली पंक्ति को दूसरी पंक्ति के पहले भाग के साथ जोड़ने की कोशिश की, फिर पहली पंक्ति के दूसरी छमाही के साथ। योग आपको पहली पंक्ति को बदलने के लिए संचालन की संख्या प्राप्त करने की अनुमति देता है, ताकि यह दूसरी पंक्ति के पहले और दूसरे छमाही के समाप्ती की ओर जाए (अर्थात दूसरी पंक्ति के लिए) ... इसका मतलब है कि हमें संपादकीय दूरी मिल गई है! लेकिन, यह बहुत खुशी की बात है, क्योंकि यह परिणाम आसान हो सकता है (ऊपर वर्णित विधि)।

हालांकि, एक अलग कोण (शाब्दिक रूप से) की तस्वीर को देखते हुए, हमें एक और महत्वपूर्ण तथ्य मिला: अब हम जानते हैं कि पहली पंक्ति को दो हिस्सों में कैसे "कट" किया जाए, ताकि संबंधित जोड़े हमें संपादकीय दूरी दें: d (S _{1 1} , S _{2 1} ) + d (S _{1 2} , S _{2 2} ) = d (S ₁ , S ₂ )। पंक्ति (मैट्रिक्स में) जिसमें न्यूनतम स्थित है वांछित विभाजन S _{1 है} , और यह विभाजन संपादकीय पर्चे जारी करने के लिए भेजा जाता है।

इसी तरह, हम पहले से ही परिणामी पदार्थों एस _{1 1} और एस _{2 1 के} लिए कार्य को विभाजित करेंगे (और हम या तो दूसरा विकल्प नहीं भूलेंगे:



हम विभाजन को पूरा करते हैं जब _{1 से} अधिक लंबाई _का कोई सबस्ट्रिंग एस ₁ नहीं होता है।



हमें विभाजनों की एक सूची मिलती है, जहां प्रत्येक सब्स्ट्रिंग S ₁ (लंबवत रूप से), संबंधित सबस्ट्रिंग S ₂ (क्षैतिज) के संबंध में परिवर्तनों का न्यूनतम अनुमान देता है।



सुविधा के लिए, मैंने रंगों के साथ निशानों को चित्रित किया: हरे रंग का अर्थ है चयनित पदों में लाइनों का एक चरित्र-दर-वर्ण मिलान, नीला का अर्थ है प्रतिस्थापन की आवश्यकता, और लाल का अर्थ है हटाना या जोड़ना। यह नोटिस करना आसान है कि "लाल" सर्कल एक ही पंक्ति / कॉलम में हैं (कार्य चौकस है: यह बताएं कि यह इस प्रकार है)।

अधिक सुविधाजनक रूप में, परिणाम निम्नानुसार लिखा जा सकता है (लाल स्ट्रोक - मिलान वाले वर्ण, बदलाव काले क्षैतिज द्वारा इंगित किए जाते हैं):

एल्गोरिथम विश्लेषण

मेमोरी: प्रत्येक चरण के लिए, एक कॉलम d (i, *) से अधिक नहीं और विभाजन का एक सेट याद रखना आवश्यक होगा: ₁ । कुल O (| S ₁ | + | S ₂ |)। यही है, एक द्विघात मात्रा के बजाय, हमें एक रैखिक मिलता है।

समय: कॉलम t में S [0..N] का प्रत्येक विभाजन सब्सट्रिंग S [0..t] और S [t ..] का प्रसंस्करण उत्पन्न करता है। कुल विभाजन एन। प्रत्येक विभाजन को संसाधित करते समय (S ₁ [i..j], S ₁ [k..n]), (j - i) x (n - k) संचालन आवश्यक हैं। सबस्ट्रिंग के लिए सबसे खराब स्थिति का अनुमान लगाने पर, हमें 2 * | S ₁ | * - एस ₂ | संचालन। एल्गोरिथ्म का चलने का समय द्विघात बना रहा, हालाँकि गुणक स्थिरांक बदल गया है।

इसलिए, हमने एक रैखिक राशि का उपयोग करके समस्या को हल किया और गति में थोड़ा खो दिया, जिसे इस मामले में एक सफलता माना जा सकता है।

[*] विकिपीडिया: हिर्शबर्ग एल्गोरिथम ।