بزرگ‌ترین زیردنباله مشترک

بزرگترین زیردنباله مشترک (به انگلیسی: Longest Common Subsequence)‏، روشی است که برای پیدا کردن بزرگترین زیردنباله در مجموعه‌ای از دنباله‌ها (غالباً دو دنباله) به کار می‌رود و مساله‌ای قدیمی در علم کامپیوتر است و همین طور اساس کار برنامه‌های مقایسه کننده فایل است که تفاوت دو فابل را نمایش می‌دهد. همین طور در بیوانفورماتیک برای مقایسه رشته‌های دی ان ای کاربرد دارد.

شرح مساله

دو رشته زیر را در نظر بگیرید:

$S_{1}=ACCGGTCGAGTGCGCGGAGCCGGCCGAA\,\!$

$S_{2}=GTCGTTCGGAATGCCGTTGCTCTGTAAA\,\!$

هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند $S_{3}$ است به طوری که حروف موجود در $S_{3}$ با حفظ ترتیب در $S_{1}$ و $S_{2}$ موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی $S_{3}$ باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته $X=\langle x_{1},x_{2},... ,x_{n}\rangle$ و $Y=\langle y_{1},y_{2},... ,y_{n}\rangle$ را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.

راه حل برای دو دنباله

مساله LCS دارای خصوصیت زیر ساختار بهینه (Optimal Substructure) است:

مساله LCS را می‌توان به زیر مساله‌های کوچکتر تقسیم نمود.

که این زیر مساله‌ها جفت دنباله‌های پیشوندی دو دنباله ورودی هستند. اگر داشته باشیم: $X=\langle x_{1},x_{2},... ,x_{n}\rangle$٫ آن گاه $X_{i}$ به این صورت تعریف می‌شود: $X_{i}=\langle x_{1},x_{2},... ,x_{i}\rangle$

فرض کنید $X=\langle x_{1},x_{2},... ,x_{m}\rangle$ و $Y=\langle y_{1},y_{2},... ,y_{n}\rangle$ دو رشته باشند و $Z=\langle z_{1},z_{2},... ,z_{k}\rangle$ بلندترین زیردنباله مشترک یا LCS دو رشته Y و X باشند. پیاده سازی الگوریتم با استفاده از روش برنامه نویسی پویا به این صورت است:

۱)اگر $X_{m}=Y_{n}\,\!$ باشد٫ آن گاه $Z_{k}=X_{m}=Y_{n}$ و $Z_{k-1}$ یک LCS برای $Y_{k-1}$ و $X_{k-1}$ است.

۲)اگر $X_{m}\ne\; Y_{n}$ باشد٫ آن گاه $Z_{k}\ne\;X_{m}$ نتیجه می‌دهد که Z یک LCS برای $Y$ و $X_{m-1}$ است.

۳)اگر $X_{m}\ne\; Y_{n}$ باشد٫ آن گاه $Z_{k}\ne\;Y_{m}$ نتیجه می‌دهد که Z یک LCS برای $Y_{n-1}$ و $X$ است.

قضیه فوق نشان می‌دهد: LCS دو رشته٫ در داخل خودش٫ حاوی یک LCS برای پیشوندهای آن دو رشته نیز می‌باشد.

یک راه حل بازگشتی برای پیداکردن LCS

فرض کنید $c[i,j]\,\!$ یک عنصر از آرایه C باشد که نشان دهنده طول LCS دو دنباله$X_{i}$ و $Y_{i}$ است. بنابراین اگر i=0 یا j=0 باشد٫ یکی از دنباله‌ها دارای طول صفر است و در نتیجه LCS دو دنباله صفر خواهد شد. $c[i,j] = \begin{cases} 0 & i=0\ or\ j=0 \\ c[i-1,j-1]+1 & i,j>0\ and\ X_{i}= Y_{j} \\ max(c[i-1,j],c[i,j-1]) & i,j>0\ and\ X_{i}\ne Y_{j} \end{cases}$ بنابراین وقتی که $X_{i}\ne\; Y_{j}$ باشد٫ زیر مساله ما پیدا کردن LCS برای $X_{i-1}$ و $Y_{i-1}$ است. در غیر این صورت ما دو زیر مساله داریم:

پیدا کردن LCS برای $Y_{i}$ و $X_{i-1}$ و

پیدا کردن LCS برای $Y_{i-1}$ و $X_{i}$

شکل ۱

االگوریتم را با استفاده از روش برنامه نویسی پویا پیاده سازی می‌کنیم. الگوریتم دو رشته $X=\langle x_{1},x_{2},... ,x_{m}\rangle$ و $Y=\langle y_{1},y_{2},... ,y_{n}\rangle$ را به عنوان ورودی دریافت می‌کند(شکل ۲). الگوریتم مقادیر $c[i,j]\,\!$ که نشان دهدنده طول LCS است را داخل آرایه $c[1..m,1..n]\,\!$ ذخیره می‌کند. عناصر آرایه به ترتیب row-major پر می‌شوند. یهنی ابتدا اولین سطر c به ترتیب از چپ به راست پر می‌شود، سپس سطر دوم و الی آخر. علاوه بر این الگوریتم آرایه دیگری به نام $b[1..m,1..n]\,\!$ را نیز پر می‌کند. این آرایه جهت حرکت را ذخیره می‌کند.

شکل ۲

مقدار b با علامت‌های جهت $\leftarrow,\uparrow,\nwarrow$ پر می‌شود. همین طور مقدار $c[i,j]\,\!$ به این بستگی دارد که آیا $x_i=y_i$ باشد (خط ۹). جهت فلش‌ها طوری انتخاب می‌شود که همواره حرکت به سمت خانه‌ای با طول LCS بزرکتر را تضمین می‌کند. در نهایت برای پیدا کردن LCS از گوشه سمت راست و پایین آرایه b در جهت پیکان‌ها به سمت گوشه بالا و چپ آرایه حرکت می‌کنیم.

function print_LCS (b,X,i,j)
  if i=0 or j=0 then
     return
  if b[i,j] = '$\nwarrow$' then
     print_LCS(b,X,i-1,j-1)
     print $x_i$
  else if b[i,j]= '$\uparrow$' then
     print_LCS(b,X,i,j-1)
  else print_LCS(b,X,i,j-1)

پیچیدگی زمانی

زمانی که تعداد دنباله‌های ورودی ثابت باشند٫ این مساله توسط برنامه نویسی پویا در زمان چندجمله‌ای حل می‌شود. فرض کنید N دنباله ورودی به طول $n_1,n_2,... ,n_N$ داشته باشیم. یک راه حل ابتدایی برای جستجوی LCS این است که هر یک از$2^{n_1}$ زیردنباله دنباله اولی را برررسی کنیم که آیا زیر دنباله برای دیگر دنباله‌های ورودی است یا خیر. هر زیر ددنباله در زمانی خطی متناسب با طول دنباله‌های باقی مانده بررسی می‌شود. بنابراین زمان الگوریتم برابر خواهد بود با:$O\left(2^{n_1} \sum_{i>1} n_i\right).$ برای حالت ورودی با دو دنباله با n و m عنصر٫ پیچیدگی زمانی الگوریتم برابر $O(mn)\,\!$ خواهد بود. برای تعداد ورودی‌های دلخواه برنامه نویسی پویا راه حلی با این زمان ارایه می‌کند:$O\left(N \prod_{i=1}^{N} n_i\right).$

توابعی با پیچیدگی کمتر موجود است،

منابع

• مشارکت‌کنندگان ویکی‌پدیا، «Longest common subsequence problem»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۸ می‌۲۰۰۹).
• دکتر جم زاد، منصور. جزوه درسی ساختمان داده و الگوریتم ها٫ نسخه ویرایش نشده. تهران: دانشگاه صنعتی شریف، ۱۳۸۵.
• توماس اچ کورمن, Charles E. Leiserson, Ronald L. Rivest and کلیفورد استین. “۱۵٫۴”. In مقدمه‌ای بر الگوریتم‌ها. second ed. MIT Press and McGraw-Hill, 2001. 350–355. ISBN 0-262-53196-8.