Algorithms/Longest Common Subsequence

نقول عن تسلسل فرعي معيّن بأنّه أطول تسلسل فرعي مشترك Longest Common Subsequence عندما يظهر هذا التسلسل الفرعي بنفس الترتيب النسبي ولكن دون اشتراط تجاور العناصر. فعلى سبيل المثال تُعدُّ التسلسلات "abc" و "abg" و "bdf" و "aeg" و "acefg" وغيرها تسلسلات متفرعة من التسلسل الأصلي "abcdefg".

تعتمد برمجيات diff (وهي برمجيات تقارن بين ملفين وتعطي الفرق بينهما) على هذه الخوارزمية، ولهذه الخوارزمية تطبيقات أخرى في مجال المعلوماتية الحيوية bioinformatics.

الطريقة البسيطة

يمكن تنفيذ هذه الخوارزمية بطريقة بسيطة تتضمن إنشاء جميع التسلسلات الفرعية لكلا التسلسلين المعطيين وإيجاد أطول تسلسل فرعي مطابق.

تعرض الأمثلة التالية كيفية تنفيذ الطريقة البسيطة لإيجاد أطول تسلسل فرعي مشترك في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

int max(int a, int b); 

/* تعيد الدالة طول أطول تسلسل فرعي مشترك */
int lcs( char *X, char *Y, int m, int n ) 
{ 
	if (m == 0 || n == 0) 
		return 0; 
	if (X[m-1] == Y[n-1]) 
		return 1 + lcs(X, Y, m-1, n-1); 
	else
		return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
} 

// دالة مساعدة للحصول على أكبر الرقمين المعطيين
int max(int a, int b) 
{ 
	return (a > b)? a : b; 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
	char X[] = "AGGTAB"; 
	char Y[] = "GXTXAYB"; 
	
	int m = strlen(X); 
	int n = strlen(Y); 
	
	cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ; 
	
	return 0; 
}

• بايثون:

# تعيد الدالة طول أطول تسلسل فرعي مشترك
def lcs(X, Y, m, n): 

	if m == 0 or n == 0: 
		return 0; 
	elif X[m-1] == Y[n-1]: 
		return 1 + lcs(X, Y, m-1, n-1); 
	else: 
		return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 

# اختبار الدالة السابقة
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X , Y, len(X), len(Y))

• جافا:

public class LongestCommonSubsequence 
{ 

/* تعيد الدالة طول أطول تسلسل فرعي مشترك */
int lcs( char[] X, char[] Y, int m, int n ) 
{ 
	if (m == 0 || n == 0) 
		return 0; 
	if (X[m-1] == Y[n-1]) 
		return 1 + lcs(X, Y, m-1, n-1); 
	else
		return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
} 

/* Utility function to get max of 2 integers */
int max(int a, int b) 
{ 
	return (a > b)? a : b; 
} 

// اختبار الدالة السابقة

public static void main(String[] args) 
{ 
	LongestCommonSubsequence lcs = new LongestCommonSubsequence(); 
	String s1 = "AGGTAB"; 
	String s2 = "GXTXAYB"; 

	char[] X=s1.toCharArray(); 
	char[] Y=s2.toCharArray(); 
	int m = X.length; 
	int n = Y.length; 

	System.out.println("Length of LCS is" + " " + 
								lcs.lcs( X, Y, m, n ) ); 
} 

}

التعقيد الزمني

يتطلب حساب التعقيد الزمني للطريقة البسيطة معرفة عدد التسلسلات الفرعية المختلفة والتي يمكن إنشاءها من سلسلة نصية يبلغ طولها n، أي معرفة عدد التسلسلات الفرعية ذات الأطوال التي تبدأ من 1 وتنتهي عند n-1.

يمكن استخدام نظرية التباديل والتوافيق permutation and combination لحساب عدد الاحتمالات، إذ أن عدد التوافيق لعنصر واحد يساوي nC1، ولعنصرين nC2 وهكذا. ولما كان ‎nC0 + nC1 + nC2 + … nCn = 2n فإنّ السلسلة النصية ذات الطول n تمتلك 2n-1 تسلسلًا فرعيًا مختلفًا إن لم نأخذ بنظر الاعتبار التسلسل الفرعي الفارغ (الطول = 0). وهذا يعني أنّ التعقيد الزمني للطريقة البسيطة يبلغ O(n*2^n)‎. ويلاحظ من الأمثلة السابقة أنّ عملية التحقق من اشتراك تسلسل فرعي معين بين السلسلتين النصيتين يستغرق O(n)‎ من الوقت.

يمكن تحسين التعقيد الزمني لهذه الخوارزمية باستخدام البرمجة الديناميكية.

طريقة البرمجة الديناميكية

تمتلك مسألة إيجاد أطول تسلسل فرعي مشترك الخاصيتين الأساسيتين في البرمجة الديناميكية، وهما البنية الفرعية المثالية والمسائل الفرعية المتداخلة.

البنية الفرعية المثالية

لنفترض أنّ التسلسلين المدخلين هما X[0..m-1]‎ و Y[0..n-1]‎ وطولهما هو m و n على التوالي. ولنفترض أن ‎L(X[0..m-1], Y[0..n-1])‎ هما طولا أطول تسلسل فرعي مشترك للتسلسلين X و Y. يمكن تعريف ‎L(X[0..m-1], Y[0..n-1])‎ تعاوديًا بما يلي:

إن كان الحرفان الأخيران في كلا التسلسلين متطابقين (أي X[m-1]‎ == Y[n-1]‎) فهذا يعني أنّ:

L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

وإن كان الحرفان الأخيران في كلا التسلسلين غير متطابقين (أي X[m-1]‎ != Y[n-1]‎) فهذا يعني أنّ:

L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) )

أمثلة:

1. يتطابق آخر حرفين في السلسلتين النصيتين "AGGTAB" و "GXTXAYB"؛ لهذا يمكن التعبير عن طول أطول تسلسل فرعي مشترك بالطريقة التالية:

L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)

1. لا يتطابق آخر حرفين في السلسلتين النصيتين "ABCDGH" و "AEDFHR"؛ لهذا يمكن التعبير عن طول أطول تسلسل فرعي مشترك بالطريقة التالية:

L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )

هذا يعني أنّ مسألة إيجاد أطول تسلسل فرعي مشترك تمتلك خاصية البنية الفرعية المثالية؛ وذلك لأن من الممكن إيجاد حلّ للمسألة الرئيسية باستخدام حلول المسائل المتفرّعة عنها.

المسائل الفرعية المتداخلة

يؤدي استخدام الخوارزمية البسيطة مع السلسلتين النصيتين "AXYT" و "AYZX" للحصول على شجرة تعاودية يعرض المخطط التالي جزءًا منها:

                         lcs("AXYT", "AYZX")
                       /                 
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /                              /               
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

يلاحظ تكرار الدالة lcs("AXY", "AYZ")‎ مرتين في المخطط السابق، وتتضمن الشجرة الكاملة الكثير من المسائل الفرعية التي تُحلّ مرارًا وتكرارًا. وهذا يعني أنّ هذه المسألة تمتلك خاصية المسائل الفرعية المتداخلة وأن بالإمكان تجنّب إعادة عملية الحساب باستخدام طريقة التحفيظ Memoization أو الجدولة Tabulation.

تعرض الأمثلة التالية طريقة تحسين الخوارزمية باستخدام طريقة الجدولة.

• C++‎:

#include<bits/stdc++.h> 

int max(int a, int b); 

/* تعيد الدالة أطول تسلسل فرعي مشترك للتسلسلين المعطيين */
int lcs( char *X, char *Y, int m, int n ) 
{ 
int L[m+1][n+1]; 
int i, j; 

/* تنشئ الخطوات التالية القيمة
L[m+1][n+1]
من الأسفل إلى الأعلى
L[i][j] لاحظ أن القيمة
تحتوي على طول أطول تسلسل فرعي مشترك للتسلسلين
X[0..i-1] and Y[0..j-1] */
    
for (i=0; i<=m; i++) 
{ 
	for (j=0; j<=n; j++) 
	{ 
	if (i == 0 || j == 0) 
		L[i][j] = 0; 

	else if (X[i-1] == Y[j-1]) 
		L[i][j] = L[i-1][j-1] + 1; 

	else
		L[i][j] = max(L[i-1][j], L[i][j-1]); 
	} 
} 
	
/* L[m][n] تحتوي القيمة
على طول أطول تسلسل فرعي مشترك للتسلسلين
X[0..n-1] و Y[0..m-1] */
return L[m][n]; 
} 

// دالة مساعدة تعيد العدد الأكبر من بين العددين المعطيين
int max(int a, int b) 
{ 
	return (a > b)? a : b; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
char X[] = "AGGTAB"; 
char Y[] = "GXTXAYB"; 

int m = strlen(X); 
int n = strlen(Y); 

printf("Length of LCS is %d", lcs( X, Y, m, n ) ); 

return 0; 
}

• بايثون:

def lcs(X , Y): 
	# حساب طول السلاسل النصية
	m = len(X) 
	n = len(Y) 

	# dp إنشاء المصفوفة التي ستخزّن فيها قيم
	L = [[None]*(n+1) for i in xrange(m+1)] 

	
    """تنشئ الخطوات التالية القيمة
	L[m+1][n+1]
	من الأسفل إلى الأعلى
	L[i][j] لاحظ أن القيمة
	تحتوي على طول أطول تسلسل فرعي مشترك للتسلسلين
	X[0..i-1] and Y[0..j-1]"""
	for i in range(m+1): 
		for j in range(n+1): 
			if i == 0 or j == 0 : 
				L[i][j] = 0
			elif X[i-1] == Y[j-1]: 
				L[i][j] = L[i-1][j-1]+1
			else: 
				L[i][j] = max(L[i-1][j] , L[i][j-1]) 

	# L[m][n] تحتوي القيمة
	# على طول أطول تسلسل فرعي مشترك للتسلسلين
	# X[0..n-1] و Y[0..m-1] 
	return L[m][n] 


# اختبار الدالة السابقة
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y)

• جافا:

public class LongestCommonSubsequence 
{ 

/* تعيد الدالة أطول تسلسل فرعي مشترك للتسلسلين المعطيين */
int lcs( char[] X, char[] Y, int m, int n ) 
{ 
	int L[][] = new int[m+1][n+1]; 

	/* تنشئ الخطوات التالية القيمة
	L[m+1][n+1]
	من الأسفل إلى الأعلى
	L[i][j] لاحظ أن القيمة
	تحتوي على طول أطول تسلسل فرعي مشترك للتسلسلين
	X[0..i-1] and Y[0..j-1] */
	for (int i=0; i<=m; i++) 
	{ 
	for (int j=0; j<=n; j++) 
	{ 
		if (i == 0 || j == 0) 
			L[i][j] = 0; 
		else if (X[i-1] == Y[j-1]) 
			L[i][j] = L[i-1][j-1] + 1; 
		else
			L[i][j] = max(L[i-1][j], L[i][j-1]); 
	} 
	} 
return L[m][n]; 
} 

// دالة مساعدة تعيد العدد الأكبر من بين العددين المعطيين
int max(int a, int b) 
{ 
	return (a > b)? a : b; 
} 

// اختبار التوابع السابقة
public static void main(String[] args) 
{ 
	LongestCommonSubsequence lcs = new LongestCommonSubsequence(); 
	String s1 = "AGGTAB"; 
	String s2 = "GXTXAYB"; 

	char[] X=s1.toCharArray(); 
	char[] Y=s2.toCharArray(); 
	int m = X.length; 
	int n = Y.length; 

	System.out.println("Length of LCS is" + " " + 
								lcs.lcs( X, Y, m, n ) ); 
} 

}

التعقيد الزمني

يبلغ التعقيد الزمني لطريقة التنفيذ السابقة المقدار O(mn)‎ وهو أفضل بكثير من التعقيد الزمني للطريقة البسيطة.

مصادر

• صفحة Longest Common Subsequence في توثيق الخوارزميات في موقع GeeksforGeeks.