Edit Distance

Q: מהי סיבוכיות הזמן של מרחק עריכה?

פתרון הטבלה פועל בזמן O(n × m) , כאשר n ו- m הם שני האורכים, כי הוא ממלא תא אחד לכל זוג של קידומות בעבודה קבועה. הוא משתמש בזיכרון של O(n × m) עבור הטבלה המלאה, או בזיכרון של O(min(n, m)) עם שתי שורות. רקורסיה פשוטה ללא טבלה היא מעריכית.

Q: איך מקבלים את רשימת העריכות, ולא רק את מספרן?

שמרו את הטבלה המלאה וחזרו לאחור מ־ dp[n][m] . אם האותיות תואמות, עברו באלכסון ללא עריכה. אחרת, עברו לשכן שערכו קטן באחד: באלכסון מדובר בהחלפה, למעלה במחיקה, שמאלה בהוספה. עצרו ב־ dp[0][0] וקראו את העריכות בסדר הפוך. גרסת שתי השורות אינה יכולה לעשות זאת לבדה, משום שהיא השליכה את השורות הקודמות.

Q: האם אפשר לפתור את מרחק העריכה באמצעות מערך יחיד?

כן. מלאו מערך אחד row במקום, משמאל לימין. לפני שאתם דורכים על row[j] , עדיין נמצא בו הערך מהשורה שמעל, וב- row[j-1] כבר נמצא הערך של השורה הנוכחית. הערך היחיד שאתם מאבדים הוא הערך האלכסוני, לכן שמרו אותו במשתנה: שמרו את הערך הישן של row[j] לפני הכתיבה, והשתמשו בו כערך האלכסוני עבור j + 1 .

קשהתכנון דינמי

+10

מקבלים שתי מילים, word1 ו־word2. עריכה אחת משנה את word1 באחת משלוש דרכים: הוספת אות בכל מקום, מחיקת אות או החלפת אות באות אחרת. החזירו את מספר העריכות הקטן ביותר שיהפוך את word1 ל־word2.

פונקציה

minDistance(word1: string, word2: string) → integer

word1string: המילה שאתה עורך
word2string: המילה להגיע
מחזירהinteger: מספר ההוספות, המחיקות וההחלפות הקטן ביותר שהופך את word1 ל-word2

אילוצים

1 ≤ word1.length ≤ 500
1 ≤ 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 כדי לקבל shin, ואז הוסיפו e. אי אפשר לעשות זאת בשתי עריכות: r ו־a לא מופיעות ב־shine, ולכן כל אחת מהן דורשת עריכה שלא מאריכה את המילה, ועדיין צריך להוסיף למילה אות אחת.

+21 בדיקות נסתרות בשליחה

שאלת המשך

האם תוכל גם להחזיר רשימה קצרה ביותר של העריכות, ולא רק לציין כמה יש?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

העריכות משפיעות זו על זו, ולכן אי אפשר לתקן את האותיות מיקום אחר מיקום: garden ו־ardent שונות בכל ששת המיקומים, ובכל זאת מספיקות שתי עריכות לאחר שמוחקים את g והכול זז שמאלה. הרעיון שפותר זאת הוא להתבונן רק באות האחרונה של כל מילה. או ששתי האותיות כבר זהות, או שאחת משלוש עריכות אפשריות גורמת להן להיות זהות, וכל אחת מהבחירות משאירה את אותה הבעיה בקידומות קצרות יותר. טבלה של תשובות (n+1) × (m+1) פותרת את כל זוגות הקידומות בבת אחת, ושתי שורות שלה מספיקות.

נסו את שלושת העריכות בעזרת רקורסיה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

נניח ש־edits(i, j) הוא מספר העריכות הקטן ביותר שנדרש כדי להפוך את הסיומת word1[i:] לסיומת word2[j:]. נבחן את האותיות הראשונות של שתי הסיומות. אם הן שוות, נשאיר אותן ונקדם את שני האינדקסים: אף פעם אין צורך לערוך אות תואמת, וכל תוכנית שמבצעת בה עריכה יכולה להשתנות לתוכנית שמשאירה אותה ללא תוספת עריכות.

אם הן שונות, עריכה כלשהי צריכה לטפל ב־word1[i] או ליצור את word2[j], ויש בדיוק שלוש דרכים לעשות זאת. להחליף את word1[i] ב־word2[j], ולקדם את שני האינדקסים: edits(i+1, j+1). למחוק את word1[i], ולקדם רק את i: edits(i+1, j). להוסיף את word2[j] לפניו, ולקדם רק את j: edits(i, j+1). התשובה היא 1 ועוד הזולה מבין שלוש האפשרויות. כשנגמרת word1, מוסיפים את שארית word2, בעלות של m - j; כשנגמרת word2, מוחקים את שארית word1, בעלות של n - i.

הפעולה איטית כי בכל אי־התאמה מתחילות שלוש קריאות. עבור שתי מילים בנות 15 אותיות שאין להן אף אות משותפת, מדובר בכ־6.7 × 10^10 קריאות, ובבדיקות הגדולות יש 500 אותיות בכל מילה. עם זאת, יש רק (n+1) × (m+1) זוגות שונים של (i, j), ולכן כמעט כל קריאה חוזרת על קריאה שכבר בוצעה.

אלגוריתם

כתבו edits(i, j) עבור הסיומות שמתחילות ב-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. אינדקס 0 מייצג תחילית ריקה.

מעברים. השוו בין האותיות האחרונות של שתי התחיליות, word1[i-1] ו־word2[j-1]. אם הן שוות, משאירים אותן: dp[i][j] = dp[i-1][j-1], התא שנמצא באלכסון למעלה ומשמאל. אם לא, משלמים עריכה אחת ובוחרים את הזול ביותר מבין שלושת התאים השכנים. התא האלכסוני dp[i-1][j-1] פירושו להחליף את word1[i-1] ב־word2[j-1]. התא שמעליו, dp[i-1][j], פירושו למחוק את word1[i-1]. התא שמשמאלו, dp[i][j-1], פירושו להוסיף את word2[j-1] בסוף.

השורה והעמודה הבסיסיות. בשונה מבעיות טבלה רבות, הערכים בהן אינם אפסים. הפיכת i אותיות לתחילית ריקה דורשת i מחיקות, ולכן dp[i][0] = i. בניית j אותיות מכלום דורשת j הוספות, ולכן dp[0][j] = j. כל תא קורא את התא שמעליו, את התא שמשמאלו ואת התא האלכסוני, ולכן מילוי שורה אחר שורה, משמאל לימין, מבטיח שהם כבר יהיו מוכנים. התשובה היא dp[n][m].

הנה הטבלה עבור הפיכת spot ל־stop, עם עמודות עבור התחיליות "", s, st, sto, stop. השורה "" היא [0, 1, 2, 3, 4], השורה s היא [1, 0, 1, 2, 3], השורה sp היא [2, 1, 1, 2, 2], השורה spo היא [3, 2, 2, 1, 2], והשורה spot היא [4, 3, 2, 2, 2]. נבחן כמה תאים. s מול s תואמות, ולכן מעתיקים את הערך האלכסוני 0. sp מול st אינן תואמות: השכנים שלהן הם 0 באלכסון, 1 מעל ו־1 משמאל, ולכן הערך הוא 1 + 0 = 1, החלפה אחת. spo מול sto תואמות באות o, ומעתיקים את הערך 1 מהתא האלכסוני. התא האחרון, spot מול stop, משווה בין t ל־p: ערכי השכנים הם 1, 2 ו־2, ולכן התשובה היא 1 + 1 = 2.

בטבלה יש (n+1) × (m+1) תאים, עם עבודה בזמן קבוע לכל אחד, כלומר בערך 2.5 × 10^5 צעדים עבור שתי מילים בנות 500 אותיות. רקורסיה עם שמירה במטמון ממלאת את אותם התאים, אבל עומק הרקורסיה יכול להגיע ל־n + m קריאות, מעבר למגבלת ברירת המחדל של Python, שהיא 1000.

אלגוריתם

צרו טבלה dp עם (n+1) × (m+1) תאים.
הגדירו dp[i][0] = i עבור כל i ואת dp[0][j] = 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. שורה 0 מתחילה בתור [0, 1, 2, ..., m], שורת הבסיס.

המרת word2 ל-word1 דורשת אותו מספר עריכות, כי כל הוספה הופכת למחיקה וכל מחיקה להוספה. לכן אפשר להחליף בין המילים ולתת לשורות להתקדם לאורך המילה הקצרה יותר. כל שורה מכילה אז min(n, m) + 1 מספרים במקום טבלה של עד 251,001 תאים, והעבודה נשארת O(n × m).

אלגוריתם

אם word2 ארוכה יותר מ־word1, החליפו ביניהן.
הגדירו prev = [0, 1, ..., m], כאשר 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, ולכן dp[i][0] חייב להיות i ו-dp[0][j] חייב להיות j.
שכחה של cur[0] = i בגרסה עם שתי שורות. הערך הראשון שומר ערך מלפני שתי שורות, וכל תא אחריו שגוי.
תשלום על עריכה כשיש התאמה. הביטוי dp[i][j] = 1 + min(...) עבור אותיות שוות גורם לכך שהפיכת a ל-a תעלה 1. כשיש התאמה, מעתיקים את הערך באלכסון.
קריאת השכן משמאל מתוך prev במקום מתוך cur. השכן משמאל נמצא בשורה הנוכחית: זוהי הוספה של word2[j-1] אחרי ש-word1[:i] כבר הומר ל-word2[:j-1].
השוואה מיקום אחר מיקום. ספירת המקומות שבהם המילים שונות מתעלמת מהוספות וממחיקות: היא נותנת 6 עבור garden ו-ardent, בעוד שהתשובה היא 2.
שמירת תוצאות במטמון באמצעות רקורסיה עם מילים באורך 500 אותיות. עומק הקריאות מגיע ל-1000, וזוהי מגבלת ברירת המחדל של Python.

שאלות נפוצות4

מהי סיבוכיות הזמן של מרחק עריכה?

פתרון הטבלה פועל בזמן O(n × m), כאשר n ו-m הם שני האורכים, כי הוא ממלא תא אחד לכל זוג של קידומות בעבודה קבועה. הוא משתמש בזיכרון של O(n × m) עבור הטבלה המלאה, או בזיכרון של O(min(n, m)) עם שתי שורות. רקורסיה פשוטה ללא טבלה היא מעריכית.

האם מרחק עריכה זהה למרחק לבנשטיין?

כן, הגרסה הזאת היא מרחק לבנשטיין: הוספה, מחיקה והחלפה עולות כל אחת יחידה אחת. מרחק עריכה הוא שם המשפחה. גרסאות אחרות מאפשרות פחות עריכות או יותר: הוספות ומחיקות בלבד נותנות n + m - 2 × LCS, החלפות בלבד במחרוזות שוות באורכן נותנות את מרחק המינג, והוספת החלפה של שתי אותיות סמוכות נותנת את גרסת דמרו.

איך מקבלים את רשימת העריכות, ולא רק את מספרן?

שמרו את הטבלה המלאה וחזרו לאחור מ־dp[n][m]. אם האותיות תואמות, עברו באלכסון ללא עריכה. אחרת, עברו לשכן שערכו קטן באחד: באלכסון מדובר בהחלפה, למעלה במחיקה, שמאלה בהוספה. עצרו ב־dp[0][0] וקראו את העריכות בסדר הפוך. גרסת שתי השורות אינה יכולה לעשות זאת לבדה, משום שהיא השליכה את השורות הקודמות.

האם אפשר לפתור את מרחק העריכה באמצעות מערך יחיד?

כן. מלאו מערך אחד row במקום, משמאל לימין. לפני שאתם דורכים על row[j], עדיין נמצא בו הערך מהשורה שמעל, וב-row[j-1] כבר נמצא הערך של השורה הנוכחית. הערך היחיד שאתם מאבדים הוא הערך האלכסוני, לכן שמרו אותו במשתנה: שמרו את הערך הישן של row[j] לפני הכתיבה, והשתמשו בו כערך האלכסוני עבור j + 1.

Python

def minDistance(word1, word2):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

word1 = "spot"
word2 = "stop"

צפוי

Edit Distance

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו את שלושת העריכות בעזרת רקורסיה

מלאו טבלה של תחיליות

השאר רק שתי שורות

מלכודות ומקרי קצה

שאלות נפוצות4

בעיות דומות