الگوریتم جستجوی رشته

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

الگوریتم جستجوی رشته (و یا تطبیق رشته‌ها) به ردهٔ مهمی از الگوریتم‌های موجود در رابطه با رشته‌ها اطلاق می‌شود.

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

\Sigma را مجموعه متناهی از حروف الفبا در نظر بگیرید، \Sigma می‌تواند الفبای معمولی (از A تا Z)، الفبای دودویی ({0,1}=\Sigma) و یا الفبای دی. ان. ای.(DNA) (\Sigma={A,C,G,T} )باشد که در این صورت متن و الگوی مورد نظر ما از کنار هم قرار گرفتن اعضای \Sigma بوجود می‌آیند.

طبقه بندی[ویرایش]

m طول الگو (و یا رشته) و n طول متن است:

{| class="wikitable"

|- ! الگوریتم ! زمان پیش پردازش ! زمان تطبیق |- ! [۱] الگوریتم جستجوی رشتهٔ نیو | ۰ (no preprocessing) | Θ(n m) |-Σ ! [۲] الگوریتم جستجوی رشتهٔ رابین - کارپ | Θ(m) | میانگین Θ(n+m),
بدترین حالت Θ(n m) |- !جستجو بر پایه[۳] خودکارهٔ حالت متناهی | Θ(m |Σ|) | Θ(n) |- ! [۴] الگوریتم کنوث - موریس -پرت | Θ(m) | Θ(n) |- ! [۵] الگوریتم جستجوی رشتهٔ بویر - مور | Θ(m + |Σ|) | Ω(n/m), O(n) |- ! [۶] الگوریتم بیتاپ (shift-or, shift-and, Baeza-Yates-Gonnet) | Θ(m + |Σ|) | Θ(n) |}

الگوریتم جستجوی رشتهٔ نیو (Naïve string search algorithm)[ویرایش]

آسانترین و نا کارآمدترین راه برای آنکه یک رشته و مکان آن را در یک متن پیدا کنیم، امتحان کردن یک به یک همهٔ مکانهایی که آن رشته می‌تواند قرار بگیرد است.

شبه کد جستجوی رشتهٔ نیو:

procedure NaiveStringMatcher (T,P)
begin
  n=lenght(T);
  m=lenght(P);
  for s=0 to n-m do
    if P[1...m]=T[s+1...s+m] then
      print «Pattern occurs with shift» s;
end

این الگوریتم از مرتبه زمانی  \operatorname{O}(m(n-m+1))\in \operatorname{O}(mn) است.

DFA search mommy.svg

جستجو بر پایه خودکارهٔ حالت متناهی (finite automata)[ویرایش]

در این روش ابتدا یک خودکارهٔ معین متناهی می‌سازیم که رشته‌هایی که حاوی الگوی مورد جستجوی ما هستند را تشخیص دهد که البته هزینه ساخت چنین خودکاره‌ای زیاد است (\operatorname{O}(m\Sigma)) اما استفاده از آن سریع است. در شکل زیر DFA برای تشخیص دادن واژه MOMMY استفاده شده‌است:

روش‌های اندیسی[ویرایش]

الگوریتم‌های سریع جستجو بر پایه پیش پردازش متن هستند؛ بعد از ساختن زیر رشته اندیسی [۷] برای مثال درخت پسوندی(suffix tree) و یا آرایه پسوندی(suffix array)، تعداد بارهایی که الگوی مورد جستجو در متن اتفاق افتاده‌است، به سرعت مشخص می‌شود؛ برای مثال یک درخت پسوندی را می‌توان در \Theta(m) ساخت و همهٔ z بار رویدادن الگوی مورد نظر در متن را می‌توان در \operatorname{O}(m+z) پیدا کرد.

پانوشت‌ها[ویرایش]

  1. Naïve string search algorithm
  2. Rabin-Karp string search algorithm
  3. Finite state automaton
  4. Knuth-Morris-Pratt algorithm
  5. Boyer-Moore string search algorithm
  6. Bitap algorithm
  7. substring index

مراجع[ویرایش]