‏الگوریتم Aho-Corasick: پیدا کردن چند رشته با یه بار خوندن متن

نویسنده‌ی این پست ساخت Aho-Corasick رو توضیح می‌ده؛ الگوریتمی برای پیدا کردن همزمان چند الگو توی یه متن. به گفته‌ی خودش، چیزی که این الگوریتم رو براش جذاب می‌کنه اینه که از یه ساختار داده‌ی درختی معمولی، خیلی تمیز یه ماشین حالت (automaton) درمیاره.

نقطه‌ی شروع یه trie هست، یعنی درختی که رشته‌ها رو نگه می‌داره و رشته‌هایی که شروعشون یکیه، اون پیشوند مشترک رو با هم شریکن. مثلاً برای suit و suited و suitable، بخش suit فقط یه بار توی درخت هست. گره‌هایی که آخر یه رشته‌ی کامل هستن هم علامت می‌خورن.

قلب الگوریتم suffix link هست، یعنی لینکی که از هر گره به بلندترین پسوندِ رشته‌ی اون گره اشاره می‌کنه که خودش شروعِ یه الگوی دیگه‌ست. مثال مقاله: با الگوهای item و suits، اگه متن suitems رو بخونی، بعد از suit حرف e جلوت نیست. پس ماشین از طریق suffix link می‌پره به گره‌ی it و ادامه می‌ده تا item پیدا بشه. یعنی لازم نیست برگردی عقب و دوباره متن رو بخونی.

این لینک‌ها با پیمایش سطح‌به‌سطح (BFS) ساخته می‌شن. ریشه و بچه‌های مستقیمش به خود ریشه لینک می‌دن. برای بقیه، از suffix link پدر شروع می‌کنی و اونقدر لینک‌ها رو دنبال می‌کنی تا گره‌ای پیدا بشه که یالی با همون حرف داشته باشه، یا به ریشه برسی. این تکه از شبه‌کد مقاله همین رو نشون می‌ده:

let suffix = node.parent.suffix
while suffix has no edge labelled char {
  suffix <- suffix.suffix
  if suffix == root then
    break
}

بعد نوبت output link هست. فرض کن الگوها spin و pin و in باشن؛ وقتی spin پیدا شد، pin و in هم همزمان پیدا شدن و باید گزارش بشن. output link هر گره به نزدیک‌ترین گره‌ای اشاره می‌کنه که پسوندش یه الگوی کامله، و درست بعد از suffix link همون گره حساب می‌شه. نویسنده می‌گه می‌شه بهش مثل یه linked list از خروجی‌ها نگاه کرد.

مشکل اینه که اگه trie رو همین‌طوری اجرا کنی، ممکنه برای هر حرف چند بار suffix link دنبال کنی و کار هر قدم ثابت نیست. برای همین با یه BFS آخر، همه‌چی تبدیل می‌شه به یه DFA (ماشین حالت قطعی که برای هر حرف دقیقاً یه حالت بعدی داره). اگه یالی برای یه حرف نبود، انتقالش همون انتقالِ گره‌ی suffix هست. چون خیلی از انتقال‌ها به ریشه می‌رسن، نویسنده پیشنهاد می‌ده جدول انتقال رو به‌صورت sparse matrix ذخیره کنی.

نکات کلیدی:

• Aho-Corasick چند الگو رو با یه بار خوندن متن پیدا می‌کنه.
• پایه‌ی الگوریتم یه trie هست که پیشوندهای مشترک رو یه بار نگه می‌داره.
• suffix link و output link هر دو با پیمایش BFS روی trie ساخته می‌شن.
• output link باعث می‌شه با پیدا شدن spin، الگوهای pin و in هم گزارش بشن.
• تبدیل به DFA کار هر انتقال رو ثابت می‌کنه و برای ذخیره‌ی جدولش sparse matrix پیشنهاد شده.
• منبع اصلی، مقاله‌ی Aho و Corasick در سال ۱۹۷۵ با عنوان Efficient String Matching هست.