مشكلة تصحيح السلاسل النصية

في علم الحاسوب ، تُشير مشكلة تصحيح السلاسل النصية إلى تحديد تسلسل عمليات التحرير الأقل تكلفة اللازمة لتغيير سلسلة نصية إلى أخرى (أي حساب أقصر مسافة تحرير ). لكل نوع من عمليات التحرير قيمة تكلفة خاصة به. ^{[ 1 ]} قد تكون عملية التحرير الواحدة تغيير رمز واحد من السلسلة إلى رمز آخر (التكلفة W_{_C} )، أو حذف رمز (التكلفة W_{_D} )، أو إدراج رمز جديد (التكلفة W_{_I} ). ^{[ 2 ]}

إذا كانت جميع عمليات التحرير لها نفس تكاليف الوحدة (W _C = W _D = W _I = 1) فإن المشكلة هي نفسها حساب مسافة ليفنشتاين لسلسلتين.

توجد العديد من الخوارزميات التي توفر طريقة فعالة لتحديد المسافة بين السلاسل النصية وتحديد الحد الأدنى لعدد عمليات التحويل المطلوبة. ^{[ 3 ] [ 4 ]} تُعد هذه الخوارزميات مفيدة بشكل خاص لعمليات إنشاء الفروقات ، حيث يتم تخزين البيانات كمجموعة من الفروقات نسبةً إلى نسخة أساسية. وهذا يسمح بتخزين عدة نسخ من كائن واحد بكفاءة أعلى بكثير من تخزينها بشكل منفصل. وينطبق هذا حتى على النسخ الفردية لعدة كائنات إذا لم تكن الفروقات بينها كبيرة، أو أي شيء بينهما. والجدير بالذكر أن خوارزميات الفروقات هذه تُستخدم في البيولوجيا الجزيئية لتوفير مقياس للقرابة بين أنواع مختلفة من الكائنات الحية بناءً على أوجه التشابه في جزيئاتها الكبيرة (مثل البروتينات أو الحمض النووي ).

يتضمن الشكل الموسع للمشكلة نوعًا جديدًا من عمليات التحرير: تبديل أي رمزين متجاورين، بتكلفة W _S .

يمكن حل هذه النسخة في وقت متعدد الحدود في ظل قيود معينة على تكاليف عمليات التحرير. ^{[ 2 ] [ 5 ]}

أثبت روبرت أ. فاغنر (1975) أن المسألة العامة هي مسألة NP-كاملة . وعلى وجه الخصوص، أثبت أنه عندما يكون W _I < W _C = W _D = ∞ و 0 < W _S < ∞ (أو بصورة مكافئة، لا يُسمح بالتغيير أو الحذف)، فإن المسألة تكون مسألة NP-كاملة. ^{[ 5 ]}