أطول تسلسل مشترك (رياضيات)

مسألة أطول تسلسل مشترك (بالإنجليزية: Longest common subsequence problem) هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات ( متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب متتالية داخل المتسلسلة الأصلية. مشكلة أطول تسلسل مشترك تعتبر مشكلة علوم حاسب كلاسيكية، ولها تطبيقات في المعلوماتية الحيوية. كما أنها تستخدم على نطاق واسع من قبل أنظمة التحكم مثل GIT للتوفيق بين العديد من التغيرات علي مجموعة من الملفات.

حل المتتاليتين

مشاكل الLSC  لها كيان امثل : المشكلة ممكن تقسيمها الي مشاكل اصغر وابسط حيث يمكن تقسيمها الي مشاكل اصغر و هكذا. في النهاية الحل يصبح صغير جدا. مشاكل الLSC  لها أيضا مشاكل ثانوية متداخلة.
الحل لاعلي مرحله من المشاكل الثانية غالبا يعيد استخدام المشاكل الثانويه  للمرحله الأقل . المشاكل ذات هاتان الخاصيتان " الكبان الامثل و المشاكل الثانويه المتداخله " يمكن أن تصاغ عن طريق تقنيه حل المشكلات تسمي البرمجه الديناميكبه . حيث أنها تقوم بحفظ الحل بدلا من حسابه مرارا و تكرارا . الخطوات تتطلب memorization  لحفظ الحلول لكل مرحله من المشاكل الثانويه في الجدول , و بهذا تكون الحلول متوفرة للمراحل المتقدمه من المشاكل الثانويه .

الخاصيه الثانيه

بفرض ان المتسلسلتين x  و y لا تنتهي بنفس العنصر , اذن ال LCS لهما يصبح الأطول بين المتسلسلتين   LCS(Xₙ,Yₘ₋₁)و LCS(Xₙ₋₁,Yₘ) . لفهم هذة الخاصيه بفرض ان المتسلسلتين كالاتي 
المتسلسله  X: ABCDEFG
المتسلسله  Y: BCDGK
ال LCS للمتسلسلتين اما ينتهي ب G  أو لا
في الحاله الأولي : ال LCS ينتهي ب G
و بهذا لا تنتهي ب K  و بهذا لا يضر عند ازاله العنصر K من المتسلسله y لو كانت ال K في ال LCS و بهذا تكون  LCS(Xₙ,Yₘ) = LCS(Xₙ, Yₘ₋₁).
الحاله الثانية :
عندما لا تحتوي ال LCS علي عنصر ال G و بهذا حذف ال G2  من المتسلسله x و بهذا تستطيع كتابه LCS(Xₙ,Yₘ) = LCS(Xₙ₋₁, Yₘ).
في أي حاله ,الLCS الذي نبحث عنه هو واحد من   LCS(Xₙ, Yₘ₋₁) أو LCS(Xₙ₋₁, Yₘ) و بهذا يكون  LCS(X,Y) الأطول بين المتسلسلات

حساب طول الـ LCS

في الكود التالي المتسلسلات هي  X[1..m] و Y[1..n] و يتم حساب الـ بين X[1..i]  و Y[1..j] لكل 1 ≤ i ≤ m  و  1 ≤ j ≤ n و تقوم بحفظها في 
C[i,j] . و يحتوي C[m,n] علي طول الـ LCS
function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

قراءة LCS

الكود التالي به تنخفض الاختيارات عند حساب جدول C , إذا كان آخر عنصر من البادئات متساوي , يجب أن تكون في الـ LCS  بالاحتفاظ بـ X و Y
function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    else if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    else
        if C[i,j-1] > C[i-1,j]
            return backtrack(C, X, Y, i, j-1)
        else
            return backtrack(C, X, Y, i-1, j)

قراءة جميع LCS

اذا كان اختيار X و Y سوف يعطينا نتيجه طويله , فقم بقراءة نتائج المتسلسلات الجزئيه . لاحظ ان هذة الداله ليست كثيرة الحدود
function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    else if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    else
        R := {}
        if C[i,j-1] ≥ C[i-1,j]
            R := R ∪ backtrackAll(C, X, Y, i, j-1)
        if C[i-1,j] ≥ C[i,j-1]
            R := R ∪ backtrackAll(C, X, Y, i-1, j)
        return R

طباعه الفرق

لاحظ انك سوف تجد اجابات مختلفه في كل مرة تقوم بتغير ≥  و  <,بـ   >  و  ≤
function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i > 0 and j > 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

نمذجه الكود

يمكن اجراء بعض التحسينات علي الخوارزميه المذكورة اعلاه لتسريعها

تقليل المشاكل

المصفوفه C في الخوارزميه تنمو تربيعيا بالتناسب مع طول المتتاليات للمصفوفتين ذات ال 100 عنصر , مصفوفه 10.000 عنصر مطلوبه و مطلوب حدوث 10.000 مقارنه
function LCS(X[1..m], Y[1..n])
    start := 1
    m_end := m
    n_end := n
    trim off the matching items at the beginning
    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
        start := start + 1
    trim off the matching items at the end
    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    C = array(start-1..m_end, start-1..n_end)
    only loop over the items that have changed
    for i := start..m_end
        for j := start..n_end
            the algorithm continues as before ...
في أفضل سيناريو، وتسلسل بدون أي تغييرات، وهذا من شأنه  ان يقضي تماما على الحاجة إلى المصفوفة C. في السيناريو الأسوأ، أي تغيير على البنود الأولى والأخيرة في تسلسل،  لا يتم تنفيذ سوى اثنين من المقارنات إضافية.

تقليل وقت المقارنه

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

تقليل المساحة المطلوبة

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

سلوك متسلسلات عشوائيه

بدءا  (Chvátal & Sankoff (1975 عدد من الباحثين التحقيق في سلوك أطول مدة subsequence مشتركه عندما يتم رسم اثنين من سلاسل معينة بشكل عشوائي من نفس الأبجدية.  عندما يكون حجم الأبجدية هو ثابت، والطول المتوقع للLCS يتناسب مع طول السلسلتين، وثوابت التناسب (اعتمادا على حجم الأبجدية) والمعروفة باسم الثوابت Chvátal-Sankoff