مسافة ليفنشتاين (Levenshtein Distance): شرح مبسّط مع مثال وطريقة الحساب

مسافة ليفنشتاين (Levenshtein Distance) هي رقم يخبرك بمدى اختلاف نصّين عن بعضهما: إنه أقل عدد من التعديلات التي تحتاجها لتحويل كلمة أو سلسلة نصية إلى أخرى. كل تعديل هو إما إضافة حرف أو حذف حرف أو استبدال حرف بآخر، وتكلفة كل عملية واحدة. كلما صغُر الرقم كان النصّان أقرب، وإذا كان صفرًا فالنصّان متطابقان تمامًا. تُسمّى أيضًا "مسافة التحرير" (Edit Distance)، وهي حجر الأساس خلف تصحيح الأخطاء الإملائية واقتراحات البحث "هل تقصد؟".

العمليات الثلاث التي تُبنى عليها المسافة

المسافة تحسب أقصر طريق من النص الأول إلى الثاني باستخدام ثلاث عمليات فقط، كلٌّ منها بتكلفة 1:

1. الإدراج (Insertion): إضافة حرف غير موجود. مثال: من "قط" إلى "قطة" نُدرج حرف "ة" فقط، فالمسافة = 1.
2. الحذف (Deletion): إزالة حرف زائد. مثال: من "كتاب" إلى "كتب" نحذف "ا"، فالمسافة = 1.
3. الاستبدال (Substitution): تبديل حرف بحرف آخر في نفس الموضع. مثال: من "نار" إلى "دار" نستبدل "ن" بـ"د"، فالمسافة = 1.

النقطة المهمة: الخوارزمية لا تجرّب طريقة واحدة، بل تبحث عن أقلّ تسلسل ممكن من هذه العمليات، ثم تُرجع عدده.

مثال عملي خطوة بخطوة

لنأخذ المثال الكلاسيكي بالإنجليزية لأنه واضح: تحويل kitten إلى sitting.

• استبدال k بـ s ← تصبح sitten (عملية 1)
• استبدال e بـ i ← تصبح sittin (عملية 2)
• إدراج g في النهاية ← تصبح sitting (عملية 3)

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

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

كيف تُحسب فعليًا؟ فكرة المصفوفة

يُحسب المقياس عبر البرمجة الديناميكية باستخدام جدول ثنائي الأبعاد. إذا كان طول النص الأول m والثاني n، ننشئ جدولًا بحجم ‎(m+1) × (n+1)‎:

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

هذا الأسلوب يمنع إعادة حساب الأجزاء المتكررة، لذا يعمل بتعقيد زمني قدره ‎O(m×n)‎ — أي أنه سريع للكلمات القصيرة، لكنه يصبح مكلفًا مع النصوص الطويلة جدًا، وهنا يلجأ المطوّرون إلى نسخ مُحسَّنة أو مكتبات جاهزة مثل python-Levenshtein أو RapidFuzz.

أين تُستخدم مسافة ليفنشتاين؟

• التدقيق الإملائي والاقتراحات: عند كتابة كلمة خاطئة، يبحث المحرّر عن الكلمات الأقرب في القاموس (أصغر مسافة) ويقترحها.
• محركات البحث والمطابقة التقريبية (Fuzzy Search): إظهار نتائج قريبة حتى لو أخطأ المستخدم في حرف أو اثنين.
• إزالة التكرار في البيانات: كشف السجلات المكرّرة التي كُتبت بصيغ مختلفة قليلًا ("محمد أحمد" مقابل "محمّد احمد").
• علم الأحياء الحسابي: مقارنة تسلسلات الحمض النووي والبروتينات لقياس التشابه.
• التعرّف على النص والصوت (OCR/ASR): مطابقة المُخرَجات مع الكلمات المعروفة لتصحيح أقرب احتمال.

مقارنة بين مقاييس التشابه النصي

مسافة ليفنشتاين ليست الخيار الوحيد؛ ولكل مقياس حالته الأنسب:

المقياس	العمليات المسموحة	الأنسب لـ
ليفنشتاين	إدراج، حذف، استبدال	تصحيح إملائي ومطابقة عامة
هامينغ (Hamming)	استبدال فقط	سلاسل بنفس الطول (مثل رموز الأخطاء)
داميرو‑ليفنشتاين	+ تبديل حرفين متجاورين	أخطاء الطباعة الشائعة ("teh" ← "the")
جارو‑وينكلر	تشابه نسبي بلا عمليات	مطابقة الأسماء القصيرة

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

نصيحة عملية قبل الحساب

قبل تطبيق المقياس على نصوص حقيقية، وحّد صيغة النص أولًا (Normalization): حوّل الأحرف إلى حالة واحدة، أزِل التشكيل والمسافات الزائدة، ووحّد أشكال الهمزات والألف في العربية ("أ/إ/ا"). بدون هذه الخطوة قد تحصل على مسافة كبيرة بين كلمتين متطابقتين فعليًا لمجرد اختلاف بسيط في التنسيق — وهو خطأ يُفسد نتائج المطابقة كثيرًا في التطبيقات العربية تحديدًا.

الأسئلة الشائعة

هل مسافة ليفنشتاين مقياس رياضي حقيقي؟ نعم. تحقّق شروط "المسافة المترية": لا تكون سالبة، وتساوي صفرًا فقط عند تطابق النصّين، وهي متماثلة (المسافة من A إلى B مثل B إلى A)، وتحقّق متباينة المثلث.

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

هل يمكن أن تكون تكلفة العمليات مختلفة؟ نعم، في النسخة الموزونة (Weighted) يمكن إعطاء الاستبدال تكلفة أعلى من الإدراج مثلًا، وهو مفيد حين تكون بعض الأخطاء أكثر خطورة من غيرها.

هل هي سريعة بما يكفي للنصوص الطويلة؟ تعقيدها ‎O(m×n)‎، ما يعني بطئًا ملحوظًا مع النصوص الطويلة. للحالات الكبيرة استخدم مكتبات محسّنة أو خوارزميات تقريبية بدل التنفيذ اليدوي.