«جستجوی الگو» (Pattern Searching) یک مسئله مهم در علوم کامپیوتر است. هنگامی که فرد به دنبال یک رشته در یک فایل مربوط به ویرایشگرهای متن (نوت‌پد، ورد، لیبره‌آفیس و دیگر موارد)، مرورگر وب و یا «پایگاه داده» (Database) می‌گردد، الگوریتم‌های جستجوی الگو برای نمایش نتایج جستجو مورد استفاده قرار می‌گیرند. یک بیان متداول از مسئله این است که متن txt[0..n-1]‎ و الگوی pat[0..m-1]‎ داده شده است. هدف نوشتن تابع search(char pat[], char txt[])‎ است که همه وقوع‌های pat[]‎ در txt[]‎ را چاپ می‌کند. می‌توان فرض کرد که n > m است.

مثال‌ها:

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

در این مطلب، «الگوریتم جستجوی الگوی بویر مور» (Boyer Moore Pattern Searching Algorithm) مورد بررسی قرار خواهد کرد. همچون الگوریتم‌های KMS و «اتوماتای متنهای» (Finite Automata)، الگوریتم بویر مور نیز الگو را «پیش‌پرداز» (Preprocesses) می‌کند. بویر مور، ترکیبی از دو رویکرد زیر است:

• هیوریستیک کاراکتر بد
• هیوریستیک پسوند خوب

هر دو «هیوریستیک» (Heuristic) بالا را می‌توان به طور مستقل برای جستجوی یک الگو در متن استفاده کرد. اکنون، ابتدا چگونگی آنکه دو رویکرد مستقل در الگوریتم بویر مور با یکدیگر کار کنند مورد بررسی قرار می‌گیرد. با نگاهی به الگوریتم «بیز ساده» (Naive Algorithm)، می‌توان فهمید که این الگوریتم الگو را با اسلاید کردن متن به صورت یک به یک انجام می‌دهد. الگوریتم KMP روی الگو پیش‌پردازش انجام می‌دهد

الگوریتم بویر مور پیش‌پردازش را به دلایل مشابهی با KMP انجام می‌دهد. این الگوریتم، الگو را پیش‌پردازش می‌کند و آرایه‌های متفاوتی را برای هر دو هیوریستیک‌ها می‌سازد. در هر گام، این الگوریتم الگو را با حداکثر تعداد اسلایدهای پیشنهاد شده به وسیله دو هیوریستیک، اسلاید می‌کند. بنابراین، الگوریتم بویر مور در هر مرحله، بهترین هیوریستیک را از میان دو هیوریستیک موجود، استفاده می‌کند. در هر گام، این الگوریتم الگو را با بیشینه اسلایدهای پیشنهاد شده به وسیله دو هیوریستیک، اسلاید می‌کند. بنابراین، این الگوریتم از بهترین دو هیوریستیک موجود در هر گام استفاده می‌کند. برخلاف الگوی جستجوی پیشین، الگوریتم بویر مور تطبیق دادن را از آخرین کاراکتر الگو آغاز می‌کند. در این مطلب، هیوریستیک کاراکتر بد مورد بررسی قرار می‌گیرد.

هیوریستیک کاراکتر بد در الگوریتم بویر مور

ایده هیوریستیک کاراکتر بد، ساده است. کاراکتری از متن که با کاراکتر کنونی الگو مطابقت ندارد، «کاراکتر بد» (Bad Character) نامیده می‌شود. پس از عدم تطابق، الگو تا هنگامی جا به جا می‌شود که:

1. عدم تطابق به یک تطابق مبدل شود.
2. الگوی P کاراکتر تطبیق نیافته پیشین را حرکت دهد.

حالت ۱: عدم تطابق به تطابق مبدل می‌شود

موقعیت آخرین وقوع کاراکتر دارای عدم تطابق در الگو جستجو می‌شود و اگر کاراکتر دارای عدم تطابق در الگو وجود داشته باشد، الگو به گونه‌ای جابهجا می‌شود که با کاراکتر دارای عدم تطابق در متن T، تراز شود.

توصیف: در مثال بالا، یک عدم تطابق در موقعیت ۳ به وقوع می‌پیوندد. در اینجا، کاراکتر تطبیق نیافته «A» است. اکنون، جستجو برای آخرین وقوع A انجام می‌شود. اکنون، الگو ۲ بار شیفت داده می‌شود بنابراین، «A» در الگو با A در متن تراز می‌شود.

حالت ۲: الگو کاراکتر ناسازگار را پشت سر می‌گذارد

موقعیت آخرین وقوع کاراکتر دارای عدم تطابق در الگو جستجو می‌شود و اگر کاراکتر وجود نداشت، الگو آخرین کاراکتر دارای عدم تطابق را پشت سر می‌گذارد.

توصیف مثال موجود در تصویر: در اینجا، یک عدم تطابق در موقعیت ۷ وجود دارد. کاراکتر دارای عدم تطابق «C» در الگو پیش از موقعیت ۷ وجود ندارد، بنابراین، الگو به پس از موقعیت ۷ جابهجا می‌شود و در نهایت در مثال بالا، تطابق خوبی از الگو (به رنگ سبز نمایش داده شده است) ایجاد می‌شود. این کار بدین دلیل انجام می‌شود که «C» در الگو وجود ندارد؛ بنابراین، در هر جا به جایی پیش از موقعیت ۷، عدم تطابق حاصل می‌شود و جستجو بی‌ثمر خواهی بود.

در پیاده‌سازی که در ادامه آمده است، الگو پیش‌پردازش می‌شود و آخرین وقوع از هر کاراکتر ممکنی در آرایه با اندازه مشابه با اندازه الفبایی پیش‌پردازش می‌شود. اگر کاراکتر اصلا وجود نداشت، در نهایت ممکن است منجر به جا به جایی m (طول الگو) شود. بنابراین، هیوریستیک کاراکتر بد، به اندازه (O(n/m بار در بهترین حالت، زمان می‌برد.

پیاده‌سازی الگوریتم بویر مور در ++C

/* C++ Program for Bad Character Heuristic of Boyer  
Moore String Matching Algorithm */
#include <bits/stdc++.h> 
using namespace std; 
# define NO_OF_CHARS 256  
  
// The preprocessing function for Boyer Moore's  
// bad character heuristic  
void badCharHeuristic( string str, int size,  
                        int badchar[NO_OF_CHARS])  
{  
    int i;  
  
    // Initialize all occurrences as -1  
    for (i = 0; i < NO_OF_CHARS; i++)  
        badchar[i] = -1;  
  
    // Fill the actual value of last occurrence  
    // of a character  
    for (i = 0; i < size; i++)  
        badchar[(int) str[i]] = i;  
}  
  
/* A pattern searching function that uses Bad  
Character Heuristic of Boyer Moore Algorithm */
void search( string txt, string pat)  
{  
    int m = pat.size();  
    int n = txt.size();  
  
    int badchar[NO_OF_CHARS];  
  
    /* Fill the bad character array by calling  
    the preprocessing function badCharHeuristic()  
    for given pattern */
    badCharHeuristic(pat, m, badchar);  
  
    int s = 0; // s is shift of the pattern with  
                // respect to text  
    while(s <= (n - m))  
    {  
        int j = m - 1;  
  
        /* Keep reducing index j of pattern while  
        characters of pattern and text are  
        matching at this shift s */
        while(j >= 0 && pat[j] == txt[s + j])  
            j--;  
  
        /* If the pattern is present at current  
        shift, then index j will become -1 after  
        the above loop */
        if (j < 0)  
        {  
            cout << "pattern occurs at shift = " <<  s << endl;  
  
            /* Shift the pattern so that the next  
            character in text aligns with the last  
            occurrence of it in pattern.  
            The condition s+m < n is necessary for  
            the case when pattern occurs at the end  
            of text */
            s += (s + m < n)? m-badchar[txt[s + m]] : 1;  
  
        }  
  
        else
            /* Shift the pattern so that the bad character  
            in text aligns with the last occurrence of  
            it in pattern. The max function is used to  
            make sure that we get a positive shift.  
            We may get a negative shift if the last  
            occurrence of bad character in pattern  
            is on the right side of the current  
            character. */
            s += max(1, j - badchar[txt[s + j]]);  
    }  
}  
  
/* Driver code */
int main()  
{  
    string txt= "ABAAABCD";  
    string pat = "ABC";  
    search(txt, pat);  
    return 0;  
}  
   
 // This code is contributed by rathbhupendra 

پیاده‌سازی الگوریتم بویر مورد در سی

/* C Program for Bad Character Heuristic of Boyer  
   Moore String Matching Algorithm */
# include <limits.h> 
# include <string.h> 
# include <stdio.h> 
  
# define NO_OF_CHARS 256 
  
// A utility function to get maximum of two integers 
int max (int a, int b) { return (a > b)? a: b; } 
  
// The preprocessing function for Boyer Moore's 
// bad character heuristic 
void badCharHeuristic( char *str, int size,  
                        int badchar[NO_OF_CHARS]) 
{ 
    int i; 
  
    // Initialize all occurrences as -1 
    for (i = 0; i < NO_OF_CHARS; i++) 
         badchar[i] = -1; 
  
    // Fill the actual value of last occurrence  
    // of a character 
    for (i = 0; i < size; i++) 
         badchar[(int) str[i]] = i; 
} 
  
/* A pattern searching function that uses Bad 
   Character Heuristic of Boyer Moore Algorithm */
void search( char *txt,  char *pat) 
{ 
    int m = strlen(pat); 
    int n = strlen(txt); 
  
    int badchar[NO_OF_CHARS]; 
  
    /* Fill the bad character array by calling  
       the preprocessing function badCharHeuristic()  
       for given pattern */
    badCharHeuristic(pat, m, badchar); 
  
    int s = 0;  // s is shift of the pattern with  
                // respect to text 
    while(s <= (n - m)) 
    { 
        int j = m-1; 
  
        /* Keep reducing index j of pattern while  
           characters of pattern and text are  
           matching at this shift s */
        while(j >= 0 && pat[j] == txt[s+j]) 
            j--; 
  
        /* If the pattern is present at current 
           shift, then index j will become -1 after 
           the above loop */
        if (j < 0) 
        { 
            printf("\n pattern occurs at shift = %d", s); 
  
            /* Shift the pattern so that the next  
               character in text aligns with the last  
               occurrence of it in pattern. 
               The condition s+m < n is necessary for  
               the case when pattern occurs at the end  
               of text */
            s += (s+m < n)? m-badchar[txt[s+m]] : 1; 
  
        } 
  
        else
            /* Shift the pattern so that the bad character 
               in text aligns with the last occurrence of 
               it in pattern. The max function is used to 
               make sure that we get a positive shift.  
               We may get a negative shift if the last  
               occurrence  of bad character in pattern 
               is on the right side of the current  
               character. */
            s += max(1, j - badchar[txt[s+j]]); 
    } 
} 
  
/* Driver program to test above function */
int main() 
{ 
    char txt[] = "ABAAABCD"; 
    char pat[] = "ABC"; 
    search(txt, pat); 
    return 0; 
}

پیاده‌سازی الگوریتم بویر مور در جاوا

/* Java Program for Bad Character Heuristic of Boyer  
Moore String Matching Algorithm */
  
  
class AWQ{ 
      
     static int NO_OF_CHARS = 256; 
       
    //A utility function to get maximum of two integers 
     static int max (int a, int b) { return (a > b)? a: b; } 
  
     //The preprocessing function for Boyer Moore's 
     //bad character heuristic 
     static void badCharHeuristic( char []str, int size,int badchar[]) 
     { 
      int i; 
  
      // Initialize all occurrences as -1 
      for (i = 0; i < NO_OF_CHARS; i++) 
           badchar[i] = -1; 
  
      // Fill the actual value of last occurrence  
      // of a character 
      for (i = 0; i < size; i++) 
           badchar[(int) str[i]] = i; 
     } 
  
     /* A pattern searching function that uses Bad 
     Character Heuristic of Boyer Moore Algorithm */
     static void search( char txt[],  char pat[]) 
     { 
      int m = pat.length; 
      int n = txt.length; 
  
      int badchar[] = new int[NO_OF_CHARS]; 
  
      /* Fill the bad character array by calling  
         the preprocessing function badCharHeuristic()  
         for given pattern */
      badCharHeuristic(pat, m, badchar); 
  
      int s = 0;  // s is shift of the pattern with  
                  // respect to text 
      while(s <= (n - m)) 
      { 
          int j = m-1; 
  
          /* Keep reducing index j of pattern while  
             characters of pattern and text are  
             matching at this shift s */
          while(j >= 0 && pat[j] == txt[s+j]) 
              j--; 
  
          /* If the pattern is present at current 
             shift, then index j will become -1 after 
             the above loop */
          if (j < 0) 
          { 
              System.out.println("Patterns occur at shift = " + s); 
  
              /* Shift the pattern so that the next  
                 character in text aligns with the last  
                 occurrence of it in pattern. 
                 The condition s+m < n is necessary for  
                 the case when pattern occurs at the end  
                 of text */
              s += (s+m < n)? m-badchar[txt[s+m]] : 1; 
  
          } 
  
          else
              /* Shift the pattern so that the bad character 
                 in text aligns with the last occurrence of 
                 it in pattern. The max function is used to 
                 make sure that we get a positive shift.  
                 We may get a negative shift if the last  
                 occurrence  of bad character in pattern 
                 is on the right side of the current  
                 character. */
              s += max(1, j - badchar[txt[s+j]]); 
      } 
     } 
  
     /* Driver program to test above function */
    public static void main(String []args) { 
          
         char txt[] = "ABAAABCD".toCharArray(); 
         char pat[] = "ABC".toCharArray(); 
         search(txt, pat); 
    } 
}

پیاده‌سازی الگوریتم بویر مور در پایتون

# Python3 Program for Bad Character Heuristic 
# of Boyer Moore String Matching Algorithm  
  
NO_OF_CHARS = 256
  
def badCharHeuristic(string, size): 
    ''' 
    The preprocessing function for 
    Boyer Moore's bad character heuristic 
    '''
  
    # Initialize all occurrence as -1 
    badChar = [-1]*NO_OF_CHARS 
  
    # Fill the actual value of last occurrence 
    for i in range(size): 
        badChar[ord(string[i])] = i; 
  
    # retun initialized list 
    return badChar 
  
def search(txt, pat): 
    ''' 
    A pattern searching function that uses Bad Character 
    Heuristic of Boyer Moore Algorithm 
    '''
    m = len(pat) 
    n = len(txt) 
  
    # create the bad character list by calling  
    # the preprocessing function badCharHeuristic() 
    # for given pattern 
    badChar = badCharHeuristic(pat, m)  
  
    # s is shift of the pattern with respect to text 
    s = 0
    while(s <= n-m): 
        j = m-1
  
        # Keep reducing index j of pattern while  
        # characters of pattern and text are matching 
        # at this shift s 
        while j>=0 and pat[j] == txt[s+j]: 
            j -= 1
  
        # If the pattern is present at current shift,  
        # then index j will become -1 after the above loop 
        if j<0: 
            print("Pattern occur at shift = {}".format(s)) 
  
            '''     
                Shift the pattern so that the next character in text 
                      aligns with the last occurrence of it in pattern. 
                The condition s+m < n is necessary for the case when 
                   pattern occurs at the end of text 
               '''
            s += (m-badChar[ord(txt[s+m])] if s+m<n else 1) 
        else: 
            ''' 
               Shift the pattern so that the bad character in text 
               aligns with the last occurrence of it in pattern. The 
               max function is used to make sure that we get a positive 
               shift. We may get a negative shift if the last occurrence 
               of bad character in pattern is on the right side of the 
               current character. 
            '''
            s += max(1, j-badChar[ord(txt[s+j])]) 
  
  
# Driver program to test above function 
def main(): 
    txt = "ABAAABCD"
    pat = "ABC"
    search(txt, pat) 
  
if __name__ == '__main__': 
    main() 
  
# This code is contributed by Atul Kumar 
# (www.facebook.com/atul.kr.007)

پیاده‌سازی الگوریتم بویر مور در #C

/* C# Program for Bad Character Heuristic of Boyer  
Moore String Matching Algorithm */
  
using System; 
public class AWQ{  
      
    static int NO_OF_CHARS = 256;  
      
    //A utility function to get maximum of two integers  
    static int max (int a, int b) { return (a > b)? a: b; }  
  
    //The preprocessing function for Boyer Moore's  
    //bad character heuristic  
    static void badCharHeuristic( char []str, int size,int []badchar)  
    {  
    int i;  
  
    // Initialize all occurrences as -1  
    for (i = 0; i < NO_OF_CHARS; i++)  
        badchar[i] = -1;  
  
    // Fill the actual value of last occurrence  
    // of a character  
    for (i = 0; i < size; i++)  
        badchar[(int) str[i]] = i;  
    }  
  
    /* A pattern searching function that uses Bad  
    Character Heuristic of Boyer Moore Algorithm */
    static void search( char []txt, char []pat)  
    {  
    int m = pat.Length;  
    int n = txt.Length;  
  
    int []badchar = new int[NO_OF_CHARS];  
  
    /* Fill the bad character array by calling  
        the preprocessing function badCharHeuristic()  
        for given pattern */
    badCharHeuristic(pat, m, badchar);  
  
    int s = 0; // s is shift of the pattern with  
                // respect to text  
    while(s <= (n - m))  
    {  
        int j = m-1;  
  
        /* Keep reducing index j of pattern while  
            characters of pattern and text are  
            matching at this shift s */
        while(j >= 0 && pat[j] == txt[s+j])  
            j--;  
  
        /* If the pattern is present at current  
            shift, then index j will become -1 after  
            the above loop */
        if (j < 0)  
        {  
            Console.WriteLine("Patterns occur at shift = " + s);  
  
            /* Shift the pattern so that the next  
                character in text aligns with the last  
                occurrence of it in pattern.  
                The condition s+m < n is necessary for  
                the case when pattern occurs at the end  
                of text */
            s += (s+m < n)? m-badchar[txt[s+m]] : 1;  
  
        }  
  
        else
            /* Shift the pattern so that the bad character  
                in text aligns with the last occurrence of  
                it in pattern. The max function is used to  
                make sure that we get a positive shift.  
                We may get a negative shift if the last  
                occurrence of bad character in pattern  
                is on the right side of the current  
                character. */
            s += max(1, j - badchar[txt[s+j]]);  
    }  
    }  
  
    /* Driver program to test above function */
    public static void Main() {  
          
        char []txt = "ABAAABCD".ToCharArray();  
        char []pat = "ABC".ToCharArray();  
        search(txt, pat);  
    }  
}  
  
// This code is contributed by PrinciRaj19992 

خروجی پیاده‌سازی‌های بالا، به صورت زیر است.

 pattern occurs at shift = 4

هیوریستیک کاراکتر بد ممکن است در بدترین حالت، از درجه (O(mn زمان ببرد. بدترین حالت هنگامی به وقوع می‌پیوندد که همه کاراکترهای متن و الگو مشابه باشند. برای مثال، ”txt[] = “AAAAAAAAAAAAAAAAAA و ”pat[] = “AAAAA را داشته باشیم.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده

منبع [+]