אלגוריתם בויאר-מור
במדעי המחשב, אלגוריתם בויאר-מור הוא אלגוריתם חיפוש מחרוזות יעיל המשמש מדד השוואה סטנדרטי עבור אלגוריתמי חיפוש. האלגוריתם פותח על ידי החוקרים האמריקאים רוברט בויאר וג' סטרותר מור ב-1977.[1] האלגוריתם מבצע עיבוד מקדים למחרוזת החיפוש (התבנית), אך לא לטקסט שבו יבוצע החיפוש. האלגוריתם מתאים היטב אפוא ליישומים שבהם תבנית החיפוש קצרה בהרבה מהטקסט או למקרים שבהם נעשה שימוש חוזר בתבנית החיפוש. אלגוריתם בויאר-מור משתמש במידע הנאסף בשלב העיבוד המקדים על מנת לדלג על חלקים בטקסט, והודות לכך הוא משיג ביצועים טובים ביחס לאלגוריתמי חיפוש אחרים. באופן כללי, האלגוריתם רץ מהר יותר ככל שמחרוזת החיפוש ארוכה יותר. התכונות החשובות של האלגוריתם הן שהוא מחפש מסוף מחרוזת החיפוש ולא תחילתה, והוא מדלג בטקסט על מספר תווים במקום לחפש תו-תו.
הגדרות עריכה
| A | N | P | A | N | M | A | N | - |
| P | A | N | - | - | - | - | - | - |
| - | P | A | N | - | - | - | - | - |
| - | - | P | A | N | - | - | - | - |
| - | - | - | P | A | N | - | - | - |
| - | - | - | - | P | A | N | - | - |
| - | - | - | - | - | P | A | N | - |
- [S[i יסמן את התו באינדקס ה-i של המחרוזת S, החל מ-1.
- [S[i..j יסמן את תת-המחרוזת ב S אשר מתחילה בתו i ומסתיימת בתו j, כולל.
- תחילית של S היא תת-מחרוזת S[1..i] עבור i כלשהו בטווח , כאשר n היא אורך המחרוזת S.
- סיפא של S היא תת-מחרוזת S[i..n] עבור i כלשהו בטווח [1, n], כאשר n היא אורך המחרוזת S.
- מחרוזת החיפוש תסומן באמצעות P ותקרא לעיתים תבנית החיפוש. האורך שלה יסומן באמצעות n.
- הטקסט שבו מחפשים את מחרוזת החיפוש מסומן באמצעות T. האורך שלו יסומן באמצעות m.
- עימוד של P ל T הוא אינדקס k ב T שבו התו האחרון של P מועמד מול האינדקס k של T.
- התאמה של P קוראת בעימוד אם P שווה ל T[(k-n+1)..k].
![{\displaystyle [1,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c79af450e22e8fd23f28e6be4cb23a47b24c1ba)
תיאור עריכה
אלגוריתם בויאר-מור מחפש מופעים של מחרוזת חיפוש P בטקסט שבו מחפשים T באמצעות השוואת תווים בעימודים שונים. במקום שימוש בחיפוש כוח גס של כל העימודים (ישנם כאלו), בויאר-מור משתמש במידע מעיבוד מקדים של תבנית החיפוש P על מנת לדלג על מספר עימודים גדול ככל האפשר.
לפני שהוצג אלגוריתם זה, השיטה הנהוגה לחיפוש טקסט הייתה לבדוק כל תו בטקסט ביחס לתו הראשון במחרוזת החיפוש, ואם נמצאה התאמה נעשה חיפוש בהתאם לתו הבא במחרוזת החיפוש וכן הלאה. בצורה זו נדרשים להשוות כל תו בטקסט.
ההבחנה החשובה באלגוריתם זה היא שאם סוף מחרוזת החיפוש מושוות לטקסט, ניתן לדלג על תווים בחיפוש ולא לבדוק כל תו בטקסט. הסיבה לכך היא שאם משווים את התו האחרון של תבנית החיפוש לתו בטקסט ואין התאמה, אין צורך לחפש אחורנית בתבנית החיפוש. אם התו בטקסט לא מתאים לאף אחד מהתווים בתבנית החיפוש, אז התו הבא להשוואה בטקסט נמצא n תווים בהמשך, כאשר n הוא אורך תבנית החיפוש. אם התו נמצא בתבנית החיפוש, נדרשת הזזה חלקית של תבנית החיפוש אל התו המתאים והתהליך חוזר על עצמו. החיפוש בטקסט באמצעות דילוגים לעריכת השוואות במקום לבדוק כל תו ותו מצמצם את מספר ההשוואות הנדרשות ובכך תורם ליעילות האלגוריתם.
באופן פורמלי יותר, האלגוריתם מתחיל בעימוד , כך שהתחלת תבנית החיפוש P מועמדת מול ההתחלה של הטקסט T. נערכת השוואה בין התווים ב-P וב-T אשר מתחילה מהאינדקס n בתבנית P ו-k ב-T, והולכת אחורה: המחרוזות מושוות ביחס לסופה של P ועד לתחילתה. ההשוואות ממשיכות עד הגעה לתחילתה של תבנית החיפוש P (במקרה של התאמה) או עד לאי התאמה שבעקבותיה העימוד מוזז קדימה בהתאם לערך המותר המרבי בהתאם למספר כללים. ההשוואות נערכות פעם נוספת בעימוד החדש, והתהליך חוזר על עצמו.
חוקי ההזזה ממומשים באמצעות טבלת חיפוש המוגדרת באמצעות עיבוד מקדים של תבנית החיפוש P.
כללי ההזזה עריכה
ההזזה מחושבת באמצעות שני כללים: כלל התו הלא מתאים, וכלל הסיפא הטובה. הזזה בפועל היא הערך המרבי המוגדר על ידי שני כללים אלו.
כלל התו הלא מתאים עריכה
תיאור עריכה
| - | - | - | - | X | - | - | K | - | - | - |
| A | N | P | A | N | M | A | N | A | M | - |
| - | N | N | A | A | M | A | N | - | - | - |
| - | - | - | N | N | A | A | M | A | N | - |
כלל התו הלא מתאים מתייחס לתו ב-T שבו ההשוואה נכשלת. המופע הקודם של תו זה ב-P נמצא, ומוצעת הזזה המעבירה את המופע אל מול האי התאמה ב-P. אם התו הלא מתאים לא נמצא מלפני P, מוצעת הזזה המזיזה את P מעבר לתו הלא מתאים.
עיבוד מקדים עריכה
ישנן שיטות שונות בנוגע לטבלאות חיפוש עבור כלל התו הלא מתאים, להלן גרסה פשוטה הפועלת בזמן קבוע: יוצרים מערך דו־ממדי שבו האינדקס הראשון הוא התו c באלפבית והאינדקס השני הוא האינדקס i בתבנית החיפוש. טבלת החיפוש תחזיר את המופע של c ב P עם האינדקס השני בגודלו או אם לא נמצא מופע. ההסטה המוצעת תהיה , כשסיבוכיות הזמן הנדרשת היא וסיבוכיות המקום היא , בהנחה של אלפבית סופי באורך k.
כלל הסיפא הטובה עריכה
תיאור עריכה
| - | - | - | - | X | - | - | K | - | - | - | - | - |
| M | A | N | P | A | N | A | M | A | N | A | P | - |
| A | N | A | M | P | N | A | M | - | - | - | - | - |
| - | - | - | - | A | N | A | M | P | N | A | M | - |
כלל הסיפא הטובה הוא כלל מורכב יותר ביחס לכלל הקודם. הוא הסיבה לכך שההשוואות נעשות מסוף תבנית החיפוש ולא מתחילה. הכלל מוגדר כך:[2]
נניח כי עבור עימוד מסוים של תבנית החיפוש P ו T, תת-מחרוזת t של T מתאימה לסיפא של P, אך יש אי התאמה בהשוואה הבאה (בתו הקודם). במקרה זה מחפשים, במידה וקיים, את העותק האחרון t' של t ב P כך ש t' אינה סיפא של P והתו הקודם ל t' ב P שונה מהתו הקודם ל t ב P. נעשית הסטה של P קדימה כך שתת-המחרוזת t' ב P מועמדת מול תת-המחרוזת t ב T. אם t' לא קיימת, מזיזים את ההתחלה של P כך שתעבור את סוף t'' ב T כך שהתחילית של התבנית המוסטת מתאימה לסיפא של t ב T. אם לא קיימת הסטה כזו, מסיטים את P ב n מקומות קדימה. אם נמצא מופע של P, אז מסיטים את P כך שהתחילית של P המוסטת תתאים לסיפא של המופע של P ב T. אם לא קיימת הסטה כזו, מסיטים את P ב n מקומות, כלומר, מסיטים את P שתעבור את t.
עיבוד מקדים עריכה
כלל הסיפא הטובה דורש שתי טבלאות: אחת לשימוש במקרה הכללי, ואחת לשימוש כאשר המקרה הכללי לא מחזיר תוצאה משמעותית או שמתקיימת התאמה. טבלאות אלה יסומנו L ו - H בהתאמה. ההגדרות שלהן הם כדלקמן:[2]
עבור כל תו i, הוא העמדה הגדולה ביותר שקטנה מ-n כך שהמחרוזת מתאימה לסיומת של כך שהתו הקודם לסיומת לא שווה . מוגדר להיות אפס אם אין עמדה המקיימת את התנאי.
נגדיר את [H[i כסיומת הארוכה ביותר של שהיא גם קידומת של P, אם קיימת כזו. אם לא קיימת כזו, הערך של יהיה אפס.
![{\displaystyle L[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f505bfd1424f010a620a5a78e2f175653949230c)
![{\displaystyle P[i..n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db3179eb72b3124f39c39a3d781c47bf1e26daac)
![{\displaystyle P[1..L[i]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ab9c5431f611e9b3d65a8385c6fecbbe2b7402c)
![{\displaystyle P[i-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/684dd0cf230387708cb8a649188c273134e8b10d)
![{\displaystyle H[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e0d1e646ae278fb8ce6fc87c85e9cf2f61fcd0)
את שתי הטבלאות האלה ניתן לבנות בזמן ובמקום . עימוד ההזזה עבור האינדקס i ב P מוגדר להיות או .ב-H נעשה שימוש רק אם הוא אפס או שנמצאה התאמה.
![{\displaystyle n-L[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc4e8398110e727ecc2a7aa5f9725eda4ae716e3)
![{\displaystyle n-H[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aa276517f98902dacacc36ded817eca08214a64)
כלל גליל עריכה
אופטימיזציה פשוטה אבל חשובה של בויאר-מור הוצעה על ידי צבי גליל ב-1979.[3] כלל גליל עוסק בהאצת ההשוואות שנעשות בכל עימוד, באמצעות דילוג על קטעים שידוע על התאמתם. נניח כי בעימוד k1, נעשית השוואה בין P ל T עד לתו c של T. אז אם P מוסט ל- k2 כך שתחילתו נמצאת בין c לבין k1, בשלב השוואה הבא הקידומת של P חייבת להתאים לתת המחרוזת [T[(k2 - n)..k1. לכן, אם ההשוואות מגיעות עד לעמדה k1 של T, ניתן להניח כי נמצא מופע של P מבלי לבדוק מעבר ל k1. בנוסף לשיפור היעילות של בויאר-מור, כלל גליל נדרש על מנת להוכיח זמן ריצה ליניארי במקרה הגרוע ביותר.
זמן ריצה עריכה
זמן הריצה במקרה הגרוע ביותר של אלגוריתם בויאר-מור כפי שהוצג במאמר המקורי הוא , רק אם תבנית החיפוש אינה מופיעה בטקסט. תוצאה זו הוכחה לראשונה על ידי קנות', מוריס ופראט בשנת 1977,[4] ואחרי כן על ידי גוביאס ואודליזקו ב-1980[5] עם חסם עליון של 5n השוואות במקרה הגרוע ביותר. ריצ'רד קול סיפק הוכחה עם חסם עליון של 3n השוואות במקרה הגרוע ביותר ב-1991.[6]
כאשר תבנית החיפוש נמצאת בטקסט, זמן ריצה של האלגוריתם המקורי הוא במקרה הגרוע ביותר. ניתן לראות זאת כאשר תבנית החיפוש והטקסט מורכבים מתו שחוזר על מנת. עם זאת, הכללתו של כלל גליל תורמת לזמן ריצה ליניארי בכל המקרים.[3][6]
מימושים עריכה
קיימים מימושים שונים במגוון שפות תכנות. ב - C++, ספריית Boost מספקת מימוש כללי של חיפוש בויאר-מור תחת ספריית Algorithm. ב-Go קיים מימוש בsearch.go.
קישורים חיצוניים עריכה
הערות שוליים עריכה
- ^ Boyer, Robert S.; Moore, J Strother (באוקטובר 1977). "A Fast String Searching Algorithm". Comm. ACM. New York, NY, USA: Association for Computing Machinery. 20 (10): 762–772. doi:10.1145/359842.359859. ISSN 0001-0782.
{{cite journal}}: (עזרה) - ^ 1 2 Gusfield, Dan (1999) [1997], "Chapter 2 - Exact Matching: Classical Comparison-Based Methods", Algorithms on Strings, Trees, and Sequences (1 ed.), Cambridge University Press, pp. 19–21, ISBN 0521585198
- ^ 1 2 Galil, Z. (בספטמבר 1979). "On improving the worst case running time of the Boyer-Moore string matching algorithm". Comm. ACM. New York, NY, USA: Association for Computing Machinery. 22 (9): 505–508. doi:10.1145/359146.359148. ISSN 0001-0782.
{{cite journal}}: (עזרה) - ^ Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). "Fast pattern matching in strings". SIAM Journal on Computing. 6 (2): 323–350. doi:10.1137/0206024.
- ^ Guibas, Odlyzko; Odlyzko, Andrew (1977). "A new proof of the linearity of the Boyer-Moore string searching algorithm". Proceedings of the 18th Annual Symposium on Foundations of Computer Science. Washington, DC, USA: IEEE Computer Society: 189–195. doi:10.1109/SFCS.1977.3.
- ^ 1 2 Cole, Richard (בספטמבר 1991). "Tight bounds on the complexity of the Boyer-Moore string matching algorithm". Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 224–233. ISBN 0-89791-376-0.
{{cite journal}}: (עזרה) - ^ https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html