java, جاوا, حل مسائل با جاوا, ساختمان داده در جاوا

الگوریتم Boyer Moore در جاوا (جستجوی رشته)

الگوریتم Boyer Moore در جاوا

در این جلسه تیم کدگیت را با آموزش الگوریتم Boyer Moore در جاوا همراهی کنید. الگوریتم Boyer Moore برای جستجوی رشته (Pattern) در یک متن استفاده می‌شود. در آموزش‌های قبلی الگوریتم‌هایی نظیر KMP برای جستجوی رشته را توضیح دادیم. در این قسمت الگوریتم Boyer Moore به همراه پیاده سازی آن را آموزش می‌دهیم. پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را بخوانید:

  1. الگوریتم KMP در جاوا
  2. شی گرایی در جاوا
  3. آرایه در جاوا
  4. حلقه for در جاوا
  5. If در جاوا
  6. متد در جاوا
  7. Constructor در جاوا

الگوریتم Boyer Moore

جستجوی الگو یا Pattern Search یکی از مسائل مهم در دنیای کامپیوتر است. وقتی ما به دنبال یک رشته در فایل notepad یا word می‌گردیم یا در مرورگر خود واژه‌ای را جستجو می‌کنیم از Pattern Search استفاده می‌کنیم. الگوریتم Boyer Moore یک الگوریتم جستجو الگو می‌باشد.

الگوریتم Boyer Moore برای پیدا کردن یک رشته در میان یک متن بکار می‌روند و مکان آن رشته بخصوص را در متن مشخص می‌کنند همانطور که در تصویر زیر می‌بینید این الگوریتم شامل دو قسمت Pattern (رشته‌ای که به دنبال آن هستیم) و Text (متنی که به دنبال Pattern در آن هستیم) می‌شود(در تصویر زیر T مخفف text و P مخفف Pattern است).

Boyer Moore برای جستجوی Pattern در متن برعکس الگوریتم‌هایی مانند KMP از انتها به دنبال تطابق می‌گردد. همانطور که در تصویر زیر می‌بینید ما یک متن به صورت  NYOONYOO داریم و رشته Pattern ما به صورت NOYO می‌باشد. حال برای جستجو NOYO در متن بجای اینکه از حرف اول Pattern شروع به جستجو در متن کنیم از حرف آخر شروع می‌کنیم و تطابق را بررسی می‌کنیم.

الگوریتم Boyer Moore چگونه کار می‌کند؟

قبل از پیاده‌سازی الگوریتم Boyer Moore در جاوا ما به توضیح نحوه کار الگوریتم پرداختیم. تاکنون می‌دانیم که این الگوریتم برای تطابق متن و Pattern از انتها شروع به بررسی حروف می‌کند. اما مراحل انجام این کار به چه صورت است؟

به طور کلی دو حالت عدم تطابق بین متن و Pattern پیش می‌آید:

  1. عدم تطابق بین حرفی باشد که در Pattern نباشد (مثلا حرف C در pattern با متن AABB وجود ندارد). در این صورت ما ادامه جستجو را از حرف بعد از عدم تطابق ادامه می‌دهیم.
  2. عدم تطابق بین حرفی باشد که در Pattern وجود دارد. فرض کنید حرف عدم تطابق ما N باشد. در این صورت جستجو را طوری ادامه می‌دهیم که سمت راست‌ترین حرف N در Pattern با متن تطابق داشته باشد(چرا؟).

فرض کنید متن ما GCAATGCCTATG و Pattern با متن TATGTG داریم. می‌خواهیم آن را بررسی کنیم.

همانطور که در تصویر فوق می‌بینید حرف A در متن با حرف G در PATTERN تطابق ندارد. حرف A (حرف عدم تطابق ما) درون Pattern وجود دارد. پس حالت دوم عدم تطابق برای ما اتفاق می‌افتد. ما باید طوری جستجو را ادامه دهیم که حرف A در متن با حرف A در Pattern در یک قسمت باشند(مانند تصویر زیر).

حال تصویر فوق را ببینید. حرف G با C مقایسه می‌کنیم. از آنجایی که C در Pattern وجود ندارد جستجو را از حرف بعد از C ادامه می‌دهیم. این حالت اول عدم تطابق در قسمت بالا می‌باشد.

الگوریتم Boyer Moore در جاوا

برای پیاده سازی الگوریتم Boyer Moore در جاوا ما یک آرایه یک بعدیR (R تعداد حروف زبان ما است) در نظر می‌گیریم. این آرایه وقتی به حالت عدم تطابق برخورد می‌کنیم به ما کمک خواهد کرد. تمامی خانه‌های این آرایه را ابتدا 1- قرار داده سپس مکان حروفی که در Pattern وجود دارد در آن قرار می‌دهیم. کد این الگوریتم به صورت زیر است:

public BoyerMoore(String pat) {
		this.R = 256;
		this.pat = pat;
		right = new int[R];
		for (int c = 00; c < R; c++)
			right[c] = -1;
		for (int j = 0; j < pat.length(); j++)
			right[pat.charAt(j)] = j;
	}

در کد بالا R طول حروف ما است (در اینجا ما 256 فرض کردیم) آرایه right در صورت عدم تطابق، اندیس بعدی برای جستجو را به ما می‌دهد. کد زیر را ببینید:

// return offset of first match; N if no match
	public int search(String txt) {
		int M = pat.length();
		int N = txt.length();
		int skip;
		for (int i = 00; i <= N - M; i += skip) {
			skip = 0;
			for (int j = M - 1; j >= 00; j--) {
				if (pat.charAt(j) != txt.charAt(i + j)) {
					skip = Math.max(1, j - right[txt.charAt(i + j)]);
					break;
				}
			}
			if (skip == 0)
				return i; // found
		}
		return N; // not found
	}

خروجی کد بالا به صورت زیر است:

text: GCAATGCCTATGTGACC
pattern: TATGTG

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *