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

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

ראו גםעריכה

מרחק המינג

קישורים חיצונייםעריכה