التتابع المشترك الأطول بين نصين: طول شاهد يحفظ الترتيب

الترتيب مطلوب والتجاور اختياري

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

يوضح NIST الفرق بين التتابع المشترك والمقطع المتصل، وتعرض محاضرة MIT طريقة الحالات والعلاقات واستعادة شاهد. ويبين دليل USACO نسخة جدول تعتمد على بادئتين من النصين. سنستعمل هذه الفكرة المعروفة في أمثلة مؤلفة برموز لاتينية واضحة، مع طول وفهارس وشاهد نراجعه، دون نقل أمثلة المصادر أو كودها أو صورها.

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

مرجع تعريف التتابع والمقطع، مرجع حالات البرمجة الديناميكية، مرجع علاقة البادئتين.

نصان من خمسة رموز وشاهد من أربعة

نختار النص الأول ACBDA، والثاني BACDA. نرقم مواضع كل نص من صفر إلى أربعة. في الأول توجد A ثم C ثم B ثم D ثم A، وفي الثاني B ثم A ثم C ثم D ثم A. نريد مقارنة الترتيب الأصلي، لا مجموعة الحروف دون مواقعها. اشتراك النصين في كثير من الرموز لا يعني إمكان أخذها كلها بالترتيب نفسه.

الشاهد ACDA يأخذ من الأول المواضع صفر وواحد وثلاثة وأربعة، ومن الثاني المواضع واحد واثنين وثلاثة وأربعة. نتجاوز B في الأول بين C و D، ونتجاوز B الأولى في الثاني قبل A. جميع المواضع في كل جانب متزايدة، والرموز في أزواجها متساوية. لذلك طول الشاهد أربعة، وقد تحققنا من وجوده فعلًا في النصين.

ولا يمكن أن يكون الطول خمسة في هذا المثال؛ لأن أخذ خمسة رموز من نص طوله خمسة يتطلب أخذ النص كاملًا. النصان مختلفان في ترتيبهما، فلا يمكن أن يتساوى التتابع الكامل ذو الخمسة فيهما. هذه مراجعة قصيرة تثبت الحد الأعلى للمثال، وتتفق مع طول الجدول الذي سنبنيه، ولا تعتمد على رؤية الشاهد في الرسم وحدها.

المقطع المتصل يعطي جوابًا آخر

المقطع المتصل لا يسمح بقفز موضع داخل الجزء المختار. في النصين المؤلفين يظهر AC متصلًا في كليهما، ويظهر DA أيضًا، وكل منهما بطول اثنين. أما ACDA فلا يظهر متصلًا في الأول، لأن B تدخل بين C و D فيه. هذا لا يفسد الشاهد الجزئي؛ إنه يوضح أن شرط التجاور يغير المسألة التي نجيب عنها.

يمكن مراجعة عدم وجود مقطع مشترك بطول ثلاثة من القوائم القصيرة. مقاطع الثلاثة في الأول هي ACB و CBD و BDA، وفي الثاني BAC و ACD و CDA. لا يتطابق أي واحد بين القائمتين. ولو وجد مقطع مشترك أطول من ثلاثة لتضمن مقطعًا مشتركًا من ثلاثة، لذلك أكبر طول متصل في مثالنا اثنان رغم أن التتابع الجزئي طوله أربعة.

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

معنى خانة البادئتين

نعرف L عند الصف i والعمود j بأنه طول أطول تتابع مشترك بين أول i رموز من النص الأول وأول j رموز من الثاني. الرمزان i و j يعدان طول البادئة، وليسا مباشرة فهارس آخر حرف. لذلك النصان ذوا الخمسة رموز يحتاجان ستة صفوف وستة أعمدة، مع حدود للبادئة الفارغة في كل جانب.

الصف صفر والعمود صفر أصفار، لأن النص الفارغ لا يحمل رمزًا نختاره ليشارك النص الآخر. خانة الصف واحد والعمود اثنين تقارن A من الأول مع BA من الثاني، وتعطي واحدًا. وخانة الصف اثنين والعمود ثلاثة تقارن AC مع BAC، وتعطي اثنين. هذان مثالان يربطان الرقم ببادئتين محددتين بدل قراءته طولًا محليًا عند حرف واحد.

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

المطابقة تمد القطر بواحد

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

في نهاية المثال، رمز A الأخير متساوٍ في النصين. الخانة السابقة عند أربعة وأربعة طولها ثلاثة، فتصبح خمسة وخمسة أربعة. وعند أربعة وأربعة تطابق D، فنقرأ ثلاثة وثلاثة التي تحمل اثنين ونضيف واحدًا إلى ثلاثة. هذه خطوات يراجعها الجدول، ثم نستعملها حين نعود من النهاية لاستعادة المواضع التي صنعت الطول.

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

الاختلاف يختار الأكبر لا مجموع الفرعين

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

عند الصف ثلاثة والعمود ثلاثة، تقارن البادئتان ACB و BAC. الرمزان الأخيران B و C مختلفان. الخانة فوقها عند اثنين وثلاثة تحمل اثنين، والخانة يسارها عند ثلاثة واثنين تحمل واحدًا، فنحفظ اثنين. الرجوع في هذه الحالة يتجاوز B من النص الأول، ويبقي إمكان أخذ AC بالترتيب من البادئتين المناسبتين.

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

الرجوع يجمع الشاهد من نهايته

نبدأ من الخانة خمسة وخمسة. نأخذ A الأخيرة من الطرفين ونعود إلى أربعة وأربعة، ثم نأخذ D ونعود إلى ثلاثة وثلاثة. هناك اختلف B من الأول عن C من الثاني، فننتقل إلى الخانة فوقها التي تحفظ الطول اثنين. صار موضعنا اثنين وثلاثة، حيث تتطابق C، فنأخذها ونعود إلى واحد واثنين.

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

نحفظ أزواج الفهارس مع الرمز، فلا نحتاج لاحقًا التخمين أي نسخة من A استعملها الرجوع. ليس كل انتقال في أثر الرجوع رمزًا جديدًا للشاهد؛ خطوة تجاوز B لم تزد طوله. لذلك عدد خطوات الأثر يمكن أن يتجاوز عدد المطابقات التي نعكسها، ونراجع الشاهد من قائمة أزواج الأخذ بدل عد جميع قراءات الرجوع.

عرض الرسم بالحجم الكامل

فهارس متزايدة في الجانبين

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

من الأزواج نعيد ACDA في الجانبين على حدة ونقارن النصين الناتجين، ثم نقارن طول الأربعة بالخانة النهائية. مراجعة الرموز وحدها قد تفوت شاهدًا يستعمل A واحدة مرتين، ومراجعة الفهارس وحدها قد تقبل رمزين مختلفين. نجمع الفحوص كي يرتبط الطول بشاهد حقيقي يحفظ عقد السؤال، لا بسلسلة نعرف أنها جميلة في المثال.

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

التعادل قد يغير الرمز المختار

نختار مثالًا ثانيًا: النص الأول AB والثاني BA. لا يوجد تتابع مشترك بطول اثنين لأن الترتيبين مختلفان، لكن A وحدها و B وحدها شاهدان بطول واحد. عند الخانة النهائية يختلف الرمزان، وتتساوى قيمة الأعلى وقيمة اليسار. لذلك توجد فرصة لاختيار أي من المسارين اللذين يحفظان الطول واحدًا.

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

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

الفارغ والتكرار والمساواة الحرفية

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

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

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

الفرز والتحرير يجيبان سؤالين آخرين

لو فرزنا رموز النصين ACBDA و BACDA، لحصلنا على الترتيب نفسه من A و A و B و C و D، ويمكن عندها أخذ خمسة رموز مشتركة. لكننا غيرنا ترتيب الأصل، فلا يثبت هذا تتابعًا من خمسة فيه كما قدمناه. لا نحتاج زيادة أبجدية في قيم الرموز؛ المطلوب ازدياد فهارس الاختيار في كل نص، ويمكن أن تنخفض أسماء الحروف أو تتكرر داخل الشاهد.

ومسافة التحرير تسأل عن أقل كلفة لتحويل نص إلى آخر بعمليات محددة، بينما LCS يعظم طول ما يبقى مشتركًا بالترتيب. مثال AB و AC له تتابع مشترك A بطول واحد. إذا سمحنا باستبدال B بحرف C بكلفة واحد، تكفي عملية واحدة للتحويل؛ وإذا منعنا الاستبدال واكتفينا بحذف ثم إدراج، يصبح المثال عمليتين. نوع العملية جزء من السؤال.

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

جدول من نسخة محددة ووحدات محددة

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

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

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

حجم الجدول وحفظ الشاهد

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

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

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

مرجع تعداد لا يستعمل العلاقة نفسها

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

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

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