تُعرف 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.