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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم کامپیوتر الگوریتم جستجوی رشته بویر مور یکی از الگوریتم های مؤثر جستجوی رشته است که توسط رابرت بویر و جی استراسر مور در سال 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-n+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] خواهد بود.

منابع[ویرایش]

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