الگوریتم بویر-مور: چگونه قواعد کاراکتر بد و پسوند خوب جستجوی رشته‌ای زیرخطی را ممکن می‌کنند

در اکتبر ۱۹۷۷، دانشمندان علوم کامپیوتر، رابرت اس. بویر و جی استروتر مور، مقاله‌ای در نشریه ارتباطات ای‌سی‌ام منتشر کردند که نحوه جستجوی متن توسط کامپیوترها را دگرگون کرد. پیش از کار آن‌ها، یافتن یک کلمه خاص در داخل یک سند بزرگ نیازمند یک رویکرد ساده‌لوحانه بود: کامپیوتر حرف اول را بررسی می‌کرد و در صورت تطابق، به سراغ حرف دوم می‌رفت. اگر عدم تطابقی رخ می‌داد، الگوی جستجو دقیقاً یک کاراکتر به جلو می‌رفت و فرآیند از نو آغاز می‌شد. این بدان معنا بود که جستجوی یک کلمه ۱۰ کاراکتری در یک متن ۱۰۰۰ کاراکتری می‌توانست در بدترین حالت به ۱۰۰۰۰ مقایسه مجزا نیاز داشته باشد.[6]

بویر و مور دریافتند که خواندن از چپ به راست اساساً ناکارآمد است. الگوریتم آن‌ها الگوی جستجو را با متن تراز می‌کند، اما به جای بررسی کاراکتر اول، کاراکتر آخر را بررسی می‌کند. اگر آخرین کاراکتر الگو با کاراکتر متنی که با آن تراز شده مطابقت نداشته باشد، الگوریتم اطلاعات فوری و کاربردی به دست می‌آورد که چقدر می‌تواند با خیال راحت و بدون از دست دادن یک تطابق احتمالی به جلو بپرد.[4][6]

برای دستیابی به این پرش‌های بزرگ، الگوریتم قبل از شروع جستجو به یک مرحله مقدماتی متکی است. همان‌طور که سم اسپیلزبری، مهندس نرم‌افزار، اشاره می‌کند: «این الگوریتم رشته‌ای که قرار است جستجو شود (الگو) را پیش‌پردازش می‌کند، اما رشته‌ای که در آن جستجو انجام می‌شود (متن) را پیش‌پردازش نمی‌کند.» با تحلیل پیشاپیش عبارت جستجو، برنامه دو جدول جستجوی مجزا می‌سازد—یکی برای قاعده کاراکتر بد و دیگری برای قاعده پسوند خوب. این جداول دقیقاً تعیین می‌کنند که وقتی یک عدم تطابق اجتناب‌ناپذیر رخ می‌دهد، الگو چند فاصله می‌تواند جابه‌جا شود.[1]

قاعده کاراکتر بد اولین روش اکتشافی است. هنگامی که الگوریتم الگو را در برابر متن از راست به چپ مقایسه می‌کند و یک عدم تطابق می‌یابد، به کاراکتر مشکل‌ساز در متن اصلی نگاه می‌کند. اگر آن کاراکتر خاص در هیچ کجای الگوی جستجو وجود نداشته باشد، الگوریتم می‌داند که هیچ تطابقی نمی‌تواند با آن موقعیت همپوشانی داشته باشد. بنابراین بلافاصله کل الگو را از آن کاراکتر عبور می‌دهد. اگر الگو هفت حرف طول داشته باشد، یک عدم تطابق منفرد می‌تواند باعث یک پرش هفت کاراکتری شود و متن میانی را کاملاً نادیده بگیرد.[3][4]

با این حال، اگر کاراکتر نامنطبق متن در جای دیگری از الگوی جستجو وجود داشته باشد، قاعده کاراکتر بد الگو را فقط به اندازه‌ای جابه‌جا می‌کند که راست‌ترین محل وقوع آن کاراکتر در الگو با کاراکتر نامنطبق در متن تراز شود. این امر تضمین می‌کند که الگوریتم هرگز از روی یک تطابق معتبر پرش نمی‌کند، اما همچنان اغلب منجر به یک جهش چند کاراکتری می‌شود تا یک حرکت کند تک‌فاصله‌ای.[3][5]

قاعده کاراکتر بد به تنهایی قدرتمند است، اما یک نقطه ضعف دارد. اگر کاراکتر نامنطبق بسیار نزدیک به انتهای الگوی جستجو ظاهر شود، جابه‌جایی حاصل ممکن است ناچیز باشد، یا در برخی موارد خاص، از نظر تئوری می‌تواند یک جابه‌جایی منفی را پیشنهاد دهد. برای جلوگیری از توقف جستجو، بویر و مور یک روش اکتشافی موازی و دوم را معرفی کردند: قاعده پسوند خوب.[2][6]

قاعده پسوند خوب زمانی فعال می‌شود که الگوریتم با موفقیت چند کاراکتر را در انتهای الگو (پسوند خوب) تطبیق داده باشد، پیش از آنکه به یک عدم تطابق در سمت چپ‌تر برخورد کند. از آنجا که الگوریتم قبلاً تأیید کرده است که این توالی خاص از کاراکترها در متن وجود دارد، به جدول پیش‌پردازش‌شده خود مراجعه می‌کند تا وقوع بعدی همان توالی دقیق را در بخش‌های قبلی الگوی جستجو بیابد. سپس الگو را به جلو جابه‌جا می‌کند تا آن وقوع قبلی با متن تطبیق‌یافته تراز شود.[2][5]

اگر پسوند تطبیق‌یافته در هیچ کجای دیگر الگو ظاهر نشود، الگوریتم بررسی می‌کند که آیا پیشوندی از الگو با پسوندی از متنِ از قبل تطبیق‌یافته مطابقت دارد یا خیر. اگر چنین باشد، الگو را برای تراز کردن آن‌ها جابه‌جا می‌کند. اگر هیچ‌یک از این شرایط برآورده نشود، الگوریتم می‌داند که کل پسوند تطبیق‌یافته نمی‌تواند بخشی از یک تطابق همپوشان معتبر باشد و الگو را کاملاً از بخش تطبیق‌یافته عبور می‌دهد.[2][6]

در طول اجرا، الگوریتم بویر-مور در هر عدم تطابق، جابه‌جایی توصیه‌شده را هم از قاعده کاراکتر بد و هم از قاعده پسوند خوب محاسبه می‌کند. سپس به سادگی عدد بزرگتر را از بین این دو انتخاب می‌کند. این رویکرد اکتشافی دوگانه تضمین می‌کند که الگوریتم همیشه تهاجمی‌ترین پرش ایمن ممکن را در سراسر سند انجام می‌دهد.[5][6]

این پرش تهاجمی منجر به یک معیار عملکردی دور از انتظار می‌شود: پیچیدگی زمانی زیرخطی. در علوم کامپیوتر، الگوریتمی که هر کاراکتر را یک بار می‌خواند در زمان خطی عمل می‌کند که با O(n) نشان داده می‌شود. از آنجا که بویر-مور کاراکترها را نادیده می‌گیرد، بهترین عملکرد آن O(n/m) است، که در آن 'n' طول متن و 'm' طول الگو است. هرچه کلمه‌ای که جستجو می‌کنید طولانی‌تر باشد، الگوریتم سریع‌تر به پایان می‌رسد، زیرا یک الگوی طولانی‌تر امکان پرش‌های طولانی‌تری را فراهم می‌کند.[1][6]

کارایی بویر-مور آن را به منطق بنیادی برای ابزارهای جستجوی استاندارد تبدیل کرد. زمانی که یک توسعه‌دهنده از دستور grep گنو برای تجزیه گیگابایت‌ها لاگ سرور استفاده می‌کند، یا یک کاربر یک فایل پی‌دی‌اف حجیم را جستجو می‌کند، موتور زیربنایی غالباً نسخه‌ای از بویر-مور است. توانایی آن در پردازش متن با سرعتی بیشتر از خواندن متوالی آن از حافظه توسط کامپیوتر، جایگاه آن را به عنوان یک معیار در ادبیات تطبیق رشته تثبیت کرد.[1][6]

این الگوریتم بسته به مجموعه‌داده با محدودیت‌هایی مواجه است. در یک متن استاندارد انگلیسی با استفاده از الفبای ۲۵۶ کاراکتری اسکی، قاعده کاراکتر بد دائماً جابه‌جایی‌های عظیمی ایجاد می‌کند زیرا بیشتر کاراکترهای متن در یک الگوی جستجوی کوتاه ظاهر نمی‌شوند. با این حال، در بیوانفورماتیک، جایی که توالی‌های دی‌ان‌ای تنها از چهار حرف (A, C, G, T) تشکیل شده‌اند، کارایی قاعده کاراکتر بد کاهش می‌یابد. کاراکتر نامنطبق تقریباً همیشه در الگو وجود دارد که منجر به جابه‌جایی‌های بسیار کوتاهی می‌شود.[3][6]

برای رسیدگی به این موارد خاص، دانشمندان علوم کامپیوتر در دوره‌های بعد تغییراتی را توسعه دادند. الگوریتم بویر-مور-هورسپول که در سال ۱۹۸۰ منتشر شد، با کنار گذاشتن کامل قاعده پسوند خوب و تکیه بر یک قاعده کاراکتر بدِ کمی اصلاح‌شده که در سناریوهای حالت متوسط با الفبای بزرگ بهتر عمل می‌کند، منطق را ساده کرد. الگوریتم آپوستولیکو-جیانکارلو بعداً قاعده پسوند خوب را بهینه‌سازی کرد تا از مقایسه‌های اضافی هنگام جابه‌جایی الگو جلوگیری کند.[6]

نزدیک به ۵۰ سال پس از انتشار آن، بینش اصلی بویر و مور دست‌نخورده باقی مانده است. با صرف کسری از میلی‌ثانیه برای تحلیل عبارت جستجو قبل از نگاه کردن به سند، و با خواندن به عقب برای حرکت به جلو، نرم‌افزار از انجام کارهای غیرضروری اجتناب می‌کند. این الگوریتم دیکته می‌کند که سریع‌ترین راه برای یافتن یک سوزن در انبار کاه، این است که دقیقاً بدانید کدام قسمت‌های کاه را باید نادیده بگیرید.