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

קורס: מבני נתונים

אוניברסיטה: אוניברסיטת בר-אילן

שנה: 2016

סמסטר: ב

נושאים: חיפוש, Boyer-Moore, כלל הסיומת הטובה

רמת קושי: בינוני

היזוחה הקנויות $$A A B A A A A B A A B A A$$ בשדל אלו-יורו { A,B,C,D }. בחתיח את הקנויות הנתונה בעזור Boyer & Moore של $\Delta_2 - \Delta_1$. | i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | --- | A | A | B | A | A | A | B | A | A | B | A | A | | $\Delta_2(i)$ | | | | | | | | | | | | |

רמז: כלל הסיומת הטובה ($\Delta_2$) קובע את ההזזה על פי הסיומת של התבנית שכבר נמצאה מתאימה. ישנם שני מקרים: או שנמצא מופע נוסף של הסיומת, או שנמצאת רישא של התבנית שמתאימה לסופה של הסיומת.

פתרון: השאלה, על אף ניסוחה המשובש, מבקשת לחשב את טבלת ההזזות $\Delta_2$ (כלל הסיומת הטובה) של אלגוריתם Boyer-Moore עבור התבנית הנתונה בטבלה. **התבנית:** $P = \text{AABAAABAABAA}$, ואורכה $m=12$. טבלת $\Delta_2(i)$ מגדירה את גודל ההזזה (shift) שיש לבצע כאשר מתגלה אי-התאמה בתו ה-$i$ של התבנית (בספירה משמאל, 1-indexed), לאחר שהסיומת $P[i+1..m]$ נמצאה מתאימה. חישוב ערכי הטבלה: * **חישוב עבור $i=12$:** אי-התאמה בתו האחרון. הסיומת הטובה ריקה. במקרה זה משתמשים בכלל התו הרע ($\Delta_1$), ולכן $\Delta_2$ אינו מוגדר. * **חישוב עבור $i=11$:** - אי-התאמה ב-$P[11] = 'A'$. - **הסיומת הטובה** היא $u = P[12] = 'A'$. - נחפש את המופע הימני ביותר של $u$ בתת-המחרוזת $P[1..11]$, כך שהתו שלפניו שונה מ-$P[11]='A'$. - המופע הימני ביותר של 'A' ב-$P[1..11]$ הוא במיקום $j=9$. התו שלפניו הוא $P[8]='A'$. התנאי לא מתקיים. נבדוק את המופע הבא: $P[8]='A'$, התו שלפניו $P[7]='B'$. מכיוון ש-$'B' \neq 'A'$, מצאנו התאמה במיקום $j=8$. - ההזזה היא המרחק שיביא את $P[8]$ למקום בו היה $P[12]$, כלומר $s = m - j = 12 - 8 = 4$. שינוי: המופע הימני ביותר הוא ב-9, לפניו 8 (A). הבא הוא ב-8, לפניו 7 (B). $P[11]=A$. $P[7]=B eq A$. אז המופע ב-8 מתאים. Shift $12-8=4$. בוא נבדוק שוב: `AABAAABAABAA`. התו ה-11 הוא A. הסיומת היא A. מופעים של A ב-P[1..11] הם ב-1,2,4,5,6,8,9,11. נבדוק מהסוף: ב-11 זה הסיומת עצמה. ב-9, לפניו P[8]=A. זהה ל-P[11]. לא טוב. ב-8, לפניו P[7]=B. שונה מ-P[11]. טוב. הזזה: $11 - (8-1) = 4$? לא. הזזה היא $m-k = 12-8=4$. המופע שמתחיל ב-$j$ צריך להיות מיושר עם ההתחלה של הסיומת הטובה $u$ בטקסט. $u$ מתחיל ב-$i+1$. אז $s = (i+1) - j$. כאן $u$ הוא תו בודד במיקום $12$. אנחנו רוצים ליישר את $P[j]$ עם מיקום $12$. $s = 12-j=12-8=4$. נראה שזה נכון. בבדיקה נוספת, המופע ב-$P[9]$ לפניו $P[8]='A'$. המופע ב-$P[8]$ לפניו $P[7]='B'$. התו באי-ההתאמה הוא $P[11]='A'$. אז עבור $j=8$, $P[7] \neq P[11]$. ההזזה היא $12-8=4$. $\Delta_2(11) = 4$. * **חישוב עבור $i=10$:** - אי-התאמה ב-$P[10] = 'B'$. - **הסיומת הטובה** היא $u = P[11..12] = 'AA'$. - נחפש מופע של 'AA' ב-$P[1..10]$ שהתו שלפניו שונה מ-$'B'$. - המופעים של 'AA' הם ב-$j=1, 4, 8$. עבור $j=8$, התו הקודם הוא $P[7]='B'$, זהה ל-$P[10]$. עבור $j=4$, התו הקודם הוא $P[3]='B'$, זהה. עבור $j=1$, אין תו קודם (תנאי מתקיים). לכן נשתמש ב-$j=1$. - ההזזה מיישרת את $P[1..2]$ עם מיקום $P[11..12]$. $s = (i+1)-j = 11-1 = 10$. - $\Delta_2(10) = 10$. * **חישוב עבור $i=9$:** - אי-התאמה ב-$P[9] = 'A'$. - **הסיומת הטובה** היא $u = P[10..12] = 'BAA'$. - אין מופע נוסף של 'BAA' בתבנית. לכן, נחפש את הרישא (prefix) הארוכה ביותר של $P$ שהיא גם סיומת (suffix) של $u$. - הסיומות של $u$ הן 'A', 'AA'. הרישאות של $P$ הן 'A', 'AA', 'AAB'.... הרישא הארוכה ביותר המשותפת היא 'AA', שאורכה $l=2$. - ההזזה היא $s = m - l = 12 - 2 = 10$. - $\Delta_2(9) = 10$. * **חישוב עבור $i=8$:** - אי-התאמה ב-$P[8] = 'A'$. - **הסיומת הטובה** היא $u = P[9..12] = 'ABAA'$. - אין מופע נוסף. הרישא הארוכה ביותר של $P$ שהיא סיומת של $u$ היא 'AA' ($l=2$). - ההזזה היא $s = m - l = 12 - 2 = 10$. - $\Delta_2(8) = 10$. * **חישוב עבור $i=1$ עד $i=7$:** - עבור כל $i$ בטווח זה, הסיומת הטובה $u=P[i+1..12]$ היא ארוכה מספיק כדי להכיל את 'AABAA' כסיומת (כיוון ש-$P[8..12] = 'AABAA'$). - אין מופעים נוספים של סיומות אלו בתבנית. - לכן, נשתמש בכלל השני. הרישא הארוכה ביותר של $P$ היא 'AABAA' ($l=5$). זוהי גם הסיומת הארוכה ביותר של כל $u$ רלוונטי שמהווה רישא של $P$. - ההזזה היא $s = m - l = 12 - 5 = 7$. - $\Delta_2(i) = 7$ לכל $i ∈ [1, 7]$. **טבלת $\Delta_2$ המסכמת:** | i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | **$\Delta_2(i)$** | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 10 | 10 | 10 | 4 | - |

היזוחה הקנויות

AA B AAAA B AA B AA

בשדל אלו-יורו { A,B,C,D }. בחתיח את הקנויות הנתונה בעזור Boyer & Moore של

Δ_{2} - Δ_{1}

.

| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | A | A | B | A | A | A | B | A | A | B | A | A |
|

Δ_{2} (i)

| | | | | | | | | | | | |

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א2016סמסטר ב

★★★★★

חיפושBoyer-Mooreכלל הסיומת הטובה

כלל הסיומת הטובה (

Δ_{2}

) קובע את ההזזה על פי הסיומת של התבנית שכבר נמצאה מתאימה. ישנם שני מקרים: או שנמצא מופע נוסף של הסיומת, או שנמצאת רישא של התבנית שמתאימה לסופה של הסיומת.

השאלה, על אף ניסוחה המשובש, מבקשת לחשב את טבלת ההזזות

Δ_{2}

(כלל הסיומת הטובה) של אלגוריתם Boyer-Moore עבור התבנית הנתונה בטבלה.

התבנית:

P = AABAAABAABAA

, ואורכה

m = 12

.

טבלת

Δ_{2} (i)

מגדירה את גודל ההזזה (shift) שיש לבצע כאשר מתגלה אי-התאמה בתו ה-

i

של התבנית (בספירה משמאל, 1-indexed), לאחר שהסיומת

P [i + 1.. m]

נמצאה מתאימה.

חישוב ערכי הטבלה:

* **חישוב עבור

i = 12

:** אי-התאמה בתו האחרון. הסיומת הטובה ריקה. במקרה זה משתמשים בכלל התו הרע (

Δ_{1}

), ולכן

Δ_{2}

אינו מוגדר.

* **חישוב עבור

i = 11

:**
- אי-התאמה ב-

P [11] =^{'} A^{'}

.
- הסיומת הטובה היא

u = P [12] =^{'} A^{'}

.
- נחפש את המופע הימני ביותר של

u

בתת-המחרוזת

P [1..11]

, כך שהתו שלפניו שונה מ-

P [11] =^{'} A^{'}

.
- המופע הימני ביותר של 'A' ב-

P [1..11]

הוא במיקום

j = 9

. התו שלפניו הוא

P [8] =^{'} A^{'}

. התנאי לא מתקיים. נבדוק את המופע הבא:

P [8] =^{'} A^{'}

, התו שלפניו

P [7] =^{'} B^{'}

. מכיוון ש-

^{'} B^{'} \neq =^{'} A^{'}

, מצאנו התאמה במיקום

j = 8

.
- ההזזה היא המרחק שיביא את

P [8]

למקום בו היה

P [12]

, כלומר

s = m - j = 12 - 8 = 4

. שינוי: המופע הימני ביותר הוא ב-9, לפניו 8 (A). הבא הוא ב-8, לפניו 7 (B).

P [11] = A

. $P[7]=B
eq A

.אזהמופעב - 8מתאים. S hi f t

12-8=4

.בואנבדוקשוב : ‘ AA B AAA B AA B AA ‘.התוה - 11הוא A .הסיומתהיא A .מופעיםשל A ב - P [1..11] הםב - 1, 2, 4, 5, 6, 8, 9, 11.נבדוקמהסוף : ב - 11זההסיומתעצמה.ב - 9, לפניו P [8] = A .זההל - P [11] .לאטוב.ב - 8, לפניו P [7] = B .שונהמ - P [11] .טוב.הזזה :

11 - (8-1) = 4

? לא.הזזההיא

m-k = 12-8=4

.המופעשמתחילב -

צריךלהיותמיושרעםההתחלהשלהסיומתהטובה

בטקסט.

מתחילב -

i+1

.אז

s = (i+1) - j

.כאן

הואתובודדבמיקום

.אנחנורוציםליישראת

P[j]

עםמיקום

.

s = 12-j=12-8=4

.נראהשזהנכון.בבדיקהנוספת, המופעב -

P[9]

לפניו

P[8]='A'

.המופעב -

P[8]

לפניו

P[7]='B'

.התובאי - ההתאמההוא

P[11]='A'

.אזעבור

j=8

,

P[7] \neq P[11]

.ההזזההיא

12-8=4

.

\Delta_2(11) = 4$.

* **חישוב עבור

i = 10

:**
- אי-התאמה ב-

P [10] =^{'} B^{'}

.
- הסיומת הטובה היא

u = P [11..12] =^{'} A A^{'}

.
- נחפש מופע של 'AA' ב-

P [1..10]

שהתו שלפניו שונה מ-

^{'} B^{'}

.
- המופעים של 'AA' הם ב-

j = 1, 4, 8

. עבור

j = 8

, התו הקודם הוא

P [7] =^{'} B^{'}

, זהה ל-

P [10]

. עבור

j = 4

, התו הקודם הוא

P [3] =^{'} B^{'}

, זהה. עבור

j = 1

, אין תו קודם (תנאי מתקיים). לכן נשתמש ב-

j = 1

.
- ההזזה מיישרת את

P [1..2]

עם מיקום

P [11..12]

s = (i + 1) - j = 11 - 1 = 10

.
-

Δ_{2} (10) = 10

.

* **חישוב עבור

i = 9

:**
- אי-התאמה ב-

P [9] =^{'} A^{'}

.
- הסיומת הטובה היא

u = P [10..12] =^{'} B A A^{'}

.
- אין מופע נוסף של 'BAA' בתבנית. לכן, נחפש את הרישא (prefix) הארוכה ביותר של

P

שהיא גם סיומת (suffix) של

u

.
- הסיומות של

u

הן 'A', 'AA'. הרישאות של

P

הן 'A', 'AA', 'AAB'.... הרישא הארוכה ביותר המשותפת היא 'AA', שאורכה

l = 2

.
- ההזזה היא

s = m - l = 12 - 2 = 10

.
-

Δ_{2} (9) = 10

.

* **חישוב עבור

i = 8

:**
- אי-התאמה ב-

P [8] =^{'} A^{'}

.
- הסיומת הטובה היא

u = P [9..12] =^{'} A B A A^{'}

.
- אין מופע נוסף. הרישא הארוכה ביותר של

P

שהיא סיומת של

u

היא 'AA' (

l = 2

).
- ההזזה היא

s = m - l = 12 - 2 = 10

.
-

Δ_{2} (8) = 10

.

* **חישוב עבור

i = 1

עד

i = 7

:**
- עבור כל

i

בטווח זה, הסיומת הטובה

u = P [i + 1..12]

היא ארוכה מספיק כדי להכיל את 'AABAA' כסיומת (כיוון ש-

P [8..12] =^{'} AA B A A^{'}

).
- אין מופעים נוספים של סיומות אלו בתבנית.
- לכן, נשתמש בכלל השני. הרישא הארוכה ביותר של

P

היא 'AABAA' (

l = 5

). זוהי גם הסיומת הארוכה ביותר של כל

u

רלוונטי שמהווה רישא של

P

.
- ההזזה היא

s = m - l = 12 - 5 = 7

.
-

Δ_{2} (i) = 7

לכל $i

∈ [1, 7]$.

**טבלת

Δ_{2}

המסכמת:**

i	1	2	3	4	5	6	7	8	9	10	11	12
$Δ_{2} (i)$	7	7	7	7	7	7	7	10	10	10	4	-

שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2016 - חיפוש