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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:21:38Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:21, 1 сентября 2022

2022-09-01T05:21:28Z

Penguinni в 17:47, 22 марта 2017

2017-03-22T17:47:06Z

Дмитрий Мурзин: ё

2017-01-24T13:26:46Z

KK: /* Историческая справка */

2015-04-13T19:31:36Z

‎Историческая справка

KK: /* Историческая справка */

2015-03-18T13:33:13Z

‎Историческая справка

KK: /* Историческая справка */

2015-03-18T13:26:20Z

‎Историческая справка

KK: /* Историческая справка */

2015-03-18T13:25:44Z

‎Историческая справка

KK в 13:24, 18 марта 2015

2015-03-18T13:24:50Z

KK: /* Источники информации */

2015-03-18T13:16:22Z

‎Источники информации

← Предыдущая		Версия 16:21, 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 Майкл Наки].
−	\|}
−
	'''Алгоритм МакКрейта''' (англ. ''McCreight's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена\| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.		'''Алгоритм МакКрейта''' (англ. ''McCreight's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена\| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.

← Предыдущая		Версия 05:21, 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 Майкл Наки].
		+	\|}
		+
	'''Алгоритм МакКрейта''' (англ. ''McCreight's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена\| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.		'''Алгоритм МакКрейта''' (англ. ''McCreight's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена\| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.

@@ Строка 6: / Строка 6: @@
 == Теоретическое обоснование ==
 Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.
-Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j..n]</tex> и <tex>s[i..n]</tex> среди всех <tex>j < i</tex>.
+Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j \ldots n]</tex> и <tex>s[i \ldots n]</tex> среди всех <tex>j < i</tex>.
 Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
@@ Строка 12: / Строка 12: @@
 {{Лемма
 |id=lemma_head
-|statement=Пусть <tex>head_i = s[i..i+h]</tex>, тогда <tex>s[i+1..i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
+|statement=Пусть <tex>head_i = s[i \ldots i+h]</tex>, тогда <tex>s[i+1 \ldots i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
 |proof=
 * При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
-* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..n]</tex>. Тогда <tex>s[j+1..n]</tex> будет иметь с <tex>s[i+1..n]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
+* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j \ldots n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i \ldots n]</tex>. Тогда <tex>s[j+1 \ldots n]</tex> будет иметь с <tex>s[i+1 \ldots n]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
 }}
@@ Строка 44: / Строка 44: @@
 |statement=Инвариант алгоритма сохраняется
 |proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf,\ head_i</tex> с неопределенными суффиксными ссылками.
-Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j..n],\ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..n]</tex>. Тогда и <tex>s[i..n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
+Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j \ldots n],\ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1 \ldots n]</tex>. Тогда и <tex>s[i \ldots n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
 }}
@@ Строка 50: / Строка 50: @@
 В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
 * <tex>parent</tex> {{---}} предок
-* <tex>start, end</tex> {{---}} метка подстроки <tex> s[start..end] </tex> на ребре от предка
+* <tex>start, end</tex> {{---}} метка подстроки <tex> s[start \ldots end] </tex> на ребре от предка
 * <tex>length = end - start + 1</tex> {{---}} длина ребра до предка
 * <tex>depth</tex> {{---}} глубина вершины в символах

@@ Строка 2: / Строка 2: @@
 ==Историческая справка==
-Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году  предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf Edward M. McCreight {{---}} A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил  свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf Esko Ukkonen {{---}} On-line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
+Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf Edward M. McCreight {{---}} A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf Esko Ukkonen {{---}} On-line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
 == Теоретическое обоснование ==
@@ Строка 18: / Строка 18: @@
 }}
-Если нам известны суффиксные ссылки <tex>u.suf</tex> для каждой вершины <tex>u</tex>, мы можем быстро перейти от позиции <tex>head_i</tex> к ее суффиксу и продолжить сравнение символов оттуда. Если бы новая позиция <tex>head_i</tex> всегда оказывалась существующей вершиной построенного дерева, этот алгоритм бы уже работал, но в реальности можно оказаться на середине ребра, для которой суффиксная ссылка неизвестна. Для нахождения ее суффиксной ссылки на следующей итерации мы сначала перейдем к предку, пройдем по суффиксной ссылке, а уже затем будем продолжать сравнение.
+Если нам известны суффиксные ссылки <tex>u.suf</tex> для каждой вершины <tex>u</tex>, мы можем быстро перейти от позиции <tex>head_i</tex> к её суффиксу и продолжить сравнение символов оттуда. Если бы новая позиция <tex>head_i</tex> всегда оказывалась существующей вершиной построенного дерева, этот алгоритм бы уже работал, но в реальности можно оказаться на середине ребра, для которой суффиксная ссылка неизвестна. Для нахождения её суффиксной ссылки на следующей итерации мы сначала перейдем к предку, пройдем по суффиксной ссылке, а уже затем будем продолжать сравнение.
 == Алгоритм ==
@@ Строка 31: / Строка 31: @@
 При добавлении каждого следующего суффикса будем выполнять следующие шаги:
 * Если суффиксная ссылка <tex>head_{i-1}</tex> не определена:
-*# Поднимемся вверх к ее предку;
+*# Поднимемся вверх к её предку;
 *# Пройдем по суффиксной ссылке;
 *# Спустимся вниз на столько символов, сколько мы прошли вверх к предку (''fast scanning'').
@@ Строка 57: / Строка 57: @@
 Конструктор будет иметь вид <code>Node(Node parent, '''int''' start, '''int''' end, '''int''' depth)</code>.
-Пусть глобально известна строка <tex>s</tex> со специальным символом на конце, ее длина <tex>n</tex> и используемый алфавит <tex>\Sigma</tex>.
+Пусть глобально известна строка <tex>s</tex> со специальным символом на конце, её длина <tex>n</tex> и используемый алфавит <tex>\Sigma</tex>.
 <code>
@@ Строка 102: / Строка 102: @@
         child = curNode.children[s[curPos]] <font color=green> // Ребенок по символу суффикса </font>
         edgePos = 0                         <font color=green> // Текущая позиция на ребре </font>
         '''while''' символы на ребре совпадают с суффиксом
            curPos++
            edgePos++
@@ Строка 117: / Строка 117: @@
 ''Slow scanning'' делает <tex>\left\vert head_i \right\vert - \left\vert head_{i-1} \right\vert + 1</tex> операций, что суммарно дает <tex>\left\vert head_n \right\vert - \left\vert head_0 \right\vert + n = O(n)</tex> операций.
-''Fast scanning'' работает с целыми ребрами, поэтому будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. Из структуры [[Сжатое суффиксное дерево| суффиксного дерева]] мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на <tex>1</tex>, так что мы на каждой итерации поднимаемся не более, чем на <tex>2</tex> {{---}} один раз к предку, а потом по суффиксной ссылке, что составляет <tex>O(n)</tex> за весь алгоритм. Соответственно, спустимся мы тоже суммарно <tex>O(n)</tex> раз, так как и максимальная глубина составляет <tex>O(n)</tex>.
+''Fast scanning'' работает с целыми рёбрами, поэтому будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. Из структуры [[Сжатое суффиксное дерево| суффиксного дерева]] мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на <tex>1</tex>, так что мы на каждой итерации поднимаемся не более, чем на <tex>2</tex> {{---}} один раз к предку, а потом по суффиксной ссылке, что составляет <tex>O(n)</tex> за весь алгоритм. Соответственно, спустимся мы тоже суммарно <tex>O(n)</tex> раз, так как и максимальная глубина составляет <tex>O(n)</tex>.
 Итоговая асимптотика алгоритма {{---}} <tex>O(n)</tex>.

@@ Строка 2: / Строка 2: @@
 ==Историческая справка==
-Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году  предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил  свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf On-line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
+Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году  предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf Edward M. McCreight {{---}} A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил  свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf Esko Ukkonen {{---}} On-line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
 == Теоретическое обоснование ==

@@ Строка 2: / Строка 2: @@
 ==Историческая справка==
-Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году  предложил [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf свой алгоритм], в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf свою версию алгоритма], которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
+Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году  предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил  свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf On–line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
 == Теоретическое обоснование ==
@@ Строка 134: / Строка 134: @@
 * [[Алгоритм Укконена]]
 * [[Алгоритм Фарача]]
 == Источники информации ==

← Предыдущая		Версия 13:16, 18 марта 2015
Строка 140:		Строка 140:
	* [[wikipedia:en:Suffix_tree\| Wikipedia {{---}} Suffix tree ]]		* [[wikipedia:en:Suffix_tree\| Wikipedia {{---}} Suffix tree ]]

−	[[Категория: ~~Дискретная математика~~ и ~~алгоритмы~~]]	+	[[Категория:Алгоритмы и структуры данных]]
		+	[[Категория:Словарные структуры данных]]