الگوریتم تطابق رشته آهو-کوراسیک

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

بسیاری از الگوریتم‌های تطابق رشته‌ای همانند الگوریتم (Knuth Morris Prat(KMP یا Boyer Moore برای جست و جوی یک رشته الگو در میان یک متن استفاده می‌شوند و مکان تکرار آن را در آن متن مشخص می‌کنند. ولی در برخی کاربردها نیاز به پیدا کردن بیش از یک رشتهٔ الگو در داخل یک متن به وجود می‌آید. استفاده از الگوریتم‌های پیشین برای پیدا کردن k رشتهٔ الگو در رشتهٔ T به طول m، بسیار هزینه بر و از مرتبه زمانی (O(km می‌باشد.

الگوریتم آهوکوراسیک (Aho-Corasick یا AC) یک الگوریتم تطابق رشته‌ای چندگانه‌است که توسط آلفرد وی آهو (Alferd V. Aho) و مارگارت جی کوراسیک (Margaret J. Corasick) ارائه شده‌است که زمان اجرای این الگوریتم خطی و از مرتبهٔ زمانی (O(m+n+k است.

الگوریتم[ویرایش]

درخت کلیدواژه[ویرایش]

درخت کلید واژه یا ترای، برای مجموعهٔ رشته‌های الگوی {P={P۱,P۲,... ,Pm یک درخت ریشه دار K است به طوری که:

  • هر یال درخت با یک حرف برچسب گذاری شده.
  • هر دو یال مختلف خروجی از هر راس، برچسب‌های متفاوت دارند.
  • هر رشته از مجموعهٔ رشته‌های الگوی P متناظر با راسی از درخت K است که الحاق حروف روی یال‌های مسیر بین ریشه و آن، با رشته یکی باشد و برچسب آن راس، برابر با اندیس آن رشته در P است.

ساختن درخت کلیدواژه[ویرایش]

با درخت تک راسی (ریشه) شروع می‌کنیم

رشته‌های الگو را یکی یکی به صورت زیر به درخت اضافه می‌کنیم:

از ریشه شروع می‌کنیم و مسیر را مطابق با حروف رشتهٔ Pi می‌پیماییم.

1 اگر مسیر قبل از تمام شدن حروف Pi تمام شد، مسیر را با اضافه کردن یال‌ها و راس‌هایی برای باقی مانده حروف Pi ادامه می‌دهیم.

2 برچسب آخرین راس این مسیر را i می‌گذاریم.

زمان اجرای ساختن درخت کلیدواژه(| O(n)= O(|P۱| + |P۲| + |P۳| +... + |Pm می‌باشد.

درخت کلیدواژه برای مجموعهٔ رشته‌های {P={drug,drum,drain,rug,rum,rump,rain:

درخت کلید واژه برای مجموعه P

درخت کلیدواژه با اضافه کردن پیوندهای ناموفق[ویرایش]

(L(V و (Lp(V را اینگونه تعریف می‌کنیم:

(L(V: الحاق حروف روی یال‌های مسیر بین ریشه و راس P.

(Lp(V: طول بزرگترین پسوند(L(V که پیشوند یک رشته در P می‌باشد.

اگر α یک پسوند (L(V باشد به ط. ری که(α| = Lp(V| در این صورت، راس ω در درخت وجود دارد به طوری که،(α = L(ω.

اگر nv یک راس در درخت باشد به طوریکه (L(nv پسوند (L(V باشد و(L(nv)| = Lp(V| در اینصورت، یال (v,nv) پیوند ناموفق خواهد بود.

الگوریتم پیدا کردن یال‌های پیوند ناموفق در درخت K[ویرایش]
Def: x is a character on (parent(v), v)

Algorithm for node v
1 w=f(parent(v))
2 while (there is no edge out of w labeled x) and (w is not equal to  r)
3  w = f(w)
4 if there is an edge (w, w’) out of w labeled x
5     f(v) = w'
6 else
7     f(v) = r

درخت کلیدواژه برای مجموعهٔ رشته‌های {P={drug,drum,drain,rug,rum,rump,rain با اضافه کردن یال‌های پیوند ناموفق:

درخت کلیدواژه با یال‌های پیوند ناموفق

خودکارهٔ حالت متناهی[ویرایش]

حالت‌های این خودکاره، رئوس درخت کلیدواژه هستند.

حالت اولیه: ریشهٔ درخت.

عملیات با سه تابع تعیین می‌شوند:

  1. ((goto function (g(q,a: حالتی را می‌دهد که خودکاره از حالت q با ورودی a به آن می‌رود.

اگر یال (q,v) با حرف a در درخت برچسب گذاری شده باشد، g(q,a)=v برای هر حرف که یال خروجی از ریشه با برچسب آن نباشد خواهیم داشت g(0,a)= ۰ در همهٔ حالت‌های دیگر g(q,a)=ф

  1. ((failure function (f(q: برای q ≠ 0 حالتی را می‌دهد که هنگام عدم تطابق به آن وارد می‌شود.

(f(q حالت متناظر با راس v در درخت کلیدواژه خواهد بود به طوری که (q,v)پیوند ناموفق راس q است.

  1. ((output function (out(q:مجموعه‌ای از رشته‌های الگو را که هنگام وارد شدن به حالت q تشخیص داده می‌شوند را می‌دهد.

شبه کد[ویرایش]

1 q = 0 // initial state(root)
2 for i=1 to m do
3   while g(q,T[i]) = ф do
4     q = f(q); //follow a fail
5   q = g(q,T[i]); //follow a goto
6   if out(q) ≠ ф then print i, out(q);
7 endfor;

منابع[ویرایش]

پیوند به بیرون[ویرایش]