برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: درخت کلید واژه یا ترای، برای مجموعه رشته‌های الگوی {p= {p ۱ ,p ۲ , … ,pm یک درخت ریشه‌دار k است به طوری که: هر یال درخت با یک حرف برچسب گذاری شده. هر دو یال مختلف خروجی از هر راس، برچسب‌های متفاوت دارند. هر رشته از مجموعه رشته‌های الگوی p متناظر با راسی از درخت k است که الحاق حروف روی یال‌های مسیر بین ریشه و آن، با رشته یکی باشد و برچسب آن راس، برابر با اندیس آن رشته در p است. با درخت تک راسی (ریشه) شروع می‌کنیم رشته‌های الگو را یکی یکی به صورت زیر به درخت اضافه می‌کنیم: از ریشه شروع می‌کنیم و مسیر را مطابق با حروف رشته pi می‌پیماییم. ۱ اگر مسیر قبل از تمام شدن حروف pi تمام شد، مسیر را با اضافه کردن یال‌ها و راس‌هایی برای باقی‌مانده حروف pi ادامه می‌دهیم. ۲ برچسب آخرین راس این مسیر را i می‌گذاریم. زمان اجرای ساختن درخت کلیدواژه (| o (n) = o (|p ۱ | + |p ۲ | + |p ۳ | + … + |pm می‌باشد. (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) پیوند ناموفق خواهد بود. حالت‌های این خودکاره، رئوس درخت کلیدواژه هستند. حالت اولیه: ریشه درخت. عملیات با سه تابع تعیین می‌شوند: ((goto function (g (q,a: حالتی را می‌دهد که خودکاره از حالت q با ورودی a به آن می‌رود. اگر یال (q,v) با حرف a در درخت برچسب گذاری شده باشد، g (q,a) =v برای هر حرف که یال خروجی از ریشه با برچسب آن نباشد خواهیم داشت g (۰ ,a) = ۰ در همه حالت‌های دیگر g (q,a) =ф ((failure function (f (q: برای q ≠ ۰ حالتی را می‌دهد که هنگام عدم تطابق به آن وارد می‌شود. (f (q حالت متناظر با راس v در درخت کلیدواژه خواهد بود به طوری که (q,v) پیوند ناموفق راس q است. ((output function (out (q: مجموعه‌ای از رشته‌های الگو را که هنگام وارد شدن به حالت q تشخیص داده می‌شوند را می‌دهد. 
برداشت:
بسیاری از الگوریتم‌های تطابق رشته‌ای همانند الگوریتم (knuth morris prat (kmp یا boyer moore برای جستجوی یک رشته الگو در میان یک متن استفاده می‌شوند و مکان تکرار آن را در آن متن مشخص می‌کنند . ولی در برخی کاربردها نیاز به پیدا کردن بیش از یک رشتهٔ الگو در داخل یک متن به وجود می‌آید . استفاده از الگوریتم‌های پیشین برای پیدا کردن k رشتهٔ الگو در رشتهٔ t به طول m ، بسیار هزینه بر و از مرتبه زمانی (o (km می‌باشد . الگوریتم آهو-کوراسیک (aho-corasick یا ac) یک الگوریتم تطابق رشته‌ای چندگانه‌است که توسط آلفرد وی آهو (alferd v.aho) و مارگارت جی کوراسیک (margaret j .