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

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

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$ वेक्टर तक कम किया जा सकता है क्योंकि गतिशील प्रोग्रामिंग दृष्टिकोण के लिए मैट्रिक्स के केवल वर्तमान और पिछले कॉलम की आवश्यकता होती है। हिर्शबर्ग का एल्गोरिदम समान द्विघात समय और रैखिक स्पेस सीमा में इष्टतम अनुक्रम के निर्माण की अनुमति देता है।

कैशे की कमी कम करें

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

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

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

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

Main article: च्वाटल-सैंकॉफ़ स्थिरांक

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

यह भी देखें

• सबसे लंबे समय तक बढ़ने वाला क्रम - संख्याओं की एक सरणी में सबसे लंबे समय तक बढ़ने वाले क्रम को खोजने के लिए एल्गोरिथ्म
• सबसे लंबा प्रत्यावर्ती क्रम
• लेवेंसहाइट दूरी - स्ट्रिंग समानता के लिए कंप्यूटर विज्ञान मीट्रिक

बाहरी संबंध

• 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