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

بسیاری از الگوریتم‌های تطابق رشته‌ای همانند الگوریتم (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 با اضافه کردن یال‌های پیوند ناموفق:

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

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

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

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

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;

منابع

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

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

• Kilpeläinen[۱], Pekka (Spring 2005). Set Matching and Aho-Corasick Algorithm. . 
• Aho–Corasick entry

• پیاده‌سازی و انیمیشن الگوریتم آهو کوراسیک
• پیاده‌سازی الگوریتم با سی‌شارپ
• پیاده سازی الگوریتم با پی‌اچ‌پی
• پیاده‌سازی الگوریتم با سی
• پیاده‌سازی الگوریتم با پایتون
• پیاده‌سازی الگوریتم با جاوا