ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

String Matching - KMP

دوشنبه, ۲۹ تیر ۱۳۹۴، ۱۲:۱۹ ق.ظ

تعاریف و مفروضات:

فرض می کنیم یه رشته داریم مثل S و می خوایم ببینیم چند بار رشته ای مثل T تکرار شده.

به رشته اصلی اصطلاحا text و به رشته ای دنبالش می گردیم، pattern می گیم.

طول text رو n فرض می کنیم و طول pattern رو m.

مثلا تو رشته aaaa رشته aa 3 بار تکرار شده.

i امین prefix رشته ای مثل S رو [S[0..i تعریف می کنیم.

i امین suffix رشته ای مثل S رو [S[i..n-1 تعریف می کنیم.


بدیهی ترین راه حل اینه که بیایم از هر نقطه شروع چک کنیم که آیا زیر رشته فعلی دقیقا برابر با pattern هست یا نه.

یعنی کاری شبیه این می کنیم:

int counter = 0;
for( int i = 0 ; i + pattern.size() <= text.size() ; i ++ )
{
  bool mismatch = false;
  for( int j = 0 ; j < pattern.size() ; j ++ )
    if( text[i+j] != pattern[j] )
    {
      mismatch = true;
      break;
    }
  if( mismatch == false )
    counter ++;
}

اگه دقت کنید این پیاده سازی (O(n*m زمان نیاز داره.

سه دانشمند به نام های Knuth, Morris, Pratt الگوریتمی ابداع کردند که تو زمان (O(n+m این کار رو انجام میده. الگوریتمی که طراحی کردند به اسم سازندگانش معروف شده.( KMP )

نحوه کار الگوریتم به این شکله:

فرض کنید تو پیاده سازی بالا برای اندیسی مثل i ما تونسته باشیم k تا کاراکتر اول pattern رو match کرده باشیم و تو اندیس k+1 از pattern به mismatch رسیده باشیم.

الگوریتم بالا میاد تمام k تا match ای که داشت رو پاک می کنه و دوباره از اول برای اندیس i+1 از text کار رو تکرار می کنه.

چیزی که تو KMP اتفاق میوفته اینه که الگوریتم بر اساس یه پیش پردازشی که انجام داده، میاد یه تعداد از k تا match ای که داشت رو پاک می کنه و ادامه میده.

چطور؟

کافیه برای هر اندیس از pattern ، "طول بلندترین suffix رو بدست میارم که prefix هم باشه".

یعنی می خوایم تو i امین prefix از pattern، عددی مثل k رو پیدا کنیم که 

pattern[0..k-1] == pattern[ i-k+1..i]

به عبارت دیگه، k کاراکتر اول از pattern دقیقا برابر k کاراکتر آخر از i امین prefix از pattern باشه.


مثلا برای رشته ای مثل abaab داریم:

برای اندیس 0:

0 امین prefix میشه : a

این رشته هیچ prefix ای نداره پس مقدار k0 = -1 فرض می کنیم.(قرارداد می کنیم که -1 یعنی هیچ)

برای اندیس 1:

1 امین prefix میشه : ab

این رشته یه prefix داره و یه suffix. اینجا هم باز چون برابر هم نیستند k1 = -1 میشه.

برای اندیس 2:

2 امین prefix میشه : aba

این رشته یه prefix به طول 1 داره که دقیقا برابر suffix به طول 1 ـه. پس k2 = 1 میشه.

برای اندیس 3:

3 امین prefix میشه : abaa

این رشته هم مثل حالت قبلی میشه. پس k3 = 1 میشه.

برای اندیس 4:

4 امین prefix میشه : abaab

این رشته یه prefix به طول 2 داره که برابر suffix به طول 2 ـه. پس k4 = 2 میشه.


این اطلاعات به چه درد می خوره؟

زمانی که تو اندیسی مثلا 3 از pattern یه mismatch رخ میده، می تونیم به جای اینکه کل match هایی که داشتیم رو پاک کنیم، می تونیم، 3 - K3  از match هارو پاک کنیم، ادامه بدیم.

برای اینکه واضح تر بشه روی یه مثال میگم

text = ababaabd

pattern = abaab

الگوریتم این طور کار می کنه:

3 کاراکتر اول از pattern رو match می کنه و به 4 امین کاراکتر می رسه.

چون [pattern[3] != text[3 پس یه mismatch اتفاق افتاده.

الگوریتم اول میاد تمام 3 تا match ای که داشت رو می ریزه دور و شروع می کنه از دومین کاراکتر text ادامه دادن.

اما KMP میاد میگه چون K3 = 1 بوده، پس می تونیم 1 دونه از match هایی که داشتیم رو نگه داریم و دنبال 2 امین match بگردیم.

اتفاقی که میوفته عملا اینجوریه:

شروع می کنیم به match کردن از اندیس 0 ام.

ababaabd

abaab

    ^

تو این اندیس mismatch داریم، الگوریتم میگه به جای اینکه برگردیم به این حالت:

ababaabd

 abaab

 ^

از مقداری که پیش محاسبه کردیم استفاده کنیم و بریم به این حالت:

ababaabd

  abaab

   ^

و ادامه بدیم به match کردن. چون match شده میریم جلو تا رشته رو پیدا کنیم یا دوباره mismatch ببینیم.

هر جا mismatch دیدیم، از مقادیری که محاسبه کردیم استفاده می کنیم.


چجوری این مقادیر رو حساب کنیم؟

خود نویسندگان یه الگوریتم برای پیدا کردن Ki ها ارائه دادن که اینجوریه:

int *fail[m+1];
int j = fail[0] = -1;
for( int i = 1 ; i <= m ; i ++ )
{
	while( j >= 0 && pattern[j] != pattern[i-1] )
		j = fail[j];
	fail[i] = ++ j;
}
آرایه fail ای که تولید شده همون K ای که بالا توضیح دادمه.
اینجوری اسمش بهتره.

کد الگوریتم چجوریه؟
کد الگوریتم خیلی شبیه قسمت بالاست.
فقط باید pattern رو روی text سرچ کنیم. یعنی:

int count = 0, k = 0;
for( int i = 0 ; i < n ; i ++ )
{
	while( k >= 0 && pattern[k] != text[i] )
		k = next[k];
	if( ++ k >= m )
	{
		k = next[k];
		count ++;//match at t[i-m+1 .. i]
	}
}
تحلیل زمانی:
برای قسمت اول:
اگه دقت کنید می تونید ببینید که برای هر j داریم: [j >= fail[j
پس عبارت [j = fail[j فقط می تونه مقدار j رو کم کنه، همچنین شرطی داریم که نمی زاره j کمتر از 0 بشه.
پس اون while داخل for حداکثر به اندازه j می تونه کار کنه.
تنها جایی که j داره زیاد میشه اون عبارت ++ j ـه که دقیقا m بار داره انجام میشه.
پس در مجموع قسمت اول الگوریتم (O(m بار اجرا میشه.

برای قسمت دوم:
تحلیل زمانی الگوریتم دقیقا مثل قسمت قبل میشه پس (O(n بار انجام میشه.

لذا در مجموع این الگوریتم به (O(n+m زمان احتیاج داره.

اگه احساس می کنید بد توضیح دادم، بگید تا اصلاح کنم.

موفق باشید
موافقین ۲ مخالفین ۱ ۹۴/۰۴/۲۹
رضا حسینی آشتیانی

نظرات  (۳)

خیلی خوب بود :)) مرسی 

ولی انصفا سخته یکمی فهمش من که الگوریتم رو تقریبا بلد بودم برام سخت بود فهمش ولی کلا این مشکل الگوریتمه که یک جوریه وگرنه به نظرم خوب نوشتی مرسی بازم :))
@sajil
الگوریتم KMP برات یه جوریه و بدیهی نیست چون باید با سبک فکر و پارادایم suffixization و prefixization آشنا باشی:
http://libgen.io/book/index.php?md5=5fbe1ebff51fb45dc4b67bb78d47abbc
http://libgen.io/book/index.php?md5=D06337A2F4804CE8A9A9573B93A66276

یه روزه دارم سایت و مقاله میخونم نفهمیدم چطوری این الگوریتم کار میکنه ولی مطلب اینجا رو که 
خوندم و فهمیدم ، واقعا خوب توضیح دادی

دمت گرم


ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی