Алгоритм Ахо-Корасик: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Исправлен баг в коде обхода басом)
Строка 134: Строка 134:
 
             Vertex *child = pair.second;
 
             Vertex *child = pair.second;
 
             Vertex *parent_suffix = v->link; // нашли максимальный суффикс родителя
 
             Vertex *parent_suffix = v->link; // нашли максимальный суффикс родителя
             while(parent_suffix != root && parent_suffix->to.count(parent_char) == 0) {
+
             while(parent_suffix != root && parent_suffix->to.count(parent_char) == 0) {//пытаемся найти вершину из которой есть ребро по символу или доходим до корня
 
                 parent_suffix = parent_suffix->->link;
 
                 parent_suffix = parent_suffix->->link;
 
             }
 
             }

Версия 20:24, 28 апреля 2020

Суффиксные ссылки

Допустим, теперь нам дана строка $s$ и словарь $D=\{a_1,...,a_n\}$, содержащий слова-маркеры. Решаемые же задачи могут быть самыми разными:

  1. Найти все "плохие" слова в тексте и заменить их всякими нечитаемыми символами (фильтрация нецензурной брани)
  2. Пометить текст как спам, если там встречаются слова "уникальное предложение только сегодня бесплатно без регистрации и смс"
  3. Попытаться классифицировать по ключевым словам отзыв на Алиэкспресс как хороший или плохой

Конечно, для решения этих задач уже давно придуманы более крутые методы, дающие на порядок лучшие результаты, но нам нужно было рассмотреть хотя бы несколько примеров, пусть и синтетических.

Итак, мы идём по строке и пытаемся понять, находится ли некоторая рассматриваемая подстрока в нашем словаре. Понятно, что если следующий рассматриваемый символ $c$ совпадает с переходом по бору, то всё ок и мы переходим дальше. Но возникает вопрос — что делать, если следующий символ в строке не совпадает с переходом по бору?

Самый очевидный вариант — откатиться в начало и выполнять поиск с первого символа. В случае, если нам необходимо выделить в тексте только целое слово, ограниченное с двух сторон пробелами, такой подход будет работать. Но что делать, если нам нужно выделить какую-то часть слова? В этом случае получится, что мы пропустим какую-то из строк словаря, если она начинается внутри другой.

Тогда нам нужно откатиться на такой шаг, где мы бы точно не пропустили какое-то другое слово. И если подумать, то получается, что этим шагом должна являться такая вершина бора, в которой лежит наибольший суффикс уже найденной строки. Как это понять?

  • Во-первых, вершина, в которую мы совершим "откат" или "переход назад", точно должна быть суффиксом — только такие строки имеют одинаковый конец и начинаются где-то внутри другой.
  • Во-вторых, нас интересует только максимальный суффикс, потому что если для какой-то строки мы нашли суффикс $s_1$ при том, что в боре есть суффикс $s_2$ и $|s_1|<|s_2|$, то мы точно пропустим $s_2$.

Теперь, наконец, можно дать определение суфф-ссылки. Суффиксная ссылка для вершины $v$ — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине $v$. Понятно, что для корня суффиксная ссылка должна вести в себя, так как мы не должны прекращать поиск по бору в случае, если не можем по какому-то символу выйти из корня.

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

Наконец, мы можем поговорить о самом алгоритме. Задачу, решаемую алгоритмом, мы уже определили выше: дан словарь $D=\{a_1,...,a_n\}$ и строка $s$. Необходимо найти все позиции, где строки словаря входят в текст. Решать эту задачу будем следующим образом. Будем обрабатывать символы текста по одному и поддерживать наибольшую строку, являющуюся

  1. префиксом строки из словаря
  2. суффиксом считанного на данный момент текста

Если эта строка совпадает с какой-то $a_i$, то отметим текущий символ — в нём заканчивается текущая строка $a_i$. Для этой задачи нам нужно как-то эффективно хранить и работать со всеми префиксами слов из словаря — для этого нам и понадобится префиксное дерево.

Добавим все слова в префиксное дерево и пометим соответствующие им вершины как терминальные. Теперь наша задача состоит в том, чтобы при добавлении очередного символа быстро находить вершину в префиксном дереве, которая соответcтвует наидлиннейшему входящему в бор суффиксу нового выписанного префикса. Для этого нам понадобятся несколько вспомогательных понятий.

Определение. Суффиксная ссылка $l(v)$ ведёт в вершину $u \ne v$, являющуюся наидлиннейшим собственным суффиксом строки $v$, принимаемым бором.

Определение. Автоматный переход $g(v,c)$ ведёт в вершину $u$, которая соответствует минимальному принимаемому бором суффиксу строки $v+c$. Если такой переход есть в боре, то автоматный переход ведёт туда же.

Нам нужно заметить, что

  • $l(s_{0:n})=g(l(s_{0:n-1}),s_n)$
  • Если не существует прямого перехода $v \longrightarrow_c u$, то $g(v,c)=g(l(v),c)$

Этими свойствами мы воспользуемся при реализации поиска суффиксных ссылок и автоматных переходов.

Реализация

const int k = 26;

struct Vertex {
    // список переходов по бору и список автоматных переходов
    Vertex *to[k] = {0}, *go[k] = {0};
    // суффиксная ссылка и ссылка на родителя
    Vertex *link = 0, *parent;
    // символ, по которому был сделан переход в эту вершину
    int parent_char;

    Vertex (int _pch, Vertex *_p) {
        parent_char = _pch;
        parent = _p;
    }
};

Добавление ссылки почти такое же:

void add_string(string s) {
    Vertex *v = root;
    for (char _c : s) {
        c -= 'a';
        if (!v->to[c]) {
            v->to[c] = new Vertex(c, v);
        }
        v = v->to[c];
    }
}

Далее мы рассмотрим два способа реализации поиска суфф-ссылок — ленивый с мемоизацией и через bfs.

// нам нужно объявить две функции, ссылающиеся друг на друга
// в C++ для этого нужно одну из них объявить только с сигнатурой перед другой
Vertex* go(Vertex *v, int c);

Vertex* link(Vertex *v) {
    if (!v->link) {
        // для строк длины меньше двух суффиксная ссылка это корень
        if (v == root || v->p == root) {
            v->link = root;
        // иначе найдём суфф-ссылку через суффикс родителя
        } else {
            v->link = go(link(v->parent), v->parent_char);
        }
    }
    return v->link;
}

Vertex* go(Vertex *v, int c) {
    if (!v->go[c]) {
        // если переход есть, то автоматный должен вести туда же
        if (v->to[c]) {
            v->go[c] = v->to[c];
        // если перехода нет из корня, то нужно сделать петлю
        } else if (v == root) {
            v->go[c] = root;
        // иначе найдём суффиксную ссылку и запишем её в переход
        } else {
            v->go[c] = go(link(v), c);
        }
    }
    return v->go[c];
}

Альтернатива данной реализации работает через поиск в ширину. В момент, когда мы построили префиксное дерево, мы можем запустить на нём bfs, который сделает ровно то же самое, только более явно. Также в этом случае мы можем попробовать обойтись без массива автоматных переходов — так как все суфф-ссылки будут посчитаны заранее, нам не нужно хранить какую-то дополнительную информацию, чтобы через неё лениво пересчитывать переходы.

Для корня и его прямых потомков ссылка, как уже было сказано выше, должна вести в корень. Для каждой последующей вершины нам нужно обращаться к потомку и пытаться по заданному символу сделать переход из суффиксной ссылки. Но, несмотря на то, что на словах это выглядит довольно стрёмно, на деле всё оказывается куда проще.

struct Vertex {
    map<int, Vertex*> to;
    Vertex *link;
};

void bfs(Vertex *root) {
    queue<Vertex*> q;
    // сразу проставим ссылку корню и его детям
    root->link = root;
    for (auto pair : root->to) {
        pair.second->link = root;
        // запушим детей в очередь, чтобы начать со второго слоя бора
        q.push(pair.second);
    }
    // идём обычным бфсом
    while (!q.empty()) {
        // достали вершину
        auto v = q.front();
        q.pop();
        // обойдём всех потомков, для которых есть переход в боре
        for (auto pair : v->to) {
            int parent_char = pair.first;
            Vertex *child = pair.second;
            Vertex *parent_suffix = v->link; // нашли максимальный суффикс родителя
            while(parent_suffix != root && parent_suffix->to.count(parent_char) == 0) {//пытаемся найти вершину из которой есть ребро по символу или доходим до корня
                parent_suffix = parent_suffix->->link;
            }
            Vertex *next_suffix = parent_suffix->to[parent_char]; // нашли переход из суффикса родителя по заданному символу
            child->link = next_suffix; // присвоили это значение ребёнку
            q.push(child); // запушили ребёнка в очередь
        }
    }
}