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

بسیاری از الگوریتم‌های تطابق رشته‌ای همانند الگوریتم (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_۲,... ,P_m یک درخت ریشه‌دار K است به طوری که:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

الگوریتم پیدا کردن یال‌های پیوند ناموفق در درخت 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 با اضافه کردن یال‌های پیوند ناموفق

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

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

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

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

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

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

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

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

((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;

منابع

ویکی‌پدیای انگلیسی

پیوند به بیرون

Kilpeläinen[۱], Pekka (2005). "Set Matching and Aho-Corasick Algorithm". doi:www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf. ; ; ;
Aho–Corasick entry