दीर्घवर्तिक सामान्य उपानुक्रम (लांगेस्ट कॉमन सब सीक्वेंस): Difference between revisions

Revision as of 23:43, 7 August 2023

एक उदाहरण फ़ाइल के दो संशोधनों की तुलना, उनके सबसे लंबे सामान्य अनुवर्ती (काले) के आधार पर

सबसे लंबा सामान्य अनुवर्ती (LCS) अनुक्रमों के एक सेट (अक्सर केवल दो अनुक्रम) में सभी अनुक्रमों के लिए सामान्य सबसे लंबा अनुवर्ती है। यह सबसे लंबे सामान्य सबस्ट्रिंग से भिन्न है: सबस्ट्रिंग के विपरीत, बाद के अनुक्रमों को मूल अनुक्रमों के भीतर लगातार पदों पर रहने की आवश्यकता नहीं होती है। सबसे लंबे समय तक सामान्य अनुक्रमों की गणना करने की समस्या एक क्लासिक कंप्यूटर विज्ञान समस्या है, जो अंतर उपयोगिता जैसे डेटा तुलना कार्यक्रमों का आधार है, diffऔर कम्प्यूटेशनल भाषाविज्ञान और जैव सूचना विज्ञान में इसका अनुप्रयोग है। फ़ाइलों के संशोधन-नियंत्रित संग्रह में किए गए कई परिवर्तनों को समेटने के लिए Git जैसी संशोधन नियंत्रण प्रणालियों द्वारा भी इसका व्यापक रूप से उपयोग किया जाता है।

उदाहरण के लिए, अनुक्रमों (ABCD) और (ACBAD) पर विचार करें। उनकी 5 लंबाई-2 सामान्य अनुवर्ती हैं: (AB), (AC), (AD), (BD), और (CD); 2 लंबाई-3 सामान्य अनुवर्ती: (ABD) और (ACD); और अब कोई सामान्य अनुवर्ती नहीं है। अतः (ABD) और (ACD) उनके सबसे लंबे सामान्य अनुवर्ती हैं।

जटिलता

इनपुट अनुक्रमों की यादृच्छिक संख्या के सामान्य मामले के लिए, समस्या एनपी-हार्ड है।^[1] जब अनुक्रमों की संख्या स्थिर होती है, तो समस्या को गतिशील प्रोग्रामिंग द्वारा बहुपद समय में हल किया जा सकता है।

दिया गया $N$ लंबाई का क्रम $n_{1},...,n_{N}$ , एक अनुभवहीन खोज प्रत्येक का परीक्षण करेगी $2^{n_{1}}$ पहले अनुक्रम के अनुवर्ती यह निर्धारित करने के लिए कि क्या वे शेष अनुक्रमों के भी अनुवर्ती हैं; प्रत्येक अनुवर्ती को शेष अनुक्रमों की लंबाई में रैखिक समय में परीक्षण किया जा सकता है, इसलिए इस एल्गोरिदम के लिए समय होगा

O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).

n और m तत्वों के दो अनुक्रमों के मामले में, गतिशील प्रोग्रामिंग दृष्टिकोण का चलने का समय O(n × m) है।^[2] इनपुट अनुक्रमों की एक मनमाने ढंग से संख्या के लिए, गतिशील प्रोग्रामिंग दृष्टिकोण एक समाधान देता है

O\left(N\prod _{i=1}^{N}n_{i}\right).

कम जटिलता वाली विधियाँ मौजूद हैं,^[3] जो अक्सर LCS की लंबाई, वर्णमाला के आकार या दोनों पर निर्भर करता है।

LCS आवश्यक रूप से अद्वितीय नहीं है; सबसे खराब स्थिति में, इनपुट की लंबाई में सामान्य अनुवर्ती की संख्या घातीय होती है, इसलिए एल्गोरिथम जटिलता कम से कम घातीय होनी चाहिए।^[4]

दो अनुक्रमों के लिए समाधान

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

उपसर्ग

S के उपसर्ग S_n को S के पहले n वर्णों के रूप में परिभाषित किया गया है।^[5] उदाहरण के लिए, S=(AGCA) के उपसर्ग हैं।

S₀ = ()

S₁ = (A)

S₂ = (AG)

S₃ = (AGC)

S₄ = (AGCA).

मान लें कि LCS(X, Y) एक ऐसा फ़ंक्शन है जो X और Y के लिए सामान्य सबसे लंबे अनुवर्ती की गणना करता है। ऐसे फ़ंक्शन में दो रोचक गुण होते हैं।

पहली गुण

LCS(X^A,Y^A) = LCS(X,Y)^A, सभी स्ट्रिंग X, Y और सभी प्रतीकों A के लिए, जहां ^ स्ट्रिंग संयोजन को दर्शाता है। यह किसी को एक ही प्रतीक में समाप्त होने वाले दो अनुक्रमों के लिए LCS गणना को सरल बनाने की अनुमति देता है। उदाहरण के लिए, LCS("BANANA","ATANA") = LCS("BANAN","ATAN")^"A", शेष सामान्य प्रतीकों के लिए जारी रखते हुए, LCS("BANANA","ATANA") = LCS(" BAN","AT")^"ANA"।

दूसरा गुण

यदि A और B अलग-अलग प्रतीक (A≠B) हैं, तो LCS(X^A,Y^B) सेट { LCS(X^A,Y), LCS(X,Y^B) } में अधिकतम लंबाई वाली स्ट्रिंग में से एक है, सभी स्ट्रिंग्स X, Y के लिए।

उदाहरण के लिए, LCS("ABCDEFG","BCDGK") LCS("ABCDEFG","BCDG") और LCS("ABCDEF","BCDGK") के बीच सबसे लंबी स्ट्रिंग है; यदि दोनों की लंबाई समान हो तो उनमें से किसी एक को मनमाने ढंग से चुना जा सकता है।

गुण का एहसास करने के लिए, दो मामलों में अंतर करें:

यदि LCS("ABCDEFG","BCDGK") "G" पर समाप्त होता है, तो अंतिम "K" LCS में नहीं हो सकता है, इसलिए LCS("ABCDEFG","BCDGK") = LCS("ABCDEFG"," BCDG ").

यदि LCS("ABCDEFG","BCDGK") "G" पर समाप्त नहीं होता है, तो अंतिम "G" LCS में नहीं हो सकता है, इसलिए LCS("ABCDEFG","BCDGK") = LCS("ABCDEF", "BCDGK")।

LCS फ़ंक्शन परिभाषित

मान लीजिए कि दो अनुक्रमों को इस प्रकार परिभाषित किया गया है: $X=(x_{1}x_{2}\cdots x_{m})$ और $Y=(y_{1}y_{2}\cdots y_{n})$ . के उपसर्ग $X$ हैं $X_{0},X_{1},X_{2},\dots ,X_{m}$ ; के उपसर्ग $Y$ हैं $Y_{0},Y_{1},Y_{2},\dots ,Y_{n}$ . मान लीजिये ${\mathit {LCS}}(X_{i},Y_{j})$ उपसर्गों के सबसे लंबे सामान्य अनुक्रम के सेट का प्रतिनिधित्व करें $X_{i}$ और $Y_{j}$ . अनुक्रमों का यह सेट निम्नलिखित द्वारा दिया गया है।

{\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\epsilon &{\mbox{if }}i=0{\mbox{ or }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}\neq y_{j}.\end{cases}}

का LCS खोजने के लिए $X_{i}$ और $Y_{j}$ , तुलना करना $x_{i}$ और $y_{j}$ . यदि वे बराबर हैं, तो क्रम ${\mathit {LCS}}(X_{i-1},Y_{j-1})$ उस एलिमेंट द्वारा विस्तारित है, $x_{i}$ . यदि वे समान नहीं हैं, तो दोनों अनुक्रमों में से सबसे लंबा, ${\mathit {LCS}}(X_{i},Y_{j-1})$ , और ${\mathit {LCS}}(X_{i-1},Y_{j})$ , रोका गया है। (यदि उनकी लंबाई समान है, लेकिन समान नहीं है, तो दोनों को बरकरार रखा जाता है।) आधार मामला, जब दोनों में से कोई एक हो $X_{i}$ या $Y_{i}$ रिक्त है, $\epsilon$ रिक्त स्ट्रिंग है, .

कार्य उदाहरण

R = (GAC), और C = (AGCAT) का सबसे लंबा अनुवर्ती सामान्य पाया जाएगा। क्योंकि LCS फ़ंक्शन "शून्य" एलिमेंट का उपयोग करता है, इसलिए इन अनुक्रमों के लिए रिक्त शून्य उपसर्गों को परिभाषित करना सुविधाजनक है: R₀ = ε; और C₀ = ε. सभी उपसर्गों को एक तालिका में पहली पंक्ति में C (इसे एक कॉलम हेडर बनाते हुए) और पहले कॉलम में R (इसे एक row हेडर बनाते हुए) के साथ रखा गया है।

LCS स्ट्रिंग्स
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε
A	ε
C	ε

इस तालिका का उपयोग गणना के प्रत्येक चरण के लिए एलसीएस अनुक्रम को संग्रहीत करने के लिए किया जाता है। दूसरे कॉलम और दूसरी पंक्ति को ε से भर दिया गया है, क्योंकि जब एक रिक्त अनुक्रम की तुलना एक गैर-रिक्त अनुक्रम से की जाती है, तो सबसे लंबा सामान्य अनुवर्ती हमेशा एक रिक्त अनुक्रम होता है।

LCS(R₁, C₁) प्रत्येक अनुक्रम में पहले तत्वों की तुलना करके निर्धारित किया जाता है। G और A समान नहीं हैं, इसलिए यह LCS ("दूसरी संपत्ति का उपयोग करके" दो अनुक्रमों, LCS(R₁, C₀) और LCS(R₀, C₁) में से सबसे लंबा प्राप्त करता है। तालिका के अनुसार, ये दोनों रिक्त हैं, इसलिए LCS(R₁, C₁) भी रिक्त है, जैसा कि नीचे दी गई तालिका में दिखाया गया है। तीर इंगित करते हैं कि अनुक्रम ऊपर की दोनों कोशिकाओं, LCS(R₀, C₁) और बाईं ओर की कोशिका, LCS(R₁, C₀) से आता है।

LCS(R₁, C₂) का निर्धारण G और G की तुलना करके किया जाता है। वे मेल खाते हैं, इसलिए G को ऊपरी बाएँ क्रम में जोड़ा जाता है, LCS(R₀, C₁), जो (ε) है, दे रहा है (εG), जो कि (G) है .

LCS(R₁, C₃) के लिए, G और C मेल नहीं खाते। उपरोक्त क्रम रिक्त है; बाईं ओर वाले में एक एलिमेंट G है। इनमें से सबसे लंबे को चुनने पर LCS(R₁, C₃) (G) है। तीर बाईं ओर इंगित करता है, क्योंकि वह दो अनुक्रमों में सबसे लंबा है।

LCS(R₁, C₄), इसी प्रकार, (G) है।

LCS(R₁, C₅),, इसी तरह, (G) है।

"G" पंक्ति पूर्ण हुई
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε	${\overset {\ \ \uparrow }{\leftarrow }}$ ε	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	ε
C	ε

LCS(R₂, C₁) के लिए, A की तुलना A से की जाती है। दोनों तत्व मेल खाते हैं, इसलिए A को ε में जोड़ा जाता है, जिससे (A) मिलता है।

LCS(R₂, C₂) के लिए, A और G मेल नहीं खाते हैं, इसलिए LCS(R₁, C₂) में से सबसे लंबा, जो कि (G) है, और LCS(R₂, C₁), जो कि (A) है, का उपयोग किया जाता है। इस मामले में, उनमें से प्रत्येक में एक तत्व होता है, इसलिए इस एलसीएस को दो अनुवर्ती दिए गए हैं: (A) और (G)।

LCS(R₂, C₃) के लिए, A, C से मेल नहीं खाता है। LCS(R₂, C₂) में अनुक्रम (A) और (G) शामिल हैं; LCS(R₁, C₃) (G) है, जो पहले से ही LCS(R₂, C₂) में समाहित है। परिणाम यह है कि LCS(R₂, C₃) में दो अनुवर्ती, (A) और (G) भी शामिल हैं।

LCS(R₂, C₄) के लिए, A, A से मेल खाता है, जो कि (GA) देते हुए ऊपरी बाएँ सेल से जुड़ा हुआ है।

LCS(R₂, C₅) के लिए, A, T से मेल नहीं खाता है। दो अनुक्रमों, (GA) और (G) की तुलना करने पर, सबसे लंबा (GA) है, इसलिए LCS(R₂, C₅) (GA) है।

"G" & "A" पंक्ति पूर्ण हुई
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε	${\overset {\ \ \uparrow }{\leftarrow }}$ ε	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	ε	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	ε

LCS(R₃, C₁) के लिए, C और A मेल नहीं खाते हैं, इसलिए LCS(R₃, C₁) को दो अनुक्रमों में से सबसे लंबा अनुक्रम मिलता है, (A)।

LCS(R₃, C₂) के लिए, C और G मेल नहीं खाते। LCS(R₃, C₁) और LCS(R₂, C₂) दोनों में एक तत्व है। परिणाम यह है कि LCS(R₃, C₂) में दो अनुवर्ती, (A) और (G) शामिल हैं।

LCS(R₃, C₃) के लिए, C और C मेल खाते हैं, इसलिए C को LCS(R₂, C₂) में जोड़ा जाता है, जिसमें दो अनुवर्ती (A) और (G) होते हैं, जो (AC) और (GC) देते हैं।

LCS(R₃, C₄) के लिए, C और A मेल नहीं खाते। LCS(R₃, C₃)), जिसमें (AC) और (GC), और LCS(R₂, C₄), जिसमें (GA) शामिल है, को मिलाने पर कुल तीन अनुक्रम मिलते हैं: (AC), (GC), और (GA) ).

अंततः, LCS(R₃, C₅) के लिए, C और T मेल नहीं खाते। परिणाम यह है कि LCS(R₃, C₅) में तीन अनुक्रम, (AC), (GC), और (GA) भी शामिल हैं।

पूर्ण LCS तालिका
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε	${\overset {\ \ \uparrow }{\leftarrow }}$ ε	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	ε	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	ε	${\overset {\ \uparrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (AC) & (GC)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) & (GC) & (GA)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) & (GC) & (GA)

अंतिम परिणाम यह है कि अंतिम सेल में (AGCAT) और (GAC) के सभी सबसे लंबे अनुवर्ती सामान्य शामिल हैं; ये (AC), (GC), और (GA) हैं। तालिका उपसर्गों की प्रत्येक संभावित जोड़ी के लिए सबसे लंबे सामान्य अनुवर्ती को भी दर्शाती है। उदाहरण के लिए, (AGC) और (GA) के लिए, सबसे लंबे सामान्य अनुवर्ती (A) और (G) हैं।

ट्रेसबैक दृष्टिकोण

LCS तालिका की एक पंक्ति की LCS की गणना के लिए केवल वर्तमान पंक्ति और पिछली पंक्ति के समाधान की आवश्यकता होती है। फिर भी, लंबे अनुक्रमों के लिए, ये अनुक्रम असंख्य और लंबे हो सकते हैं, जिसके लिए बहुत अधिक भंडारण स्थान की आवश्यकता होती है। वास्तविक अनुवर्ती को नहीं, बल्कि अनुवर्ती की लंबाई और तीरों की दिशा को सेव कर स्टोरेज स्पेस को बचाया जा सकता है, जैसा कि नीचे दी गई तालिका में है।

अनुक्रमों के स्थान पर लंबाई संग्रहित करना
	A	G	C	A	T
ε	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
A	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

वास्तविक अनुवर्ती एक "ट्रेसबैक" प्रक्रिया में निकाले जाते हैं जो तालिका में अंतिम सेल से शुरू होकर पीछे की ओर तीरों का अनुसरण करता है। जब लंबाई कम हो जाती है, तो अनुक्रमों में एक सामान्य तत्व होना चाहिए। जब किसी कक्ष में दो तीर दिखाए जाते हैं तो कई पथ संभव होते हैं। इस तरह के विश्लेषण के लिए नीचे तालिका दी गई है, जिसमें उन कोशिकाओं में रंगीन संख्याएँ हैं जहाँ लंबाई घटने वाली है। बोल्ड नंबर अनुक्रम (GA) का पता लगाते हैं।^[6]

ट्रैसबैक उदाहरण
	A	G	C	A	T
ε	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
A	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

अन्य समस्याओं से संबंध

दो स्ट्रिंग्स के लिए $X_{1\dots m}$ और $Y_{1\dots n}$ , सबसे छोटी सामान्य सुपरसीक्वेंस समस्या की लंबाई LCS की लंबाई से संबंधित है^[3]

\left|SCS(X,Y)\right|=n+m-\left|LCS(X,Y)\right|.

जब केवल सम्मिलन और विलोपन की अनुमति है (कोई प्रतिस्थापन नहीं), या जब प्रतिस्थापन की लागत सम्मिलन या विलोपन की लागत से दोगुनी है, तो संपादन दूरी है:

d'(X,Y)=n+m-2\cdot \left|LCS(X,Y)\right|.

डायनामिक प्रोग्रामिंग समाधान के लिए कोड

LCS की लंबाई की गणना

नीचे दिया गया फ़ंक्शन इनपुट अनुक्रम के रूप में लेता है X[1..m] और Y[1..n], के बीच LCS की गणना करता है X[1..i] और Y[1..j] सभी के लिए 1 ≤ i ≤ m और 1 ≤ j ≤ n, और इसे संग्रहीत करता है C[i,j]. C[m,n] की LCS की लंबाई शामिल होगी X और Y.^[7]

   function LCSLength(X[1..m], Y[1..n])

    C = array(0..m, 0..n)
    for i := 0..m
        C[i,0] = 0
    for j := 0..n
        C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

वैकल्पिक रूप से, मेमोइज़ेशन का उपयोग किया जा सकता है।

LCS पढ़ना

निम्नलिखित फ़ंक्शन गणना करते समय लिए गए विकल्पों को बैक ट्रैकिंग करता है C मेज़। यदि उपसर्गों में अंतिम वर्ण समान हैं, तो उन्हें LCS में होना चाहिए। यदि नहीं, तो जांचें कि किस चीज़ ने रखने का सबसे बड़ा LCS दिया $x_{i}$ और $y_{j}$ , और वही चुनाव करें। यदि वे समान रूप से लंबे हों तो बस एक चुनें। फ़ंक्शन को कॉल करें i=m और j=n.

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    if C[i,j-1] > C[i-1,j]
        return backtrack(C, X, Y, i, j-1)
    return backtrack(C, X, Y, i-1, j)

सभी LCS को पढ़ना

अगर चुन रहे हैं $x_{i}$ और $y_{j}$ समान रूप से लंबा परिणाम देगा, दोनों परिणामी अनुवर्ती पढ़ें। इसे इस फ़ंक्शन द्वारा एक सेट के रूप में लौटाया जाता है। ध्यान दें कि यह फ़ंक्शन बहुपद नहीं है, क्योंकि यदि तार समान हैं तो यह लगभग हर चरण में शाखाबद्ध हो सकता है।

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    R := {}
    if C[i,j-1] ≥ C[i-1,j]
        R := backtrackAll(C, X, Y, i, j-1)
    if C[i-1,j] ≥ C[i,j-1]
        R := R ∪ backtrackAll(C, X, Y, i-1, j)
    return R

diff प्रिंट करें

यह फ़ंक्शन C मैट्रिक्स के माध्यम से बैकट्रैक करेगा, और दो अनुक्रमों के बीच अंतर प्रिंट करेगा। ध्यान दें कि यदि आप ≥ और< को नीचे > और ≤से बदलते हैं तो आपको एक अलग उत्तर मिलेगा।

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i >= 0 and j >= 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

उदाहरण

मान लीजिये $X$ "XMJYAUZ" और $Y$ "MZJAWXU”के बीच सबसे लंबा सामान्य अनुवर्ती $X$ और $Y$ है "MJAU”। टेबल C नीचे दिखाया गया है, जो फ़ंक्शन द्वारा उत्पन्न होता है LCSLength, के उपसर्गों के बीच सबसे लंबे सामान्य अनुवर्ती की लंबाई दिखाता है $X$ और $Y$ . $i$ वें पंक्ति और $j$ वां कॉलम बीच में LCS $X_{1..i}$ और $Y_{1..j}$ .लंबाई दिखाता है

		0	1	2	3	4	5	6	7
		ε	M	Z	J	A	W	X	U
0	ε	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

हाइलाइट नंबर फ़ंक्शन का पथ दिखाते हैं backtrack LCS पढ़ते समय, नीचे दाएं से ऊपरी बाएं कोने तक चलेगा। यदि वर्तमान प्रतीकों में $X$ और $Y$ बराबर हैं, वे LCS का हिस्सा हैं, और हम ऊपर और बाएं दोनों तरफ जाते हैं (बोल्ड में दिखाया गया है)। यदि नहीं, तो हम ऊपर या बाएँ जाते हैं, यह इस बात पर निर्भर करता है कि किस सेल की संख्या अधिक है। यह या तो LCS $X_{1..i-1}$ और $Y_{1..j}$ , या $X_{1..i}$ और $Y_{1..j-1}$ .के बीच में लेने से मेल खाता है।

कोड अनुकूलन

वास्तविक दुनिया के मामलों के लिए इसे गति देने के लिए उपरोक्त एल्गोरिदम में कई अनुकूलन किए जा सकते हैं।

समस्या सेट कम करें

अनुभवहीन एल्गोरिथ्म में सी मैट्रिक्स अनुक्रमों की लंबाई के साथ चतुर्भुज रूप से बढ़ता है। दो 100-आइटम अनुक्रमों के लिए, 10,000-आइटम मैट्रिक्स की आवश्यकता होगी, और 10,000 तुलनाएं करने की आवश्यकता होगी। वास्तविक दुनिया के अधिकांश मामलों में, विशेष रूप से स्रोत कोड अंतर और पैच में, फ़ाइलों की शुरुआत और अंत शायद ही कभी बदलते हैं, और लगभग निश्चित रूप से एक ही समय में दोनों नहीं। यदि अनुक्रम के मध्य में केवल कुछ आइटम बदले गए हैं, तो शुरुआत और अंत को हटाया जा सकता है। यह न केवल मैट्रिक्स के लिए मेमोरी आवश्यकताओं को कम करता है, बल्कि की जाने वाली तुलनाओं की संख्या को भी कम करता है।

function LCS(X[1..m], Y[1..n])
    start := 1
    m_end := m
    n_end := n
    trim off the matching items at the beginning
    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
        start := start + 1
    trim off the matching items at the end
    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    C = array(start-1..m_end, start-1..n_end)
    only loop over the items that have changed
    for i := start..m_end
        for j := start..n_end
            the algorithm continues as before ...

सर्वोत्तम स्थिति में, बिना किसी बदलाव वाले अनुक्रम में, यह अनुकूलन सी मैट्रिक्स की आवश्यकता को समाप्त कर देगा। सबसे खराब स्थिति में, अनुक्रम में सबसे पहले और आखिरी आइटम में बदलाव के बाद केवल दो अतिरिक्त तुलनाएं की जाती हैं।

तुलना समय कम करें

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

स्ट्रिंग्स को हैश में कम करें

अनुक्रमों में स्ट्रिंग के आकार को कम करने के लिए हैश फंकशन या अंततः, का उपयोग किया जा सकता है। अर्थात्, स्रोत कोड के लिए जहां औसत पंक्ति 60 या अधिक वर्ण लंबी है, उस पंक्ति के लिए हैश या चेकसम केवल 8 से 40 वर्ण लंबा हो सकता है। इसके अतिरिक्त, हैश और चेकसम की यादृच्छिक प्रकृति यह गारंटी देगी कि तुलना तेजी से शॉर्ट-सर्किट होगी, क्योंकि शुरुआत में स्रोत कोड की लाइनें शायद ही कभी बदली जाएंगी।

इस अनुकूलन में तीन प्राथमिक कमियाँ हैं। सबसे पहले, दो अनुक्रमों के लिए हैश की पूर्व-गणना करने के लिए पहले से ही काफी समय खर्च करने की आवश्यकता होती है। दूसरा, नए हैशेड अनुक्रमों के लिए अतिरिक्त मेमोरी आवंटित करने की आवश्यकता है। हालाँकि, यहाँ उपयोग किए गए सरल एल्गोरिदम की तुलना में, ये दोनों कमियाँ अपेक्षाकृत न्यूनतम हैं।

तीसरा दोष हैश टकराव का है। चूंकि चेकसम या हैश के अद्वितीय होने की गारंटी नहीं है, इसलिए इस बात की बहुत कम संभावना है कि दो अलग-अलग आइटमों को एक ही हैश में घटाया जा सकता है। स्रोत कोड में इसकी संभावना नहीं है, लेकिन यह संभव है। इसलिए एक क्रिप्टोग्राफ़िक हैश इस अनुकूलन के लिए कहीं अधिक उपयुक्त होगा, क्योंकि इसकी एन्ट्रॉपी एक साधारण चेकसम की तुलना में काफी अधिक होगी। हालाँकि, लाभ छोटी अनुक्रम लंबाई के लिए क्रिप्टोग्राफ़िक हैश की सेटअप और कम्प्यूटेशनल आवश्यकताओं के लायक नहीं हो सकते हैं।

आवश्यक स्थान कम करें

यदि केवल LCS की लंबाई की आवश्यकता है, तो मैट्रिक्स को कम किया जा सकता है $2\times \min(n,m)$ मैट्रिक्स, या करने के लिए एक $\min(m,n)+1$ गतिशील प्रोग्रामिंग दृष्टिकोण के रूप में वेक्टर को मैट्रिक्स के केवल वर्तमान और पिछले कॉलम की आवश्यकता होती है। हिर्शबर्ग का एल्गोरिदम समान द्विघात समय और रैखिक स्थान सीमा में ही इष्टतम अनुक्रम के निर्माण की अनुमति देता है।^[8]

कैश छूट को कम करें

चौधरी और रामचंद्रन ने एक द्विघात-समय रैखिक-अंतरिक्ष एल्गोरिदम तैयार किया^[9]^[10] एक इष्टतम अनुक्रम के साथ LCS लंबाई खोजने के लिए जो अपने बेहतर कैश प्रदर्शन के कारण व्यवहार में हिर्शबर्ग के एल्गोरिदम से तेज़ चलता है।^[9] कैश-ओब्लिवियस#आदर्शीकृत कैश मॉडल के तहत एल्गोरिदम में एक असम्बद्ध रूप से इष्टतम कैश जटिलता है।^[11] दिलचस्प बात यह है कि एल्गोरिथ्म स्वयं कैश-अनभिज्ञ है^[11]इसका मतलब यह है कि यह मशीन के कैश पैरामीटर (उदाहरण के लिए, कैश आकार और कैश लाइन आकार) के आधार पर कोई विकल्प नहीं बनाता है।

आगे अनुकूलित एल्गोरिदम

कई एल्गोरिदम मौजूद हैं जो प्रस्तुत गतिशील प्रोग्रामिंग दृष्टिकोण से तेज़ चलते हैं। उनमें से एक हंट-स्ज़िमंस्की एल्गोरिदम है, जो आम तौर पर चलता है $O((n+r)\log(n))$ के लिए समय $n>m$ ), कहाँ $r$ दो अनुक्रमों के बीच मिलान की संख्या है।^[12] सीमित वर्णमाला आकार की समस्याओं के लिए, चार रूसी की विधि का उपयोग लॉगरिदमिक कारक द्वारा गतिशील प्रोग्रामिंग एल्गोरिदम के चलने के समय को कम करने के लिए किया जा सकता है।^[13]

यादृच्छिक स्ट्रिंग्स पर व्यवहार

इसके साथ शुरुआत Chvátal & Sankoff (1975),^[14] कई शोधकर्ताओं ने सबसे लंबी सामान्य अनुवर्ती लंबाई के व्यवहार की जांच की है जब दो दिए गए तार एक ही वर्णमाला से यादृच्छिक रूप से खींचे जाते हैं। जब वर्णमाला का आकार स्थिर होता है, तो LCS की अपेक्षित लंबाई दो स्ट्रिंग्स की लंबाई के समानुपाती होती है, और आनुपातिकता के स्थिरांक (वर्णमाला के आकार के आधार पर) च्वाटल-सैंकॉफ स्थिरांक के रूप में जाने जाते हैं। उनके सटीक मूल्य ज्ञात नहीं हैं, लेकिन उनके मूल्यों की ऊपरी और निचली सीमाएं सिद्ध हो चुकी हैं,^[15] और यह ज्ञात है कि वे वर्णमाला के आकार के वर्गमूल के विपरीत आनुपातिक रूप से बढ़ते हैं।^[16] सबसे लंबी सामान्य अनुवर्ती समस्या के सरलीकृत गणितीय मॉडल को ट्रेसी-विडोम वितरण द्वारा नियंत्रित दिखाया गया है।^[17]

यह भी देखें

संदर्भ

↑ David Maier (1978). "परवर्ती और अतिपरवर्ती पर कुछ समस्याओं की जटिलता". J. ACM. ACM Press. 25 (2): 322–336. doi:10.1145/322063.322075. S2CID 16120634.
↑ Wagner, Robert; Fischer, Michael (January 1974). "स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या". Journal of the ACM. 21 (1): 168–173. CiteSeerX 10.1.1.367.5281. doi:10.1145/321796.321811. S2CID 13381535.
↑ ^3.0 ^3.1 L. Bergroth and H. Hakonen and T. Raita (2000). "A survey of longest common subsequence algorithms". Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000. pp. 39–48. doi:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8. S2CID 10375334. {{cite book}}: |journal= ignored (help)
↑ Ronald I. Greenberg (2003-08-06). "सबसे लंबे सामान्य अनुवर्ती की संख्या पर सीमा". arXiv:cs.DM/0301030.
↑ Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. p. 24. ISBN 978-0-387-71336-6.
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "15.4". एल्गोरिदम का परिचय (2nd ed.). MIT Press and McGraw-Hill. pp. 350–355. ISBN 0-262-53196-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "Dynamic Programming". Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 394. ISBN 0-262-03384-4.
↑ Hirschberg, D. S. (1975). "अधिकतम सामान्य अनुवर्ती की गणना के लिए एक रैखिक अंतरिक्ष एल्गोरिदम". Communications of the ACM. 18 (6): 341–343. doi:10.1145/360825.360861. S2CID 207694727.
↑ ^9.0 ^9.1 Chowdhury, Rezaul; Ramachandran, Vijaya (January 2006). "कैश-विस्मृत गतिशील प्रोग्रामिंग". Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA): 591–600. doi:10.1145/1109557.1109622. ISBN 0898716055. S2CID 9650418.
↑ Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (July 2010). "जैव सूचना विज्ञान के लिए कैश-विस्मृत गतिशील प्रोग्रामिंग". IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB). 7 (3): 495–510. doi:10.1109/TCBB.2008.94. PMID 20671320. S2CID 2532039.
↑ ^11.0 ^11.1 Frigo, Matteo; Leiserson, Charles E.; Prokop, Harald; Ramachandran, Sridhar (January 2012). "कैश-विस्मृत एल्गोरिदम". ACM Transactions on Algorithms. 8 (1): 1–22. doi:10.1145/2071379.2071383.
↑ Apostolico, Alberto; Galil, Zvi (1997-05-29). पैटर्न मिलान एल्गोरिदम. ISBN 9780195354348.
↑ Masek, William J.; Paterson, Michael S. (1980), "A faster algorithm computing string edit distances", Journal of Computer and System Sciences, 20 (1): 18–31, doi:10.1016/0022-0000(80)90002-1, MR 0566639.
↑ Chvatal, Václáv; Sankoff, David (1975), "Longest common subsequences of two random sequences", Journal of Applied Probability, 12 (2): 306–315, doi:10.2307/3212444, JSTOR 3212444, MR 0405531, S2CID 250345191.
↑ Lueker, George S. (2009), "Improved bounds on the average length of longest common subsequences", Journal of the ACM, 56 (3), A17, doi:10.1145/1516512.1516519, MR 2536132, S2CID 7232681.
↑ Kiwi, Marcos; Loebl, Martin; Matoušek, Jiří (2005), "Expected length of the longest common subsequence for large alphabets", Advances in Mathematics, 197 (2): 480–498, arXiv:math/0308234, doi:10.1016/j.aim.2004.10.012, MR 2173842.
↑ Majumdar, Satya N.; Nechaev, Sergei (2005), "Exact asymptotic results for the Bernoulli matching model of sequence alignment", Physical Review E, 72 (2): 020901, 4, arXiv:q-bio/0410012, Bibcode:2005PhRvE..72b0901M, doi:10.1103/PhysRevE.72.020901, MR 2177365, PMID 16196539, S2CID 11390762.

बाहरी संबंध

[1] David Maier (1978). "परवर्ती और अतिपरवर्ती पर कुछ समस्याओं की जटिलता". J. ACM. ACM Press. 25 (2): 322–336. doi:10.1145/322063.322075. S2CID 16120634.

[2] Wagner, Robert; Fischer, Michael (January 1974). "स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या". Journal of the ACM. 21 (1): 168–173. CiteSeerX 10.1.1.367.5281. doi:10.1145/321796.321811. S2CID 13381535.

[BHR00-3] 3.0 ^3.1 L. Bergroth and H. Hakonen and T. Raita (2000). "A survey of longest common subsequence algorithms". Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000. pp. 39–48. doi:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8. S2CID 10375334. {{cite book}}: |journal= ignored (help)

[4] Ronald I. Greenberg (2003-08-06). "सबसे लंबे सामान्य अनुवर्ती की संख्या पर सीमा". arXiv:cs.DM/0301030.

[5] Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. p. 24. ISBN 978-0-387-71336-6.

[6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "15.4". एल्गोरिदम का परिचय (2nd ed.). MIT Press and McGraw-Hill. pp. 350–355. ISBN 0-262-53196-8.{{cite book}}: CS1 maint: multiple names: authors list (link)

[:1-7] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "Dynamic Programming". Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 394. ISBN 0-262-03384-4.

[8] Hirschberg, D. S. (1975). "अधिकतम सामान्य अनुवर्ती की गणना के लिए एक रैखिक अंतरिक्ष एल्गोरिदम". Communications of the ACM. 18 (6): 341–343. doi:10.1145/360825.360861. S2CID 207694727.

[CR-06-9] 9.0 ^9.1 Chowdhury, Rezaul; Ramachandran, Vijaya (January 2006). "कैश-विस्मृत गतिशील प्रोग्रामिंग". Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA): 591–600. doi:10.1145/1109557.1109622. ISBN 0898716055. S2CID 9650418.

[CLR-08-10] Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (July 2010). "जैव सूचना विज्ञान के लिए कैश-विस्मृत गतिशील प्रोग्रामिंग". IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB). 7 (3): 495–510. doi:10.1109/TCBB.2008.94. PMID 20671320. S2CID 2532039.

[FLPR-12-11] 11.0 ^11.1 Frigo, Matteo; Leiserson, Charles E.; Prokop, Harald; Ramachandran, Sridhar (January 2012). "कैश-विस्मृत एल्गोरिदम". ACM Transactions on Algorithms. 8 (1): 1–22. doi:10.1145/2071379.2071383.

[12] Apostolico, Alberto; Galil, Zvi (1997-05-29). पैटर्न मिलान एल्गोरिदम. ISBN 9780195354348.

[13] Masek, William J.; Paterson, Michael S. (1980), "A faster algorithm computing string edit distances", Journal of Computer and System Sciences, 20 (1): 18–31, doi:10.1016/0022-0000(80)90002-1, MR 0566639.

[14] Chvatal, Václáv; Sankoff, David (1975), "Longest common subsequences of two random sequences", Journal of Applied Probability, 12 (2): 306–315, doi:10.2307/3212444, JSTOR 3212444, MR 0405531, S2CID 250345191.

[15] Lueker, George S. (2009), "Improved bounds on the average length of longest common subsequences", Journal of the ACM, 56 (3), A17, doi:10.1145/1516512.1516519, MR 2536132, S2CID 7232681.

[16] Kiwi, Marcos; Loebl, Martin; Matoušek, Jiří (2005), "Expected length of the longest common subsequence for large alphabets", Advances in Mathematics, 197 (2): 480–498, arXiv:math/0308234, doi:10.1016/j.aim.2004.10.012, MR 2173842.

[17] Majumdar, Satya N.; Nechaev, Sergei (2005), "Exact asymptotic results for the Bernoulli matching model of sequence alignment", Physical Review E, 72 (2): 020901, 4, arXiv:q-bio/0410012, Bibcode:2005PhRvE..72b0901M, doi:10.1103/PhysRevE.72.020901, MR 2177365, PMID 16196539, S2CID 11390762.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

@@ Line 407: / Line 407: @@
 == कोड अनुकूलन ==
-वास्तविक दुनिया के मामलों के लिए इसे तेज़ करने के लिए उपरोक्त एल्गोरिदम में कई अनुकूलन किए जा सकते हैं।
+वास्तविक दुनिया के मामलों के लिए इसे गति देने के लिए उपरोक्त एल्गोरिदम में कई अनुकूलन किए जा सकते हैं।
 === समस्या सेट कम करें ===
-अनुभवहीन एल्गोरिथ्म में सी मैट्रिक्स अनुक्रमों की लंबाई के साथ [[द्विघात वृद्धि]]। दो 100-आइटम अनुक्रमों के लिए, 10,000-आइटम मैट्रिक्स की आवश्यकता होगी, और 10,000 तुलनाएँ करने की आवश्यकता होगी। अधिकांश वास्तविक दुनिया के मामलों में, विशेष रूप से स्रोत कोड अंतर और पैच में, फ़ाइलों की शुरुआत और अंत शायद ही कभी बदलते हैं, और लगभग निश्चित रूप से एक ही समय में दोनों नहीं। यदि अनुक्रम के बीच में केवल कुछ आइटम बदले गए हैं, तो शुरुआत और अंत को हटाया जा सकता है। इससे न केवल मैट्रिक्स के लिए मेमोरी आवश्यकताएं कम हो जाती हैं, बल्कि तुलनाओं की संख्या भी कम हो जाती है।
+अनुभवहीन एल्गोरिथ्म में सी मैट्रिक्स अनुक्रमों की लंबाई के साथ चतुर्भुज रूप से बढ़ता है। दो 100-आइटम अनुक्रमों के लिए, 10,000-आइटम मैट्रिक्स की आवश्यकता होगी, और 10,000 तुलनाएं करने की आवश्यकता होगी। वास्तविक दुनिया के अधिकांश मामलों में, विशेष रूप से स्रोत कोड अंतर और पैच में, फ़ाइलों की शुरुआत और अंत शायद ही कभी बदलते हैं, और लगभग निश्चित रूप से एक ही समय में दोनों नहीं। यदि अनुक्रम के मध्य में केवल कुछ आइटम बदले गए हैं, तो शुरुआत और अंत को हटाया जा सकता है। यह न केवल मैट्रिक्स के लिए मेमोरी आवश्यकताओं को कम करता है, बल्कि की जाने वाली तुलनाओं की संख्या को भी कम करता है।
-  फ़ंक्शन LCS(X[1..m], Y[1..n])
+  function LCS(X[1..m], Y[1..n])
-      प्रारंभ := 1
+      start := 1
       m_end := m
       n_end := n
-      ''शुरुआत में मेल खाने वाली वस्तुओं को काट दें''
+      ''trim off the matching items at the beginning''
-      जबकि प्रारंभ ≤ m_end और प्रारंभ ≤ n_end और X[प्रारंभ] = Y[प्रारंभ]
+      '''while''' start ≤ m_end '''and''' start ≤ n_end '''and''' X[start] = Y[start]
-          प्रारंभ := प्रारंभ + 1
+          start := start + 1
-      ''अंत में मेल खाने वाली वस्तुओं को काट दें''
+      ''trim off the matching items at the end''
-      जबकि प्रारंभ ≤ m_end और प्रारंभ ≤ n_end और X[m_end] = Y[n_end]
+      '''while''' start ≤ m_end '''and''' start ≤ n_end '''and''' X[m_end] = Y[n_end]
           m_end := m_end - 1
           n_end := n_end - 1
-      सी = सरणी(प्रारंभ-1..एम_एंड, प्रारंभ-1..एन_एंड)
+      C = array(start-1..m_end, start-1..n_end)
-      ''केवल उन आइटमों पर लूप करें जो बदल गए हैं''
+      ''only loop over the items that have changed''
-      मेरे लिए := प्रारंभ..m_end
+      '''for''' i := start..m_end
-          j के लिए := प्रारंभ..n_end
+          '''for''' j := start..n_end
-              ''एल्गोरिदम पहले की तरह जारी है...''
+              the algorithm continues as before ...
 सर्वोत्तम स्थिति में, बिना किसी बदलाव वाले अनुक्रम में, यह अनुकूलन सी मैट्रिक्स की आवश्यकता को समाप्त कर देगा। सबसे खराब स्थिति में, अनुक्रम में सबसे पहले और आखिरी आइटम में बदलाव के बाद केवल दो अतिरिक्त तुलनाएं की जाती हैं।

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt Pattern Matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting

Anonymous

Search

दीर्घवर्तिक सामान्य उपानुक्रम (लांगेस्ट कॉमन सब सीक्वेंस): Difference between revisions

Namespaces

More

Page actions

Revision as of 23:43, 7 August 2023

Contents

जटिलता

दो अनुक्रमों के लिए समाधान

उपसर्ग

पहली गुण

दूसरा गुण

LCS फ़ंक्शन परिभाषित

कार्य उदाहरण

ट्रेसबैक दृष्टिकोण

अन्य समस्याओं से संबंध

डायनामिक प्रोग्रामिंग समाधान के लिए कोड

LCS की लंबाई की गणना

LCS पढ़ना

सभी LCS को पढ़ना

diff प्रिंट करें

उदाहरण

कोड अनुकूलन

समस्या सेट कम करें

तुलना समय कम करें

स्ट्रिंग्स को हैश में कम करें

आवश्यक स्थान कम करें

कैश छूट को कम करें

आगे अनुकूलित एल्गोरिदम

यादृच्छिक स्ट्रिंग्स पर व्यवहार

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

		0	1	2	3	4	5	6	7
		ε	M	Z	J	A	W	X	U
0	ε	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

		0	1	2	3	4	5	6	7
		ε	M	Z	J	A	W	X	U
0	ε	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

Anonymous

Search

दीर्घवर्तिक सामान्य उपानुक्रम (लांगेस्ट कॉमन सब सीक्वेंस): Difference between revisions

Revision as of 23:43, 7 August 2023

जटिलता

दो अनुक्रमों के लिए समाधान

उपसर्ग

पहली गुण

दूसरा गुण

LCS फ़ंक्शन परिभाषित

कार्य उदाहरण

ट्रेसबैक दृष्टिकोण

अन्य समस्याओं से संबंध

डायनामिक प्रोग्रामिंग समाधान के लिए कोड

LCS की लंबाई की गणना

LCS पढ़ना

सभी LCS को पढ़ना

diff प्रिंट करें

उदाहरण

कोड अनुकूलन

समस्या सेट कम करें

तुलना समय कम करें

स्ट्रिंग्स को हैश में कम करें

आवश्यक स्थान कम करें

कैश छूट को कम करें

आगे अनुकूलित एल्गोरिदम

यादृच्छिक स्ट्रिंग्स पर व्यवहार

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories

		0	1	2	3	4	5	6	7
		ε	M	Z	J	A	W	X	U
0	ε	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4