ⓘ بزرگترین زیررشته مشترک. در علوم کامپیوتر، مسئله بلندترین زیررشته مشترک برای یافتن بلندترین رشتهیا رشته‌هایی که زیر رشته یا زیررشته‌هاییاز دویاچندین رشته هستند،م ..

                                     

ⓘ بزرگترین زیررشته مشترک

در علوم کامپیوتر، مسئله بلندترین زیررشته مشترک برای یافتن بلندترین رشتهیا رشته‌هایی که زیر رشته یا زیررشته‌هاییاز دویاچندین رشته هستند،می‌باشد.این مسئله نباید با مسئله بلندترین زیردنباله مشترک اشتباه گرفته شود.برای توضیحی در مورد تفاوت میان یک زیررشته و یک زیردنباله به زیررشته درمقابل زیردنباله رجوع کنید.

                                     

1. مثال

بلندترین زیررشته مشترک از رشته‌های "ABAB", "BABA و "ABBA" ، رشته‌های "AB" و "BA" از طول دو هستند.دیگر زیر رشته‌های مشترک "A" و "B" هستند.

ABAB ||| BABA || ABBA
                                     

2. تعریف مسئله

با دو رشته داده شده، S {\displaystyle S} از طول m {\displaystyle m} و T {\displaystyle T} از طول n {\displaystyle n} ،بلندترین رشته‌هایی که زیر رشته‌های هر دوی S {\displaystyle S} و T {\displaystyle T} هستند را پیدا کنید.یک تعمیم از این مسئله، مسئله K {\displaystyle K} زیررشته مشترک است.بارشته‌های داده شده S = { S 1., S K } {\displaystyle S=\{S_{1}.,S_{K}\}} جایی که | S i | = n i {\displaystyle |S_{i}|=n_{i}} و Σ n i = N {\displaystyle n_{i}=N}.

                                     

3. الگوریتم‌ها

ما می‌توانیم طول‌ها و مکان‌های شروع بلندترین زیررشته‌های مشترک S {\displaystyle S} و T {\displaystyle T} را در زمان Θ n + m {\displaystyle \Theta n+m} به کمک درخت پسوندی توسعه یافته بیابیم.پیداکردن آن‌ها به کمک برنامه نویسی پویاهزینه‌ای معادل Θ n m {\displaystyle \Theta nm} دارد.راه حل مسئله تعمیم یافته،زمان Θ n 1 +. n k {\displaystyle \Theta n_{1}+.n_{k}} و Θ n 1. n k {\displaystyle \Theta n_{1}.n_{k}} را می‌گیرد.

                                     

4. درخت پسوندی

بزرگترین زیررشته مشترک از یک مجموعه از رشته‌ها می‌تواند توسط ساختن یک درخت پسوندی تعمیم یافته برای رشته‌ها ، و سپس یافتن عمیق‌ترین نودهای داخلی که گره‌های برگی که از همه رشته‌ها در درخت پایین اشان دارند ،یافت شود.

شکل سمت چپ درخت پسوندی برای رشته‌های "ABAB" ،"BABA" و"ABBA" است که توسط پایانه‌های یکتای رشته‌ها خالی شده‌اند، تا "ABAB$0", "BABA$1" و "ABBA$2" شوند.گره‌هایی که "A", "B", "AB" و "BA" را نمایش می‌دهند همگی برگ‌های فرزندی از همهٔ رشته‌ها دارند،که با0،1 و 2 شماره‌گذاری شده‌اند.

ساختن درخت پسوندی زمان Θ n {\displaystyle \Theta n} time می‌گیردطول الفبا ثابت است.اگردرخت از پایین به بالا با یک بردار بیتی که می‌گوید چه رشته‌هایی پایین هر گره دیده شده‌اند،پیمایش شود،مسئله K زیررشته مشترک می‌تواند در زمان Θ N K {\displaystyle \Theta NK} حل شود.اگردرخت پسوندی برای زمان ثابت بازیابی کم‌ترین پدران مشترک آماده شود،می‌تواند در زمان Θ N {\displaystyle \Theta N} time. حل شود.

                                     

5. برنامه‌نویسی پویا

درابتدا بزرگترین پسوند مشترک رابرای همهٔ جفت پیشوندهای رشته بیابید.بزرگترین پسوند مشترک L C S u f S 1. p, T 1. q = { L C S u f S 1. p − 1, T 1. q − 1 + 1 i f S \\0&\mathrm {otherwise}.\end{cases}}} است.

برای مثال رشته‌های "ABAB" و "BABA":

حداکثراین طولانی‌ترین پسوندهای مشترک ازپیشوندهای مشترک باید طولانی‌ترین زیررشته‌های مشترک از S و T باشند.این‌ها در جدول،باقرمز،روی قطرها نمایش داده شده‌اند.برای این مثال طولانی‌ترین زیر رشته‌های مشترک "BAB" و "ABA" هستند.

L C S u b s t r S, T = max 1 ≤ i ≤ m, 1 ≤ j ≤ n L C S u f S 1. i, T 1. j {\displaystyle {\mathit {LCSubstr}}S,T=\max _{1\leq i\leq m,1\leq j\leq n}{\mathit {LCSuff}}S_{1.i},T_{1.j}\;}

این مورد می‌تواند به بیش از دو رشته با اضافه کردن ابعاد بیشتر به جدول بسط داده شود.

                                     

6. شبه کد

شبه کد پایین مجموعه بزرگترین زیر رشته‌های مشترک رامیان دورشته با برنامه نویسی پویا می‌یابد.

این الگوریتم در زمان O n m {\displaystyle Onm} اجرا می‌شود. متغیر z برای نگهداری طول بزرگترین زیررشته مشرک که ناکنون یافت شده‌است به کار می‌رود.مجموعه ret برای نگهداری مجموعه‌ای از رشته‌ها که از طول z هستند به کار می‌رود.مجموعه ret می‌تواند به‌طور کارایی توسط انباره کردن اندیس i ذخیره شود،که آخرین کاراکتر از طولانی‌ترین زیررشته مشترکاز اندازه Z به جای S خواهند بود.

ترفندهای زیر می‌تواند برای کاهش حافظه در یک اجرا به کار رود.

  • فقط مقادیر غیر صفر را در سطرها نگهداری کنید.این امر می‌تواند توسط استفاده از جداول هش به جای آرایه‌ها انجام شود.این امر برای الفباهای بزرگ مفید است.
  • فقط آخرین و سطرکنونی جدول برنامه نویسی پویارابرای ذخیره حافظه O min m, n) {\displaystyle O\minm,n)} به جای O n m {\displaystyle Onm} نگاه دارید.
                                     

7. پیوند به بیرون

  • Perl/XS implementation of the suffix tree algorithm
  • Perl/XS implementation of the dynamic programming algorithm
  • Dynamic programming implementations in various languages on wikibooks
  • working AS3 implementation of the dynamic programming algorithm