Алгоритм Ахо-Корасик - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:18:53Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:33, 1 сентября 2022

2022-09-01T05:33:35Z

93.175.2.117: /* Пример автомата Ахо-Корасик */ Replace back to tex, to the same style as in the beginning of the article

2020-01-19T16:42:24Z

‎Пример автомата Ахо-Корасик: Replace back to tex, to the same style as in the beginning of the article

93.175.2.117: /* Пример автомата Ахо-Корасик */ Replace tex with `because it is more suitable for strings and quotes were separated with extra spaces`


2020-01-19T16:39:35Z
‎Пример автомата Ахо-Корасик:  Replace tex with <code> because it is more suitable for strings and quotes were separated with extra spaces

				
				
				
				
				
				← Предыдущая
				Версия 16:39, 19 января 2020
				
Строка 38:
Строка 38:
  Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.   Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
    
− Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>"she"</tex> максимальным подходящим суффиксом является строка <tex>"he"</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex> . + Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <code>she</code> максимальным подходящим суффиксом является строка <code>he</code>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex> .
    
  ===Шаг 3. Построение сжатых суффиксных ссылок ===   ===Шаг 3. Построение сжатых суффиксных ссылок ===



91.185.54.128: /* Поиск шаблонов с масками */
2019-09-12T13:07:07Z
‎Поиск шаблонов с масками

				
				
				
				
				
				← Предыдущая
				Версия 13:07, 12 сентября 2019
				
Строка 141:
Строка 141:
  |definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>   |definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
  }}   }}
− Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>8</tex> строки <tex>xabvccababcax</tex>.   + Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>.  
    
  === Алгоритм поиска ===   === Алгоритм поиска ===



188.227.78.184: /* Пример реализации */
2017-11-22T18:35:45Z
‎Пример реализации

				
				
				
				
				
				← Предыдущая
				Версия 18:35, 22 ноября 2017
				
Строка 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



Shersh: /* Оптимизации */
2016-06-05T10:39:14Z
‎Оптимизации

				
				
				
				
				
				← Предыдущая
				Версия 10:39, 5 июня 2016
				
Строка 129:
Строка 129:
    
  == Оптимизации ==   == Оптимизации ==
− Существует несколько оптимизаций данного алгоритма: + Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
− # Сброс сжатых суффиксных ссылок для посещённых вершин. Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку. +  
− # Сброс пометки терминальной вершины. В изначальном множестве образцов могут быть дублирующиеся строки. Если же таких строк будет много, то наш алгоритм будет очень долго работать. Если же мы будем делать сброс пометки терминальной вершины, когда обнаруживаем ее в первый раз, то таким образом ускорим время работы, так как нас будет интересовать только первое вхождение. + # '''Сброс сжатых суффиксных ссылок для посещённых вершин.''' 
  + #: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
  + # '''Сброс пометки терминальной вершины.''' 
  + #: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
    
  == Поиск шаблонов с масками ==   == Поиск шаблонов с масками ==



Shersh: /* Пример реализации */
2016-06-05T10:32:46Z
‎Пример реализации

				
				
				
				
				
				← Предыдущая
				Версия 10:32, 5 июня 2016
				
Строка 57:
Строка 57:
  == Пример реализации ==   == Пример реализации ==
  Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />   Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
− <tex>k</tex> {{---}} это размер алфавита. + <tex>k</tex> {{---}} размер алфавита.
    
  '''Структура вершины:'''   '''Структура вершины:'''



Shersh: /* Шаг 3. Построение сжатых суффиксных ссылок */
2016-06-05T10:32:21Z
‎Шаг 3. Построение сжатых суффиксных ссылок

				
				
				
				
				
				← Предыдущая
				Версия 10:32, 5 июня 2016
				
Строка 42:
Строка 42:
  ===Шаг 3. Построение сжатых суффиксных ссылок ===   ===Шаг 3. Построение сжатых суффиксных ссылок ===
  При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.   При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
  + 
  <tex>up(u) =     <tex>up(u) =  
     \begin{cases}      \begin{cases}
Строка 47:
Строка 48:
       \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> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br /> +    \end{cases}</tex> 
− Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии. +  
  + где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.
    
  == Использование автомата ==   == Использование автомата ==



Shersh: /* Шаг 2. Преобразование бора */
2016-06-05T10:30:35Z
‎Шаг 2. Преобразование бора

				
				
				
				
				
				← Предыдущая
				Версия 10:30, 5 июня 2016
				
Строка 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>.
  Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].   Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
  + 
  + Из определений выше можно заметить два следующих факта:
  + * функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;
  + * для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.
  + Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.
    
  ==== Пример автомата Ахо-Корасик ====   ==== Пример автомата Ахо-Корасик ====

← Предыдущая		Версия 05:33, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Задача		{{Задача
	\|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.		\|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.

← Предыдущая		Версия 16:18, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Задача		{{Задача
	\|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.		\|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.

Алгоритм Ахо-Корасик - История изменений

Maintenance script: rollbackEdits.php mass rollback

171.25.193.80 в 05:33, 1 сентября 2022

93.175.2.117: /* Пример автомата Ахо-Корасик */ Replace back to tex, to the same style as in the beginning of the article

93.175.2.117: /* Пример автомата Ахо-Корасик */ Replace tex with because it is more suitable for strings and quotes were separated with extra spaces

91.185.54.128: /* Поиск шаблонов с масками */

188.227.78.184: /* Пример реализации */

Shersh: /* Оптимизации */

Shersh: /* Пример реализации */

Shersh: /* Шаг 3. Построение сжатых суффиксных ссылок */

Shersh: /* Шаг 2. Преобразование бора */

93.175.2.117: /* Пример автомата Ахо-Корасик */ Replace tex with `because it is more suitable for strings and quotes were separated with extra spaces`