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