הצגת המקור של הדף "מרחק לוינשטיין"

'''מרחק לוינשטיין''' (ב[[רוסית]]: Левенштейн; מכונה גם '''מרחק עריכה''') הוא מונח ב[[מדעי המחשב]] וב[[תורת האינפורמציה]] שמתאר את מידת השונות בין שתי [[מחרוזת (מדעי המחשב)|מחרוזות תווים]]. את המונח טבע [[ולדימיר לוינשטיין]]{{אנ|Vladimir Levenshtein}} ב-[[1965]].

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

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

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

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

<div style="direction: ltr;">
  '''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]
  '''}'''

</div>

==דוגמת הרצה==
<div style="text-align: center;">
<div style="direction: ltr;">
{|class="wikitable"
| 
| 
!ח 
!י
!פ
!א 
!י 
!ם
|-
| ||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'''
|}

</div>
</div>

==ראו גם==
[[מרחק המינג]]

==קישורים חיצוניים==
* [http://planetcalc.com/1721/ מחשבון מרחק לוינשטיין]

[[קטגוריה:תורת האינפורמציה]]