جست‌ و جوی هم‌ زمان چند الگوی متنی در یک متن بزرگ، یکی از مسائل بنیادی پردازش متن است که در کتاب‌ شناسی، موتور های جست‌ و جو، آنتی‌ ویروس‌ ها و سامانه‌ های کشف نفوذ نقشی حیاتی دارد. مقاله حاضر به تحلیل دقیق درخت Trie به‌عنوان ساختار داده بنیادی نگهداری مجموعه الگوها و الگوریتم Aho-Corasick به‌ عنوان نخستین راه‌ حل خطی و قطعی این مسئله می‌پردازد. این الگوریتم که آلفرد آهو و مارگارت کوراسیک در سال ۱۹۷۵ در نشریه Communications of the ACM منتشر کردند ([S1])، با تبدیل درخت الگو ها به یک اتوماتای قطعی متن‌ ها و افزودن «تابع شکست» (Failure Function)، همه وقوع‌های k الگو را در متنی به طول n در زمان O(n + m + z) پیدا می‌کند که در آن m مجموع طول الگوها و z تعداد وقوع‌ های گزارش‌ شده است. بررسی‌ های اخیر نشان می‌دهند که همین پارادایم نیم‌ قرن بعد همچنان هسته موتور های تشخیص امضای بدافزار در آنتی‌ ویروس‌های مدرن است ([S2]). در این نوشتار، ساختار ریاضی اتوماتا، مراحل ساخت آن، تحلیل پیچیدگی، کاربرد های عملی و بهینه‌ سازی‌ های نوین آن به‌ تفصیل بررسی می‌شود.

مقدمه و پیشینه تاریخی

مسئله‌ای که آهو و کوراسیک با آن روبه‌رو بودند، مسئله کلاسیک «جست‌وجوی کتاب‌شناختی» بود: با داشتن یک واژه‌نامه شامل k واژه و یک متن دلخواه، همه محل‌هایی که هر یک از واژه‌ها در متن ظاهر می‌شود را بیاب ([S1]). رویکرد بدیهی — اجرای یک بار الگوریتم جست‌وجوی تک‌الگویی مانند KMP برای هر واژه — زمانی از مرتبه O(k·n) می‌طلبد که برای واژه‌نامه‌های بزرگ (مانند همه نام‌های زیستی یا هزاران امضای بدافزار) عملاً غیرقابل‌تحمل است.

در مقاله‌ای که در ژوئن ۱۹۷۵ با عنوان «Efficient String Matching: An Aid to Bibliographic Search» منتشر شد، آهو و کوراسیک — که هر دو در آزمایشگاه‌های بل کار می‌کردند — نشان دادند که چگونه می‌توان همه الگوها را در یک ساختار واحد ادغام کرد و با یک پاس منفرد روی متن، همه وقوع‌ها را در زمان خطی مستقل از تعداد الگوها یافت ([S1]). ایده کلیدی، تکمیل درخت Trie الگوها با سه تابع گوتو، شکست و خروجی بود تا ساختار حاصل به یک ماشین حالت متناهی قطعی (DFA) کامل تبدیل شود. این کار نه‌تنها پاسخی عملی به مسئله کتاب‌شناسی داد، بلکه پایه نظری هزاران سامانه مدرن — از موتور قواعد Snort تا موتورهای امضای آنتی‌ویروس — شد ([S2]، [S4]). امروز، پنجاه سال پس از انتشار، الگوریتم در کتاب‌های درسی نظریه اتوماتا و طراحی الگوریتم‌ها جایگاهی ثابت دارد و نسخه‌های بهینه‌شده آن همچنان در خط مقدم پردازش متن و امنیت سایبری فعال‌اند.

روش‌شناسی: چارچوب تحلیل الگوریتم

این مقاله رویکردی تحلیلی–توصیفی دارد و ساختار بحث بر پایه زنجیره مفهومی «ساختار داده ← اتوماتا ← تحلیل پیچیدگی ← کاربرد» سازمان یافته است. نخست درخت Trie به‌عنوان پیش‌نیاز مفهومی معرفی و خواص ساختاری و حافظه‌ای آن تحلیل می‌شود؛ سپس نشان داده می‌شود چگونه افزودن تابع شکست، Trie ناقص را به اتوماتای کامل Aho-Corasick ارتقا می‌دهد. برای استخراج دقیق مراحل ساخت، رفتار تابع شکست و پیچیدگی الگوریتم از مقاله اصلی آهو و کوراسیک ([S1]) و توصیف‌های مرجع الگوریتمی ([S3]) استفاده شده است. در بخش کاربردها، ادعاها بر اساس مرورهای پژوهشی جدید در حوزه آنتی‌ویروس ([S2]) و پیاده‌سازی‌های مهندسی سامانه‌های کشف نفوذ ([S4]) سنجیده می‌شوند. مثال‌های عددی از یک مجموعه الگوی نمونه کوچک (شامل واژه‌هایی مانند he، she، his و hers) گرفته شده‌اند تا سازوکار انتقال‌ها به‌صورت گام‌به‌گام قابل ردیابی باشد.

درخت Trie: ساختار داده بنیادی

درخت Trie (که درخت دیجیتال یا درخت پیشوندی نیز نامیده می‌شود) ساختار داده‌ای درختی است که مجموعه‌ای از رشته‌ها را روی مسیرهای ریشه تا گره ذخیره می‌کند: هر یال از یک گره به فرزندش با یک نویسه برچسب‌گذاری می‌شود و هر گره در عمق d دقیقاً پیشوند طول d از یک یا چند الگو را نمایش می‌دهد. ریشه درخت، رشته تهی ε را نشان می‌دهد و گره‌هایی که انتهای یک الگو هستند با یک پرچم «پایان واژه» مشخص می‌شوند ([S1]).

ساخت Trie

ساختن Trie از مجموعه الگوها ساده است: برای هر الگو از ریشه شروع می‌کنیم و به‌ترتیب نویسه‌ها پایین می‌رویم؛ هرجا یال موردنظر وجود نداشت، گره و یال تازه‌ای می‌سازیم. اگر مجموع طول الگوها m باشد، کل ساخت در زمان O(m) انجام می‌شود و درخت حداکثر m یال و m+۱ گره دارد ([S1]). برای مثال، با الگوهای {he, she, his, hers}، درخت حاصل شامل شاخه s→h (با انشعاب به e و i)، شاخه h→e (با انشعاب به r) و شاخه h→i→s است؛ گره‌های انتهای he، she، his و hers به‌عنوان گره‌های خروجی علامت‌گذاری می‌شوند ([S3]).

ویژگی‌های کلیدی

کارکرد اصلی Trie، بازیابی سریع پیشوندهاست: پرس‌وجوی «آیا رشته‌ای در مجموعه هست؟» با یک پیمایش به طول رشته، در زمان O(|رشته|) پاسخ داده می‌شود و از تعداد الگوها مستقل است ([S3]). همین خاصیت، Trie را در غلط‌گیر املایی، تکمیل خودکار، مسیریابی IP با طول‌متغیر و فشرده‌سازی کارآمد می‌کند. از سوی دیگر، کاربرد Trie در جست‌وجوی متن یک ضعف اساسی دارد: Trie فقط برای «بازیابی پیشوند» طراحی شده است، نه برای ردیابی هم‌زمان چند الگو حین خواندن یک متن؛ اگر در نویسه‌ای شکست بخوریم، باید از ریشه دوباره آغاز کنیم ([S1]). این ضعف دقیقاً نقطه ورود الگوریتم Aho-Corasick است که در بخش بعد بررسی می‌شود.

حافظه

نمایش ساده Trie با آرایه‌ای از ۶۵٬۵۳۶ (یا ۲۵۶) نشانگر برای هر گره، سرعت انتقال O(۱) می‌دهد اما حافظه‌ای از مرتبه O(m·σ) مصرف می‌کند که σ اندازه الفباست و برای واژه‌نامه‌های بزرگ بسیار سنگین است ([S4]). همین جریمه حافظه، انگیزه ساختارهای جایگزینی مانند نگاشت درختی (Map)، کدگذاری دوگانه (Double-Array) و تراکم انتقال (Delta Transitions) شده است که در بخش بهینه‌سازی‌ها به آن‌ها بازمی‌گردیم ([S3]).

ساختار اتوماتای Aho-Corasick و تابع شکست

قلب الگوریتم Aho-Corasick، تبدیل Trie الگوها به یک اتوماتای قطعی کامل با سه تابع است ([S1]):

• تابع گوتو (goto): انتقال درون درخت است؛ اگر یال برچسب‌دار از گره فعلی با نویسه فعلی متن وجود داشته باشد، به فرزند می‌رویم. برای نویسه‌هایی که از ریشه یال ندارند، گوتو به ریشه برمی‌گردد.
• تابع شکست (failure): برای هر گره u، طولانی‌ترین پسوند درستِ برچسب مسیرِ u که هم‌زمان پیشوند یک الگوی دیگر است را می‌دهد. تابع شکست عمق گره را اکیداً کاهش می‌دهد، پس زنجیره‌ای از شکست‌ها همیشه در چند گام به ریشه می‌رسد ([S1]).
• تابع خروجی (output): فهرست الگوهایی را برمی‌گرداند که در گره فعلی یا در زنجیره لینک‌های شکست آن پایان می‌یابند؛ این سازوکار وقوع‌های هم‌پوشان الگوها را بدون بازگشت به عقب در متن ثبت می‌کند ([S3]).

ساخت در دو فاز

اتوماتا در دو مرحله ساخته می‌شود. فاز نخست، تعیین تابع گوتو است: Trie ساخته می‌شود و همه انتقال‌های مفقود از ریشه مستقیماً به خود ریشه اشاره می‌کنند ([S1]). فاز دوم، تعیین تابع شکست و خروجی است که با یک پیمایش سطح‌به‌سطح (BFS) انجام می‌شود: تابع شکست همه گره‌های عمق ۱، ریشه است؛ برای گره عمیق‌تر u با فرزند v از روی یال a، داریم fail(v) = g(fail(u), a) — یعنی از تابع شکست والد دوباره با نویسه a جلو می‌رویم. در همین پیمایش، اگر گوتو(v) تعریف‌نشده بود به‌جای آن g(fail(u), a) قرار می‌گیرد و Trie به تدریج به DFA کامل تبدیل می‌شود؛ به این ترتیب تابع شکست به‌صورت «لینک شکست» در خود اتوماتا ادغام و خروجی هر گره نیز از خروجی لینک شکستش به ارث می‌رسد ([S1]، [S3]). کل ساخت در زمان O(m) تمام می‌شود.

مثال گام‌به‌گام

متن را «ushers» و الگوها را {he, she, his, hers} بگیرید ([S1]). اتوماتا با ریشه شروع می‌شود؛ با خواندن u شکست می‌خوریم و در ریشه می‌مانیم، با s به گره s می‌رویم، با h به گره sh می‌رسیم — پس از خواندن «us»، پسوند «she» هنوز محتمل است. با خواندن e به گره she می‌رسیم و تابع خروجی وقوع she در جایگاه ۳ را گزارش می‌کند؛ لینک شکست این گره به he می‌رود و وقوع he در جایگاه ۳ نیز به‌طور خودکار گزارش می‌شود ([S3]). سپس r و s به گره hers می‌رسند و وقوع hers در جایگاه ۵ ثبت می‌شود. نکته مهم این است که متن هرگز به عقب بازگشت نمی‌خورد و شمارنده جایگاه فقط رو به جلو پیش می‌رود؛ همه الگوها با یک پاس و بدون بازگشت یافت می‌شوند.

تحلیل پیچیدگی زمانی و حافظه

برتری بنیادین Aho-Corasick، زمان اجرای خطی آن است که آهو و کوراسیک به‌صورت صوری اثبات کردند ([S1]).

ساخت اتوماتا

هر نویسه از هر الگو در ساخت Trie دقیقاً یک‌بار پردازش می‌شود، پس این مرحله O(m) است ([S1]). پیمایش سطح‌به‌سطح برای تابع شکست نیز با استدلال پتانسیل جمع‌شونده تحلیل می‌شود: هر بار که از زنجیره شکست‌ها پایین می‌رویم عمق گره اکیداً کم می‌شود و هر انتقال رو به جلو حداکثر یک واحد به عمق می‌افزاید؛ چون کل افزایش عمق در طول ساخت حداکثر m است، کل گام‌های رو به عقب نیز از m فراتر نمی‌رود ([S1]). پس فاز دوم نیز O(m) است و ساخت کل اتوماتا خطی است.

پیمایش متن

پس از ادغام لینک‌های شکست در جدول انتقال، پیمایش متن ساده است: برای هر یک از n نویسه، دقیقاً یک انتقال قطعی انجام می‌شود. زمان پیمایش O(n + z) است که z تعداد وقوع‌های گزارش‌شده الگوهاست؛ چون z در بدترین حالت کران‌دار است، کل زمان الگوریتم ([S3]):

$$T(n) = O(m) + O(n + z) = O(n + m + z)$$

خواهد بود. نکته قابل‌توجه، استقلال این زمان از تعداد الگوها (k) است: جست‌وجوی ۱۰ هزار الگو و ۱۰ الگو با همین مرتبه انجام می‌شود، در حالی‌که رویکرد ساده یک‌به‌یک زمان O(k·n) می‌طلبد ([S3]).

حافظه

حافظه مصرفی به نمایش بستگی دارد. نمایش کلاسیک با جدول انتقال کامل، فضایی از مرتبه O(m·σ) می‌طلبد که σ اندازه الفباست؛ برای الفبای بایت (σ = ۲۵۶) و واژه‌نامه‌های چندصدهزارتایی، مصرف حافظه به چند ده گیگابایت می‌رسد و این «حافظه‌گرسنگی» مهم‌ترین ضعف عملی الگوریتم است ([S4]). نمایش‌های جایگزین (نگاشت درختی با O(m) حافظه و انتقال O(log σ)، یا کدگذاری دوگانه با O(m) حافظه و انتقال سریع‌تر) میان‌جی سرعت و حافظه را فراهم می‌کنند. از دید نظری، الگوریتم در مدل ماشین قطعی بهینه است: هر نویسه ورودی حداکثر یک‌بار خوانده می‌شود و تعداد گام‌ها با مرتبه خطی، حد پایین مسئله را لمس می‌کند ([S1]).

کاربردها در پردازش متن و امنیت

کاربرد اصلی الگوریتم در مقاله ۱۹۷۵، شتاب‌بخشیدن به جست‌وجوی کتاب‌شناختی بود؛ امروز همین هسته در دامنه‌ای بسیار وسیع‌تر فعال است ([S1]، [S2]):

• موتورهای جست‌وجو و فهرست‌نویسی: یافتن هم‌زمان هزاران کلیدواژه در اسناد برای برچسب‌زنی، استخراج موجودیت و ساخت نمایه معکوس.
• فیلترینگ محتوا و پست الکترونیکی: ردیابی واژه‌های ممنوع، لینک‌های هرزنامه و امضاهای هرزنامه‌ای در جریان پیام‌ها با یک پاس خطی ([S3]).
• ژنومیکس: جست‌وجوی هم‌زمان هزاران توالی نوکلئوتیدی (پرایمرها، بافت‌های تکراری) در رشته‌های DNA که الفبای چهارحرفی آن شرایط را برای جدول‌های انتقال فشرده ایده‌آل می‌کند ([S3]).
• استخراج داده و تحلیل احساس: یافتن وقوع‌های چندواژه‌ای (n-gram) در پیکره‌های متنی بزرگ برای آموزش مدل‌های زبانی.

امنیت سایبری: مهم‌ترین کاربرد مدرن

در حوزه امنیت، پارادایم Aho-Corasick ستون فقرات سامانه‌های تشخیص امضاست. مرور پژوهشی جدیدی که پارادایم AC را در موتورهای آنتی‌ویروس مدرن بررسی کرده، نشان می‌دهد این الگوریتم همچنان گزینه نخست برای مسابقه‌ی امضاهای بدافزار در مرزهای شبکه است، زیرا تضمین عملکرد قطعی و پیش‌بینی‌پذیر آن — برخلاف روش‌های یادگیری ماشین — امکان تحلیل و اعتبارسنجی دقیق را فراهم می‌کند ([S2]).

در سامانه‌های کشف نفوذ مانند Snort، قواعد حاوی محتوای تحت‌اللفظی استخراج و در یک اتوماتای AC ادغام می‌شوند؛ سپس بسته‌های شبکه با یک پاس روی بارِ حمله عبور داده می‌شوند و فقط جریان‌هایی که امضایی در آن‌ها ردیابی شد، به پردازش سنگین‌تر (مثل بازسازی جریان TCP یا موتور قواعد کامل) می‌روند ([S4]). پیاده‌سازی پیش‌فرض AC در Snort از ساختار بهینه‌شده حافظه استفاده می‌کند تا چند هزار قاعده را با تأخیر قابل‌قبول پردازش کند ([S4]). چالش اصلی در این کاربردها، مقیاس است: مجموعه‌های امضا به سدها هزار قاعده رسیده‌اند و همان جریمه حافظه O(m·σ) به تنگنای اصلی تبدیل شده است ([S4]).

بهبودها و پیاده‌سازی‌های بهینه

پنجاه سال تحقیق، خانواده‌ای از بهینه‌سازی‌ها برای رفع ضعف حافظه و افزایش گذردهی الگوریتم تولید کرده است ([S2]، [S4]):

• کدگذاری دوگانه (Double-Array Trie): همه گره‌ها در دو آرایه تک‌بعدی BASE و NEXT ذخیره می‌شوند تا حافظه به O(m) کاهش یابد و انتقال‌ها بدون اشاره‌گرها در چند دسترسی حافظه انجام شود؛ پژوهش‌های اخیر روش‌های مهندسی‌شده‌ای برای ساخت سریع‌تر این ساختار ارائه کرده‌اند ([S2]).
• تراکم انتقال (Delta/Fast-Transitions): به‌جای ذخیره ۲۵۶ نشانگر برای هر گره، انتقال‌های پرتکرار به‌صورت صریح و بقیه از طریق لینک شکست محاسبه می‌شوند؛ حافظه به O(m) می‌رسد و هزینه انتقال تا O(log σ) افزایش می‌یابد — همان سازوکاری که پیاده‌سازی پیش‌فرض Snort برای مقیاس‌پذیری به کار می‌برد ([S4]).
• تسریع سخت‌افزاری: پیاده‌سازی‌های FPGA و TCAM انتقال‌های چندنویسه‌ای را موازی می‌کنند تا گذردهی لازم برای لینک‌های گیگابیتی فراهم شود ([S4]).
• گسترش‌های الگوریتمی: نسخه‌های تطبیقی برای تطبیق فازی، واریانت‌های موازی چندنخی و ادغام با فهرست‌های بلوم برای غربال اولیه واژه‌نامه‌های عظیم ([S2]).

مرور اخیر MDPI نشان می‌دهد با وجود ظهور موتورهای یادگیری ماشین برای تشخیص بدافزار، هسته امضایی AC به دلیل قطعیت، قابل‌اعتماد بودن و کارایی انرژی، همچنان در خط مقدم آنتی‌ویروس‌ها باقی مانده و نسخه‌های بهینه آن با بوم‌های سخت‌افزاری ترکیب می‌شوند ([S2]). مسیر پژوهش جاری، کاهش حتی‌الامکان دسترسی به حافظه (مکان زمانی) و بهره‌گیری از پردازش بردادی (SIMD) برای انتقال‌های هم‌زمان است ([S2]).

نتیجه‌گیری

الگوریتم Aho-Corasick نمونه کم‌نظیری از پژوهشی است که در نیم‌قرن عمر خود، از یک راه‌حل مسأله کتاب‌شناختی به زیرساخت قابل‌اعتماد پردازش متن و امنیت سایبری تبدیل شده است. با ادغام درخت Trie الگوها در یک اتوماتای قطعی کامل و افزودن تابع شکست، الگوریتم نشان داد همه وقوع‌های k الگو در متنی به طول n را می‌توان در زمان O(n + m + z) — مستقل از تعداد الگوها و بدون بازگشت به عقب — یافت؛ ویژگی‌ای که هیچ رویکرد ترکیبی از جست‌وجوهای تک‌الگویی نمی‌تواند تأمین کند ([S1]).

درخت Trie خود نیز ساختاری بنیادی و فراگیر است: هم به‌عنوان پیش‌نیاز مفهومی AC و هم به‌صورت مستقل در بازیابی پیشوند، تکمیل خودکار و مسیریابی، حضوری کلیدی دارد ([S1]). چالش اصلی امروز، نه زمان اجرا بلکه مقیاس حافظه است و پاسخ به آن، سه دهه پژوهش در کدگذاری دوگانه، تراکم انتقال و تسریع سخت‌افزاری را رقم زده است ([S4]، [S2]). برای پژوهشگر و مهندس امروز، Aho-Corasick همچنان نقطه شروع طبیعی برای هر مسئله جست‌وجوی چندالگویی در مقیاس بزرگ است: الگوریتمی خطی، قطعی، قابل‌اثبات و پس از پنجاه سال، همچنان به‌روز ([S2]).

منابع

[۱] Aho, A. V., & Corasick, M. J. (1975). Efficient String Matching: An Aid to Bibliographic Search. Communications of the ACM, 18(6), 333–340. متن کامل مقاله

[۲] The Aho-Corasick Paradigm in Modern Antivirus Engines: A Cornerstone of Signature-Based Malware Detection. Algorithms (MDPI), 2025. متن مقاله

[۳] Aho-Corasick Algorithm for Pattern Searching. GeeksforGeeks. متن راهنما

[۴] Norton, M., et al. Aho-Corasick FSM Implementation for Intrusion Detection Systems. Google Research. متن گزارش