Редактирование: Алгоритм Ахо-Корасик

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.
+
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст за время <tex>O(m)</tex> и <tex>O(mk)</tex> памяти.
 
}}
 
}}
  
Строка 9: Строка 9:
  
 
====Пример построенного бора====
 
====Пример построенного бора====
Бор для набора строк <tex> \{ \textbf{he},\ \textbf{she},\ \textbf{his},\ \textbf{hers}\} </tex>:<br />
+
Бор для набора строк <tex> \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} </tex>:<br />
 
[[Файл:Бор.jpg‎]]
 
[[Файл:Бор.jpg‎]]
  
 
=== Шаг 2. Преобразование бора ===
 
=== Шаг 2. Преобразование бора ===
Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br />
+
'''Обозначения''': <tex>[u]</tex> {{---}} слово, приводящее в вершину <tex>u</tex> в боре.<br />
Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br />
+
Узлы бора можно понимать как состояния автомата, а корень как начальное состояние.<br />
Узлы бора, в которых заканчиваются строки, становятся терминальными.<br />
+
Узлы бора, в которых заканчиваются строк, становятся терминалами.<br />
 
Для переходов по автомату заведём в узлах несколько функций:<br />
 
Для переходов по автомату заведём в узлах несколько функций:<br />
 
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />
 
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />
*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка''', и существует переход из  <tex>\mathrm{parent}(u)</tex> в <tex>u</tex> по символу <tex>c</tex>;<br />
+
*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} суффиксная ссылка; здесь <tex>u</tex> {{---}} сын <tex>\mathrm{parent}(u)</tex> по символу <tex>c</tex>;<br />
 
*<tex>\delta(u, c) =  
 
*<tex>\delta(u, c) =  
 
   \begin{cases}
 
   \begin{cases}
Строка 28: Строка 28:
 
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
 
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
 
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
 
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
 
Из определений выше можно заметить два следующих факта:
 
* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;
 
* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.
 
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.
 
  
 
==== Пример автомата Ахо-Корасик ====
 
==== Пример автомата Ахо-Корасик ====
Строка 38: Строка 33:
 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
  
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>\textbf{she}</tex> максимальным подходящим суффиксом является строка <tex>\textbf{he}</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex>.
+
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора; для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>"she"</tex> суффиксной ссылкой является вершина <tex>2</tex> с соответствующей ей строкой <tex>"he"</tex>, которая и является максимальным суффиксом.
 
 
===Шаг 3. Построение сжатых суффиксных ссылок ===
 
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
 
  
 +
===Шаг 3. Построение сжатых суффиксных ссылок. ===
 
<tex>up(u) =  
 
<tex>up(u) =  
 
   \begin{cases}
 
   \begin{cases}
Строка 48: Строка 41:
 
     \varnothing,&\text{if $\pi(u)$ is root;}\\
 
     \varnothing,&\text{if $\pi(u)$ is root;}\\
 
     up(\pi(u)), &\text{else.}
 
     up(\pi(u)), &\text{else.}
   \end{cases}</tex>
+
   \end{cases}</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />
 
+
Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.
где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.
 
  
 
== Использование автомата ==
 
== Использование автомата ==
Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.<br />
+
По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.<br />
  
 
== Пример реализации ==
 
== Пример реализации ==
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
+
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br /><br />
<tex>k</tex> {{---}} размер алфавита.
 
 
 
 
'''Структура вершины:'''
 
'''Структура вершины:'''
 
  '''struct''' Node:
 
  '''struct''' Node:
     '''Node''' son[k]                                 <font color=green>// массив сыновей</font>
+
     '''Node''' son[k]       <font color=green>// массив сыновей; k - это размер алфавита</font>
     '''Node''' go[k]                                 <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font>
+
     '''Node''' go[k]         <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии)</font>
     '''Node''' parent                                 <font color=green>// вершина родитель</font>
+
     '''Node''' parent         <font color=green>// вершина родитель</font>
     '''Node''' suffLink                               <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
+
     '''Node''' suffLink       <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
     '''Node''' up                                     <font color=green>// сжатая суффиксная ссылка</font>
+
     '''Node''' up             <font color=green>// сжатая суффиксная ссылка</font>
     '''char''' charToParent                           <font color=green>// символ, ведущий к родителю</font>
+
     '''char''' charToParent   <font color=green>// символ, ведущий к родителю</font>
     '''bool''' isLeaf                                 <font color=green>// флаг, является ли вершина терминалом</font>
+
     '''bool''' isLeaf           <font color=green>// флаг, является ли вершина терминалом</font>
     '''vector<int>''' leafPatternNumber               <font color=green>// номера строк, за которые отвечает терминал</font>
+
     '''vector<int>''' leafPatternNumber   <font color=green>// номера строк, за которые отвечает терминал</font>
  
'''Функция для вычисления суффиксной ссылки:'''
+
'''Функция, для вычисления суффиксной ссылки:'''
 
  '''Node''' getSuffLink('''Node''' v):
 
  '''Node''' getSuffLink('''Node''' v):
     '''if''' v.suffLink == ''null''                       <font color=green>// если суффиксная ссылка ещё не вычислена</font>
+
     '''if''' '''not''' v.suffLink  <font color=green>// если суффиксная ссылка ещё не вычислена</font>
 
         '''if''' v == root '''or''' v.parent == root
 
         '''if''' v == root '''or''' v.parent == root
 
             v.suffLink = root
 
             v.suffLink = root
Строка 79: Строка 69:
 
     '''return''' v.suffLink
 
     '''return''' v.suffLink
 
   
 
   
'''Функция для вычисления перехода:'''
+
'''Функция, для вычисления перехода:'''
 
  '''Node''' getLink('''Node''' v, '''char''' c):  
 
  '''Node''' getLink('''Node''' v, '''char''' c):  
     '''if''' v.go[c] == ''null''                          <font color=green>// если переход по символу c ещё не вычислен</font>
+
     '''if''' '''not''' v.go[c]   <font color=green>// если переход по символу c ещё не вычислен</font>
 
         '''if''' v.son[c]
 
         '''if''' v.son[c]
 
             v.go[c] = v.son[c]
 
             v.go[c] = v.son[c]
Строка 90: Строка 80:
 
     '''return''' v.go[c]
 
     '''return''' v.go[c]
 
   
 
   
'''Функция для вычисления сжатой суффиксной ссылки:'''
+
'''Функция, для вычисления сжатой суффиксной ссылки:'''
 
  '''Node''' getUp('''Node''' v):
 
  '''Node''' getUp('''Node''' v):
     '''if''' v.up == ''null''                             <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
+
     '''if''' '''not''' v.up      <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
 
         '''if''' getSuffLink(v).isLeaf
 
         '''if''' getSuffLink(v).isLeaf
 
             v.up = getSuffLink(v)
 
             v.up = getSuffLink(v)
Строка 101: Строка 91:
 
     '''return''' v.up
 
     '''return''' v.up
  
'''Функция для добавления строки в бор:'''
+
'''Функция, для добавление строки в бор:'''
  '''fun''' addString('''string''' s, '''int''' patternNumber):
+
  '''fun''' addString('''string const&''' s, '''int''' patternNumber):
 
     '''Node''' cur = root
 
     '''Node''' cur = root
 
     '''for''' i = 0 '''to''' s.length - 1
 
     '''for''' i = 0 '''to''' s.length - 1
         '''char''' c = s[i]
+
         '''char''' c = s[i] - 'a'
 
         '''if''' cur.son[c] == 0
 
         '''if''' cur.son[c] == 0
 
             cur.son[c] = Node
 
             cur.son[c] = Node
Строка 116: Строка 106:
 
         cur = cur.son[c]
 
         cur = cur.son[c]
 
     cur.isLeaf = ''true''
 
     cur.isLeaf = ''true''
     cur.leafPatternNumber.pushBack(patternNumber)
+
     cur.leafPatternNumber.push_back(patternNumber)
'''Функция для процессинга текста (поиск, встречается строка или нет):'''
+
'''Функция, для процессинга текста (поиск, встречается строка или нет):'''
  '''fun''' processText('''string''' t):   
+
  '''fun''' processText('''string const&''' t, '''vector<bool>&''' found):  <font color=green>// found - это вектор, длина которого равна количеству строк</font>
 +
    found.assign(w, ''false'')  <font color=green>// w - количество строк</font>
 
     '''Node''' cur = root
 
     '''Node''' cur = root
 
     '''for''' i = 0 '''to''' t.length - 1  
 
     '''for''' i = 0 '''to''' t.length - 1  
 
         '''char''' c = t[i] - 'a'
 
         '''char''' c = t[i] - 'a'
 
         cur = getLink(cur, c)
 
         cur = getLink(cur, c)
 +
        '''for''' j = 0 '''to''' cur.leafPatternNumber.size - 1
 +
            found[cur.leafPatternNumber[j]] = ''true''
 
         <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
 
         <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
 
             обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
 
             обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
             и так до корня. */</font>
+
             и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */</font>
 
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
 
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
  
 
== Оптимизации ==
 
== Оптимизации ==
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
 
  
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.'''
+
Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 
# '''Сброс пометки терминальной вершины.'''
 
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
 
  
 
== Поиск шаблонов с масками ==
 
== Поиск шаблонов с масками ==
Строка 141: Строка 130:
 
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
 
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
 
}}
 
}}
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>.  
+
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>8</tex> строки <tex>xabvccababcax</tex>.  
  
 
=== Алгоритм поиска ===
 
=== Алгоритм поиска ===

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: