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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

ראו גם[עריכת קוד מקור | עריכה]

מרחק המינג

קישורים חיצוניים[עריכת קוד מקור | עריכה]