الگوریتم بویر مور

در علوم کامپیوتر الگوریتم جستجوی رشته بویر مور یکی از الگوریتم‌های موثر جستجوی رشته است که توسط رابرت بویر و جی استراسر مور در سال 1977 منتشر شده‌است. این الگوریتم رشته االگو را پیش پردازش می‌کند اما رشته متن را پیش پردازش نمی‌کند. این الگوریتم زمانی مناسب است که رشته الگو بسیار کوتاه‌تر از رشته متن باشد. این الگوریتم با استفاده از اطلاعاتی که از پیش پردازش الگو به دست می‌آورد بعضی از قسمت‌های متن را بررسی نمی‌کند. بنابراین نسبت به بسیاری از الگوریتم‌های دیگر ضریب ثابت پایین‌تری دارد. ایده اصلی الگوریتم این است که به جا اینکه سر الگو را با متن مقایسه کند انتهای الگو را با متن مقایسه می‌کند.
تعاریف
به کاراکتر i- ام رشته S اشاره می‌کند.
زیر رشته S از موقعیت i تا موقعیت j را نشان می‌دهد.
پیشوند رشته S زیر رشته است به‌طوری‌که i در بازه و n طول رشته S باشد.
پسوند رشته S زیر رشته است به‌طوری‌که i در بازه و n طول رشته S باشد.
رشته‌ای را که جستجو را برای آن انجام می‌دهیم الگو می‌نامیم و با P نمایش می‌دهیم.
رشته‌ای را که جستجو را در آن انجام می‌دهیم متن می‌نامیم و با T نمایش می‌دهیم.
طول رشته P را با n نشان می‌دهیم.
طول رشته T را با m نشان می‌دهیم.
هم طرازی رشته P با T موقعیتی مانند k است به‌طوری‌که آخرین حرف P با حرف موقعیت k- ام رشته T هم طراز شود.
تطابق P در یک هم طرازی اتفاق می‌افتد به‌طوری‌که P با معادل باشد.
الگوریتم بویر مور
الگوریتم بویر مور به دنبال تطابق‌های رشته P در رشته T به وسیله مقایسه کاراکتر در هم طرازی‌های متفاوت می‌گردد. به جای جستجوی خام همه هم طرازی‌های متفاوت (که تعداد آن‌ها n - m + 1 است) ، بویر مور از اطلاعات پیش پردازش P استفاده می‌کند تا جای که امکان دارد هم طرازی‌های کمتری را بررسی کند. راه معمول جستجوی یک متن مقایسه کاراکترهای آن با اولین کاراکتر الگو است. هنگامی که دو کاراکتر یکسان بودند مابقی کاراکترهای متن با کاراکترهای الگو مقایسه می‌شوند. اگر تطابقی وجود نداشت دوباره متن ، کاراکتر به کاراکتر برای پیدا کردن تطابق بررسی می‌شود. بنابراین بیشتر کاراکترهای متن باید بررسی شود. نکته کلیدی این الگوریتم این است که با مقایسه انتهای الگو با کاراکترهای متن بسیاری از کاراکترهای متن را بررسی نمی‌کند. چراکه اگر دو کاراکتر یکسان نباشند نیاز نیست تا تمام کاراکترهای دیگر را عقب گرد بررسی کنیم. نکته جالب اینجاست که اگر این کاراکتر با هیچکدام از کاراکترهای الگو یکسان نباشد ، کاراکتر بعدی که در متن نیاز به بررسی در متن دارد ؛ n (طول الگو) موقعیت جلوتر است. اگر این کاراکتر در الگو وجود داشت یک انتقال جزئی صورت می‌گیرد تا این دو کاراکتر زیر هم قرار گیرند. این انتقال‌ها باعث می‌شود که تعداد کاراکترهایی که باید بررسی شوند کاهش یابد.
به‌طور دقیقتر، الگوریتم با هم طرازی k = n شروع می‌شود؛ بنابراین شروع P با شروع T هم طراز می‌شود. سپس کاراکترهای P و T از موقعیت n ام به صورت عقبگرد با هم مقایسه می‌شوند. مقایسه ادامه می‌یابد تا هنگامی که یا به ابتدای p برسیم(یک تطابق پیدا کردیم) ؛ یا عدم تطابق مشاهده شود که در این صورت با استفاده از قوانین زیر الگو را بیشترین مقدار ممکن انتقال می‌دهیم و مقایسه‌ها در هم طرازی جدید انجام می‌شود. این روند تا جایی ادامه می‌یابد که که الگو به مکانی بعد از انتهای T انتقال یابد که به این معناست که تطابق جدیدی وجود ندارد.انتقال‌ها با استفاده از جداولی که از پیش پردازش P به دست می‌آید در اجرا می‌شود.
قوانین انتقال
قانون کاراکتر بد
توضیح
قانون کاراکتر بد ، کاراکترهایی از T را مد نظر قرار می‌دهد که موجب می‌شوند عمل مقایسه شکست بخورد. اولین موقعیتی در سمت چپ P که آن کاراکتر وجود داشته باشد پیدا می‌شود و الگو تا جایی که این دو کاراکتر منطبق شوند انتقال می‌یابد. اگر این کاراکتر در متن وجود نداشت الگو به بعد از مکان این کاراکتر انتقال می‌یابد.
پیش پردازش
روش‌های متفاوتی برای این کار موجود است که یکی از آن‌ها را اینجا بیان می‌کنیم : یک جدول دو بعدی که سطر آن متناظر با کاراکتر c ام در الفبا و ستون آن متناظر با کاراکتر i ام‌الگو است را در نظر بگیرید. سطر c ام ، ستون i ام این جدول بزرگترین j ای از P را نشان می‌دهد که Pj = c و j <i و اگر همچین کاراکتری وجود نداشت برابر با -1 خواهد بود. در این صورت انتقال در به اندازه i - j خواهد بود و با فرض متناهی بودن الفبا با اندازه k به میزان فضا نیاز است.
قانون پسوند خوب
توضیح
قانون پسوند خوب اندکی پیچیده‌تر از قانون کاراکتر بد است. دلیل اصلی اینکه الگو را از انتها به صورت عقبگرد بررسی می‌کنیم همین قانون است.
فرض کنید برای یک هم طرازی T و P ، یک زیررشته مانند t از T با پسوندی از P مطابق باشد؛ اما کاراکتر بعدی در سمت چپ این پسوند با کاراکتر متناظر خود یکسان نباشد. حال فرض کنید که ’t سمت راست‌ترین زیررشته‌ای از P که باشد که یکسان با t است ولی پسوند P نیست و کاراکتر سمت چپ آن با کاراکتر سمت چپ t فرق می‌کند. اگر ’t وجود نداشت ، سمت چپ P را به بعد از سمت چپ t و اولین جایی که پیشوندی از P با پسوندی از t در T مطابق شود. اگر همچین انتقالی ممکن نبود ، P را n موقعیت به سمت راست انتقال می‌دهیم. اگر تطابقی از P پیدا شد ، P را به اولین جایی انتقال می‌دهیم که پیشوندی از P با پسوندی از آن تطابق در T مطابق شود. اگر چنین انتقالی ممکن نبود ، P را n موقعیت انتقال می‌دهیم.
پیش پردازش
قانون پسوند خوب به دو جدول نیازمند است : یکی برای حالت کلی ، و یکی برای زمانی که جدول اولی چیز بامعنایی نداشت یا یک تطابق پیدا شد. این جداول را به ترتیب با L و H نشان می‌دهیم. تعریف این دو به صورت زیر است :
برای هر ، بزرگترین مکان کمتر از n است که مطابق با پسوندی از باشد به‌طوری‌که کاراکتر سمت چپ این پسوند با برابر نباشد. اگر چنین شرایطی برقرار نباشد را برابر با صفر تعریف می‌کنیم.
نشان دهنده طول بزرگترین پسوندی از که پیشوند P نیز باشد.در این حالت هم اگر چنین پسوندی وجود نداشت را برابر با صفر تعریف می‌کنیم.
هر دوی این جداول فضا مصرف می‌کنند و قابل ساخت در زمان هستند. میزان انتقال در موقعیت i از P برابر با خواهد بود. اگر این مقدار برابر با صفر بود ، میزان انتقال برابر با خواهد بود.