الگوریتم بویر مور برای جستجوی الگو — راهنمای کاربردی
«جستجوی الگو» (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) نامیده می‌شود. پس از عدم تطابق، الگو تا هنگامی جا به جا می‌شود که:
- عدم تطابق به یک تطابق مبدل شود.
- الگوی 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) — به زبان ساده
مجموعه: برنامه نویسی, تشخیص الگو
Loading...