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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
== Описание ==
Автомат Ахо-Корасик позволяет находить в тексте вхождения любой строки из заданного набора строк.
Автомат Ахо-Корасик позволяет находить в тексте вхождения любой строки из заданного набора строк.


Строка 12: Строка 14:
* Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].
* Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].


Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (текст — AAB, набор строк — AAA и B, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.
Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (набор строк — ABA и B, текст — AB, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.
 
== Определение позиций вхождений каждой строки ==
Если нужно не просто проверить, содержал ли текст хотя бы одну строку из набора, а найти позиции вхождений каждой строки, вносятся следующие изменения:
* Вместо bool isTerminal используются vector<int> termIndexes и Vertex *termLink;
* termIndexes — массив номеров исходных строк, заканчивающихся в данной вершине (если в наборе не могло быть одинаковых строк, то достаточно одного номера);
* termLink — ссылка на ближайшую вершину, отличную от данной, у которой isTerminal был бы равен true (то есть эта вершина либо сама является концом какой-то из исходных строк, либо из неё по суффиксным ссылкам достижим такой конец);
* Признаком того, что найдено вхождение какой-то из исходных строк, раньше было isTerminal == true у текущей вершины. Сейчас это будет либо !termIndexes.empty(), либо termLink != nullptr;
* Когда мы обнаруживаем вершину с вхождением, от неё нужно переходить по termLink, пока такой переход возможен, и добавлять в ответ termIndexes всех посещённых вершин.
 
== Оптимизации ==
* Если не важен порядок символов, тип next и autLink можно заменить на unordered_map;
* Тип autLink можно заменить на vector или array;
* Новые вершины можно складывать в отдельный vector или list, тогда тип next можно будет заменить на map<char, int> (если вершины хранятся в vector) или map<char, Vertex *> (если вершины хранятся в list);
* Можно объединить next и autLink.
 
== Код ==
{| width="100%"
| width=50% |


  class Trie {
  class Trie {
     struct Vertex {
     struct Vertex {
         bool isTerminal = false;
         bool isTerminal = 0;
         map<char, Vertex> next;
         map<char, Vertex> next;
         Vertex *sufLink = nullptr;
         Vertex *sufLink = 0;
         map<char, Vertex *> autLink;
         map<char, Vertex *> autLink;
     } root;
     } root;
   
   
  public:
  public:
     void add(const string &s) {
     void insert(const string &s) {
         Vertex *v = &root;
         Vertex *v = &root;
         for (const char &c : s)
         for (char c : s)
             v = &v->next[c];
             v = &v->next[c];
         v->isTerminal = true;
         v->isTerminal = 1;
     }
     }
   
   
Строка 57: Строка 77:
     bool check(const string &s) {
     bool check(const string &s) {
         Vertex *v = &root;
         Vertex *v = &root;
         for (const char &c : s) {
         for (char c : s) {
             v = v->autLink[c];
             v = v->autLink[c];
             if (v->isTerminal)
             if (v->isTerminal)
                 return true;
                 return 1;
        }
        return 0;
    }
};
 
| width="10px" | &nbsp;
| width=50% |
 
class Trie {
    struct Vertex {
        vector<int> termIndexes;
        Vertex *termLink = 0;
        unordered_map<char, Vertex> next;
        Vertex *sufLink = 0;
        unordered_map<char, Vertex *> autLink;
    } root;
    int stringCount = 0;
public:
    void insert(const string &s) {
        Vertex *v = &root;
        for (char c : s)
            v = &v->next[c];
        v->termIndexes.push_back(stringCount++);
    }
    void build(int alphabetSize) {
        queue<Vertex *> q;
        root.sufLink = &root;
        q.push(&root);
        while (!q.empty()) {
            Vertex *v = q.front();
            q.pop();
            for (auto &[c, to] : v->next) {
                to.sufLink = (v == &root ? &root : v->sufLink->autLink[c]);
                q.push(&to);
            }
            for (char c = 'a'; c < 'a' + alphabetSize; c++) {
                if (v->next.count(c))
                    v->autLink[c] = &v->next[c];
                else
                    v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]);
            }
            v->termLink = (!v->sufLink->termIndexes.empty() ? v->sufLink : v->sufLink->termLink);
         }
         }
         return false;
    }
    vector<vector<int>> check(const string &s) {
        vector<vector<int>> res(stringCount);
        Vertex *v = &root;
        for (int i = 0; i < s.size(); i++) {
            v = v->autLink[s[i]];
            if (!v->termIndexes.empty() || v->termLink)
                for (Vertex *term = (!v->termIndexes.empty() ? v : v->termLink); term; term = term->termLink)
                    for (int termIndex : term->termIndexes)
                        res[termIndex].push_back(i);
        }
         return res;
     }
     }
  };
  };
|}


== Ссылки ==
== Ссылки ==

Текущая версия от 13:01, 10 сентября 2023

Описание

Автомат Ахо-Корасик позволяет находить в тексте вхождения любой строки из заданного набора строк.

Автомат строится на основе бора. Каждая вершина в боре соответствует некоторой строке. Терминальные вершины соответствуют строкам из исходного набора.

Суффиксная ссылка из вершины, соответствующей строке s, ведёт в вершину, соответствующую длиннейшему из имеющихся в боре суффиксов строки s.
Суть суффиксных ссылок та же, что и ячеек префикс-функции — они определяют, в какое состояние (в какую вершину) мы переходим, если очередной символ текста не совпал с ожидаемым (в данном случае ожидаемыми будут символы, имеющиеся в next у соответствующей вершины бора).

Чтобы за O(1) определять, в какую вершину мы должны перейти, если были в вершине v и встретили символ c, дополнительно вычисляются автоматные ссылки: v->autLink[c].

Если мы будем просматривать вершины бора в порядке обхода BFSом, то суффиксные и автоматные ссылки можно вычислять так:

  • Суффиксная ссылка из вершины to при просмотре ребра v → (c, to): Если v — корень, то to->sufLink = v, иначе to->sufLink = v->sufLink->autLink[c].
  • Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].

Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (набор строк — ABA и B, текст — AB, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.

Определение позиций вхождений каждой строки

Если нужно не просто проверить, содержал ли текст хотя бы одну строку из набора, а найти позиции вхождений каждой строки, вносятся следующие изменения:

  • Вместо bool isTerminal используются vector<int> termIndexes и Vertex *termLink;
  • termIndexes — массив номеров исходных строк, заканчивающихся в данной вершине (если в наборе не могло быть одинаковых строк, то достаточно одного номера);
  • termLink — ссылка на ближайшую вершину, отличную от данной, у которой isTerminal был бы равен true (то есть эта вершина либо сама является концом какой-то из исходных строк, либо из неё по суффиксным ссылкам достижим такой конец);
  • Признаком того, что найдено вхождение какой-то из исходных строк, раньше было isTerminal == true у текущей вершины. Сейчас это будет либо !termIndexes.empty(), либо termLink != nullptr;
  • Когда мы обнаруживаем вершину с вхождением, от неё нужно переходить по termLink, пока такой переход возможен, и добавлять в ответ termIndexes всех посещённых вершин.

Оптимизации

  • Если не важен порядок символов, тип next и autLink можно заменить на unordered_map;
  • Тип autLink можно заменить на vector или array;
  • Новые вершины можно складывать в отдельный vector или list, тогда тип next можно будет заменить на map<char, int> (если вершины хранятся в vector) или map<char, Vertex *> (если вершины хранятся в list);
  • Можно объединить next и autLink.

Код

class Trie {
    struct Vertex {
        bool isTerminal = 0;
        map<char, Vertex> next;
        Vertex *sufLink = 0;
        map<char, Vertex *> autLink;
    } root;

public:
    void insert(const string &s) {
        Vertex *v = &root;
        for (char c : s)
            v = &v->next[c];
        v->isTerminal = 1;
    }

    void build(int alphabetSize) {
        queue<Vertex *> q;
        root.sufLink = &root;
        q.push(&root);

        while (!q.empty()) {
            Vertex *v = q.front();
            q.pop();

            for (auto &[c, to] : v->next) {
                to.sufLink = (v == &root ? &root : v->sufLink->autLink[c]);                
                q.push(&to);
            }

            for (char c = 'a'; c < 'a' + alphabetSize; c++) {
                if (v->next.count(c))
                    v->autLink[c] = &v->next[c];
                else
                    v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]);
            }

            v->isTerminal |= v->sufLink->isTerminal;
        }
    }

    bool check(const string &s) {
        Vertex *v = &root;
        for (char c : s) {
            v = v->autLink[c];
            if (v->isTerminal)
                return 1;
        }
        return 0;
    }
};
 
class Trie {
    struct Vertex {
        vector<int> termIndexes;
        Vertex *termLink = 0;
        unordered_map<char, Vertex> next;
        Vertex *sufLink = 0;
        unordered_map<char, Vertex *> autLink;
    } root;
    int stringCount = 0;

public:
    void insert(const string &s) {
        Vertex *v = &root;
        for (char c : s)
            v = &v->next[c];
        v->termIndexes.push_back(stringCount++);
    }

    void build(int alphabetSize) {
        queue<Vertex *> q;
        root.sufLink = &root;
        q.push(&root);

        while (!q.empty()) {
            Vertex *v = q.front();
            q.pop();

            for (auto &[c, to] : v->next) {
                to.sufLink = (v == &root ? &root : v->sufLink->autLink[c]);
                q.push(&to);
            }

            for (char c = 'a'; c < 'a' + alphabetSize; c++) {
                if (v->next.count(c))
                    v->autLink[c] = &v->next[c];
                else
                    v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]);
            }

            v->termLink = (!v->sufLink->termIndexes.empty() ? v->sufLink : v->sufLink->termLink);
        }
    }

    vector<vector<int>> check(const string &s) {
        vector<vector<int>> res(stringCount);

        Vertex *v = &root;
        for (int i = 0; i < s.size(); i++) {
            v = v->autLink[s[i]];

            if (!v->termIndexes.empty() || v->termLink)
                for (Vertex *term = (!v->termIndexes.empty() ? v : v->termLink); term; term = term->termLink)
                    for (int termIndex : term->termIndexes)
                        res[termIndex].push_back(i);
        }

        return res;
    }
};

Ссылки

Теория:

Код: