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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 38: Строка 38:
 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
  
Суффиксная ссылка для каждой вершины <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>"he"</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex> .
  
 
===Шаг 3. Построение сжатых суффиксных ссылок ===
 
===Шаг 3. Построение сжатых суффиксных ссылок ===
Строка 57: Строка 57:
 
== Пример реализации ==
 
== Пример реализации ==
 
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
 
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
<tex>k</tex> {{---}} размер алфавита.
+
<tex>k</tex> {{---}} это размер алфавита.
  
 
'''Структура вершины:'''
 
'''Структура вершины:'''
Строка 70: Строка 70:
 
     '''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>
Строка 79: Строка 79:
 
     '''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>
Строка 90: Строка 90:
 
     '''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>
Строка 101: Строка 101:
 
     '''return''' v.up
 
     '''return''' v.up
  
'''Функция для добавления строки в бор:'''
+
'''Функция, для добавление строки в бор:'''
 
  '''fun''' addString('''string''' s, '''int''' patternNumber):
 
  '''fun''' addString('''string''' s, '''int''' patternNumber):
 
     '''Node''' cur = root
 
     '''Node''' cur = root
Строка 117: Строка 117:
 
     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: Строка 129:
  
 
== Оптимизации ==
 
== Оптимизации ==
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
+
Существует несколько оптимизаций данного алгоритма:
 
+
# Сброс сжатых суффиксных ссылок для посещённых вершин. Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.'''
+
# Сброс пометки терминальной вершины. В изначальном множестве образцов могут быть дублирующиеся строки. Если же таких строк будет много, то наш алгоритм будет очень долго работать. Если же мы будем делать сброс пометки терминальной вершины, когда обнаруживаем ее в первый раз, то таким образом ускорим время работы, так как нас будет интересовать только первое вхождение.
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 
# '''Сброс пометки терминальной вершины.'''
 
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
 
  
 
== Поиск шаблонов с масками ==
 
== Поиск шаблонов с масками ==
Строка 141: Строка 138:
 
|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>.  
  
 
=== Алгоритм поиска ===
 
=== Алгоритм поиска ===

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

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

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

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