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

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

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

שנה: 2015

סמסטר: ב

נושאים: Boyer-Moore, חיפוש מחרוזות

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

נתונה התבנית $A A B A A A B A A B A A$ מעל אלף-בית $\Sigma = \{A, B, C, D\}$. בנו את טבלאות $\Delta_1$ ו-$\Delta_2$ מהאלגוריתם של Boyer & Moore עבור התבנית הנתונה. | $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_1$, מצאו את המופע האחרון של כל תו מהאלפבית בתבנית. עבור טבלת $\Delta_2(i)$, חשבו את גודל ההזזה הנדרש עבור כל "סיומת טובה" אפשרית $P[i..m]$.

פתרון: אלגוריתם Boyer & Moore משתמש בשתי היוריסטיקות (טבלאות) כדי לקבוע את גודל ההזזה (shift) של התבנית על פני הטקסט: היוריסטיקת התו הרע ($\\Delta_1$) והיוריסטיקת הסיומת הטובה ($\\Delta_2$). נבנה את הטבלאות עבור התבנית $P = AABA AAB AAB AA$ שאורכה $m=12$ והאלף-בית $\Sigma = \{A, B, C, D\}$. ### בניית טבלת $\Delta_1$ (היוריסטיקה של התו הרע) טבלת $\Delta_1$ שומרת עבור כל תו $c \in \Sigma$ את המיקום (אינדקס) של המופע הימני ביותר שלו בתבנית $P$. אם תו אינו מופיע בתבנית, נהוג לסמן את מיקומו כ-0 (בהנחת אינדקסים מ-1). התבנית $P$ והאינדקסים שלה: | אינדקס | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | תו | A | A | B | A | A | A | B | A | A | B | A | A | נמצא את המופע הימני ביותר עבור כל תו מהאלף-בית: - **עבור 'A'**: המופע הימני ביותר הוא באינדקס 12. - **עבור 'B'**: המופע הימני ביותר הוא באינדקס 10. - **עבור 'C'**: התו אינו מופיע בתבנית, לכן המיקום הוא 0. - **עבור 'D'**: התו אינו מופיע בתבנית, לכן המיקום הוא 0. לכן, טבלת $\Delta_1$ היא: - $\Delta_1('A') = 12$ - $\Delta_1('B') = 10$ - $\Delta_1('C') = 0$ - $\Delta_1('D') = 0$ ### בניית טבלת $\Delta_2$ (היוריסטיקה של הסיומת הטובה) טבלת $\Delta_2(i)$ מכילה את גודל ההזזה כאשר מתגלה אי-התאמה בתו ה-$i-1$ של התבנית, כלומר כאשר הסיומת $P[i..12]$ היא "סיומת טובה" (התאימה לטקסט). החישוב מתבצע בשני שלבים: 1. נחפש את המופע הימני ביותר של הסיומת הטובה $t=P[i..m]$ בתבנית, $P[j..j+|t|-1]$, כך ש-$j < i$ והתו שלפניו שונה, כלומר $P[j-1] \neq P[i-1]$. אם נמצא כזה, ההזזה היא $i-j$. ניקח את ההזזה המינימלית. 2. אם לא נמצא מופע כזה, נחפש את הרישא (prefix) הארוכה ביותר של $P$ שהיא גם סיפא (suffix) של הסיומת הטובה $t$. אם אורך הרישא הוא $k$, ההזזה תהיה $m-k$. אם אין כזו, ההזזה היא $m$. נחשב את $\Delta_2(i)$ עבור $i=12, 11, \dots, 1$: - **i=12**: סיומת טובה `"A"`. אי-התאמה ב-$P[11]=\'A\'$. המופע הימני ביותר של `"A"` שאינו מופיע אחרי `"A"` הוא ב-$P[11]$ (לפניו $P[10]=\'B\'$). ההזזה: $12-11=1$. לכן, $\Delta_2(12)=1$. - **i=11**: סיומת טובה `"AA"`. אי-התאמה ב-$P[10]=\'B\'$. המופע הימני ביותר של `"AA"` שאינו מופיע אחרי `"B"` הוא $P[5..6]$ (לפניו $P[4]=\'A\'$). ההזזה: $11-5=6$. לכן, $\Delta_2(11)=6$. - **i=10**: סיומת טובה `"BAA"`. אי-התאמה ב-$P[9]=\'A\'$. אין מופע של `"BAA"` שאינו אחרי `"A"`. רישא של $P$ שהיא סיפא של `"BAA"` היא `"AA"` (אורך 2). ההזזה: $12-2=10$. לכן, $\Delta_2(10)=10$. - **i=9**: סיומת טובה `"ABAA"`. אי-התאמה ב-$P[8]=\'A\'$. אין מופע מתאים. רישא של $P$ שהיא סיפא של `"ABAA"` היא `"AA"` (אורך 2). ההזזה: $12-2=10$. לכן, $\Delta_2(9)=10$. - **i=8**: סיומת טובה `"AABAA"`. אי-התאמה ב-$P[7]=\'B\'$. המופע $P[5..9]$ אינו אחרי `"B"`. ההזזה: $8-5=3$. לכן, $\Delta_2(8)=3$. - **i=7**: סיומת טובה `"BAABAA"`. אי-התאמה ב-$P[6]=\'A\'$. אין מופע מתאים. רישא של $P$ שהיא סיפא של `"BAABAA"` היא `"AABAA"` (אורך 5). ההזזה: $12-5=7$. לכן, $\Delta_2(7)=7$. - **i=6**: סיומת טובה `"ABAABAA"`. אי-התאמה ב-$P[5]=\'A\'$. אין מופע מתאים. רישא של $P$ שהיא סיפא של `"ABAABAA"` היא `"AA"` (אורך 2). ההזזה: $12-2=10$. לכן, $\Delta_2(6)=10$. - **i=5**: סיומת טובה `"AABAABAA"`. אי-התאמה ב-$P[4]=\'A\'$. אין מופע מתאים. רישא של $P$ שהיא סיפא של `"AABAABAA"` היא `"AABAA"` (אורך 5). ההזזה: $12-5=7$. לכן, $\Delta_2(5)=7$. - **i=4**: סיומת טובה `"AAABAABAA"`. אי-התאמה ב-$P[3]=\'B\'$. אין מופע מתאים. רישא של $P$ שהיא סיפא של `"AAABAABAA"` היא `"AA"` (אורך 2). ההזזה: $12-2=10$. לכן, $\Delta_2(4)=10$. - **i=3**: סיומת טובה `"BAAABAABAA"`. אי-התאמה ב-$P[2]=\'A\'$. אין מופע מתאים. רישא של $P$ שהיא סיפא של `"BAAABAABAA"` היא `"AABAA"` (אורך 5). ההזזה: $12-5=7$. לכן, $\Delta_2(3)=7$. - **i=2**: סיומת טובה `"ABAABAA"`. לא, `P[2..12]` = `"A B A A A B A A B A A"`. אין מופע מתאים. רישא של $P$ שהיא סיפא של $P[2..12]$ היא `"AA"` (אורך 2). ההזזה: $12-2=10$. לכן, $\Delta_2(2)=10$. - **i=1**: במקרה זה הסיומת היא כל התבנית. אין אי-התאמה לפני, ולכן הערך לא רלוונטי לחישוב הזזה. לרוב מגדירים $\Delta_2(1)=1$ כדי להבטיח התקדמות. לכן, $\Delta_2(1)=1$. הטבלה המלאה: | $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | $P$ | A | A | B | A | A | A | B | A | A | B | A | A | | $\Delta_2(i)$ | 1 | 10 | 7 | 10 | 7 | 10 | 7 | 3 | 10 | 10 | 6 | 1 |

נתונה התבנית

AA B AAA B AA B AA

מעל אלף-בית

Σ = {A, B, C, D}

. בנו את טבלאות

Δ_{1}

ו-

Δ_{2}

מהאלגוריתם של Boyer & Moore עבור התבנית הנתונה.

$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)$

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

Boyer-Mooreחיפוש מחרוזות

עבור טבלת

Δ_{1}

, מצאו את המופע האחרון של כל תו מהאלפבית בתבנית. עבור טבלת

Δ_{2} (i)

, חשבו את גודל ההזזה הנדרש עבור כל "סיומת טובה" אפשרית

P [i .. m]

אלגוריתם Boyer & Moore משתמש בשתי היוריסטיקות (טבלאות) כדי לקבוע את גודל ההזזה (shift) של התבנית על פני הטקסט: היוריסטיקת התו הרע (

D e l t a_{1}

) והיוריסטיקת הסיומת הטובה (

D e l t a_{2}

). נבנה את הטבלאות עבור התבנית

P = AA B AAA B AA B AA

שאורכה

m = 12

והאלף-בית

Σ = {A, B, C, D}

.

### בניית טבלת

Δ_{1}

(היוריסטיקה של התו הרע)

טבלת

Δ_{1}

שומרת עבור כל תו

c \in Σ

את המיקום (אינדקס) של המופע הימני ביותר שלו בתבנית

P

. אם תו אינו מופיע בתבנית, נהוג לסמן את מיקומו כ-0 (בהנחת אינדקסים מ-1).

התבנית

P

והאינדקסים שלה:

אינדקס	1	2	3	4	5	6	7	8	9	10	11	12
תו	A	A	B	A	A	A	B	A	A	B	A	A

נמצא את המופע הימני ביותר עבור כל תו מהאלף-בית:
- עבור 'A': המופע הימני ביותר הוא באינדקס 12.
- עבור 'B': המופע הימני ביותר הוא באינדקס 10.
- עבור 'C': התו אינו מופיע בתבנית, לכן המיקום הוא 0.
- עבור 'D': התו אינו מופיע בתבנית, לכן המיקום הוא 0.

לכן, טבלת

Δ_{1}

היא:
-

Δ_{1} (^{'} A^{'}) = 12

Δ_{1} (^{'} B^{'}) = 10

Δ_{1} (^{'} C^{'}) = 0

Δ_{1} (^{'} D^{'}) = 0

### בניית טבלת

Δ_{2}

(היוריסטיקה של הסיומת הטובה)

טבלת

Δ_{2} (i)

מכילה את גודל ההזזה כאשר מתגלה אי-התאמה בתו ה-

i - 1

של התבנית, כלומר כאשר הסיומת

P [i ..12]

היא "סיומת טובה" (התאימה לטקסט). החישוב מתבצע בשני שלבים:
1. נחפש את המופע הימני ביותר של הסיומת הטובה

t = P [i .. m]

בתבנית,

P [j .. j + ∣ t ∣ - 1]

, כך ש-

j < i

והתו שלפניו שונה, כלומר

P [j - 1] \neq = P [i - 1]

. אם נמצא כזה, ההזזה היא

i - j

. ניקח את ההזזה המינימלית.
2. אם לא נמצא מופע כזה, נחפש את הרישא (prefix) הארוכה ביותר של

P

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

t

. אם אורך הרישא הוא

k

, ההזזה תהיה

m - k

. אם אין כזו, ההזזה היא

m

.

נחשב את

Δ_{2} (i)

עבור

i = 12, 11, \dots, 1

:
- i=12: סיומת טובה "A". אי-התאמה ב-

P[11]=\'A\'

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

P [11]

(לפניו

P[10]=\'B\'

). ההזזה:

12 - 11 = 1

. לכן,

Δ_{2} (12) = 1

.
- i=11: סיומת טובה "AA". אי-התאמה ב-

P[10]=\'B\'

. המופע הימני ביותר של "AA" שאינו מופיע אחרי "B" הוא

P [5..6]

(לפניו

P[4]=\'A\'

). ההזזה:

11 - 5 = 6

. לכן,

Δ_{2} (11) = 6

.
- i=10: סיומת טובה "BAA". אי-התאמה ב-

P[9]=\'A\'

. אין מופע של "BAA" שאינו אחרי "A". רישא של

P

שהיא סיפא של "BAA" היא "AA" (אורך 2). ההזזה:

12 - 2 = 10

. לכן,

Δ_{2} (10) = 10

.
- i=9: סיומת טובה "ABAA". אי-התאמה ב-

P[8]=\'A\'

. אין מופע מתאים. רישא של

P

שהיא סיפא של "ABAA" היא "AA" (אורך 2). ההזזה:

12 - 2 = 10

. לכן,

Δ_{2} (9) = 10

.
- i=8: סיומת טובה "AABAA". אי-התאמה ב-

P[7]=\'B\'

. המופע

P [5..9]

אינו אחרי "B". ההזזה:

8 - 5 = 3

. לכן,

Δ_{2} (8) = 3

.
- i=7: סיומת טובה "BAABAA". אי-התאמה ב-

P[6]=\'A\'

. אין מופע מתאים. רישא של

P

שהיא סיפא של "BAABAA" היא "AABAA" (אורך 5). ההזזה:

12 - 5 = 7

. לכן,

Δ_{2} (7) = 7

.
- i=6: סיומת טובה "ABAABAA". אי-התאמה ב-

P[5]=\'A\'

. אין מופע מתאים. רישא של

P

שהיא סיפא של "ABAABAA" היא "AA" (אורך 2). ההזזה:

12 - 2 = 10

. לכן,

Δ_{2} (6) = 10

.
- i=5: סיומת טובה "AABAABAA". אי-התאמה ב-

P[4]=\'A\'

. אין מופע מתאים. רישא של

P

שהיא סיפא של "AABAABAA" היא "AABAA" (אורך 5). ההזזה:

12 - 5 = 7

. לכן,

Δ_{2} (5) = 7

.
- i=4: סיומת טובה "AAABAABAA". אי-התאמה ב-

P[3]=\'B\'

. אין מופע מתאים. רישא של

P

שהיא סיפא של "AAABAABAA" היא "AA" (אורך 2). ההזזה:

12 - 2 = 10

. לכן,

Δ_{2} (4) = 10

.
- i=3: סיומת טובה "BAAABAABAA". אי-התאמה ב-

P[2]=\'A\'

. אין מופע מתאים. רישא של

P

שהיא סיפא של "BAAABAABAA" היא "AABAA" (אורך 5). ההזזה:

12 - 5 = 7

. לכן,

Δ_{2} (3) = 7

.
- i=2: סיומת טובה "ABAABAA". לא, P[2..12] = "A B A A A B A A B A A". אין מופע מתאים. רישא של

P

שהיא סיפא של

P [2..12]

היא "AA" (אורך 2). ההזזה:

12 - 2 = 10

. לכן,

Δ_{2} (2) = 10

.
- i=1: במקרה זה הסיומת היא כל התבנית. אין אי-התאמה לפני, ולכן הערך לא רלוונטי לחישוב הזזה. לרוב מגדירים

Δ_{2} (1) = 1

כדי להבטיח התקדמות. לכן,

Δ_{2} (1) = 1

.

הטבלה המלאה:

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

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