Агуулгыг алгасах

Ахо-Корасикийн алгоритм

Ахо-Корасикийн алгоритм нь бидэнд текстээс олон хэв маягийг хурдан хайх боломж олгоно. Хэв маягийн тэмдэгт мөрүүдийн олонлогийг толь бичиг гэж бас нэрлэдэг. Бид түүнийг бүрдүүлэгч тэмдэгт мөрүүдийн нийт уртыг $m$, цагаан толгойн хэмжээг $k$ гэж тэмдэглэнэ. Алгоритм нь trie дээр суурилсан төгсгөлөг төлөвт автоматыг $O(m k)$ хугацаанд байгуулж, дараа нь түүнийг ашиглан текстийг боловсруулна.

Энэ алгоритмыг Alfred Aho, Margaret Corasick нар 1975 онд санал болгосон.

Trie байгуулах


A trie based on words "Java", "Rad", "Rand", "Rau", "Raum" and "Rose".
The image by [nd](https://de.wikipedia.org/wiki/Benutzer:Nd) is distributed under CC BY-SA 3.0 license.

Албан ёсоор trie гэдэг нь модны ирмэг бүр ямар нэг үсгээр тэмдэглэгдсэн, оройноос гарах ирмэгүүд нь ялгаатай тэмдэглэгээтэй байх үндэстэй мод юм.

Бид trie дэх орой бүрийг үндэснээс тэр орой хүртэлх зам дээрх тэмдэглэгээнүүдээр үүссэн тэмдэгт мөрөөр таних болно.

Орой бүр мөн $\text{output}$ тугтай байх ба хэрэв тэр орой толь бичиг дэх хэв маягт харгалзаж байвал энэ туг тавигдана.

Үүний дагуу тэмдэгт мөрийн олонлогийн trie гэдэг нь $\text{output}$ орой бүр олонлогийн нэг тэмдэгт мөрд харгалзах, эсрэгээрээ олонлогийн тэмдэгт мөр бүр нэг $\text{output}$ оройд харгалзах trie юм.

Одоо бид өгөгдсөн тэмдэгт мөрийн олонлогийн trie-г тэдгээрийн нийт уртын хувьд шугаман хугацаанд хэрхэн байгуулахыг тайлбарлана.

Бид модны оройнуудын бүтцийг танилцуулна: 

const int K = 26;

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

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

vector<Vertex> trie(1);

Энд бид trie-г $\text{Vertex}$-үүдийн массив хэлбэрээр хадгална. $\text{Vertex}$ бүр $\text{output}$ туг ба $\text{next}[]$ массив хэлбэрийн ирмэгүүдийг агуулна, энд $\text{next}[i]$ нь $i$ тэмдэгтийг дагаж хүрэх оройн индекс, эсвэл ийм ирмэг байхгүй бол $-1$ юм. Эхэндээ trie нь ердөө нэг орой буюу $0$ индекстэй үндэснээс бүрдэнэ.

Одоо бид trie-д $s$ тэмдэгт мөрийг нэмэх функцийг хэрэгжүүлнэ. Хэрэгжүүлэлт нь энгийн: бид үндэс зангилаанаас эхлэх ба $s$-ийн тэмдэгтүүдэд харгалзах ирмэг байх хооронд бид тэдгээрийг дагана. Хэрэв ямар нэг тэмдэгтийн ирмэг байхгүй бол бид шинэ орой үүсгэж, түүнийг ирмэгээр холбоно. Үйл явцын төгсгөлд бид сүүлийн оройг $\text{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$ холбоос хадгалдаг тул $O(m k)$ санах ой ашиглана.

Орой бүрд массивын оронд map ашигласнаар санах ойн хэрэглээг $O(m)$ болгон бууруулах боломжтой. Гэвч энэ нь time complexity-г $O(m \log k)$ болгож нэмэгдүүлнэ.

Автомат байгуулах

Бид өгөгдсөн тэмдэгт мөрийн олонлогийн trie-г байгуулсан гэж үзье. Одоо түүнийг өөр талаас нь харцгаая. Хэрэв бид дурын оройг харвал түүнд харгалзах тэмдэгт мөр нь олонлог дахь нэг буюу хэд хэдэн тэмдэгт мөрийн угтвар байх тул trie-ийн орой бүрийг олонлогийн нэг буюу хэд хэдэн тэмдэгт мөр дэх байрлал гэж тайлбарлаж болно.

Үнэндээ trie-ийн оройнуудыг төгсгөлөг детерминистик автомат дахь төлвүүд гэж тайлбарлаж болно. Дурын төлвөөс бид ямар нэг оролтын үсэг ашиглан бусад төлөв рүү буюу тэмдэгт мөрийн олонлогийн өөр байрлал руу шилжиж болно. Жишээ нь толь бичигт ердөө нэг $abc$ тэмдэгт мөр байгаа бөгөөд бид $ab$ оройд зогсож байвал $c$ үсэг ашиглан бид $abc$ орой руу очиж болно.

Ингэснээр бид trie-ийн ирмэгүүдийг харгалзах үсгийн дагуух автомат дахь шилжилт гэж ойлгож болно. Гэвч автоматад бид төлөв ба үсгийн хослол бүрийн хувьд шилжилттэй байх хэрэгтэй. Хэрэв бид үсэг ашиглан шилжилт хийхийг оролдоход trie-д харгалзах ирмэг байхгүй бол бид тэр байтугай ямар нэг төлөв рүү орох ёстой.

Тодруулбал бид $t$ тэмдэгт мөрд харгалзах төлөвт байгаа ба $c$ тэмдэгт ашиглан өөр төлөв рүү шилжихийг хүсэж байна гэж үзье. Хэрэв энэ $c$ үсгээр тэмдэглэгдсэн ирмэг байвал бид энэ ирмэгээр зүгээр л явж, $t + c$-д харгалзах оройг авч болно. Хэрэв ийм ирмэг байхгүй бол одоогийн төлөв нь боловсруулж буй тэмдэгт мөр дэх хамгийн урт хэсэгчилсэн таарц байх инвариантыг хадгалахыг хүсэж байгаа тул бид $t$ тэмдэгт мөрийн жинхэнэ дагавар байх хамгийн урт тэмдэгт мөрийг trie-ээс олж, тэндээс шилжилт хийхийг оролдох ёстой.

Жишээ нь trie нь $ab$ ба $bc$ тэмдэгт мөрүүдээр байгуулагдсан бөгөөд бид одоогоор $ab$-д харгалзах оройд байгаа, энэ нь мөн $\text{output}$ орой байг. $c$ үсгээр шилжихийн тулд бид $b$ тэмдэгт мөрд харгалзах төлөв рүү очиж, тэндээс $c$ үсэгтэй ирмэгийг дагахаас өөр аргагүй.


An Aho-Corasick automaton based on words "a", "ab", "bc", "bca", "c" and "caa".
Blue arrows are suffix links, green arrows are terminal links.

Орой $p$-ийн дагаврын холбоос гэдэг нь орой $p$-д харгалзах тэмдэгт мөрийн хамгийн урт жинхэнэ дагавар руу заасан ирмэг юм. Цорын ганц онцгой тохиолдол бол trie-ийн үндэс бөгөөд түүний дагаврын холбоос өөр рүүгээ заана. Одоо бид автомат дахь шилжилтийн тухай мэдэгдлийг дараах байдлаар дахин томьёолж болно: одоогийн үсэг ашиглан trie-ийн одоогийн оройноос шилжилт байхгүй байх хооронд (эсвэл бид үндэст хүртэл) бид дагаврын холбоосыг дагана.

Ингэснээр бид автомат байгуулах бодлогыг trie-ийн бүх оройн дагаврын холбоосыг олох бодлого болгон хураалаа. Гэвч бид эдгээр дагаврын холбоосыг хачирхалтай нь автоматад байгуулсан шилжилтүүдийг ашиглан байгуулна.

Үндэс орой ба түүний бүх шууд хүүхдийн дагаврын холбоос үндэс орой руу заана. Модонд илүү гүн байгаа дурын орой $v$-ийн хувьд бид дагаврын холбоосыг дараах байдлаар тооцоолж болно: хэрэв $p$ нь $v$-ийн өвөг бөгөөд $c$ нь $p$-ээс $v$ рүү чиглэсэн ирмэгийг тэмдэглэх үсэг бол $p$ руу оч, дараа нь түүний дагаврын холбоосыг дагаж, тэндээс $c$ үсгээр шилжилт хий.

Ингэснээр шилжилт олох бодлого нь дагаврын холбоос олох бодлого болж хураагдсан ба дагаврын холбоос олох бодлого нь үндэсэнд ойр оройнуудаас бусад тохиолдолд дагаврын холбоос ба шилжилт олох бодлого болж хураагдлаа. Тиймээс бидэнд шугаман хугацаанд шийдэж болох рекурсив хамаарал байна.

Хэрэгжүүлэлт рүү шилжье. Бид одоо орой $v$ бүрийн хувьд өвөг $p$ ба $p$-ээс $v$ рүү чиглэсэн ирмэгийн тэмдэгт $pch$-г хадгалахыг анзаар. Мөн орой бүрд бид дагаврын холбоос $\text{link}$-г (эсвэл хараахан тооцоологдоогүй бол $-1$), $\text{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];
}

Дагаврын холбоос ба шилжилтийг мемоизаци хийсний ачаар бүх дагаврын холбоос, шилжилтийг олох нийт хугацаа шугаман байх нь харахад амархан.

Энэ ойлголтын дүрслэлийг Стэнфордын слайд-ын 103 дугаар слайдаас үз.

BFS-д суурилсан байгуулалт

Шилжилт ба дагаврын холбоосыг go, get_link-д рекурсив дуудалт хийж тооцоолохын оронд тэдгээрийг үндэснээс эхлэн доороос дээш тооцоолох боломжтой. (Үнэндээ толь бичиг ердөө нэг тэмдэгт мөрөөс бүрдэх үед бид танил Кнут-Моррис-Праттын алгоритмыг авна.)

Энэ арга дээр тайлбарласнаас зарим давуу талтай, учир нь түүний ажиллах хугацаа нийт урт $m$-ээс биш зөвхөн trie дэх оройн тоо $n$-ээс хамаарна. Түүнчлэн persistent массив өгөгдлийн бүтэц ашиглан үүнийг том цагаан толгойд тохируулах боломжтой ба ингэснээр байгуулах хугацаа $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$-ээс маш олон шилжилтийг хуулдагт оршино, харин хоёр дахь тохиолдлын шилжилтүүд trie-г үүсгэх ба бүх оройн хувьд нийлээд $n$ болно. $go[u][c]$-г хуулахаас зайлсхийхийн тулд бид persistent массив өгөгдлийн бүтэц ашиглаж болох ба үүнийг ашиглан бид эхлээд $go[u]$-г $go[v]$ рүү хуулж, дараа нь зөвхөн шилжилт нь ялгаатай байх тэмдэгтүүдийн утгыг шинэчилнэ. Энэ нь $O(n \log k)$ алгоритмд хүргэнэ.

Хэрэглээ

Өгөгдсөн олонлогийн бүх тэмдэгт мөрийг текстээс олох

Бидэнд тэмдэгт мөрийн олонлог ба текст өгөгдсөн. Бид өгөгдсөн текст дэх олонлогийн бүх тэмдэгт мөрийн бүх орцыг $O(\text{len} + \text{ans})$-д хэвлэх ёстой, энд $\text{len}$ нь текстийн урт, $\text{ans}$ нь хариуны хэмжээ юм.

Бид энэ тэмдэгт мөрийн олонлогийн автоматыг байгуулна. Одоо бид trie-ийн үндэснээс эхлэн автомат ашиглан текстийг үсэг үсгээр нь боловсруулна. Хэрэв бид ямар нэг үед төлөв $v$-д байгаа бөгөөд дараагийн үсэг нь $c$ бол бид $\text{go}(v, c)$-ээр дараагийн төлөв рүү шилжих ба ингэснээр одоогийн таарсан дэд мөрийн уртыг $1$-ээр нэмэгдүүлэх, эсвэл дагаврын холбоосыг дагаж багасгана.

Төлөв $v$-ийн хувьд олонлогийн тэмдэгт мөрүүдтэй таарц байгаа эсэхийг бид хэрхэн олж мэдэх вэ? Эхлээд хэрэв бид $\text{output}$ оройд зогсож байвал тэр оройд харгалзах тэмдэгт мөр текстийн энэ байрлалд дуусах нь ойлгомжтой. Гэвч энэ бол таарц олох цорын ганц боломжит тохиолдол огт биш: хэрэв бид дагаврын холбоосуудыг дагаж нэг буюу хэд хэдэн $\text{output}$ оройд хүрч чадвал олдсон $\text{output}$ орой бүрд харгалзах таарц мөн байх болно. Энэ нөхцөл байдлыг харуулах энгийн жишээг $\{dabce, abc, bc\}$ тэмдэгт мөрийн олонлог ба $dabc$ текстийг ашиглан үүсгэж болно.

Тиймээс хэрэв бид $\text{output}$ орой бүрд түүнд харгалзах тэмдэгт мөрийн индексийг (эсвэл олонлогт давхардсан тэмдэгт мөр гарч ирвэл индексүүдийн жагсаалтыг) хадгалбал бид одоогийн оройноос үндэс хүртэл дагаврын холбоосыг зүгээр л дагах замаар одоогийн төлөвт таарах бүх тэмдэгт мөрийн индексийг $O(n)$ хугацаанд олж чадна. Энэ бол хамгийн үр ашигтай шийдэл биш, учир нь энэ нь нийтдээ $O(n ~ \text{len})$ complexity-д хүргэнэ. Гэвч үүнийг дагаврын холбоос ашиглан хүрч болох хамгийн ойрын $\text{output}$ оройг тооцоолж хадгалах замаар оновчилж болно (үүнийг заримдаа гарцын холбоос гэж нэрлэдэг). Энэ утгыг бид залхуугаар шугаман хугацаанд тооцоолж болно. Ингэснээр орой бүрийн хувьд бид дагаврын холбоосын зам дахь дараагийн тэмдэглэгдсэн орой руу буюу дараагийн таарц руу $O(1)$ хугацаанд ахиж чадна. Тиймээс таарц бүрд бид $O(1)$ хугацаа зарцуулах бөгөөд ингэснээр бид $O(\text{len} + \text{ans})$ complexity-д хүрнэ.

Хэрэв та зөвхөн орцын тоог тоолохыг хүсэж байгаа бөгөөд индексүүдийг өөрсдийг нь олохыг хүсэхгүй байвал та орой $v$ бүрийн хувьд дагаврын холбоосын зам дахь тэмдэглэгдсэн оройн тоог тооцоолж болно. Үүнийг нийтдээ $O(n)$ хугацаанд тооцоолж болно. Ингэснээр бид бүх таарцыг $O(\text{len})$-д нийлбэрлэж чадна.

Өгөгдсөн тэмдэгт мөрүүдийн алинтай нь ч таарахгүй, өгөгдсөн урттай лексикографийн хамгийн бага тэмдэгт мөрийг олох

Тэмдэгт мөрийн олонлог ба $L$ урт өгөгдсөн. Бид тэдгээр тэмдэгт мөрийн алийг нь ч агуулаагүй $L$ урттай тэмдэгт мөрийг олж, ийм тэмдэгт мөрүүдээс лексикографийн хамгийн багыг нь гаргах ёстой.

Бид тэмдэгт мөрийн олонлогийн автоматыг байгуулж болно. $\text{output}$ оройнууд нь бид олонлогийн тэмдэгт мөртэй таарц олсон төлвүүд болохыг сана. Энэ бодлогод бид таарцаас зайлсхийх ёстой тул бидэнд ийм төлөв рүү орохыг зөвшөөрөхгүй. Нөгөө талаас бид бусад бүх оройд орж болно. Тиймээс бид машинаас бүх "муу" оройг устгаж, автоматын үлдсэн графаас $L$ урттай лексикографийн хамгийн бага замыг олно. Энэ бодлогыг жишээ нь гүнээр эхлэх хайлт-аар $O(L)$-д бодож болно.

Өгөгдсөн бүх тэмдэгт мөрийг агуулах хамгийн богино тэмдэгт мөрийг олох

Энд бид ижил санааг ашиглана. Орой бүрд бид энэ төлөвт таарч буй тэмдэгт мөрүүдийг тэмдэглэх маск хадгална. Тэгвэл бодлогыг дараах байдлаар дахин томьёолж болно: эхэндээ $(v = \text{root},~ \text{mask} = 0)$ төлөвт байгаад бид $(v,~ \text{mask} = 2^n - 1)$ төлөвт хүрэхийг хүсэж байна, энд $n$ нь олонлог дахь тэмдэгт мөрийн тоо юм. Бид үсэг ашиглан нэг төлвөөс нөгөө рүү шилжихдээ маскаа зохих ёсоор шинэчилнэ. Өргөнөөр эхлэх хайлт ажиллуулснаар бид $(v,~ \text{mask} = 2^n - 1)$ төлөв рүү хамгийн бага урттай замыг олж чадна.

$k$ тэмдэгт мөр агуулах $L$ урттай лексикографийн хамгийн бага тэмдэгт мөрийг олох

Өмнөх бодлогын адил бид орой бүрд түүнд харгалзах таарцын тоог (өөрөөр хэлбэл дагаврын холбоос ашиглан хүрч болох тэмдэглэгдсэн оройн тоог) тооцоолно. Бид бодлогыг дахин томьёолъё: одоогийн төлөв нь $(v,~ \text{len},~ \text{cnt})$ гурван тоогоор тодорхойлогдох ба бид $(\text{root},~ 0,~ 0)$ төлвөөс $(v,~ L,~ k)$ төлөвт хүрэхийг хүсэж байна, энд $v$ дурын орой байж болно. Ингэснээр бид гүнээр эхлэх хайлт ашиглан ийм замыг олж чадна (мөн хэрэв хайлт ирмэгүүдийг байгалийн дарааллаар нь харвал олдсон зам автоматаар лексикографийн хамгийн бага байх болно).

Дасгал бодлогууд

Эх сурвалж