
_START_ARTICLE_
أطول تسلسل مشترك (رياضيات)
_START_PARAGRAPH_
مسألة أطول تسلسل مشترك (بالإنجليزية: Longest common subsequence problem) هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات ( متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب متتالية داخل المتسلسلة الأصلية. مشكلة أطول تسلسل مشترك تعتبر مشكلة علوم حاسب كلاسيكية، ولها تطبيقات في المعلوماتية الحيوية. كما أنها تستخدم على نطاق واسع من قبل أنظمة التحكم مثل GIT للتوفيق بين العديد من التغيرات علي مجموعة من الملفات.
_START_SECTION_
حل المتتاليتين
_START_PARAGRAPH_
مشاكل الLSC  لها كيان امثل : المشكلة ممكن تقسيمها الي مشاكل اصغر وابسط حيث يمكن تقسيمها الي مشاكل اصغر و هكذا. في النهاية الحل يصبح صغير جدا. مشاكل الLSC  لها أيضا مشاكل ثانوية متداخلة._NEWLINE_الحل لاعلي مرحله من المشاكل الثانية غالبا يعيد استخدام المشاكل الثانويه  للمرحله الأقل . المشاكل ذات هاتان الخاصيتان " الكبان الامثل و المشاكل الثانويه المتداخله " يمكن أن تصاغ عن طريق تقنيه حل المشكلات تسمي البرمجه الديناميكبه . حيث أنها تقوم بحفظ الحل بدلا من حسابه مرارا و تكرارا . الخطوات تتطلب memorization  لحفظ الحلول لكل مرحله من المشاكل الثانويه في الجدول , و بهذا تكون الحلول متوفرة للمراحل المتقدمه من المشاكل الثانويه .
_START_SECTION_
الخاصيه الثانيه
_START_PARAGRAPH_
بفرض ان المتسلسلتين x  و y لا تنتهي بنفس العنصر , اذن ال LCS لهما يصبح الأطول بين المتسلسلتين   LCS(Xₙ,Yₘ₋₁)و LCS(Xₙ₋₁,Yₘ) . لفهم هذة الخاصيه بفرض ان المتسلسلتين كالاتي _NEWLINE_المتسلسله  X: ABCDEFG_NEWLINE_المتسلسله  Y: BCDGK_NEWLINE_ال LCS للمتسلسلتين اما ينتهي ب G  أو لا_NEWLINE_في الحاله الأولي : ال LCS ينتهي ب G_NEWLINE_و بهذا لا تنتهي ب K  و بهذا لا يضر عند ازاله العنصر K من المتسلسله y لو كانت ال K في ال LCS و بهذا تكون  LCS(Xₙ,Yₘ) = LCS(Xₙ, Yₘ₋₁)._NEWLINE_الحاله الثانية :_NEWLINE_عندما لا تحتوي ال LCS علي عنصر ال G و بهذا حذف ال G2  من المتسلسله x و بهذا تستطيع كتابه LCS(Xₙ,Yₘ) = LCS(Xₙ₋₁, Yₘ)._NEWLINE_في أي حاله ,الLCS الذي نبحث عنه هو واحد من   LCS(Xₙ, Yₘ₋₁) أو LCS(Xₙ₋₁, Yₘ) و بهذا يكون  LCS(X,Y) الأطول بين المتسلسلات
_START_SECTION_
حساب طول الـ LCS
_START_PARAGRAPH_
في الكود التالي المتسلسلات هي  X[1..m] و Y[1..n] و يتم حساب الـ بين X[1..i]  و Y[1..j] لكل 1 ≤ i ≤ m  و  1 ≤ j ≤ n و تقوم بحفظها في _NEWLINE_C[i,j] . و يحتوي C[m,n] علي طول الـ LCS_NEWLINE_function LCSLength(X[1..m], Y[1..n])_NEWLINE_    C = array(0..m, 0..n)_NEWLINE_    for i := 0..m_NEWLINE_       C[i,0] = 0_NEWLINE_    for j := 0..n_NEWLINE_       C[0,j] = 0_NEWLINE_    for i := 1..m_NEWLINE_        for j := 1..n_NEWLINE_            if X[i] = Y[j]_NEWLINE_                C[i,j] := C[i-1,j-1] + 1_NEWLINE_            else_NEWLINE_                C[i,j] := max(C[i,j-1], C[i-1,j])_NEWLINE_    return C[m,n]
_START_SECTION_
قراءة LCS
_START_PARAGRAPH_
الكود التالي به تنخفض الاختيارات عند حساب جدول C , إذا كان آخر عنصر من البادئات متساوي , يجب أن تكون في الـ LCS  بالاحتفاظ بـ X و Y_NEWLINE_function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)_NEWLINE_    if i = 0 or j = 0_NEWLINE_        return ""_NEWLINE_    else if  X[i] = Y[j]_NEWLINE_        return backtrack(C, X, Y, i-1, j-1) + X[i]_NEWLINE_    else_NEWLINE_        if C[i,j-1] > C[i-1,j]_NEWLINE_            return backtrack(C, X, Y, i, j-1)_NEWLINE_        else_NEWLINE_            return backtrack(C, X, Y, i-1, j)
_START_SECTION_
قراءة جميع LCS
_START_PARAGRAPH_
اذا كان اختيار X و Y سوف يعطينا نتيجه طويله , فقم بقراءة نتائج المتسلسلات الجزئيه . لاحظ ان هذة الداله ليست كثيرة الحدود_NEWLINE_function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)_NEWLINE_    if i = 0 or j = 0_NEWLINE_        return {""}_NEWLINE_    else if X[i] = Y[j]_NEWLINE_        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}_NEWLINE_    else_NEWLINE_        R := {}_NEWLINE_        if C[i,j-1] ≥ C[i-1,j]_NEWLINE_            R := R ∪ backtrackAll(C, X, Y, i, j-1)_NEWLINE_        if C[i-1,j] ≥ C[i,j-1]_NEWLINE_            R := R ∪ backtrackAll(C, X, Y, i-1, j)_NEWLINE_        return R
_START_SECTION_
طباعه الفرق
_START_PARAGRAPH_
لاحظ انك سوف تجد اجابات مختلفه في كل مرة تقوم بتغير ≥  و  <,بـ   >  و  ≤_NEWLINE_function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)_NEWLINE_    if i > 0 and j > 0 and X[i] = Y[j]_NEWLINE_        printDiff(C, X, Y, i-1, j-1)_NEWLINE_        print "  " + X[i]_NEWLINE_    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])_NEWLINE_        printDiff(C, X, Y, i, j-1)_NEWLINE_        print "+ " + Y[j]_NEWLINE_    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])_NEWLINE_        printDiff(C, X, Y, i-1, j)_NEWLINE_        print "- " + X[i]_NEWLINE_    else_NEWLINE_        print ""
_START_SECTION_
نمذجه الكود
_START_PARAGRAPH_
يمكن اجراء بعض التحسينات علي الخوارزميه المذكورة اعلاه لتسريعها
_START_SECTION_
تقليل المشاكل
_START_PARAGRAPH_
المصفوفه C في الخوارزميه تنمو تربيعيا بالتناسب مع طول المتتاليات للمصفوفتين ذات ال 100 عنصر , مصفوفه 10.000 عنصر مطلوبه و مطلوب حدوث 10.000 مقارنه_NEWLINE_function LCS(X[1..m], Y[1..n])_NEWLINE_    start := 1_NEWLINE_    m_end := m_NEWLINE_    n_end := n_NEWLINE_    trim off the matching items at the beginning_NEWLINE_    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]_NEWLINE_        start := start + 1_NEWLINE_    trim off the matching items at the end_NEWLINE_    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]_NEWLINE_        m_end := m_end - 1_NEWLINE_        n_end := n_end - 1_NEWLINE_    C = array(start-1..m_end, start-1..n_end)_NEWLINE_    only loop over the items that have changed_NEWLINE_    for i := start..m_end_NEWLINE_        for j := start..n_end_NEWLINE_            the algorithm continues as before ..._NEWLINE_في أفضل سيناريو، وتسلسل بدون أي تغييرات، وهذا من شأنه  ان يقضي تماما على الحاجة إلى المصفوفة C. في السيناريو الأسوأ، أي تغيير على البنود الأولى والأخيرة في تسلسل،  لا يتم تنفيذ سوى اثنين من المقارنات إضافية.
_START_SECTION_
تقليل وقت المقارنه
_START_PARAGRAPH_
معظم الوقت المستغرق من قبل خوارزمية بسيطه يمر في أداء المقارنات بين العناصر في متواليات. لمتواليات نصية مثل شفرة المصدر، وكنت ترغب في عرض خطوط باعتبارها عناصر تسلسل بدلا من أحرف واحدة. هذا يمكن أن يعني مقارنات سلاسل طويلة نسبيا لكل خطوة في الخوارزمية. ويمكن إجراء اثنين من التحسينات التي يمكن أن تساعد على تقليل الوقت المستهلك في هذه المقارنات.
_START_SECTION_
تقليل المساحة المطلوبة
_START_PARAGRAPH_
إذا كنت بحاجة  لطول LCS، يمكن تقليل المصفوفة ل  مصفوفة بكل سهولة، أو ل   حيث أن البرمجة الديناميكية يحتاج فقط الأعمدة الحالية والسابقة للمصفوفة. خوارزمية هرشبيرغ تسمح للبناء التسلسل الأمثل نفسها في نفس الوقت من الدرجة الثانية .
_START_SECTION_
سلوك متسلسلات عشوائيه
_START_PARAGRAPH_
بدءا  (Chvátal & Sankoff (1975 عدد من الباحثين التحقيق في سلوك أطول مدة subsequence مشتركه عندما يتم رسم اثنين من سلاسل معينة بشكل عشوائي من نفس الأبجدية.  عندما يكون حجم الأبجدية هو ثابت، والطول المتوقع للLCS يتناسب مع طول السلسلتين، وثوابت التناسب (اعتمادا على حجم الأبجدية) والمعروفة باسم الثوابت Chvátal-Sankoff