Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 24.06.2014 | нет комментариев

В посте я постарался избежать трудных дефиниций и суровых матетематических доказательств, а некоторые вещи вообще внятны подсознательно. Алгорифм комфортно разбивается взаимосвязные части, следственно и уловить правило его работы не должно составлять труда.

Исходное изложение

Алгорифм Ахо-Корасик реализует результативный поиск всех вступлений всех строк-примеров в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем официально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — обнаружить все допустимые вступления строк pattern[i] в s.

Суть алгорифма заключена в применение конструкции данных — бора и построения по нему финального детерминированного автомата. Значимо помнить, что задача поиска подстроки в строки банально реализуется за квадратичное время, следственно для высокоэффективной работы значимо, чтоб все части Ахо-Корасика ассимптотически не превосходили линию касательно длинны строк. Мы возвратимся к оценке трудности в конце, а пока поближе посмотрим на составляющие алгорифма.

Построение бора по комплекту строк-примеров

Конструкция бора

Что же такое бор? Сурово говоря, бор — это дерево, в котором всякая вершина обозначает какую-то строку (корень обозначает нулевую строку — !>Функции создания новой вершины и инициализации бора:

vector<bohr_vrtx> bohr;

bohr_vrtx make_bohr_vrtx(){
   bohr_vrtx v;
   //(255)=(2^8-1)=(все единицы в всяком байте памяти)=(-1 в дополнительном коде целого 4-байтного числа int)
   memset(v.next_vrtx, 255, sizeof(v.next_vrtx));
   v.flag=false;
   return v;
}

void bohr_ini(){
   //добавляем исключительную вершину - корень
   bohr.push_back(make_bohr_vrtx());
}   

Процедура добавление строки-примера в бор:

void add_string_to_bohr(const string& s){
   int num=0; //начинаем с корня   
   for (int i=0; i<s.length(); i  ){
      char ch=s[i]-'a'; //получаем номер в алфавите
      if (bohr[num].next_vrtx[ch]==-1){ //-1 - знак отсутствия ребра
         bohr.push_back(make_bohr_vrtx());
         bohr[num].next_vrtx[ch]=bohr.size()-1;         
         }
      num=bohr[num].next_vrtx[ch];
   }
   bohr[num].flag=true;
   pattern.push_back(s);
   bohr[num].pat_num=pattern.size()-1;
}

Проверка наличия строки в боре:

bool is_string_in_bohr(const string& s){
   int num=0;   
   for (int i=0; i<s.length(); i  ){
      char ch=s[i]-'a';
      if (bohr[num].next_vrtx[ch]==-1){
         return false;         
         }
      num=bohr[num].next_vrtx[ch];
   }
   return true;
}

Построение автомата по бору

Изложение правила работы

Наша задача — возвести финальный детерминированный автомат. Что за штука такая дозволено посмотреть тут. Лаконично, состояние автомата — это какая-то вершина бора. Переход из состояний осуществляется по 2 параметрам — нынешней вершине v и символу ch. по которорому нам нужно сдвинуться из этой вершины. Поопределеннее, нужно обнаружить вершину u, которая обозначает наидлиннейшую строку, состоящую из суффикса строки v (допустимо нулевого) символа ch. Если такого в боре нет, то идем в корень.

Для чего это нам нужно? Представим, что мы можем вычислить такую вершину стремительно, за константное время. Пускай, мы стоим в некой вершине бора, соответствующей подстроке [i..j] строки s, вступления в которую мы ищем. Сейчас обнаружим все строки бора, суффиксы s[i..j]. Утверждается, что их дозволено искать стремительно (описано дальше). Позже этого, легко перейдем из состояния автомата v в состояние u по символу s[j 1] и продолжим поиск.

image
(Рис. 3)
Для реализации автомата нам потребуется представление суффиксной ссылки из вершины.

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

Назовем суффиксной ссылкой вершины v указатель на вершину u, такую что строка u — крупнейший cобственный суффикс строки v, либо, если такой вершины нет в боре, то указатель на корень. В частности, ссылка из корня ведет в него же. Нам потребуются суффиксные ссылки для всякой вершины в боре, следственно немножко изменим конструкцию вершины и процедуру создание вершины, введя дополнительную переменную suff_link.

Метаморфозы в коде:

struct bohr_vrtx{
   //...
   int suff_link; //suff_link - суффиксная ссылка
};

bohr_vrtx make_bohr_vrtx(){
   bohr_vrtx v;
   //...
   v.suff_link=-1; //изначально - суф. ссылки нет
   return v;
}

Вот пример расстановки суф. ссылок для бора на рис. 1:
image
(Рис. 4)

Реализация автомата

Возвратимся к задача стремительного перехода между состояниями автомата. Видимо, что каждого допустимых переходов существует bohr.size()*k, так как для для всякой допустимой вершиной и всяким допустимым символом в алфавите необходимо знать переход. Предподсчет значительно снизит среднее время работы алгорифма, следственно воспользуемся идеями ленивой динамики — будем считать по необходимости и запоминать теснее сосчитанные значения.
Введем вычисляемую функцию для перехода (v,ch). Идея здесь вот в чем: если из нынешней вершины есть ребро c символом ch, то пройдем по нему, в обратном случаем пройдем по суффиксной ссылке и запустимся рекурсивно от новой вершины. Отчего это работает, додуматься не сложно.

image
(Рис. 5)

Вопрос лишь в правильном приобретение суф. ссылки от вершины. В этой задаче тоже дозволено применять ленивую динамику. Эвристика заключена в дальнейшем: для приобретения суф. ссылки вершины v (строки s[i..j]) спустимся до ее прародителя par, пройдем по суф. ссылке par и запустим переход от нынешней вершины t по символу symb, тот, что написан на ребре от par до v. Видимо, что вначале мы попадем в крупнейший суфикс s[i..j-1] такой что, он имеет ребро с символом symb, потом пройдем по этому ребру. По определению, получившаяся вершина и есть суффикная ссылка из вершин v.

image
(Рис. 6)

Выходит, видно, что функции приобретения суффиксной ссылки и перехода из состояния автомата взаимосвязаны. Их комфортная реализация представляет 2 функции, всякая из которых рекурсивно вызывает иную. База обоих рекурсий — суф. ссылка из корня либо из сына корня ведет в корень.

Для начала изменим конструкцию вершины и процедуру создания новой вершины:

struct bohr_vrtx{
   //...
   int auto_move[k],par; //auto_move - запоминание перехода автомата, par - вершина-папа в дереве
   char symb; //символ на ребре от par к этой вершине 
};

bohr_vrtx make_bohr_vrtx(int p,char c){ //передаем номер папы и символ на ребре в боре
   bohr_vrtx v;
   //...
   memset(v.auto_move, 255, sizeof(v.auto_move));
   v.par=p;
   v.symb=c;
   return v;
}

Полная реализация автомата требует предобъявления одной из функций:

int get_auto_move(int v, char ch);

int get_suff_link(int v){
   if (bohr[v].suff_link==-1) //если еще не считали
      if (v==0||bohr[v].par==0) //если v - корень либо прародитель v - корень
         bohr[v].suff_link=0;
      else
         bohr[v].suff_link=get_auto_move(get_suff_link(bohr[v].par), bohr[v].symb);
   return bohr[v].suff_link;
}

int get_auto_move(int v, char ch){
   if (bohr[v].auto_move[ch]==-1)
      if (bohr[v].next_vrtx[ch]!=-1)
         bohr[v].auto_move[ch]=bohr[v].next_vrtx[ch];
      else
         if (v==0)
            bohr[v].auto_move[ch]=0;
         else
            bohr[v].auto_move[ch]=get_auto_move(get_suff_link(v), ch);
   return bohr[v].auto_move[ch];
}

Обнаружение «отличных» суффиксных ссылок

С автоматом нетрудно определить сам алгорифм: считываем строку, двигаемся из состояния в состояние по символам строки, в всяком из состояний двигаемся по суф. ссылками, то есть по суффиксам строки в позиции автомата, проверяя при этом присутствие их в боре.
Все бы ничего, но оказывается, что данный вариант Ахо-Корасика имеет квадратичную ассимптотику касательно N — длинны считываемой строки s. Подлинно, для строки из состояния v дозволено обнаружить v.length() суффиксов, а переход из состояний может легко увеличивать на 1 длину этой строки. Цимес в том, Дабы двигаясь по суф. ссылкам попадать только в заведомо имеющиеся среди строк-примеров. Введем представление «отличных» суф. ссылок suff_flink. Так, bohr[v].suff_flink — это ближайший суффикс, имеющийся в боре, для которого flag=true. Число «прыжков» при применение таких ссылок уменьшится и станет пропорционально числу желанных вступлений, оканчивающихся в этой позиции.

image
(Рис. 7)

Вновь мальца изменим конструкцию вершины и процедуру добавления:

struct bohr_vrtx{
   //...
   int suff_flink; //suff_flink - "отличная" суф. ссылка
};

bohr_vrtx make_bohr_vrtx(int p,char c){
   bohr_vrtx v;
   //...
   v.suff_flink=-1;
   return v;
}

Вычислять их достаточно легко, все той же ленивой динамикой. Введем функцию подсчета «хорошой» суф. ссылки. Если для вершине по суф. ссылке flag=true, то это и есть желанная вершина, в другом случае рекурсивно запускаемся от этой же вершины.

Вычисление отличной суф. ссылки:

int get_suff_flink(int v){ 
   if (bohr[v].suff_flink==-1){
      int u=get_suff_link(v);
      if (u==0) //либо v - корень, либо суф. ссылка v указывает на корень 
         bohr[v].suff_flink=0;
      else
         bohr[v].suff_flink=(bohr[u].flag)?u:get_suff_flink(u);
   }
   return bohr[v].suff_flink;
}

Реализация поиска по автомату

Поиск реализуется банально. Нам понадобится процедура хождения по «отличным» суф. ссылкам check(v,i) из нынешней позиции автомата v рассматривая, что эта позиция оканчивается на i-ую букву в слове s.

check(v,i)

void check(int v,int i){
    for(int u=v;u!=0;u=get_suff_flink(u)){
        if (bohr[u].flag) cout<<i-pattern[bohr[u].pat_num].length() 1<<" "<<pattern[bohr[u].pat_num]<<endl;
    }
}

Вот и сам поиск:

void find_all_pos(const string& s){
    int u=0;
    for(int i=0;i<s.length();i  ){
        u=get_auto_move(u,s[i]-'a');
        check(u,i 1);
    }
}

А вот пример работы:

   bohr_ini();
   add_str_to_bohr("abc");
   add_str_to_bohr("bcdc");
   add_str_to_bohr("cccb");
   add_str_to_bohr("bcdd");
   add_str_to_bohr("bbbc");
   find_all_pos("abcdcbcddbbbcccbbbcccbb");   

Запуск:
1 abc
2 bcdc
6 bcdd
10 bbbc
13 cccb
16 bbbc
19 cccb

Оценка трудности и методы хранения

Присутствующий вариант алгорифм проходит циклом по длине s (N=s.length()), откуда его теснее дозволено оценить как O(N*O(check)), но так как check прыгает только по заведомо помеченным вершинам, для которых flag=true, то всеобщую ассимптотику дозволено оценить как O(N t), где t — число всех допустимых вступлений всех строк-примеров в s. Если быть точным и рассматривать вычисления автомата и суф. ссылок, то алгорифм работает O(M*k N t), где M=bohr.size(). Память — константные массивы размера k для всякой вершины бора, откуда и выливается оценка O(M*k).

Оказывается, иной метод хранение, а определенно, обращения к алфавиту, горазд изменить эту оценку. Будем применять отображение map<char,int> взамен массива. Читаем тут и тут, видим, что конструкция данных map из STL реализована красно-черным деревом, а время обращения к его элементам пропорционально логарифму числа элементов. В нашем случае — двоичному логарифму размера алфавита k (что фактически константа). Всеобщее время — O((M N)*log k t). На практике, это значительнее стремительней массива. Map совсем не хранит лишних ячеек памяти для элементов, следственно память пропорциональна числу ребер в боре (а следственно и числу вершин в боре, т.к. в дереве с M вершин — M-1 ребер). число вычислений переходов автомата, видимо, пропорционально длине строки. Получившаяся оценка — O((M N)*log k).

Вариант с массивами next_vrtx[k],auto_move[k] Вариант с red-black tree map<char,int>
Time complexity O(M*k N t) O((M N)*log k t)
Space complexity O(M*k) O((M N)*log k)

PS: Вот ссылка на всецело реализованный рабочий алгорифм: Aho-Corasick alg.

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB