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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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‎]]
  
Строка 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>"she"</tex>, но такой строки больше в нашем автомате нет. Возьмем второй по длине суффикс <tex>"he"</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</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> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.
 
  
 
== Использование автомата ==
 
== Использование автомата ==
Строка 57: Строка 49:
 
== Пример реализации ==
 
== Пример реализации ==
 
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
 
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
<tex>k</tex> {{---}} размер алфавита.
+
<tex>k</tex> {{---}} это размер алфавита.
  
 
'''Структура вершины:'''
 
'''Структура вершины:'''
 
  '''struct''' Node:
 
  '''struct''' Node:
 
     '''Node''' son[k]                                <font color=green>// массив сыновей</font>
 
     '''Node''' son[k]                                <font color=green>// массив сыновей</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>
Строка 70: Строка 62:
 
     '''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''' v.suffLink == '''null'''                        <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: Строка 71:
 
     '''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''' v.go[c] == '''null'''                              <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: Строка 82:
 
     '''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''' v.up == '''null'''                                <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
 
         '''if''' getSuffLink(v).isLeaf
 
         '''if''' getSuffLink(v).isLeaf
 
             v.up = getSuffLink(v)
 
             v.up = getSuffLink(v)
Строка 101: Строка 93:
 
     '''return''' v.up
 
     '''return''' v.up
  
'''Функция для добавления строки в бор:'''
+
'''Функция, для добавление строки в бор:'''
 
  '''fun''' addString('''string''' s, '''int''' patternNumber):
 
  '''fun''' addString('''string''' 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];
 
         '''if''' cur.son[c] == 0
 
         '''if''' cur.son[c] == 0
 
             cur.son[c] = Node
 
             cur.son[c] = Node
Строка 117: Строка 109:
 
     cur.isLeaf = ''true''
 
     cur.isLeaf = ''true''
 
     cur.leafPatternNumber.pushBack(patternNumber)
 
     cur.leafPatternNumber.pushBack(patternNumber)
'''Функция для процессинга текста (поиск, встречается строка или нет):'''
+
'''Функция, для процессинга текста (поиск, встречается строка или нет):'''
 
  '''fun''' processText('''string''' t):   
 
  '''fun''' processText('''string''' t):   
 
     '''Node''' cur = root
 
     '''Node''' cur = root
Строка 129: Строка 121:
  
 
== Оптимизации ==
 
== Оптимизации ==
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
+
# Сброс сжатых суффиксных ссылок для посещённых вершин. Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 
+
# Сброс пометки терминальной вершины.
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.'''
 
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 
# '''Сброс пометки терминальной вершины.'''
 
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
 
  
 
== Поиск шаблонов с масками ==
 
== Поиск шаблонов с масками ==
Строка 141: Строка 129:
 
|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>.  
  
 
=== Алгоритм поиска ===
 
=== Алгоритм поиска ===

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

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

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

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