پرش به محتویات

الگوریتم آهو-کوراسیک

الگوریتم آهو-کوراسیک به ما امکان جستجوی سریع چندین الگو را در یک متن می‌دهد. مجموعه‌ی رشته‌های الگو، دیکشنری نیز نامیده می‌شود. طول کل رشته‌های تشکیل‌دهنده آن را با $m$ و اندازه‌ی الفبا را با $k$ نشان خواهیم داد. این الگوریتم یک ماشین حالت متناهی را بر اساس یک ترای (trie) در زمان $O(m k)$ می‌سازد و سپس از آن برای پردازش متن استفاده می‌کند.

این الگوریتم در سال ۱۹۷۵ توسط آلفرد آهو و مارگارت کوراسیک ارائه شد.

ساخت ترای


یک ترای بر اساس کلمات "Java"، "Rad"، "Rand"، "Rau"، "Raum" و "Rose".
این تصویر توسط [nd](https://de.wikipedia.org/wiki/Benutzer:Nd) تحت مجوز CC BY-SA 3.0 منتشر شده است.

به طور رسمی، ترای (trie) یک درخت ریشه‌دار است که در آن هر یال درخت با یک حرف برچسب‌گذاری شده و یال‌های خروجی از یک رأس، برچسب‌های متمایزی دارند.

ما هر رأس در ترای را با رشته‌ای که از برچسب‌های روی مسیر از ریشه تا آن رأس تشکیل شده است، شناسایی می‌کنیم.

هر رأس همچنین یک پرچم (flag) به نام $\text{output}$ خواهد داشت که اگر رأس مربوط به یک الگو در دیکشنری باشد، این پرچم تنظیم (set) می‌شود.

بر این اساس، یک ترای برای مجموعه‌ای از رشته‌ها، ترای‌ای است که در آن هر رأس $\text{output}$ به یکی از رشته‌های مجموعه متناظر است و بالعکس، هر رشته از مجموعه به یک رأس $\text{output}$ متناظر است.

اکنون نحوه‌ی ساخت یک ترای برای مجموعه‌ای از رشته‌ها را در زمان خطی نسبت به طول کل آن‌ها شرح می‌دهیم.

ما یک ساختار (structure) برای رأس‌های درخت معرفی می‌کنیم: 

const int K = 26;

struct Vertex {
    int next[K];
    bool output = false;

    Vertex() {
        fill(begin(next), end(next), -1);
    }
};

vector<Vertex> trie(1);

در اینجا، ما ترای را به صورت آرایه‌ای از Vertex ذخیره می‌کنیم. هر Vertex شامل پرچم output و یال‌ها به شکل یک آرایه next[] است، که در آن next[i] اندیس رأسی است که با دنبال کردن کاراکتر $i$ به آن می‌رسیم، یا اگر چنین یالی وجود نداشته باشد، مقدار آن $-1$ است. در ابتدا، ترای فقط از یک رأس - ریشه - با اندیس $0$ تشکیل شده است.

حالا تابعی را پیاده‌سازی می‌کنیم که رشته $s$ را به ترای اضافه می‌کند. پیاده‌سازی ساده است: ما از گره ریشه شروع می‌کنیم و تا زمانی که یال‌های متناظر با کاراکترهای $s$ وجود دارند، آن‌ها را دنبال می‌کنیم. اگر برای یک کاراکتر یالی وجود نداشته باشد، یک رأس جدید ایجاد کرده و آن را با یک یال متصل می‌کنیم. در پایان فرآیند، آخرین رأس را با پرچم output علامت‌گذاری می‌کنیم.

void add_string(string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next[c];
    }
    trie[v].output = true;
}

این پیاده‌سازی به وضوح در زمان خطی اجرا می‌شود، و از آنجایی که هر رأس $k$ پیوند (link) ذخیره می‌کند، از حافظه‌ی $O(m k)$ استفاده خواهد کرد.

می‌توان با استفاده از یک map به جای آرایه در هر رأس، مصرف حافظه را به $O(m)$ کاهش داد. با این حال، این کار پیچیدگی زمانی را به $O(m \log k)$ افزایش می‌دهد.

ساخت یک ماشین (automaton)

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

در واقع، رأس‌های ترای را می‌توان به عنوان حالت‌هایی در یک ماشین قطعی متناهی (finite deterministic automaton) تفسیر کرد. از هر حالت می‌توانیم - با استفاده از یک حرف ورودی - به حالت‌های دیگر، یعنی به موقعیت دیگری در مجموعه‌ی رشته‌ها، انتقال پیدا کنیم. برای مثال، اگر تنها یک رشته $abc$ در دیکشنری وجود داشته باشد و ما در رأس $ab$ ایستاده باشیم، با استفاده از حرف $c$ می‌توانیم به رأس $abc$ برویم.

بنابراین می‌توانیم یال‌های ترای را به عنوان انتقال‌هایی در یک ماشین بر اساس حرف متناظر درک کنیم. با این حال، در یک ماشین، باید برای هر ترکیب از یک حالت و یک حرف، انتقال داشته باشیم. اگر سعی کنیم با استفاده از یک حرف انتقالی انجام دهیم و یال متناظری در ترای وجود نداشته باشد، با این وجود باید به حالتی برویم.

دقیق‌تر بگوییم، فرض کنید در حالتی متناظر با رشته‌ی $t$ هستیم و می‌خواهیم با استفاده از کاراکتر $c$ به حالت دیگری انتقال پیدا کنیم. اگر یالی با برچسب این حرف $c$ وجود داشته باشد، می‌توانیم به سادگی از این یال عبور کنیم و به رأس متناظر با $t + c$ برسیم. اگر چنین یالی وجود نداشته باشد، از آنجا که می‌خواهیم این ناوردا را حفظ کنیم که حالت فعلی طولانی‌ترین تطابق جزئی در رشته‌ی پردازش شده است، باید طولانی‌ترین رشته در ترای را که پسوند مناسبی (proper suffix) از رشته $t$ است پیدا کنیم و سعی کنیم از آنجا انتقال را انجام دهیم.

برای مثال، فرض کنید ترای با رشته‌های $ab$ و $bc$ ساخته شده است، و ما در حال حاضر در رأس متناظر با $ab$ هستیم که یک رأس $\text{output}$ نیز هست. برای انتقال با حرف $c$، مجبوریم به حالت متناظر با رشته $b$ برویم و از آنجا یال با حرف $c$ را دنبال کنیم.


یک ماشین آهو-کوراسیک بر اساس کلمات "a"، "ab"، "bc"، "bca"، "c" و "caa".
فلش‌های آبی پیوندهای پسوندی (suffix links) و فلش‌های سبز پیوندهای پایانی (terminal links) هستند.

یک پیوند پسوندی (suffix link) برای یک رأس $p$ یالی است که به طولانی‌ترین پسوند مناسب (proper suffix) از رشته‌ی متناظر با رأس $p$ اشاره می‌کند. تنها حالت خاص، ریشه‌ی ترای است که پیوند پسوندی آن به خودش اشاره خواهد کرد. اکنون می‌توانیم عبارت مربوط به انتقال‌ها در ماشین را اینگونه بازنویسی کنیم: تا زمانی که انتقالی از رأس فعلی ترای با استفاده از حرف فعلی وجود ندارد (یا تا زمانی که به ریشه برسیم)، پیوند پسوندی را دنبال می‌کنیم.

بنابراین ما مسئله‌ی ساخت یک ماشین را به مسئله‌ی یافتن پیوندهای پسوندی برای تمام رأس‌های ترای تقلیل دادیم. با این حال، ما این پیوندهای پسوندی را، به طرز عجیبی، با استفاده از انتقال‌های ساخته شده در ماشین خواهیم ساخت.

پیوندهای پسوندی رأس ریشه و تمام فرزندان مستقیم آن به رأس ریشه اشاره می‌کنند. برای هر رأس $v$ در عمق بیشتر درخت، می‌توانیم پیوند پسوندی را به صورت زیر محاسبه کنیم: اگر $p$ جد $v$ باشد و $c$ حرف برچسب‌گذاری شده روی یال از $p$ به $v$ باشد، به $p$ بروید، سپس پیوند پسوندی آن را دنبال کنید و از آنجا انتقال با حرف $c$ را انجام دهید.

بنابراین، مسئله‌ی یافتن انتقال‌ها به مسئله‌ی یافتن پیوندهای پسوندی، و مسئله‌ی یافتن پیوندهای پسوندی به مسئله‌ی یافتن یک پیوند پسوندی و یک انتقال، به جز برای رأس‌های نزدیک‌تر به ریشه، تقلیل یافته است. پس ما یک وابستگی بازگشتی داریم که می‌توانیم آن را در زمان خطی حل کنیم.

به سراغ پیاده‌سازی برویم. توجه داشته باشید که اکنون برای هر رأس $v$، جد $p$ و کاراکتر $pch$ یال از $p$ به $v$ را ذخیره خواهیم کرد. همچنین، در هر رأس پیوند پسوندی link (یا $-1$ اگر هنوز محاسبه نشده باشد) و در آرایه go[k] انتقال‌های ماشین برای هر نماد (باز هم $-1$ اگر هنوز محاسبه نشده باشد) را ذخیره خواهیم کرد.

const int K = 26;

struct Vertex {
    int next[K];
    bool output = false;
    int p = -1;
    char pch;
    int link = -1;
    int go[K];

    Vertex(int p=-1, char ch='$') : p(p), pch(ch) {
        fill(begin(next), end(next), -1);
        fill(begin(go), end(go), -1);
    }
};

vector<Vertex> t(1);

void add_string(string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (t[v].next[c] == -1) {
            t[v].next[c] = t.size();
            t.emplace_back(v, ch);
        }
        v = t[v].next[c];
    }
    t[v].output = true;
}

int go(int v, char ch);

int get_link(int v) {
    if (t[v].link == -1) {
        if (v == 0 || t[v].p == 0)
            t[v].link = 0;
        else
            t[v].link = go(get_link(t[v].p), t[v].pch);
    }
    return t[v].link;
}

int go(int v, char ch) {
    int c = ch - 'a';
    if (t[v].go[c] == -1) {
        if (t[v].next[c] != -1)
            t[v].go[c] = t[v].next[c];
        else
            t[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
    }
    return t[v].go[c];
}

به راحتی می‌توان دید که به لطف بهینه‌سازی با به خاطرسپاری (memoization) پیوندهای پسوندی و انتقال‌ها، زمان کل برای یافتن تمام پیوندهای پسوندی و انتقال‌ها خطی خواهد بود.

برای تصویری از این مفهوم به اسلاید شماره ۱۰۳ از اسلایدهای استنفورد مراجعه کنید.

ساخت مبتنی بر BFS

به جای محاسبه‌ی انتقال‌ها و پیوندهای پسوندی با فراخوانی‌های بازگشتی به go و get_link، می‌توان آنها را به صورت پایین به بالا (bottom-up) از ریشه محاسبه کرد. (در واقع، زمانی که دیکشنری فقط از یک رشته تشکیل شده باشد، الگوریتم آشنای Knuth-Morris-Pratt را به دست می‌آوریم.)

این رویکرد نسبت به روشی که در بالا توضیح داده شد، مزایایی خواهد داشت، زیرا زمان اجرای آن به جای طول کل $m$، تنها به تعداد رأس‌های $n$ در ترای بستگی دارد. علاوه بر این، می‌توان آن را برای الفباهای بزرگ با استفاده از یک ساختمان داده آرایه پایا (persistent array) تطبیق داد، و در نتیجه زمان ساخت را به جای $O(mk)$ به $O(n \log k)$ رساند، که با توجه به اینکه $m$ ممکن است تا $n^2$ برسد، بهبود قابل توجهی است.

می‌توانیم به صورت استقرایی با استفاده از این واقعیت استدلال کنیم که BFS از ریشه، رأس‌ها را به ترتیب طول افزایشی پیمایش می‌کند. می‌توانیم فرض کنیم که وقتی در یک رأس $v$ هستیم، پیوند پسوندی آن $u = link[v]$ قبلاً با موفقیت محاسبه شده است، و برای تمام رأس‌های با طول کوتاه‌تر، انتقال‌ها از آنها نیز به طور کامل محاسبه شده‌اند.

فرض کنید در حال حاضر در یک رأس $v$ ایستاده‌ایم و کاراکتر $c$ را در نظر می‌گیریم. ما اساساً دو حالت داریم:

  1. $go[v][c] = -1$. در این حالت، می‌توانیم $go[v][c] = go[u][c]$ را اختصاص دهیم که طبق فرض استقرا از قبل مشخص است؛
  2. $go[v][c] = w \neq -1$. در این حالت، می‌توانیم $link[w] = go[u][c]$ را اختصاص دهیم.

به این ترتیب، ما برای هر جفت رأس و کاراکتر، زمان $O(1)$ صرف می‌کنیم که زمان اجرا را $O(nk)$ می‌کند. سربار اصلی در اینجا این است که در حالت اول، ما تعداد زیادی از انتقال‌ها را از $u$ کپی می‌کنیم، در حالی که انتقال‌های حالت دوم، ترای را تشکیل می‌ده دهند و در مجموع روی تمام رأس‌ها به $n$ می‌رسند. برای جلوگیری از کپی کردن $go[u][c]$، می‌توانیم از یک ساختمان داده آرایه پایا استفاده کنیم که با استفاده از آن، ابتدا $go[u]$ را در $go[v]$ کپی می‌کنیم و سپس فقط مقادیر را برای کاراکترهایی که انتقال در آنها متفاوت است، به‌روزرسانی می‌کنیم. این منجر به الگوریتم $O(n \log k)$ می‌شود.

کاربردها

یافتن تمام رشته‌های یک مجموعه در یک متن

به ما مجموعه‌ای از رشته‌ها و یک متن داده شده است. باید تمام رخدادهای تمام رشته‌های مجموعه را در متن داده شده در زمان $O(\text{len} + \text{ans})$ چاپ کنیم، که در آن $\text{len}$ طول متن و $\text{ans}$ اندازه پاسخ است.

ما برای این مجموعه‌ی رشته‌ها یک ماشین می‌سازیم. اکنون متن را حرف به حرف با استفاده از ماشین، با شروع از ریشه ترای، پردازش خواهیم کرد. اگر در هر زمان در حالت $v$ باشیم و حرف بعدی $c$ باشد، با $\text{go}(v, c)$ به حالت بعدی انتقال می‌یابیم، و بدین ترتیب یا طول زیررشته تطابق فعلی را ۱ واحد افزایش می‌دهیم یا با دنبال کردن یک پیوند پسوندی آن را کاهش می‌دهیم.

چگونه می‌توانیم برای یک حالت $v$ بفهمیم که آیا تطابقی با رشته‌های مجموعه وجود دارد؟ اول، واضح است که اگر روی یک رأس $\text{output}$ بایستیم، رشته متناظر با آن رأس در این موقعیت از متن به پایان می‌رسد. با این حال، این به هیچ وجه تنها حالت ممکن برای رسیدن به یک تطابق نیست: اگر بتوانیم با حرکت در امتداد پیوندهای پسوندی به یک یا چند رأس $\text{output}$ برسیم، آنگاه به ازای هر رأس $\text{output}$ پیدا شده، یک تطابق نیز وجود خواهد داشت. یک مثال ساده که این وضعیت را نشان می‌دهد را می‌توان با استفاده از مجموعه رشته‌های $\{dabce, abc, bc\}$ و متن $dabc$ ایجاد کرد.

بنابراین اگر در هر رأس $\text{output}$ اندیس رشته متناظر با آن را ذخیره کنیم (یا لیست اندیس‌ها در صورتی که رشته‌های تکراری در مجموعه وجود داشته باشند)، آنگاه می‌توانیم در زمان $O(n)$ اندیس‌های تمام رشته‌هایی را که با حالت فعلی تطابق دارند، با دنبال کردن ساده پیوندهای پسوندی از رأس فعلی به ریشه، پیدا کنیم. این کارآمدترین راه‌حل نیست، زیرا در کل منجر به پیچیدگی $O(n \cdot \text{len})$ می‌شود. با این حال، این را می‌توان با محاسبه و ذخیره‌ی نزدیک‌ترین رأس $\text{output}$ که با استفاده از پیوندهای پسوندی قابل دسترسی است (که گاهی اوقات پیوند خروجی (exit link) نامیده می‌شود) بهینه کرد. این مقدار را می‌توانیم به صورت تنبل (lazily) در زمان خطی محاسبه کنیم. بنابراین برای هر رأس می‌توانیم در زمان $O(1)$ به رأس علامت‌گذاری شده بعدی در مسیر پیوند پسوندی، یعنی به تطابق بعدی، پیش برویم. در نتیجه برای هر تطابق زمان $O(1)$ صرف می‌کنیم و به پیچیدگی $O(\text{len} + \text{ans})$ می‌رسیم.

اگر فقط بخواهید تعداد رخدادها را بشمارید و خود اندیس‌ها را پیدا نکنید، می‌توانید تعداد رأس‌های علامت‌گذاری شده در مسیر پیوند پسوندی را برای هر رأس $v$ محاسبه کنید. این کار را می‌توان در کل در زمان $O(n)$ محاسبه کرد. بنابراین می‌توانیم تمام تطابق‌ها را در زمان $O(\text{len})$ جمع بزنیم.

یافتن کوچکترین رشته از نظر لغوی با طول معین که با هیچ یک از رشته‌های داده شده تطابق ندارد

یک مجموعه از رشته‌ها و یک طول $L$ داده شده است. باید یک رشته به طول $L$ پیدا کنیم که شامل هیچ یک از رشته‌ها نباشد و کوچکترین رشته از نظر لغوی با این ویژگی را بیابیم.

ما می‌توانیم ماشین را برای این مجموعه از رشته‌ها بسازیم. به یاد بیاورید که رأس‌های output حالت‌هایی هستند که در آنها با یک رشته از مجموعه تطابق داریم. از آنجایی که در این مسئله باید از تطابق‌ها اجتناب کنیم، مجاز به ورود به چنین حالت‌هایی نیستیم. از طرف دیگر می‌توانیم وارد تمام رأس‌های دیگر شویم. بنابراین تمام رأس‌های «بد» را از ماشین حذف می‌کنیم و در گراف باقی‌مانده ماشین، کوچکترین مسیر از نظر لغوی به طول $L$ را پیدا می‌کنیم. این مسئله را می‌توان برای مثال با جستجوی عمق-اول در زمان $O(L)$ حل کرد.

یافتن کوتاه‌ترین رشته‌ای که شامل تمام رشته‌های داده شده باشد

در اینجا از ایده‌های مشابهی استفاده می‌کنیم. برای هر رأس یک ماسک (mask) ذخیره می‌کنیم که رشته‌هایی را که در این حالت تطابق دارند، مشخص می‌کند. سپس مسئله را می‌توان به صورت زیر بازنویسی کرد: در ابتدا در حالت $(v = \text{root},~ \text{mask} = 0)$ هستیم و می‌خواهیم به حالت $(v,~ \text{mask} = 2^n - 1)$ برسیم، که در آن $n$ تعداد رشته‌ها در مجموعه است. وقتی با استفاده از یک حرف از یک حالت به حالت دیگر منتقل می‌شویم، ماسک را متناسب با آن به‌روز می‌کنیم. با اجرای یک جستجوی سطح-اول می‌توانیم مسیری به حالت $(v,~ \text{mask} = 2^n - 1)$ با کوتاه‌ترین طول پیدا کنیم.

یافتن کوچکترین رشته از نظر لغوی به طول $L$ که شامل $k$ رشته باشد

مانند مسئله قبل، برای هر رأس تعداد تطابق‌هایی را که به آن متناظر است محاسبه می‌کنیم (یعنی تعداد رأس‌های علامت‌گذاری شده که با استفاده از پیوندهای پسوندی قابل دسترسی هستند). مسئله را بازنویسی می‌کنیم: حالت فعلی با یک سه‌تایی از اعداد $(v,~ \text{len},~ \text{cnt})$ تعیین می‌شود و می‌خواهیم از حالت $(\text{root},~ 0,~ 0)$ به حالت $(v,~ L,~ k)$ برسیم، که در آن $v$ می‌تواند هر رأسی باشد. بنابراین می‌توانیم چنین مسیری را با استفاده از جستجوی عمق-اول پیدا کنیم (و اگر جستجو یال‌ها را به ترتیب طبیعی آنها بررسی کند، مسیر یافت شده به طور خودکار کوچکترین از نظر لغوی خواهد بود).

مسائل

منابع