אלגוריתם בויאר-מור

במדעי המחשב, אלגוריתם בויאר-מור הוא אלגוריתם חיפוש מחרוזות יעיל המשמש מדד השוואה סטנדרטי עבור אלגוריתמי חיפוש. האלגוריתם פותח על ידי החוקרים האמריקאים רוברט בויאר וג' סטרותר מור ב-1977. האלגוריתם מבצע עיבוד מקדים למחרוזת החיפוש (התבנית), אך לא לטקסט שבו יבוצע החיפוש. האלגוריתם מתאים היטב אפוא ליישומים שבהם תבנית החיפוש קצרה בהרבה מהטקסט או למקרים שבהם נעשה שימוש חוזר בתבנית החיפוש. אלגוריתם בויאר-מור משתמש במידע הנאסף בשלב העיבוד המקדים על מנת לדלג על חלקים בטקסט, והודות לכך הוא משיג ביצועים טובים ביחס לאלגוריתמי חיפוש אחרים. באופן כללי, האלגוריתם רץ מהר יותר ככל שמחרוזת החיפוש ארוכה יותר. התכונות החשובות של האלגוריתם הן שהוא מחפש מסוף מחרוזת החיפוש ולא תחילתה, והוא מדלג בטקסט על מספר תווים במקום לחפש תו-תו.

תיאור

אלגוריתם בויאר-מור מחפש מופעים של מחרוזת חיפוש P בטקסט שבו מחפשים T באמצעות השוואת תווים בעימודים שונים. במקום שימוש בחיפוש כוח גס של כל העימודים (ישנם  כאלו), בויאר-מור משתמש במידע מעיבוד מקדים של תבנית החיפוש P על מנת לדלג על מספר עימודים גדול ככל האפשר.
לפני שהוצג אלגוריתם זה, השיטה הנהוגה לחיפוש טקסט הייתה לבדוק כל תו בטקסט ביחס לתו הראשון במחרוזת החיפוש, ואם נמצאה התאמה נעשה חיפוש בהתאם לתו הבא במחרוזת החיפוש וכן הלאה. בצורה זו נדרשים להשוות כל תו בטקסט.
ההבחנה החשובה באלגוריתם זה היא שאם סוף מחרוזת החיפוש מושוות לטקסט, ניתן לדלג על תווים בחיפוש ולא לבדוק כל תו בטקסט. הסיבה לכך היא שאם משווים את התו האחרון של תבנית החיפוש לתו בטקסט ואין התאמה, אין צורך לחפש אחורנית בתבנית החיפוש. אם התו בטקסט לא מתאים לאף אחד מהתווים בתבנית החיפוש, אז התו הבא להשוואה בטקסט נמצא n תווים בהמשך, כאשר n הוא אורך תבנית החיפוש. אם התו נמצא בתבנית החיפוש, נדרשת הזזה חלקית של תבנית החיפוש אל התו המתאים והתהליך חוזר על עצמו. החיפוש בטקסט באמצעות דילוגים לעריכת השוואות במקום לבדוק כל תו ותו מצמצם את מספר ההשוואות הנדרשות ובכך תורם ליעילות האלגוריתם.
באופן פורמלי יותר, האלגוריתם מתחיל בעימוד , כך שהתחלת תבנית החיפוש P מועמדת מול ההתחלה של הטקסט T. נערכת השוואה בין התווים ב-P וב-T אשר מתחילה מהאינדקס n בתבנית P ו-k ב-T, והולכת אחורה: המחרוזות מושוות ביחס לסופה של P ועד לתחילתה. ההשוואות ממשיכות עד הגעה לתחילתה של תבנית החיפוש P (במקרה של התאמה) או עד לאי התאמה שבעקבותיה העימוד מוזז קדימה בהתאם לערך המותר המרבי בהתאם למספר כללים. ההשוואות נערכות פעם נוספת בעימוד החדש, והתהליך חוזר על עצמו.
חוקי ההזזה ממומשים באמצעות טבלת חיפוש המוגדרת באמצעות עיבוד מקדים של תבנית החיפוש P.

כללי ההזזה

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

עיבוד מקדים

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

עיבוד מקדים

כלל הסיפא הטובה דורש שתי טבלאות: אחת לשימוש במקרה הכללי, ואחת לשימוש כאשר המקרה הכללי לא מחזיר תוצאה משמעותית או שמתקיימת התאמה. טבלאות אלה יסומנו L ו - H בהתאמה. ההגדרות שלהן הם כדלקמן:
עבור כל תו i,‏  הוא העמדה הגדולה ביותר שקטנה מ-n כך שהמחרוזת  מתאימה לסיומת של  כך שהתו הקודם לסיומת לא שווה .‏   מוגדר להיות אפס אם אין עמדה המקיימת את התנאי.
נגדיר את [H[i כסיומת הארוכה ביותר של  שהיא גם קידומת של P, אם קיימת כזו. אם לא קיימת כזו, הערך של  יהיה אפס.
את שתי הטבלאות האלה ניתן לבנות בזמן  ובמקום . עימוד ההזזה עבור האינדקס i ב P מוגדר להיות  או .ב-H נעשה שימוש רק אם  הוא אפס או שנמצאה התאמה.

כלל גליל

אופטימיזציה פשוטה אבל חשובה של בויאר-מור הוצעה על ידי צבי גליל ב-1979. כלל גליל עוסק בהאצת ההשוואות שנעשות בכל עימוד, באמצעות דילוג על קטעים שידוע על התאמתם. נניח כי בעימוד k₁, נעשית השוואה בין P ל T עד לתו c של T. אז אם P מוסט ל- k₂ כך שתחילתו נמצאת בין c לבין k₁, בשלב השוואה הבא הקידומת של P חייבת להתאים לתת המחרוזת [T[(k₂ - n)..k₁. לכן, אם ההשוואות מגיעות עד לעמדה k₁ של T, ניתן להניח כי נמצא מופע של P מבלי לבדוק מעבר ל k₁. בנוסף לשיפור היעילות של בויאר-מור, כלל גליל נדרש על מנת להוכיח זמן ריצה ליניארי במקרה הגרוע ביותר.

זמן ריצה

זמן הריצה במקרה הגרוע ביותר של אלגוריתם בויאר-מור כפי שהוצג במאמר המקורי הוא , רק אם תבנית החיפוש אינה מופיעה בטקסט. תוצאה זו הוכחה לראשונה על ידי קנות', מוריס ופראט בשנת 1977,
ואחרי כן על ידי גוביאס ואודליזקו ב-1980 עם חסם עליון של 5n השוואות במקרה הגרוע ביותר. ריצ'רד קול סיפק הוכחה עם חסם עליון של 3n השוואות במקרה הגרוע ביותר ב-1991.
כאשר תבנית החיפוש נמצאת בטקסט, זמן ריצה של האלגוריתם המקורי הוא  במקרה הגרוע ביותר. ניתן לראות זאת כאשר תבנית החיפוש והטקסט מורכבים מתו שחוזר על מנת. עם זאת, הכללתו של כלל גליל תורמת לזמן ריצה ליניארי בכל המקרים.