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

מרחק לוינשטיין (ברוסית: Левенштейн; מכונה גם מרחק עריכה) הוא מונח במדעי המחשב ובתורת האינפורמציה שמתאר את מידת השונות בין שתי מחרוזות תווים. את המונח טבע ולדימיר לוינשטיין ב-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	2
ת	7	6	5	4	4	3	3

ראו גם

מרחק המינג

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

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