שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2016 - גנרטורים

בשאלה זו נממש חיפוש של תת-מחרוזות משותפות לשתי מחרוזות טקסט באמצעות אלגוריתם Rabin-Karp וגנרטורים. נתונות שתי הפונקציות הבאות (הראשונה זהה והשניה דומה מאד לקוד של KR מהשיעור): ```python def fingerprint(string, basis=2**16, r=2**32-3): """ computes karp-rabin fingerprint of the pattern employs Horner method (modulo r) """ partial_sum = 0 for x in string: partial_sum = (partial_sum * basis + ord(x)) % r return partial_sum def slide(prev_fp, prev_char, next_char, b_power, basis=2**16, r=2**32-3): new_fp = ((prev_fp - ord(prev_char)*b_power)*basis + ord(next_char)) % r return new_fp ``` א. (8 נק') השלימו את פונקציית הגנרטור הבאה אשר מייצרת את רצף ה-fingerprints של תת מחרוזות באורך `length` ממחרוזת נתונה `text`, על פי סדר הופעתן במחרוזת `text`. קריאה ל-`next` כאשר תמו ה-fingerprints תגרום לזריקת exception, כרגיל כפי שראינו בכיתה. דרישות נוספות: על הפונקציה לעשות שימוש בפונקציות `fingerprint` ו-`slide`. במהלך ייצור רצף ה-fingerprints המלא עבור מחרוזת נתונה תקרא הפונקציה `fingerprint` **פעם אחת בלבד**. לדוגמה: ```python >>> list(kr_gen("bye bye", 3)) [7930251, 6619531, 2097553, 6422745, 7930251] ``` ```python def kr_gen(text, length, basis=2**16, r=2**32-3): if length <= len(text): ___ ___ b_power = pow(basis, length-1, r) for s in range(1, len(text)-length+1): ___ ___ ``` ב. (12 נק') השלימו את פונקציית הגנרטור הבאה, אשר מקבלת שתי מחרוזות טקסט ומייצרת את האינדקסים של כל תת המחרוזות באורך `length` המשותפות להן. ליתר דיוק, הפונקציה מייצרת רצף של tuples, כשכל tuple מייצג match ומכיל זוג מספרים: המספר הראשון הוא אינדקס המופע במחרוזת הראשונה, והשני במחרוזת השניה. אין חשיבות לסדר ייצור ה-tuples (אבל, כאמור, יש חשיבות לסדר המספרים בתוך כל tuple). זיכרו כי כרגיל בעת שימוש ב-fingerprints לצורך השוואת מחרוזות, תיתכן שגיאה בהסתברות קטנה, בדומה לקוד שראינו בשיעור. אין צורך לטפל בבעיה זו. דרישות נוספות: 1. על הפונקציה לעשות שימוש ב-`kr_gen`. 2. אסור לפונקציה להקצות זיכרון בגודל שהוא לינארי באורכי מחרוזות הטקסט או יותר מכך. בפרט, אסור לפונקציה בשום שלב לפרוש את רצף ה-fingerprints המלא של אחת ממחרוזות הטקסט. לדוגמה: ```python >>> list(generate_shared_substrings("abcdef", "xcdefx", 3)) [(2, 1), (3, 2)] ``` תזכורת מהשיעור - try ו-except: ```python def division(a, b): try: return a/b except ZeroDivisionError: print("division by zero") ``` ```python def generate_shared_substrings(text1, text2, length): ___ i1 = -1 while True: ___ i1 += 1 ___ i2 = -1 while True: try: ___ i2 += 1 except StopIteration: ___ if fp1 == fp2: yield (i1, i2) ```

רמז: בסעיף א': קראו ל-fingerprint פעם אחת עבור תת-המחרוזת הראשונה, ואז השתמשו ב-yield כדי להחזיר אותה. בלולאה, השתמשו ב-slide כדי לחשב את ה-fingerprint הבא ולעשות yield. בסעיף ב': צרו שני גנרטורים מ-kr_gen. עבור כל fingerprint מהגנרטור הראשון, עברו על כל ה-fingerprints מהגנרטור השני. שימו לב שצריך ליצור גנרטור חדש עבור text2 בכל איטרציה של text1 (בגלל מגבלת הזיכרון).

פתרון: **סעיף א':** ```python def kr_gen(text, length, basis=2**16, r=2**32-3): if length <= len(text): fp = fingerprint(text[:length], basis, r) yield fp b_power = pow(basis, length-1, r) for s in range(1, len(text)-length+1): fp = slide(fp, text[s-1], text[s+length-1], b_power, basis, r) yield fp ``` הסבר: קודם מחשבים fingerprint לתת-מחרוזת הראשונה (אינדקס 0) ועושים yield. אחר כך בלולאה, משתמשים ב-slide כדי לעבור לתת-מחרוזת הבאה ועושים yield. **סעיף ב':** ```python def generate_shared_substrings(text1, text2, length): gen1 = kr_gen(text1, length) i1 = -1 while True: try: fp1 = next(gen1) except StopIteration: break i1 += 1 gen2 = kr_gen(text2, length) i2 = -1 while True: try: fp2 = next(gen2) i2 += 1 except StopIteration: break if fp1 == fp2: yield (i1, i2) ``` הסבר: עוברים על כל fingerprint מהמחרוזת הראשונה. עבור כל אחד, יוצרים גנרטור חדש עבור המחרוזת השניה (כי אי אפשר לשמור את כל ה-fingerprints בזיכרון). משווים ואם יש התאמה עושים yield של זוג האינדקסים. הערה: הפונקציה כפי שהיא בבחינה עם המבנה הנתון (try/except בתוך while True פנימי, ו-break בחלק ה-except) מתאימה בדיוק למבנה הזה. שימו לב שהשוואת fp1==fp2 ו-yield נמצאים בתוך ה-while הפנימי.