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

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

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

$\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)$ است.

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

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

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

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

مراجع

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.

• دیکشنری انگلیسی به فارسی ساختمان داده و الگوریتم‌ها
• تطابق رشته‌ها در ویکی‌پدیای انگلیسی
• فهرست همهٔ الگوریتم‌های جستجوی رشته‌ها