أطول متتالية جزئية مشتركة (LCS)

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

جدول تمتد فيه كلمة على طول أعلاه وأخرى على جانبه، وفي خلاياه أرقام، ومسار من الخلايا البرتقالية يصعد من الزاوية السفلية اليمنى
جدول تمتد فيه كلمة على طول أعلاه وأخرى على جانبه، وفي خلاياه أرقام، ومسار من الخلايا البرتقالية يصعد من الزاوية السفلية اليمنى

المسألة

المتتالية الجزئية من كلمة تحتفظ ببعض حروفها بترتيبها الأصلي: ACE متتالية جزئية من ABCDE، أما EA فليست كذلك. والمتتالية الجزئية المشتركة بين كلمتين هي متتالية جزئية من كلتيهما، والمسألة هي إيجاد أطولها. للكلمة التي طولها n ما مجموعه 2ⁿ متتالية جزئية، لذا فإن تجربتها كلها ميؤوس منها بعد بضعة حروف.

الجدول

لتكن len[i][j] طول أطول متتالية جزئية مشتركة بين أول i حرفًا من إحدى الكلمتين وأول j حرفًا من الأخرى. الكلمة الفارغة لا تشترك في شيء، لذا فإن قيمة الصف الأول والعمود الأول 0. إذا كان الحرف رقم i يساوي الحرف رقم j، فإن len[i][j] = len[i − 1][j − 1] + 1: فالتطابق يمدّ ما سبقه. وإلا فإن len[i][j] هي الأكبر من len[i − 1][j] وlen[i][j − 1]: أسقط أحد الحرفين واحتفظ بالنتيجة الأفضل.

مثال

قارن ABCBDAB مع BDCABA. الحرف الأول من الكلمة الثانية، B، يطابق B في الصف 2؛ وC في العمود الثالث يطابق الصف 3، وهكذا، وكل تطابق يضيف واحدًا إلى الخلية أعلاها إلى اليسار. تنتهي الخلية السفلية اليمنى عند 4. والقراءة رجوعًا من هناك تعطي BCBA، لكن BCAB وBDAB بالطول نفسه: فأطول متتالية جزئية مشتركة ليست بالضرورة وحيدة.

قراءة الإجابة رجوعًا

ابدأ من الخلية السفلية اليمنى. إذا تطابق حرفا صفها وعمودها، فذلك الحرف ينتمي إلى الإجابة: سجّله وانتقل قطريًا إلى أعلى اليسار. وإلا فانتقل إلى الخلية المجاورة، فوقها أو على يسارها، ذات القيمة الأكبر، لأن الخلية أخذت قيمتها من هناك. توقف عند الصف الأول أو العمود الأول. الحروف المسجّلة، بعد عكس ترتيبها، هي المتتالية الجزئية.

التاريخ والاستخدامات

اكتشف عدة أشخاص طريقة الجدول كلٌّ على حدة نحو عام 1970، ومنهم روبرت واغنر ومايكل فيشر، اللذان حلّت ورقتهما عام 1974 مسألة مسافة التحرير وثيقة الصلة. وفي عام 1975 بيّن دان هيرشبرغ كيف تُوجد المتتالية الجزئية بذاكرة أقل بكثير، وفي عام 1976 بنى جيمس هانت ودوغلاس ماكلروي برنامج Unix diff على أطول المتتاليات الجزئية المشتركة بين الأسطر. ويستخدم علماء الأحياء الفكرة نفسها، مع نقاط تقييم، لمحاذاة تسلسلات الحمض النووي والبروتينات.

دوغلاس ماكلروي، بعدسة بيتر آدامز لمشروع Faces of Open Source. بنى هو وجيمس هانت عام 1976 برنامج diff في يونكس على أطول التتابعات الجزئية المشتركة بين الأسطر.
دوغلاس ماكلروي، بعدسة بيتر آدامز لمشروع Faces of Open Source. بنى هو وجيمس هانت عام 1976 برنامج diff في يونكس على أطول التتابعات الجزئية المشتركة بين الأسطر.

استكشفها بنفسك

افتح التطبيق واضغط «خطوة». يضيء الحرفان المقارنان في العناوين؛ عند التطابق تُقرأ الخلية الزرقاء أعلى اليسار، وعند الاختلاف تُقرأ الخليتان الزرقاوان فوقها وعلى يسارها. وعندما يمتلئ الجدول، يصعد المسار البرتقالي رجوعًا من الزاوية وتظهر حروف الإجابة تحت الجدول.

الأسئلة المتداولة

كم من الوقت والذاكرة تحتاج خوارزمية LCS؟

وقت O(m·n) لكلمتين طولاهما m وn. ويحتاج الجدول الكامل أيضًا إلى ذاكرة O(m·n) لقراءة الإجابة رجوعًا؛ وقد بيّن دان هيرشبرغ عام 1975 كيف تُوجد المتتالية الجزئية نفسها بذاكرة O(min(m, n)) فقط.

كيف يستخدم diff أطول متتالية جزئية مشتركة؟

يعامل كل سطر من الملف كرمز واحد، ويجد أطول متتالية جزئية مشتركة بين أسطر الملفين. الأسطر الموجودة في تلك المتتالية لم تتغير؛ أما بقية أسطر الملف القديم فقد حُذفت، وبقية أسطر الملف الجديد فقد أُضيفت.

وماذا عن ثلاث كلمات أو أكثر؟

يكتسب الجدول بُعدًا لكل كلمة، لذا تحتاج ثلاث كلمات طول كل منها n إلى n³ خلية. ومع عدد اعتباطي من الكلمات تصبح المسألة NP-صعبة.

ما علاقة LCS بمسافة التحرير؟

إذا سُمح بالإدراج والحذف فقط، فإن مسافة التحرير بين كلمتين تساوي مجموع طوليهما ناقص ضعف طول أطول متتالية جزئية مشتركة بينهما. وإذا سُمح بالاستبدال أيضًا نحصل على مسافة ليفنشتاين، التي تُحسب بجدول مشابه جدًا.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب أطول متتالية جزئية مشتركة