أطول سلسلة فرعية مشتركة

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 24 صور
الموسوعة الحرة

في علم الحاسوب ، تُعرَّف أطول سلسلة فرعية مشتركة بين سلسلتين أو أكثر بأنها أطول سلسلة فرعية مشتركة بين جميع تلك السلاسل . وقد يوجد أكثر من سلسلة فرعية مشتركة واحدة. تشمل تطبيقاتها إزالة البيانات المكررة وكشف الانتحال .

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

أمثلة

تشترك السلسلتان "BADANAT" و "CANADAS" في السلاسل الفرعية ذات الطول الأقصى "ADA" و "ANA".

تُظهر الصورة سلسلتين نصيتين حيث توجد حلول متعددة للمشكلة. على الرغم من أن تكرارات السلاسل الفرعية تتداخل دائمًا، إلا أنه من المستحيل الحصول على سلسلة فرعية مشتركة أطول عن طريق "دمجها".

تحتوي السلاسل "ABABC" و "BABCA" و "ABCBA" على سلسلة فرعية مشتركة واحدة فقط، وهي "ABC" بطول 3. أما السلاسل الفرعية المشتركة الأخرى فهي "A" و "AB" و "B" و "BA" و "BC" و "C".

 أب أ ب ج ||| بابكا ||| ABCBA

تعريف المشكلة

بفرض وجود سلسلتين نصيتين،S{\displaystyle S}من الطولم{\displaystyle m}وتي{\displaystyle T}من الطولن{\displaystyle n}ابحث عن أطول سلسلة فرعية من كليهماS{\displaystyle S}وتي{\displaystyle T}.

تُعدّ مشكلة السلسلة الفرعية المشتركة k تعميمًا لهذه المشكلة . بالنظر إلى مجموعة السلاسلS={S1،...،Sك}{\displaystyle S=\{S_{1},\ldots ,S_{K}\}}، أين|Sأنا|=نأنا{\displaystyle |S_{i}|=n_{i}}و∑نأنا=شمال{\textstyle \sum n_{i}=N}أوجد لكل2≤ك≤ك{\displaystyle 2\leq k\leq K}أطول سلسلة تظهر كسلسلة فرعية من سلسلة واحدة على الأقلك{\displaystyle k}أوتار.

الخوارزميات

يمكن للمرء أن يجد أطوال ومواقع بداية أطول السلاسل الفرعية المشتركة لـS{\displaystyle S}وتي{\displaystyle T}فيΘ{\displaystyle \Theta }(ن+م){\displaystyle (n+m)}يمكن تحسين الوقت باستخدام شجرة لاحقة معممة . ويمكن تحقيق خوارزمية أسرع في نموذج حساب ذاكرة الوصول العشوائي للكلمات إذا كان الحجمσ{\displaystyle \sigma }جزء من الأبجدية المدخلة موجود في2o(سجل⁡(ن+م)){\displaystyle 2^{o\left({\sqrt {\log(n+m)}}\right)}}وعلى وجه الخصوص، تعمل هذه الخوارزمية فييا((ن+م)سجل⁡σ/سجل⁡(ن+م)){\textstyle O\left((n+m)\log \sigma /{\sqrt {\log(n+m)}}\right)}الوقت المستخدميا((ن+م)سجل⁡σ/سجل⁡(ن+م)){\displaystyle O\left((n+m)\log \sigma /\log(n+m)\right)}المساحة. [ 1 ] حل المشكلة باستخدام البرمجة الديناميكية يكلفΘ(نم){\displaystyle \Theta (nm)}. حلول المسألة المعممة تأخذΘ(ن1+⋯+نك){\displaystyle \Theta (n_{1}+\cdots +n_{K})}الفضاء وΘ(ن1⋯نك){\displaystyle \Theta (n_{1}\cdots n_{K})}الوقت مع البرمجة الديناميكية واستغلالهΘ(ن1+⋯+نك){\displaystyle \Theta (n_{1}+\cdots +n_{K})}الوقت مع شجرة لاحقة معممة .

شجرة اللواحق

شجرة لاحقة معممة للسلاسل "ABAB" و "BABA" و "ABBA"، مرقمة 0 و 1 و 2.

يمكن إيجاد أطول السلاسل الفرعية المشتركة لمجموعة من السلاسل النصية عن طريق بناء شجرة لواحق معممة لهذه السلاسل، ثم إيجاد أعمق العقد الداخلية التي تحتوي على عقد أوراق من جميع السلاسل في الشجرة الفرعية أسفلها. يوضح الشكل على اليمين شجرة اللواحق للسلاسل "ABAB" و"BABA" و"ABBA"، بعد إضافة فواصل فريدة بين السلاسل، لتصبح "ABAB$0" و"BABA$1" و"ABBA$2". تحتوي العقد التي تمثل "A" و"B" و"AB" و"BA" على أوراق فرعية من جميع السلاسل، المرقمة 0 و1 و2 على التوالي.

يستغرق بناء شجرة اللواحقΘ(شمال){\displaystyle \Theta (N)}الوقت (إذا كان حجم الأبجدية ثابتًا). إذا تم اجتياز الشجرة من الأسفل إلى الأعلى باستخدام متجه بتات يحدد السلاسل المرئية أسفل كل عقدة، فيمكن حل مشكلة السلسلة الفرعية المشتركة k فيΘ(شمالك){\displaystyle \Theta (NK)}الوقت. إذا تم إعداد شجرة اللواحق لاسترجاع السلف المشترك الأدنى في وقت ثابت ، فيمكن حلها فيΘ(شمال){\displaystyle \Theta (N)}الوقت. [ 2 ]

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

تُستخدم الشفرة الزائفة التالية لإيجاد مجموعة أطول السلاسل الفرعية المشتركة بين سلسلتين باستخدام البرمجة الديناميكية :

دالة LongestCommonSubstring(S[1..r], T[1..n]) L := array (1..r, 1..n) z := 0 # طول أطول سلسلة فرعية مشتركة تم العثور عليها حتى الآن ret := {} لـ i := 1..r لـ j := 1..n إذا كان S[i] = T[j] إذا كان i = 1 أو j = 1 L[i, j] := 1 آخر L[i, j] := L[i − 1, j − 1] + 1 إذا كان L[i, j] > z z := L[i, j] ret := {S[(i − z + 1)..i]} وإلا إذا كان L[i, j] = z ret := ret ∪ {S[(i − z + 1)..i]} آخر L[i, j] := 0 إرجاع ret

يتم تشغيل هذه الخوارزمية فييا(نر){\displaystyle O(nr)}الوقت. يخزن المصفوفة Lطول أطول لاحقة مشتركة للبادئات S[1..i]التي T[1..j]تنتهي عند الموضعينi و jعلى التوالي. يُستخدم المتغير zلتخزين طول أطول سلسلة فرعية مشتركة تم العثور عليها حتى الآن. retتُستخدم المجموعة لتخزين مجموعة السلاسل التي طولها z. يمكن حفظ المجموعة retبكفاءة عن طريق تخزين الفهرس i، وهو الحرف الأخير من أطول سلسلة فرعية مشتركة (بحجم z) بدلاً من S[(i-z+1)..i]. وبالتالي، ستكون جميع أطول السلاسل الفرعية المشتركة، لكل i في ret، S[(ret[i]-z)..(ret[i])].

يمكن استخدام الحيل التالية لتقليل استخدام الذاكرة في التطبيق:

  • احتفظ فقط بالصف الأخير والصف الحالي من جدول DP لتوفير الذاكرة (يا(مين(ر،ن)){\displaystyle O(\min(r,n))}بدلاً منيا(نر){\displaystyle O(nr)})
    • يمكن تخزين الصف الأخير والصف الحالي في نفس المصفوفة أحادية البعد عن طريق اجتياز الحلقة الداخلية للخلف.
  • خزّن القيم غير الصفرية فقط في الصفوف. يمكن تحقيق ذلك باستخدام جداول التجزئة بدلاً من المصفوفات. وهذا مفيد للأحرف الكبيرة.

انظر أيضاً

مراجع

  1. ^ شارالامبوبولوس، باناجيوتيس. كوسيوماكا، توماسز؛ بيسيس، سولون ب. رادوزيفسكي ، جاكوب (أغسطس 2021). موتزل، البتراء؛ باغ، راسموس. هيرمان، جريزيجورز (محرران). خوارزميات أسرع لأطول سلسلة فرعية مشتركة . الندوة الأوروبية حول الخوارزميات. إجراءات لايبنيز الدولية في مجال المعلوماتية (LIPIcs). المجلد.  204. شلوس داجشتول. دوى : 10.4230/LIPIcs.ESA.2021.30 .هنا: النظرية 1، ص 30:2.
  2. ↑ غوسفيلد، دان (1999) [1997]. خوارزميات على السلاسل والأشجار والمتتاليات: علوم الحاسوب وعلم الأحياء الحاسوبي . الولايات المتحدة الأمريكية: مطبعة جامعة كامبريدج. ISBN 0-521-58519-8.