آخر تحديث: 2026-07-01

مسافة ليفنشتاين

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

عمليات التحرير الثلاث

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

سُميت المسافة باسم فلاديمير ليفنشتاين الذي عرّفها عام 1965، وهي تعميم لمسافة حاسبة مسافة هامينغ الأقدم: إذ تسمح مسافة هامينغ بالاستبدال فقط، وللسلاسل المتساوية الطول فحسب، بينما تسمح مسافة ليفنشتاين أيضًا بالإدراج والحذف، فتعالج السلاسل المختلفة الأطوال.

جدول البرمجة الديناميكية

تُحسب المسافة بملء جدول $D$ يحتوي على صف لكل محرف من السلسلة الأولى (مع صف فارغ في المقدمة) وعمود لكل محرف من السلسلة الثانية (مع عمود فارغ في المقدمة). تحمل الخلية $D[i][j]$ مسافة التحرير بين أول $i$ محرفًا من A وأول $j$ محرفًا من B.

يَعُدّ الصف الأول والعمود الأول عمليات التحرير مقابل السلسلة الفارغة، فيكون $D[i][0] = i$ و$D[0][j] = j$. أما كل خلية أخرى فهي أصغر ثلاثة مرشحين:

حيث تكلفة الاستبدال $c$ تساوي 0 عند تطابق المحرفين و1 عند اختلافهما. ويوجد الجواب في الخلية السفلية اليمنى. ويستغرق ملء الجدول زمنًا يتناسب مع حاصل ضرب الطولين، $m \times n$.

مثال محلول

لنأخذ الزوج الكلاسيكي «kitten» و«sitting». تتبُّع المسار الأمثل عبر الجدول يعطي ثلاث عمليات تحرير:

لا يوجد تتابع أقصر، فالمسافة إذن 3. وللسلسلة الأطول 7 محارف، ومن ثَمّ يكون التشابه $1 - 3/7 \approx 0{.}571$، أي نحو 57%.

التشابه وحدوده

تُطبِّع الحاسبة المسافة الخام إلى درجة تشابه عبر العلاقة

$S = 1 - \dfrac{d_L}{\max(m, n)}$

والقسمة على طول السلسلة الأطول تُبقي النتيجة بين 0% للسلاسل المختلفة تمامًا و100% للمتطابقة؛ وتُعَدّ السلسلتان الفارغتان متطابقتين. وهذه إحدى طرق التطبيع الشائعة — إذ تقسم أدوات أخرى على مجموع الطولين أو تستخدم مقاييس قائمة على النسب — لذا لا يمكن مقارنة أرقام التشابه من مصادر مختلفة مباشرةً.

أين تُستخدم

تُرتِّب أدوات التدقيق الإملائي التصحيحات المقترحة بحسب مسافة التحرير عن الكلمة المكتوبة خطأً. وتستخدمها أنظمة البحث وقواعد البيانات في المطابقة التقريبية، فتتسامح مع الأخطاء المطبعية عند البحث عن الأسماء أو العناوين. وفي المعلوماتية الحيوية، تقوم مسافة التحرير عليها محاذاة المتتاليات لمقارنة الحمض النووي DNA والـRNA والبروتينات، حيث تقابل عمليات الإدراج والحذف الطفراتِ. ويعامل نموذج تكلفة ليفنشتاين البسيط جميع عمليات التحرير بالتساوي؛ أما التطبيقات التي تحتاج إلى عقوبات مختلفة لعمليات مختلفة، أو يجب أن تحاذي متتاليات طويلة جدًا بكفاءة، فتوسّعه بتكاليف موزونة أو خوارزميات محاذاة متخصصة.