מרחק עריכה
שיעור 9 מתוך 15 בקורס תכנות דינמי 101 של Coddy.
מרחק עריכה, הידוע גם כמרחק לבנשטיין, הוא מדד המשמש למדידת ההבדל בין שתי מחרוזות. באופן ספציפי, זהו המספר המינימלי של פעולות הדרושות כדי להפוך מחרוזת אחת לאחרת.
הפעולות האפשריות הן:
- הוספה: הוספת תו לאחת המחרוזות
- מחיקה: מחיקת תו מאחת המחרוזות
- החלפה: החלפת תו באחת המחרוזות בתו אחר
מרחק עריכה נמצא בשימוש נרחב בתחומים כגון עיבוד שפה טבעית, ראייה ממוחשבת וביואינפורמטיקה.
אפשר להשתמש בתכנות דינמי כדי לחשב ביעילות את מרחק העריכה בין שתי מחרוזות.
אתגר
בינוניכתבו פונקציה ב-Python בשם edit_distance שמקבלת שתי מחרוזות ומחזירה את מרחק העריכה ביניהן.
לדוגמה:
edit_distance("kitten", "sitting")אמורה להחזיר 3edit_distance("intention", "execution")אמורה להחזיר 5
נסו בעצמכם
def edit_distance(str1, str2):
# כתבו כאן קודכל השיעורים ביחידה תכנות דינמי 101
תרגלו בעצמכם: קומפיילר Python אונליין