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

در علوم کامپیوتر الگوریتم جستجوی رشته بویر مور یکی از الگوریتم‌های مؤثر جستجوی رشته است که توسط رابرت بویر و جی استراسر مور در سال 1977 منتشر شده‌است. این الگوریتم رشته االگو را پیش پردازش می‌کند اما رشته متن را پیش پردازش نمی‌کند. این الگوریتم زمانی مناسب است که رشته الگو بسیار کوتاه‌تر از رشته متن باشد. این الگوریتم با استفاده از اطلاعاتی که از پیش پردازش الگو به دست می‌آورد بعضی از قسمت‌های متن را بررسی نمی‌کند. بنابراین نسبت به بسیاری از الگوریتم‌های دیگر ضریب ثابت پایین تری دارد. ایده اصلی الگوریتم این است که به جا اینکه سر الگو را با متن مقایسه کند انتهای الگو را با متن مقایسه می‌کند.

تعاریف

• $S[i]$ به کاراکتر i-ام رشته S اشاره می‌کند.
• $S[i..j]$ زیر رشته S از موقعیت i تا موقعیت j را نشان می‌دهد.
• پیشوند رشته S زیر رشته $S[1..i]$ است به‌طوری‌که i در بازه [1..n] و n طول رشته S باشد.
• پسوند رشته S زیر رشته $S[i..n]$ است به‌طوری‌که i در بازه [i..n] و n طول رشته S باشد.
• رشته‌ای را که جستجو را برای آن انجام می دهیم الگو می نامیم و با P نمایش می دهیم.
• رشته‌ای را که جستجو را در آن انجام می دهیم متن می نامیم و با T نمایش می دهیم.
• طول رشته P را با n نشان می دهیم.
• طول رشته T را با m نشان می دهیم.
• هم طرازی رشته P با T موقعیتی مانند k است به‌طوری‌که آخرین حرف P با حرف موقعیت k-ام رشته T هم طراز شود.
• تطابق P در یک هم طرازی اتفاق می افتد به‌طوری‌که P با $T[(k-m+1)..k]$ معادل باشد.

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

الگوریتم بویر مور به دنبال تطابق‌های رشته P در رشته T به وسیله مقایسه کاراکتر در هم طرازی‌های متفاوت می گردد. به جای جستجوی خام همه هم طرازی‌های متفاوت (که تعداد آن‌ها n - m + 1 است) ، بویر مور از اطلاعات پیش پردازش P استفاده می‌کند تا جای که امکان دارد هم طرازی‌های کمتری را بررسی کند. راه معمول جستجوی یک متن مقایسه کاراکترهای آن با اولین کاراکتر الگو است. هنگامی که دو کاراکتر یکسان بودند مابقی کاراکترهای متن با کاراکترهای الگو مقایسه می‌شوند. اگر تطابقی وجود نداشت دوباره متن ، کاراکتر به کاراکتر برای پیدا کردن تطابق بررسی می‌شود. بنابراین بیشتر کاراکترهای متن باید بررسی شود. نکته کلیدی این الگوریتم این است که با مقایسه انتهای الگو با کاراکترهای متن بسیاری از کاراکترهای متن را بررسی نمی‌کند. چراکه اگر دو کاراکتر یکسان نباشند نیاز نیست تا تمام کاراکترهای دیگر را عقب گرد بررسی کنیم. نکته جالب اینجاست که اگر این کاراکتر با هیچکدام از کاراکترهای الگو یکسان نباشد ، کاراکتر بعدی که در متن نیاز به بررسی در متن دارد ؛ n (طول الگو) موقعیت جلوتر است. اگر این کاراکتر در الگو وجود داشت یک انتقال جزئی صورت می‌گیرد تا این دو کاراکتر زیر هم قرار گیرند. این انتقال‌ها باعث می‌شود که تعداد کاراکترهایی که باید بررسی شوند کاهش یابد. به‌طور دقیقتر، الگوریتم با هم طرازی k = n شروع می‌شود؛ بنابراین شروع P با شروع T هم طراز می‌شود. سپس کاراکترهای P و T از موقعیت n ام به صورت عقبگرد با هم مقایسه می‌شوند. مقایسه ادامه می یابد تا هنگامی که یا به ابتدای p برسیم(یک تطابق پیدا کردیم) ؛ یا عدم تطابق مشاهده شود که در این صورت با استفاده از قوانین زیر الگو را بیشترین مقدار ممکن انتقال می دهیم و مقایسه‌ها در هم طرازی جدید انجام می‌شود. این روند تا جایی ادامه می یابد که که الگو به مکانی بعد از انتهای T انتقال یابد که به این معناست که تطابق جدیدی وجود ندارد.انتقال‌ها با استفاده از جداولی که از پیش پردازش P به دست می‌آید در $O(1)$ اجرا می‌شود.

قوانین انتقال

قانون کاراکتر بد

توضیح

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

پیش پردازش

روش‌های متفاوتی برای این کار موجود است که یکی از آن‌ها را اینجا بیان می کنیم : یک جدول دو بعدی که سطر آن متناظر با کاراکتر c ام در الفبا و ستون آن متناظر با کاراکتر i ام‌الگو است را در نظر بگیرید. سطر c ام ، ستون i ام این جدول بزرگترین j ای از P را نشان می دهد که P[j] = c و j <i و اگر همچین کاراکتری وجود نداشت برابر با -1 خواهد بود. در این صورت انتقال در $O(1)$ به اندازه i - j خواهد بود و با فرض متناهی بودن الفبا با اندازه k به میزان $O(kn)$ فضا نیاز است.

قانون پسوند خوب

توضیح

قانون پسوند خوب اندکی پیچیده تر از قانون کاراکتر بد است. دلیل اصلی اینکه الگو را از انتها به صورت عقبگرد بررسی می کنیم همین قانون است. فرض کنید برای یک هم طرازی 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 نشان می دهیم. تعریف این دو به صورت زیر است : برای هر $L[i]$ ، بزرگترین مکان کمتر از n است که $P[i..n]$ مطابق با پسوندی از $P[1..L[i]]$ باشد به‌طوری‌که کاراکتر سمت چپ این پسوند با $P[i-1]$ برابر نباشد. اگر چنین شرایطی برقرار نباشد $L[i]$ را برابر با صفر تعریف می کنیم. $H[i]$ نشان دهنده طول بزرگترین پسوندی از $P[i..n]$ که پیشوند P نیز باشد.در این حالت هم اگر چنین پسوندی وجود نداشت $H[i]$ را برابر با صفر تعریف می کنیم. هر دوی این جداول $O(n)$ فضا مصرف می‌کنند و قابل ساخت در زمان $O(n)$ هستند. میزان انتقال در موقعیت i از P برابر با $n-L[i]$ خواهد بود. اگر این مقدار برابر با صفر بود ، میزان انتقال برابر با $n-H[i]$ خواهد بود.

منابع

ویکی‌پدیای انگلیسی