במדעי המחשב, אלגוריתם בויאר-מור הוא אלגוריתם חיפוש מחרוזות יעיל המשמש מדד השוואה סטנדרטי עבור אלגוריתמי חיפוש. האלגוריתם פותח על ידי החוקרים האמריקאים רוברט בויאר וג' סטרותר מור ב-1977.[1] האלגוריתם מבצע עיבוד מקדים למחרוזת החיפוש (התבנית), אך לא לטקסט שבו יבוצע החיפוש. האלגוריתם מתאים היטב אפוא ליישומים שבהם תבנית החיפוש קצרה בהרבה מהטקסט או למקרים שבהם נעשה שימוש חוזר בתבנית החיפוש. אלגוריתם בויאר-מור משתמש במידע הנאסף בשלב העיבוד המקדים על מנת לדלג על חלקים בטקסט, והודות לכך הוא משיג ביצועים טובים ביחס לאלגוריתמי חיפוש אחרים. באופן כללי, האלגוריתם רץ מהר יותר ככל שמחרוזת החיפוש ארוכה יותר. התכונות החשובות של האלגוריתם הן שהוא מחפש מסוף מחרוזת החיפוש ולא תחילתה, והוא מדלג בטקסט על מספר תווים במקום לחפש תו-תו.
אלגוריתם בויאר-מור מחפש מופעים של מחרוזת חיפוש P בטקסט שבו מחפשים T באמצעות השוואת תווים בעימודים שונים. במקום שימוש בחיפוש כוח גס של כל העימודים (ישנם כאלו), בויאר-מור משתמש במידע מעיבוד מקדים של תבנית החיפוש P על מנת לדלג על מספר עימודים גדול ככל האפשר.
לפני שהוצג אלגוריתם זה, השיטה הנהוגה לחיפוש טקסט הייתה לבדוק כל תו בטקסט ביחס לתו הראשון במחרוזת החיפוש, ואם נמצאה התאמה נעשה חיפוש בהתאם לתו הבא במחרוזת החיפוש וכן הלאה. בצורה זו נדרשים להשוות כל תו בטקסט.
ההבחנה החשובה באלגוריתם זה היא שאם סוף מחרוזת החיפוש מושוות לטקסט, ניתן לדלג על תווים בחיפוש ולא לבדוק כל תו בטקסט. הסיבה לכך היא שאם משווים את התו האחרון של תבנית החיפוש לתו בטקסט ואין התאמה, אין צורך לחפש אחורנית בתבנית החיפוש. אם התו בטקסט לא מתאים לאף אחד מהתווים בתבנית החיפוש, אז התו הבא להשוואה בטקסט נמצא n תווים בהמשך, כאשר n הוא אורך תבנית החיפוש. אם התו נמצא בתבנית החיפוש, נדרשת הזזה חלקית של תבנית החיפוש אל התו המתאים והתהליך חוזר על עצמו. החיפוש בטקסט באמצעות דילוגים לעריכת השוואות במקום לבדוק כל תו ותו מצמצם את מספר ההשוואות הנדרשות ובכך תורם ליעילות האלגוריתם.
באופן פורמלי יותר, האלגוריתם מתחיל בעימוד , כך שהתחלת תבנית החיפוש P מועמדת מול ההתחלה של הטקסט T. נערכת השוואה בין התווים ב-P וב-T אשר מתחילה מהאינדקס n בתבנית P ו-k ב-T, והולכת אחורה: המחרוזות מושוות ביחס לסופה של P ועד לתחילתה. ההשוואות ממשיכות עד הגעה לתחילתה של תבנית החיפוש P (במקרה של התאמה) או עד לאי התאמה שבעקבותיה העימוד מוזז קדימה בהתאם לערך המותר המרבי בהתאם למספר כללים. ההשוואות נערכות פעם נוספת בעימוד החדש, והתהליך חוזר על עצמו.
חוקי ההזזה ממומשים באמצעות טבלת חיפוש המוגדרת באמצעות עיבוד מקדים של תבנית החיפוש P.
כלל התו הלא מתאים מתייחס לתו ב-T שבו ההשוואה נכשלת. המופע הקודם של תו זה ב-P נמצא, ומוצעת הזזה המעבירה את המופע אל מול האי התאמה ב-P. אם התו הלא מתאים לא נמצא מלפני P, מוצעת הזזה המזיזה את P מעבר לתו הלא מתאים.
ישנן שיטות שונות בנוגע לטבלאות חיפוש עבור כלל התו הלא מתאים, להלן גרסה פשוטה הפועלת בזמן קבוע: יוצרים מערך דו־ממדי שבו האינדקס הראשון הוא התו c באלפבית והאינדקס השני הוא האינדקס i בתבנית החיפוש. טבלת החיפוש תחזיר את המופע של c ב P עם האינדקס השני בגודלו או אם לא נמצא מופע. ההסטה המוצעת תהיה , כשסיבוכיות הזמן הנדרשת היא וסיבוכיות המקום היא , בהנחה של אלפבית סופי באורך k.
כלל הסיפא הטובה הוא כלל מורכב יותר ביחס לכלל הקודם. הוא הסיבה לכך שההשוואות נעשות מסוף תבנית החיפוש ולא מתחילה. הכלל מוגדר כך:[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, אם קיימת כזו. אם לא קיימת כזו, הערך של יהיה אפס.
את שתי הטבלאות האלה ניתן לבנות בזמן ובמקום . עימוד ההזזה עבור האינדקס i ב P מוגדר להיות או .ב-H נעשה שימוש רק אם הוא אפס או שנמצאה התאמה.
אופטימיזציה פשוטה אבל חשובה של בויאר-מור הוצעה על ידי צבי גליל ב-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.
אלגוריתם בויאר-מור משמש גם את תוכנית החיפוש grep.[7]
מימוש פייתון
defalphabet_index(c):""" Returns the index of the given character in the English alphabet, counting from 0. """returnord(c.lower())-97# 'a' is ASCII character 97defmatch_length(S,idx1,idx2):""" Returns the length of the match of the substrings of S beginning at idx1 and idx2. """ifidx1==idx2:returnlen(S)-idx1match_count=0whileidx1<len(S)andidx2<len(S)andS[idx1]==S[idx2]:match_count+=1idx1+=1idx2+=1returnmatch_countdeffundamental_preprocess(S):""" Returns Z, the Fundamental Preprocessing of S. Z[i] is the length of the substring beginning at i which is also a prefix of S. This pre-processing is done in O(n) time, where n is the length of S. """iflen(S)==0:# Handles case of empty stringreturn[]iflen(S)==1:# Handles case of single-character stringreturn[1]z=[0forxinS]z[0]=len(S)z[1]=match_length(S,0,1)foriinrange(2,1+z[1]):# Optimization from exercise 1-5z[i]=z[1]-i+1# Defines lower and upper limits of z-boxl=0r=0foriinrange(2+z[1],len(S)):ifi<=r:# i falls within existing z-boxk=i-lb=z[k]a=r-i+1ifb<a:# b ends within existing z-boxz[i]=belse:# b ends at or after the end of the z-box, we need to do an explicit match to the right of the z-boxz[i]=a+match_length(S,a,r+1)l=ir=i+z[i]-1else:# i does not reside within existing z-boxz[i]=match_length(S,0,i)ifz[i]>0:l=ir=i+z[i]-1returnzdefbad_character_table(S):""" Generates R for S, which is an array indexed by the position of some character c in the English alphabet. At that index in R is an array of length |S|+1, specifying for each index i in S (plus the index after S) the next location of character c encountered when traversing S from right to left starting at i. This is used for a constant-time lookup for the bad character rule in the Boyer-Moore string search algorithm, although it has a much larger size than non-constant-time solutions. """iflen(S)==0:return[[]forainrange(26)]R=[[-1]forainrange(26)]alpha=[-1forainrange(26)]fori,cinenumerate(S):alpha[alphabet_index(c)]=iforj,ainenumerate(alpha):R[j].append(a)returnRdefgood_suffix_table(S):""" Generates L for S, an array used in the implementation of the strong good suffix rule. L[i] = k, the largest position in S such that S[i:] (the suffix of S starting at i) matches a suffix of S[:k] (a substring in S ending at k). Used in Boyer-Moore, L gives an amount to shift P relative to T such that no instances of P in T are skipped and a suffix of P[:L[i]] matches the substring of T matched by a suffix of P in the previous match attempt. Specifically, if the mismatch took place at position i-1 in P, the shift magnitude is given by the equation len(P) - L[i]. In the case that L[i] = -1, the full shift table is used. Since only proper suffixes matter, L[0] = -1. """L=[-1forcinS]N=fundamental_preprocess(S[::-1])# S[::-1] reverses SN.reverse()forjinrange(0,len(S)-1):i=len(S)-N[j]ifi!=len(S):L[i]=jreturnLdeffull_shift_table(S):""" Generates F for S, an array used in a special case of the good suffix rule in the Boyer-Moore string search algorithm. F[i] is the length of the longest suffix of S[i:] that is also a prefix of S. In the cases it is used, the shift magnitude of the pattern P relative to the text T is len(P) - F[i] for a mismatch occurring at i-1. """F=[0forcinS]Z=fundamental_preprocess(S)longest=0fori,zvinenumerate(reversed(Z)):longest=max(zv,longest)ifzv==i+1elselongestF[-i-1]=longestreturnFdefstring_search(P,T):""" Implementation of the Boyer-Moore string search algorithm. This finds all occurrences of P in T, and incorporates numerous ways of pre-processing the pattern to determine the optimal amount to shift the string and skip comparisons. In practice it runs in O(m) (and even sublinear) time, where m is the length of T. This implementation performs a case-insensitive search on ASCII alphabetic characters, spaces not included. """iflen(P)==0orlen(T)==0orlen(T)<len(P):return[]matches=[]# PreprocessingR=bad_character_table(P)L=good_suffix_table(P)F=full_shift_table(P)k=len(P)-1# Represents alignment of end of P relative to Tprevious_k=-1# Represents alignment in previous phase (Galil's rule)whilek<len(T):i=len(P)-1# Character to compare in Ph=k# Character to compare in Twhilei>=0andh>previous_kandP[i]==T[h]:# Matches starting from end of Pi-=1h-=1ifi==-1orh==previous_k:# Match has been found (Galil's rule)matches.append(k-len(P)+1)k+=len(P)-F[1]iflen(P)>1else1else:# No match, shift by max of bad character and good suffix ruleschar_shift=i-R[alphabet_index(T[h])][i]ifi+1==len(P):# Mismatch happened on first attemptsuffix_shift=1elifL[i+1]==-1:# Matched suffix does not appear anywhere in Psuffix_shift=len(P)-F[i+1]else:# Matched suffix appears in Psuffix_shift=len(P)-L[i+1]shift=max(char_shift,suffix_shift)previous_k=kifshift>=i+1elseprevious_k# Galil's rulek+=shiftreturnmatches
מימוש ב-C
#include<stdint.h>#include<stdlib.h>#define ALPHABET_LEN 256#define NOT_FOUND patlen#define max(a, b) ((a < b) ? b : a)// delta1 table: delta1[c] contains the distance between the last// character of pat and the rightmost occurrence of c in pat.// If c does not occur in pat, then delta1[c] = patlen.// If c is at string[i] and c != pat[patlen-1], we can// safely shift i over by delta1[c], which is the minimum distance// needed to shift pat forward to get string[i] lined up // with some character in pat.// this algorithm runs in alphabet_len+patlen time.voidmake_delta1(int*delta1,uint8_t*pat,int32_tpatlen){inti;for(i=0;i<ALPHABET_LEN;i++){delta1[i]=NOT_FOUND;}for(i=0;i<patlen-1;i++){delta1[pat[i]]=patlen-1-i;}}// true if the suffix of word starting from word[pos] is a prefix // of wordintis_prefix(uint8_t*word,intwordlen,intpos){inti;intsuffixlen=wordlen-pos;// could also use the strncmp() library function herefor(i=0;i<suffixlen;i++){if(word[i]!=word[pos+i]){return0;}}return1;}// length of the longest suffix of word ending on word[pos].// suffix_length("dddbcabc", 8, 4) = 2intsuffix_length(uint8_t*word,intwordlen,intpos){inti;// increment suffix length i to the first mismatch or beginning// of the wordfor(i=0;(word[pos-i]==word[wordlen-1-i])&&(i<pos);i++);returni;}// delta2 table: given a mismatch at pat[pos], we want to align // with the next possible full match could be based on what we// know about pat[pos+1] to pat[patlen-1].//// In case 1:// pat[pos+1] to pat[patlen-1] does not occur elsewhere in pat,// the next plausible match starts at or after the mismatch.// If, within the substring pat[pos+1 .. patlen-1], lies a prefix// of pat, the next plausible match is here (if there are multiple// prefixes in the substring, pick the longest). Otherwise, the// next plausible match starts past the character aligned with // pat[patlen-1].// // In case 2:// pat[pos+1] to pat[patlen-1] does occur elsewhere in pat. The// mismatch tells us that we are not looking at the end of a match.// We may, however, be looking at the middle of a match.// // The first loop, which takes care of case 1, is analogous to// the KMP table, adapted for a 'backwards' scan order with the// additional restriction that the substrings it considers as // potential prefixes are all suffixes. In the worst case scenario// pat consists of the same letter repeated, so every suffix is// a prefix. This loop alone is not sufficient, however:// Suppose that pat is "ABYXCDBYX", and text is ".....ABYXCDEYX".// We will match X, Y, and find B != E. There is no prefix of pat// in the suffix "YX", so the first loop tells us to skip forward// by 9 characters.// Although superficially similar to the KMP table, the KMP table// relies on information about the beginning of the partial match// that the BM algorithm does not have.//// The second loop addresses case 2. Since suffix_length may not be// unique, we want to take the minimum value, which will tell us// how far away the closest potential match is.voidmake_delta2(int*delta2,uint8_t*pat,int32_tpatlen){intp;intlast_prefix_index=patlen-1;// first loopfor(p=patlen-1;p>=0;p--){if(is_prefix(pat,patlen,p+1)){last_prefix_index=p+1;}delta2[p]=last_prefix_index+(patlen-1-p);}// second loopfor(p=0;p<patlen-1;p++){intslen=suffix_length(pat,patlen,p);if(pat[p-slen]!=pat[patlen-1-slen]){delta2[patlen-1-slen]=patlen-1-p+slen;}}}uint8_t*boyer_moore(uint8_t*string,uint32_tstringlen,uint8_t*pat,uint32_tpatlen){inti;intdelta1[ALPHABET_LEN];int*delta2=(int*)malloc(patlen*sizeof(int));make_delta1(delta1,pat,patlen);make_delta2(delta2,pat,patlen);// The empty pattern must be considered speciallyif(patlen==0){free(delta2);returnstring;}i=patlen-1;while(i<stringlen){intj=patlen-1;while(j>=0&&(string[i]==pat[j])){--i;--j;}if(j<0){free(delta2);return(string+i+1);}i+=max(delta1[string[i]],delta2[j]);}free(delta2);returnNULL;}
![{\displaystyle [1,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c79af450e22e8fd23f28e6be4cb23a47b24c1ba)
![{\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)
![{\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)
