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

Not to be confused with सबसे लंबी सामान्य उपस्ट्रिंग.

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

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

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

जटिलता

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

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

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

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

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

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

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

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

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

उपसर्ग

S के उपसर्ग S_n को S के पहले n वर्णों के रूप में परिभाषित किया गया है। उदाहरण के लिए, 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	0
G	0	${\overset {\ \ \uparrow }{\leftarrow }}$0	${\overset {\nwarrow }{\ }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1
A	0	${\overset {\nwarrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ }{\leftarrow }}$2
C	0	${\overset {\ \uparrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2

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

ट्रैसबैक उदाहरण

	ε	A	G	C	A	T
ε	0	0	0	0	0	0
G	0	${\overset {\ \ \uparrow }{\leftarrow }}$0	${\overset {\nwarrow }{\ }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1
A	0	${\overset {\nwarrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ }{\leftarrow }}$2
C	0	${\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 की लंबाई से संबंधित है

$\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.

   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 तुलनाएँ करने की आवश्यकता होगी। अधिकांश वास्तविक दुनिया के मामलों में, विशेष रूप से स्रोत कोड अंतर और पैच में, फ़ाइलों की शुरुआत और अंत शायद ही कभी बदलते हैं, और लगभग निश्चित रूप से एक ही समय में दोनों नहीं। यदि अनुक्रम के बीच में केवल कुछ आइटम बदले गए हैं, तो शुरुआत और अंत को हटाया जा सकता है। इससे न केवल मैट्रिक्स के लिए मेमोरी आवश्यकताएं कम हो जाती हैं, बल्कि तुलनाओं की संख्या भी कम हो जाती है।

फ़ंक्शन LCS(X[1..m], Y[1..n])
    प्रारंभ := 1
    m_end := m
    n_end := n
    शुरुआत में मेल खाने वाली वस्तुओं को काट दें
    जबकि प्रारंभ ≤ m_end और प्रारंभ ≤ n_end और X[प्रारंभ] = Y[प्रारंभ]
        प्रारंभ := प्रारंभ + 1
    अंत में मेल खाने वाली वस्तुओं को काट दें
    जबकि प्रारंभ ≤ m_end और प्रारंभ ≤ n_end और X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    सी = सरणी(प्रारंभ-1..एम_एंड, प्रारंभ-1..एन_एंड)
    केवल उन आइटमों पर लूप करें जो बदल गए हैं
    मेरे लिए := प्रारंभ..m_end
        j के लिए := प्रारंभ..n_end
            एल्गोरिदम पहले की तरह जारी है...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Main article: Chvátal–Sankoff constants

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

यह भी देखें

• सबसे लंबे समय तक बढ़ने वाला क्रम
• सबसे लंबा वैकल्पिक क्रम
• लेवेनशेटिन दूरी

बाहरी संबंध

• Dictionary of Algorithms and Data Structures: longest common subsequence
• A collection of implementations of the longest common subsequence in many programming languages
• Find Longest Common Subsequence in Python