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

Not to be confused with longest common substring.

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

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

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

जटिलता

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

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

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

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

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

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

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

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

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

उपसर्ग

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

एस₀ = ()

एस₁ = (ए)

एस₂ = (एजी)

एस₃ = (एजीसी)

एस₄ = (एजीसीए).

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

पहली संपत्ति

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

दूसरा गुण

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

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

संपत्ति का एहसास करने के लिए, दो मामलों में अंतर करें:

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

एलसीएस फ़ंक्शन परिभाषित

मान लीजिए कि दो अनुक्रमों को इस प्रकार परिभाषित किया गया है: $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}}$

का एलसीएस खोजने के लिए $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 फ़ंक्शन एक शून्य तत्व का उपयोग करता है, इसलिए इन अनुक्रमों के लिए खाली शून्य उपसर्गों को परिभाषित करना सुविधाजनक है: आर₀ = ε; और सी₀ = ε. सभी उपसर्गों को पहली पंक्ति में C के साथ एक तालिका में रखा गया है (इसे एक column हेडर बनाते हुए) और R को पहले कॉलम में रखा गया है (इसे एक row हेडर बनाते हुए)।

LCS Strings

	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε
A	ε
C	ε

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

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

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

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

एलसीएस(आर₁, सी₄), इसी तरह, (जी) है।

एलसीएस(आर₁, सी₅), इसी तरह, (जी) है।

"G" Row Completed

	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε	${\overset {\ \ \uparrow }{\leftarrow }}$ε	${\overset {\nwarrow }{\ }}$(G)	${\overset {\ }{\leftarrow }}$(G)	${\overset {\ }{\leftarrow }}$(G)	${\overset {\ }{\leftarrow }}$(G)
A	ε
C	ε

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

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

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

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

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

"G" & "A" Rows Completed

	ε	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	ε

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

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

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

एलसीएस (आर) के लिए₃, सी₄), सी और ए मेल नहीं खाते। एलसीएस(आर) का संयोजन₃, सी₃), जिसमें (एसी) और (जीसी), और एलसीएस (आर) शामिल हैं₂, सी₄), जिसमें (जीए) शामिल है, कुल तीन अनुक्रम देता है: (एसी), (जीसी), और (जीए)।

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

Completed LCS Table

	ε	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)

अंतिम परिणाम यह है कि अंतिम सेल में (एजीसीएटी) और (जीएसी) के सभी सबसे लंबे अनुवर्ती सामान्य शामिल हैं; ये हैं (एसी), (जीसी), और (जीए)। तालिका उपसर्गों की प्रत्येक संभावित जोड़ी के लिए सबसे लंबे समय तक सामान्य अनुवर्ती भी दिखाती है। उदाहरण के लिए, (एजीसी) और (जीए) के लिए, सबसे लंबे सामान्य अनुवर्ती (ए) और (जी) हैं।

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

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

Storing length, rather than sequences

	ε	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

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

Traceback example

	ε	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}$, सबसे छोटी सामान्य सुपरसीक्वेंस समस्या की लंबाई एलसीएस की लंबाई से संबंधित है

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

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

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

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

एलसीएस की लंबाई की गणना

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

    सी = सरणी(0..एम, 0..एन)
    i के लिए := 0..m
        सी[i,0] = 0
    j के लिए := 0..n
        सी[0,जे] = 0
    मेरे लिए := 1..मी
        j के लिए := 1..n
            यदि X[i] = Y[j]
                सी[आई,जे] := सी[आई-1,जे-1] + 1
            अन्य
                सी[आई,जे] := अधिकतम(सी[आई,जे-1], सी[आई-1,जे])
    वापसी सी[एम,एन]

वैकल्पिक रूप से, संस्मरण का उपयोग किया जा सकता है।

====सी#==== में उदाहरण

static int LcsLength(string a, string b)
{
	int m = a.Length;
	int n = b.Length;
	int[,] C = new int[m + 1, n + 1];
	for (int i = 0; i <= m; i++)
		C[i, 0] = 0;
	for (int j = 0; j <= n; j++)
		C[0, j] = 0;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
		{
			if (a[i - 1] == b[j - 1])
				C[i, j] = C[i - 1, j - 1] + 1;
			else
				C[i, j] = Math.Max(C[i, j - 1], C[i - 1, j]);
		}
	return C[m, n];
}

एलसीएस पढ़ना

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

फ़ंक्शन बैकट्रैक (C[0..m,0..n], X[1..m], Y[1..n], i, j)
    यदि मैं = 0 या जे = 0
        वापस करना
    यदि X[i] = Y[j]
        बैकट्रैक लौटें (सी, एक्स, वाई, आई-1, जे-1) + एक्स[आई]
    यदि C[i,j-1] > C[i-1,j]
        बैकट्रैक लौटें (सी, एक्स, वाई, आई, जे-1)
    बैकट्रैक लौटें (सी, एक्स, वाई, आई-1, जे)

====सी#==== में उदाहरण

string backtrack(int[,] C, char[] aStr, char[] bStr, int x, int y)
{
    if (x == 0 | y == 0)
        return "";
    if (aStr[x - 1] == bStr[y - 1]) // x-1, y-1
        return backtrack(C, aStr, bStr, x - 1, y - 1) + aStr[x - 1]; // x-1
    if (C[x, y - 1] > C[x - 1, y])
        return backtrack(C, aStr, bStr, x, y - 1);
    return backtrack(C, aStr, bStr, x - 1, y);
}

सभी एलसीएस को पढ़ना

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

फ़ंक्शन बैकट्रैकऑल(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    यदि मैं = 0 या जे = 0
        वापस करना {  }
    यदि X[i] = Y[j]
        बैकट्रैकऑल में सभी Z के लिए {Z + X[i] लौटाएं(C, X, Y, i-1, j-1)}
    आर := {}
    यदि C[i,j-1] ≥ C[i-1,j]
        आर := बैकट्रैकऑल(सी, एक्स, वाई, आई, जे-1)
    यदि C[i-1,j] ≥ C[i,j-1]
        आर := आर ∪ बैकट्रैकऑल(सी, एक्स, वाई, आई-1, जे)
    वापसी आर

अंतर प्रिंट करें

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

फ़ंक्शन printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    यदि i >= 0 और j >= 0 और X[i] = Y[j]
        प्रिंटडिफ (सी, एक्स, वाई, आई-1, जे-1)
        प्रिंट + एक्स[i]
    अन्यथा यदि j > 0 और (i = 0 या C[i,j-1] ≥ C[i-1,j])
        प्रिंटडिफ (सी, एक्स, वाई, आई, जे-1)
        प्रिंट + + वाई[जे]
    अन्यथा यदि i > 0 और (j = 0 या C[i,j-1] < C[i-1,j])
        प्रिंटडिफ (सी, एक्स, वाई, आई-1, जे)
        प्रिंट - + एक्स[i]
    अन्य
        छपाई

उदाहरण

होने देना $X$ होना "XMJYAUZ" और $Y$ होना "MZJAWXU”। के बीच सबसे लंबा सामान्य अनुवर्ती $X$ और $Y$ है "MJAU”। टेबल C नीचे दिखाया गया है, जो फ़ंक्शन द्वारा उत्पन्न होता है LCSLength, के उपसर्गों के बीच सबसे लंबे सामान्य अनुवर्ती की लंबाई दिखाता है $X$ और $Y$. $i$वें>वें पंक्ति और $j$वां कॉलम बीच में एलसीएस की लंबाई दिखाता है $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 एलसीएस पढ़ते समय, नीचे दाएं से ऊपरी बाएं कोने तक चलेगा। यदि वर्तमान प्रतीकों में $X$ और $Y$ बराबर हैं, वे एलसीएस का हिस्सा हैं, और हम ऊपर और बाएं दोनों तरफ जाते हैं (बोल्ड में दिखाया गया है)। यदि नहीं, तो हम ऊपर या बाएँ जाते हैं, यह इस बात पर निर्भर करता है कि किस सेल की संख्या अधिक है। यह या तो एलसीएस को बीच में लेने से मेल खाता है $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 वर्ण लंबा हो सकता है। इसके अतिरिक्त, हैश और चेकसम की यादृच्छिक प्रकृति यह गारंटी देगी कि तुलना तेजी से शॉर्ट-सर्किट होगी, क्योंकि शुरुआत में स्रोत कोड की लाइनें शायद ही कभी बदली जाएंगी।

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

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

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

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

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

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

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

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

यादृच्छिक तारों पर व्यवहार

Main article: Chvátal–Sankoff constants

इसके साथ शुरुआत Chvátal & Sankoff (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