מציאת תת-הרצף המשותף הארוך ביותר: Longest common subsequence (LCS)

מציאת תת-הרצף המשותף הארוך ביותר: Longest common subsequence (LCS)#

הגדרת תת-רצף#

B הוא תת-רצף (subsequence) של A אם ניתן לגזור את B מ־A על ידי הסרה של איברים מתוך A.

דוגמאות עם רשימות:

  • [2,4,6] היא תת־רצף של [1,2,3,4,5,6]

  • [6,4,2] איננה תת־רצף של [1,2,3,4,5,6] (יש חשיבות לסדר)

דוגמאות עם מחרוזות:

  • ‘is’ היא תת־רצף של =’distance’

  • ‘nice’ איננה תת־רצף של ‘distance’

בהנתן שתי סדרות (מחרוזות או רשימות), נרצה למצוא את תת־הרצף המשותף הארוך ביותר (Longest Common Subsequence – LCS).

דוגמא 1: “ABCD” ו־”ACBAD” מכילות:
- ארבעה תתי־רצף משותפים באורך 1: “A”, “B”, “C”, “D”
- חמישה תתי־רצף משותפים באורך 2: “AB”, “AC”, “AD”, “BD”, “CD”
- שני תתי־רצף משותפים באורך 3: “ABD”, “ACD”
- אפס תתי־רצף משותפים באורך 4.
לכן, ה־LCS הוא “ABD” או “ACD”

דוגמא 2: “HUMAN” ו־”CHIMPANZEE” מכילות: - ארבעה תתי רצף משותפים באורך 1: “H”, “M”, “A”, “N”
- הרצף “HMAN” הוא תת רצף משותף. וגם ה-LCS.

מעניין לדעת

מציאת תתי רצפים משותפים היא משימה שימושית מאוד בפתרון מגוון בעיות, בין השאר ביישומים ביואינפורמטיים ובבקרת גרסאות (למשל git)

גישה רקורסיבית למציאת LCS#

נפרק את הבעיה לתתי-בעיות פשוטות יותר.

נבחן את התו האחרון של שני הרצפים, למשל:
- “ABCD” ו־”ACBAD”
- “HUMAN” ו־”CHIMPANZEE”

אם התווים האחרונים של הרצפים הם זהים, הם חלק מ־LCS, כיוון שניתן להוסיף אותם ל־LCS של שאר הרצפים. לדוגמה:
- "ABCD" == "ABC" + "D"
- "ACBAD" == "ACBA" + "D"
- "LCS("ABCD", "ACBAD") == LCS("ABC", "ACBA") + "D

אחרת, כלומר שני התווים האחרונים שונים (כלומר last_1 ו־last_2). במקרה זה לא ייתכן ששניהם יהיו חלק מה-LCS - אם שניהם בLCS, מי מהם הוא התו האחרון? last_1 או last_2?

לכן יש לנו 3 אפשרויות לגבי last_1 ו־last_2:

  • רק last_1 הוא חלק מה־LCS:

    • LCS(“HUMAN”,”CHIMPANZEE”) = LCS(“HUMAN”,”CHIMPANZE”)

  • רק last_2 הוא חלק מה־LCS:

    • LCS(“HUMAN”,”CHIMPANZEE”) = LCS(“HUMA”,”CHIMPANZEE”)

  • אף אחד מהם אינו חלק מה־LCS:

    • LCS(“HUMAN”,”CHIMPANZEE”) = LCS(“HUMA”,”CHIMPANZE”)

פסאודו-קוד#

כעת נכתוב פסאודו קוד לבעיה “מהו אורך ה-LCS בין שתי מחרוזות”.

לשם כך נגדיר לכל רצף x:

  • last_x: התו האחרון של x

  • prefix_x: כל התווים שלפני last_x

ובאופן דומה נגדיר עבור הרצף y את last_y ו-prefix_y

פסאודו קוד בהינתן שני רצפים x ו-y:

1. מצב בסיס (תנאי עצירה):
1.1. אם אחד מהרצפים (x או y) ריק - החזר שהאורך הוא 0.

2. שלב רקורסיה (פירוק + הרכבה):
2.1 אם last_x == last_y:
2.1.1 LCS = lcs_rec(prefix_x, prefix_y) + 1
2.2 אחרת:
2.2.1 LCS = max(lcs_rec(prefix_x, y), lcs_rec(x, prefix_y))

נבחן כעת את עץ הרקורסיה עבור x="ab" ו-y="bc"

עיצרו וחישבו: למה בסוף לא מימשנו את האפשרות השלישית שבה שני התווים האחרונים לא בLCS?

הסיבה לכך היא שאפשרות זו נבדקת בתוך הקריאה הרקורסיבית. ניתן לראות שהמחרוזות “a” ו”b” נבדקות בתוך הקריאה הרקורסיבית של “a”,”bc”.

מימוש הפתרון בפייתון#

ממשו את הפונקציה lcs_rec אשר מקבלת שני רצפים x וy, ומחזירה את אורך ה-LCS שלהן. מצורפות לכם מספר מקרי בדיקה.

שימו לב

על הפונקציה שלכם לעבוד גם על מחרוזות וגם על רשימות.

def lcs_rec(x,y):
    # write your code here
    pass

lcs_rec("HUMAN","CHIMPANZEE")

lcs_rec("rykz","rickz")

lcs_rec(['r','y','k','z'],['r','i','c','k','z'])

lcs_rec([1,2,3,4,5,6],[7,2,4,9,9,9,6])

lcs_rec([1,2,3,4,5,6],[6,5,4,3,2,1])

תזכורת: פסאודו-קוד

1. מצב בסיס (תנאי עצירה):
1.1. אם אחד מהרצפים (x או y) ריק - החזר שהאורך הוא 0.

2. שלב רקורסיה (פירוק + הרכבה):
2.1 אם last_x == last_y:
2.1.1 LCS = lcs_rec(prefix_x, prefix_y) + 1
2.2 אחרת:
2.2.1 LCS = max(lcs_rec(prefix_x, y), lcs_rec(x, prefix_y))

לחצו כאן כדי לצפות בפתרון

def lcs_rec(x,y):
    if len(x) == 0 or len(y) == 0:
        return 0
    if x[-1] == y[-1]:
        return lcs_rec(x[:-1],y[:-1]) + 1
    else:
        return max(lcs_rec(x[:-1],y), lcs_rec(x,y[:-1]))

המנעות משכפול רשימות#

נבחן כעת את הפעלת הפונקציה על רשימות של תווים במקום על מחרוזות (שימו לב שמימוש הפונקציה לא השתנה!)

בכל פעם שהפונקציה הרקורסיבית נקראת, מבוצע slicing על הרשימה (שנחתכה), שמועבר לקריאה הרקורסיבית. זכרו כי פעולת slicing משכפלת את של אותה רשימה. כלומר, בכל קריאה רקורסיבית, יועבר שכפול של הרשימה לscope החדש שנוצר עבור קריאה זו.

ראו דוגמא להרצת התכנית בPython Tutor:

עיצרו וחישבו: באיזה עוד אלגוריתם נתקלתם בslicing מיותר? מה עשינו אז?

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

פתרון: שימוש באינדקסים במקום slicing#

במקום לחתוך את סוף הרשימות ב-slicing, נוסיף בחתימת הפונקציה אינדקסים המייצגים את סוף הרשימה הנוכחי, כלומר, לאחר ה”חיתוך”.

  • בדיקת התו תהיה לפי אינדקסים (ולא התו האחרון ברשימה).

  • כל פעולת חיתוך רשימה תוחלף בהקטנת אינדקס סוף הרשימה ב1.

  • תנאי הבסיס יבדוק את ערך האינדקס במקום גודל הרשימה

ממשו בפייתון את הפונקציה lcs_rec אשר מחזירה את אורך ה-LCS בין שני רצפים. הפעם השתמשו בx_i, y_i במקום לבצע slicing.

לחצו כאן כדי לצפות בפתרון

def lcs_rec(x,y,x_i,y_i):
    if y_i == -1 or x_i == -1:
        return 0
    if x[x_i] == y[y_i]:
        return lcs_rec(x,y,x_i-1,y_i-1) + 1
    else:
        return max(lcs_rec(x,y,x_i-1,y_i), lcs_rec(x,y,x_i,y_i-1))

def lcs_rec(x,y, x_i, y_i):
    # write your code here
    pass

s1=["r","y","k","z"]
s2=["r","i","c","k","z"]
lcs_rec(s1,s2,x_i=len(s1)-1,y_i=len(s2)-1)

כך יראה הזכרון התכנית של המימוש החדש בPython Tutor:

פתרון העברת האינדקסים אמנם חסך לנו slicing מיותר ושימוש בזכרון, אך קיימים לו 2 חסרונות:

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

  • הקריאה לפונקציה עם הפרמטרים החדשים מעט מסורבלת:

s1=["r","y","k","z"]
s2=["r","i","c","k","z"]
lcs_rec(s1,s2,x_i=len(s1)-1,y_i=len(s2)-1)

על מנת לעקוף את הבעיה, ניתן למשתמש בפונקצית עזר

  • נממש את הפתרון שלנו כולו בפונקצית העזר

  • נקרא לפונצית העזר מהפונקציה המקורית עם הפרמטרים הנדרשים

כך אנו למעשה

  • לא משנים את חתימת הפונקציה המקורית

  • לא צריכים לחזר עם הקריאה המסורבלת (עם ארבעת הפרמטרים) בכל פעם שנקרא לפונקציה המקורית

def lcs_rec_helper(x,y,x_i,y_i):
    if y_i == -1 or x_i == -1:
        return 0
    if x[x_i] == y[y_i]:
        return lcs_rec_helper(x,y,x_i-1,y_i-1) + 1
    else:
        return max(lcs_rec_helper(x,y,x_i-1,y_i), lcs_rec_helper(x,y,x_i,y_i-1))

def lcs_rec(s1,s2):
    return lcs_rec_helper(s1,s2,x_i=len(s1)-1,y_i=len(s2)-1)

lcs_rec(["r","y","k","z"],["r","i","c","k","z"])

3
Contents