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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

במדעי המחשב, אלגוריתם בויאר-מור הוא אלגוריתם חיפוש מחרוזות יעיל המשמש מדד השוואה סטנדרטי עבור אלגוריתמי חיפוש. האלגוריתם פותח על ידי החוקרים האמריקאים רוברט בויאר וג' סטרותר מור ב-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 -
עימודים של התבנית PAN על הטקסט ANPANMAN, מ k=3 ועד k=8. התאמה נמצאת ב k=5.
  • [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].

תיאור

אלגוריתם בויאר-מור מחפש מופעים של מחרוזת חיפוש 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 -
הדגמה של הכלל עבור תבנית החיפוש NNAAMAN.

כלל התו הלא מתאים מתייחס לתו ב-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 -
הדגמה של הכלל עבור תבנית החיפוש ANAMPNAM.

כלל הסיפא הטובה הוא כלל מורכב יותר ביחס לכלל הקודם. הוא הסיבה לכך שההשוואות נעשות מסוף תבנית החיפוש ולא מתחילה. הכלל מוגדר כך:[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]

מימוש פייתון 
def alphabet_index(c):
    """
    Returns the index of the given character in the English alphabet, counting from 0.
    """
    return ord(c.lower()) - 97 # 'a' is ASCII character 97

def match_length(S, idx1, idx2):
    """
    Returns the length of the match of the substrings of S beginning at idx1 and idx2.
    """
    if idx1 == idx2:
        return len(S) - idx1
    match_count = 0
    while idx1 < len(S) and idx2 < len(S) and S[idx1] == S[idx2]:
        match_count += 1
        idx1 += 1
        idx2 += 1
    return match_count

def fundamental_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.
    """
    if len(S) == 0: # Handles case of empty string
        return []
    if len(S) == 1: # Handles case of single-character string
        return [1]
    z = [0 for x in S]
    z[0] = len(S)
    z[1] = match_length(S, 0, 1)
    for i in range(2, 1+z[1]): # Optimization from exercise 1-5
        z[i] = z[1]-i+1
    # Defines lower and upper limits of z-box
    l = 0
    r = 0
    for i in range(2+z[1], len(S)):
        if i <= r: # i falls within existing z-box
            k = i-l
            b = z[k]
            a = r-i+1
            if b < a: # b ends within existing z-box
                z[i] = b
            else: # b ends at or after the end of the z-box, we need to do an explicit match to the right of the z-box
                z[i] = a+match_length(S, a, r+1)
                l = i
                r = i+z[i]-1
        else: # i does not reside within existing z-box
            z[i] = match_length(S, 0, i)
            if z[i] > 0:
                l = i
                r = i+z[i]-1
    return z

def bad_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.
    """
    if len(S) == 0:
        return [[] for a in range(26)]
    R = [[-1] for a in range(26)]
    alpha = [-1 for a in range(26)]
    for i, c in enumerate(S):
        alpha[alphabet_index(c)] = i
        for j, a in enumerate(alpha):
            R[j].append(a)
    return R

def good_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 = [-1 for c in S]
    N = fundamental_preprocess(S[::-1]) # S[::-1] reverses S
    N.reverse()
    for j in range(0, len(S)-1):
        i = len(S) - N[j]
        if i != len(S):
            L[i] = j
    return L

def full_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 = [0 for c in S]
    Z = fundamental_preprocess(S)
    longest = 0
    for i, zv in enumerate(reversed(Z)):
        longest = max(zv, longest) if zv == i+1 else longest
        F[-i-1] = longest
    return F

def string_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.
    """
    if len(P) == 0 or len(T) == 0 or len(T) < len(P):
        return []

    matches = []

    # Preprocessing
    R = 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 T
    previous_k = -1     # Represents alignment in previous phase (Galil's rule)
    while k < len(T):
        i = len(P) - 1  # Character to compare in P
        h = k           # Character to compare in T
        while i >= 0 and h > previous_k and P[i] == T[h]:   # Matches starting from end of P
            i -= 1
            h -= 1
        if i == -1 or h == previous_k:  # Match has been found (Galil's rule)
            matches.append(k - len(P) + 1)
            k += len(P)-F[1] if len(P) > 1 else 1
        else:   # No match, shift by max of bad character and good suffix rules
            char_shift = i - R[alphabet_index(T[h])][i]
            if i+1 == len(P):   # Mismatch happened on first attempt
                suffix_shift = 1
            elif L[i+1] == -1:   # Matched suffix does not appear anywhere in P
                suffix_shift = len(P) - F[i+1]
            else:               # Matched suffix appears in P
                suffix_shift = len(P) - L[i+1]
            shift = max(char_shift, suffix_shift)
            previous_k = k if shift >= i+1 else previous_k  # Galil's rule
            k += shift
    return matches
מימוש ב-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.
void make_delta1(int *delta1, uint8_t *pat, int32_t patlen) {
    int i;
    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 word
int is_prefix(uint8_t *word, int wordlen, int pos) {
    int i;
    int suffixlen = wordlen - pos;
    // could also use the strncmp() library function here
    for (i = 0; i < suffixlen; i++) {
        if (word[i] != word[pos+i]) {
            return 0;
        }
    }
    return 1;
}

// length of the longest suffix of word ending on word[pos].
// suffix_length("dddbcabc", 8, 4) = 2
int suffix_length(uint8_t *word, int wordlen, int pos) {
    int i;
    // increment suffix length i to the first mismatch or beginning
    // of the word
    for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
    return i;
}

// 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.
void make_delta2(int *delta2, uint8_t *pat, int32_t patlen) {
    int p;
    int last_prefix_index = patlen-1;

    // first loop
    for (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 loop
    for (p=0; p < patlen-1; p++) {
        int slen = 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_t stringlen, uint8_t *pat, uint32_t patlen) {
    int i;
    int delta1[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 specially
    if (patlen == 0) {
        free(delta2);
        return string;
    }

    i = patlen-1;
    while (i < stringlen) {
        int j = 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);
    return NULL;
}

קישורים חיצוניים

הערות שוליים

  1. ^ 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}}: (עזרה)
  2. ^ 2.0 2.1 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
  3. ^ 3.0 3.1 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}}: (עזרה)
  4. ^ 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.
  5. ^ 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.
  6. ^ 6.0 6.1 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}}: (עזרה)
  7. ^ https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

אוחזר מתוך "https://www.hamichlol.org.il/w/index.php?title=אלגוריתם_בויאר-מור&oldid=449327"