ما هي مسافة Levenshtein؟ شرح Edit Distance باستخدام Dynamic Programming

تُعرف Levenshtein Distance أيضاً باسم Edit Distance، وهي تقيس مدى اختلاف سلسلتين عن طريق حساب الحد الأدنى من العمليات اللازمة لتحويل إحداهما إلى الأخرى.

العمليات الأساسية هي:

• Insert
• Delete
• Replace

وتكون تكلفة كل عملية عادة 1.

مثال:

cat → cut

نحتاج فقط إلى استبدال a بـ u، ولذلك:

Distance = 1

مثال مشهور

kitten
sitting

يمكن التحويل عبر ثلاث عمليات:

kitten → sitten
sitten → sittin
sittin → sitting

إذن:

Distance = 3

لماذا نستخدم Dynamic Programming؟

نعرّف:

dp[i][j]

ليكون الحد الأدنى من العمليات اللازمة لتحويل أول i أحرف من السلسلة الأولى إلى أول j أحرف من السلسلة الثانية.

إذا كانت إحدى السلسلتين فارغة:

dp[0][j] = j
dp[i][0] = i

إذا كان الحرفان الحاليان متساويين:

dp[i][j] = dp[i - 1][j - 1]

أما عند الاختلاف:

dp[i][j] = 1 + min(
  dp[i - 1][j],
  dp[i][j - 1],
  dp[i - 1][j - 1]
)

وتمثل الحالات Delete وInsert وReplace.

تنفيذ TypeScript

function levenshteinDistance(a: string, b: string): number {
  const dp = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  for (let i = 0; i <= a.length; i++) {
    dp[i][0] = i;
  }

  for (let j = 0; j <= b.length; j++) {
    dp[0][j] = j;
  }

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],
          dp[i][j - 1],
          dp[i - 1][j - 1]
        );
      }
    }
  }

  return dp[a.length][b.length];
}

التعقيد

إذا كان طول السلسلتين n وm:

Time Complexity: O(n × m)
Space Complexity: O(n × m)

ويمكن تقليل الذاكرة إلى:

O(min(n, m))

إذا احتفظنا فقط بالصف الحالي والسابق.

Spell Checking

إذا كتب المستخدم:

programing

يمكن مقارنة الكلمة مع كلمات القاموس. المسافة إلى:

programming

هي 1 فقط، ولذلك تعد اقتراحاً جيداً.

Fuzzy Search

إذا كانت القيمة المخزنة:

Alexander

والبحث:

Alexnder

يمكن لـ Edit Distance اكتشاف أن السلسلتين متقاربتان جداً رغم عدم وجود Exact Match.

CRM وDeduplication

في CRM قد نجد:

Arian Soleimanzadeh
Arian Soleimanzade

المسافة الصغيرة قد تكون إشارة إلى وجود Duplicate Record.

لكن الأنظمة الحقيقية يجب أن تستخدم أيضاً البريد الإلكتروني ورقم الهاتف ومعرفات أخرى قبل دمج السجلات.

استخدامات أخرى

تظهر Levenshtein Distance في:

• Spell Checking
• Fuzzy Search
• OCR Correction
• NLP
• Data Cleaning
• Record Matching
• Bioinformatics

الفرق عن Hamming Distance

Hamming Distance تقارن المواضع المتناظرة فقط وتتطلب عادة طولاً متساوياً.

أما Levenshtein فتسمح بالإضافة والحذف.

لذلك:

cat → cats

له Levenshtein Distance تساوي 1.

Weighted Edit Distance

يمكن أيضاً إعطاء تكاليف مختلفة للعمليات.

مثلاً:

Insert = 1
Delete = 1
Replace = 2

وهذا مفيد عندما لا تكون جميع الأخطاء متساوية الأهمية.

سؤال مقابلات شائع

من أشهر مسائل Dynamic Programming:

احسب أقل عدد من Insert وDelete وReplace لتحويل word1 إلى word2.

مثلاً:

horse → ros

والإجابة 3.

أخطاء شائعة

يجب الانتباه إلى أن صف وعمود الصفر يمثلان السلسلة الفارغة، ولذلك نستخدم عادة:

a[i - 1]
b[j - 1]

كما يجب عدم إضافة تكلفة عندما يكون الحرفان متساويين.

الخلاصة

Levenshtein Distance تقيس أقل عدد من عمليات Insert وDelete وReplace اللازمة لتحويل سلسلة إلى أخرى.

وهي مثال كلاسيكي على Dynamic Programming بتعقيد:

Time: O(n × m)
Space: O(n × m)

وتُستخدم عملياً في البحث التقريبي، وتصحيح الإملاء، وتنظيف البيانات، وإزالة التكرار، وNLP وOCR.