מרחק לוינשטיין

מרחק לוינשטיין (Левенштейн) הוא מונח במדעי המחשב ובתורת האינפורמציה שמתאר את כמות השינויים בין שתי מחרוזות תווים. את המונח טבע ולדימיר לוינשטיין ב-1965.

מרחק לוינשטיין בין שתי מחרוזות מוגדר כמספר המינימלי של פעולות עריכה שיש לבצע על מחרוזת אחת כדי להגיע למחרוזת השנייה, כאשר פעולות העריכה המותרות הן: הוספת אות, מחיקת אות, ושינוי אות לאות אחרת.

דוגמה

מרחק לוינשטיין בין "חיפנים" ל"חיפאיות" הינו 3.
חיפנים -> חיפאיות (החלפה של 'נ' ו'א')
חיפנים -> חיפאיות (הוספה של 'ו')
חיפנים -> חיפאיות (החלפה של 'ם' ו'ת')

ישומים

השוואה בין מחרוזות נדרשת, למשל, בחיפושים במילונים מתוך קלט שגוי "במקצת" לצורך בדיקת איות. לדוגמה אם מוגדר במילון המילה "חיפאיות", קלט המשתמש יהיה "חיפנים" והמרחק המרבי המוגדר הוא 3 אזי תוצאות החיפוש יראו גם את המילה "חיפאיות". ישומים נוספים שמשתמשים בוריאציות שונות של מרחק לוינשטיין הם זיהוי תווים אופטי, ועיבוד שפות טבעיות.

מימוש

מימוש יעיל של מציאת מרחק לוינשטיין דורש שימוש בטכניקת תכנות דינמי. סיבוכיות המקום וסיבוכיות הזמן במימוש הטרויאלי הוא (NM).

 int LevenshteinDistance(char s[1..m], char t[1..n])
 {
   // d is a table with m+1 rows and n+1 columns
   declare int d[0..m, 0..n]
  
   for i from 0 to m
     d[i, 0] := i // deletion
   for j from 0 to n
     d[0, j] := j // insertion
  
   for j from 1 to n
   {
     for i from 1 to m
     {
       if s[i] = t[j] then 
         d[i, j] := d[i-1, j-1]
       else
         d[i, j] := minimum
                    (
                      d[i-1, j] + 1,  // deletion
                      d[i, j-1] + 1,  // insertion
                      d[i-1, j-1] + 1 // substitution
                    )
     }
   }
  
   return d[m,n]
 }

דוגמת הרצה

		ח	י	פ	א	י	ם
	0	1	2	3	4	5	6
ח	1	0	1	2	3	4	5
י	2	1	0	1	2	3	4
פ	3	2	1	0	1	2	3
נ	4	3	2	1	1	2	3
י	5	4	3	2	2	1	2
ו	6	5	4	3	3	2	3
ת	7	6	5	4	4	3	3

ראו גם

מרחק המינג

קישורים חיצוניים

• מחשבון מרחק לוינשטיין