Edit Distance
ניתנות לך שתי מילים, word1 ו־word2. עריכה אחת משנה את word1 באחת משלוש דרכים: הוספת אות בכל מקום, מחיקת אות או החלפת אות באות אחרת. החזר את מספר העריכות הקטן ביותר שיהפוך את word1 ל־word2.
פונקציה
- word1string
- המילה שאתה עורך
- word2string
- המילה להגיע
- מחזירהinteger
- המספר הקטן ביותר של הוספות, מחיקות והחלפות שנדרשות כדי להפוך את word1 ל־word2
אילוצים
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- שתי המילים מכילות רק אותיות קטנות באנגלית.
דוגמאות
- קלט
- word1 = "spot"word2 = "stop"
- פלט
- 2
- הסבר
- החלף את p ב-t ואת t ב-p:
spotהופכת ל-stot, ואז ל-stop. עריכה אחת אינה מספיקה, כי המילים שונות בשני מקומות, והוספה או מחיקה ישנו את האורך.
- קלט
- word1 = "garden"word2 = "ardent"
- פלט
- 2
- הסבר
- מחקו את g כדי לקבל
arden, ואז הוסיפו t בסוף כדי לקבלardent. החלפה של אות אחר אות הייתה עולה 6, כי שתי המילים שונות בכל מיקום.
- קלט
- word1 = "rain"word2 = "shine"
- פלט
- 3
- הסבר
- החליפו את r ב־s ואת a ב־h, ואז הוסיפו e. שני שינויים נכשלים: r ו־a אינם מופיעים ב־
shine, ולכן כל אחד מהם דורש שינוי ששומר על האורך, והמילה עדיין צריכה להתארך באות אחת.
שאלת המשך
האם תוכל גם להחזיר את רשימת העריכות הקצרה ביותר, מלבד מספרן?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התבוננו באות האחרונה של כל מילה. אם הן זהות, האם צריך לגעת בהן? אם הן שונות, אילו עריכות יכולות לגרום לשתי המילים להסתיים באותה צורה?
יש שלוש אפשרויות לאותיות האחרונות השונות: להחליף אחת באחרת, למחוק את האות האחרונה של
word1, או להוסיף את האות האחרונה שלword2. כל אפשרות משאירה את אותה הבעיה עבור תחיליות קצרות יותר, לכן בוחרים באפשרות הזולה ביותר ומוסיפים אחת.שמרו את התשובה עבור כל זוג של אורכי קידומות
(i, j)בטבלה. קידומת ריקה עולהiמחיקות אוjהוספות, וכך מתמלאים השורה והעמודה הראשונות. מלאו את שאר הטבלה שורה אחר שורה וקראו את התשובה מהתא האחרון.
פתרון
פעולות עריכה משפיעות זו על זו: garden ו־ardent שונות בכל ששת המיקומים, ובכל זאת די בשתי פעולות עריכה. לכן נבחן את האות האחרונה של כל מילה. או שהן זהות, או שאחת משלוש פעולות העריכה גורמת להן להיות זהות, וכל אחת מהאפשרויות משאירה את אותה בעיה בקידומות קצרות יותר. טבלה פותרת פעם אחת כל זוג קידומות.
נסה את כל שלושת השינויים באמצעות רקורסיה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
נסמן edits(i, j) כמספר העריכות הקטן ביותר שהופכות את הסיומת word1[i:] לסיומת word2[j:]. אם האותיות הראשונות זהות, נשאיר אותן ונקדם את שני האינדקסים: ביצוע עריכה על אות זהה לעולם לא מועיל. אחרת, ניקח 1 ועוד הזולה מבין שלוש הקריאות: החלפה מקדמת את שני האינדקסים, מחיקה של word1[i] מקדמת את i, והוספה של word2[j] מקדמת את j. כשנגמרת אחת המילים, כל אות שנותרה במילה השנייה עולה עריכה אחת.
כל אי־התאמה מתחילה שלוש קריאות: שתי מילים בנות 15 אותיות שאין להן אף אות משותפת דורשות בערך 6.7 × 10^10 קריאות. ובכל זאת, יש רק (n+1) × (m+1) זוגות שונים (i, j), כך שכמעט כל קריאה חוזרת על קריאה קודמת.
אלגוריתם
- אם
iנמצא אחרי סוףword1, החזר אתm - j; אםjנמצא אחרי סוףword2, החזר אתn - i. - אם
word1[i] == word2[j], החזר אתedits(i+1, j+1). - אחרת, החזר את
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)). - התשובה היא
edits(0, 0).
def minDistance(word1, word2):
n, m = len(word1), len(word2)
def edits(i, j):
# Fewest edits to turn word1[i:] into word2[j:]
if i == n:
return m - j # insert the rest of word2
if j == m:
return n - i # delete the rest of word1
if word1[i] == word2[j]:
return edits(i + 1, j + 1)
return 1 + min(edits(i + 1, j + 1), # replace word1[i] with word2[j]
edits(i + 1, j), # delete word1[i]
edits(i, j + 1)) # insert word2[j]
return edits(0, 0)מלא טבלת קידומות
האינטואיציה
יהי dp[i][j] מספר העריכות הקטן ביותר הנדרש כדי להפוך את i האותיות הראשונות של word1 ל־j האותיות הראשונות של word2. אם word1[i-1] שווה ל־word2[j-1], מעתיקים את הערך האלכסוני dp[i-1][j-1]. אחרת מוסיפים 1 לשכן הזול ביותר: הערך האלכסוני מייצג החלפה, התא שמעל מייצג מחיקה של word1[i-1], והתא שמשמאל מייצג הוספה של word2[j-1]. השורה והעמודה הראשונות אינן אפסים: הפיכת i אותיות לכלום דורשת i מחיקות, ולכן dp[i][0] = i, ובדומה לכך dp[0][j] = j.
עבור הפיכת spot ל־stop, השורה האחרונה היא [4, 3, 2, 2, 2]. התא האחרון משווה בין t ל־p; הערך האלכסוני שלו (הפיכת spo ל־sto) הוא 1, ושני השכנים האחרים הם 2, לכן התשובה היא 1 + 1 = 2. שתי מילים בנות 500 אותיות ממלאות 2.5 × 10^5 תאים, כשכל אחד מהם מחושב בזמן קבוע.
אלגוריתם
- צרו את
dpעם(n+1) × (m+1)תאים, כאשרdp[i][0] = iו-dp[0][j] = j. - עבור
iמ-1 עדnועבורjמ-1 עדm: אםword1[i-1] == word2[j-1], קבעוdp[i][j] = dp[i-1][j-1]. - אחרת, קבעו
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). - החזירו את
dp[n][m].
def minDistance(word1, word2):
n, m = len(word1), len(word2)
# dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # delete all i letters
for j in range(m + 1):
dp[0][j] = j # insert all j letters
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete word1[i-1]
dp[i][j - 1]) # insert word2[j-1]
return dp[n][m]השאר רק שתי שורות
האינטואיציה
שורה i קוראת רק את שורה i-1 ואת התאים שמשמאל לה באותה שורה, ולכן מספיקים שני מערכים: prev עבור השורה שהושלמה ו-cur עבור השורה שממלאים. האלכסון הוא prev[j-1], התא שמעל הוא prev[j] והתא שמשמאל הוא cur[j-1]. עמודת הבסיס נמצאת כעת באיבר הראשון של כל שורה, לכן יש להגדיר את cur[0] = i לפני מילוי שורה i.
המרת word2 ל-word1 דורשת אותו מספר של עריכות, מכיוון שהוספות ומחיקות מחליפות תפקידים. החליפו בין המילים כך שהשורות ירוצו לאורך המילה הקצרה יותר: min(n, m) + 1 מספרים בכל שורה במקום טבלה של עד 251,001 תאים, עם אותה כמות עבודה של O(n × m).
אלגוריתם
- אם
word2ארוכה יותר מ־word1, החליפו ביניהן. - הגדירו
prev = [0, 1, ..., m]. - עבור כל
iמ־1 עדn, הגדירוcur[0] = iומלאו אתcur[1..m]לפי כלל הטבלה, תוך קריאת האלכסון והתא שמעליו מתוךprev, ואת התא שמשמאל מתוךcur. לאחר מכן החליפו ביןprevל־cur. - החזירו את
prev[m].
def minDistance(word1, word2):
if len(word2) > len(word1):
word1, word2 = word2, word1 # the rows run along the shorter word
m = len(word2)
# prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
prev = list(range(m + 1))
for i in range(1, len(word1) + 1):
cur = [i] + [0] * m # i letters into an empty prefix: delete them all
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete word1[i-1]
cur[j - 1]) # insert word2[j-1]
prev = cur
return prev[m]
מלכודות ומקרי קצה
- מילוי שורה 0 ועמודה 0 באפסים, כמו בתת־רצף המשותף הארוך ביותר. הפיכת
abcלקידומת ריקה עולה 3 מחיקות, לא 0. - שכחת
cur[0] = iבגרסה של שתי השורות. הערך שבכניסה הראשונה נשאר מהשורה שלפני הקודמת, ולכן כל התאים שאחריה שגויים. - תשלום על עריכה כשיש התאמה. עם
1 + min(...)עבור אותיות זהות, הפיכתaל־aעולה 1. - קריאת השכן משמאל מתוך
prevבמקום מתוךcur. השכן משמאל מייצג את ההכנסה שלword2[j-1]בשורה הנוכחית. - רקורסיה עם שינון ב-Python עבור מילים באורך 500 אותיות. עומק הקריאות מגיע עד 1000, מעבר למגבלת הרקורסיה כברירת מחדל.
שאלות נפוצות3
מהי סיבוכיות הזמן של מרחק עריכה?
פתרון הטבלה ממלא תא אחד לכל זוג קידומות בזמן קבוע: זמן O(n × m) עבור אורכים n ו־m. הוא משתמש בזיכרון O(n × m) עבור הטבלה המלאה, או ב־O(min(n, m)) עם שתי שורות. רקורסיה רגילה ללא טבלה היא אקספוננציאלית.
האם מרחק עריכה זהה למרחק לוונשטיין?
זו גרסת מרחק לוונשטיין: להוספה, למחיקה ולהחלפה יש עלות של אחת. מרחק עריכה הוא שם המשפחה. הוספות ומחיקות בלבד נותנות n + m - 2 × LCS, החלפות בלבד כאשר האורכים שווים נותנות את מרחק המינג, והוספת החלפה בין שתי אותיות סמוכות נותנת את גרסת דמרו.
האם אפשר לפתור את מרחק העריכה בעזרת מערך יחיד?
כן. מלא מערך אחד row במקום, משמאל לימין. לפני שכותבים מעל row[j], עדיין נמצא בו הערך מהשורה שמעל, ו-row[j-1] כבר מכיל את השורה הנוכחית. רק הערך האלכסוני הולך לאיבוד, לכן שמור את row[j] הישן במשתנה והשתמש בו כערך האלכסוני עבור j + 1.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def minDistance(word1, word2):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
word1 = "spot" word2 = "stop"
הפלט הצפוי
2