Сжатое суффиксное дерево - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:45Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:27, 1 сентября 2022

2022-09-01T03:27:27Z

37.204.71.254: /* Наивный алгоритм */

2021-12-25T23:45:50Z

‎Наивный алгоритм

79.175.1.65: в условии "=" заменено на "=="

2018-12-23T19:23:12Z

в условии "=" заменено на "=="

194.85.161.2: /* Число вершин */ Когда отрезаем 2 листа от внутренней, она сама становится листом.

2017-05-31T15:27:51Z

‎Число вершин: Когда отрезаем 2 листа от внутренней, она сама становится листом.

91.151.202.175: /* Построение из суффиксного массива */

2016-04-29T22:20:06Z

‎Построение из суффиксного массива

91.151.202.175: /* Построение суффиксного массива и массива lcp из суффиксного дерева */

2016-04-29T22:17:29Z

‎Построение суффиксного массива и массива lcp из суффиксного дерева

91.151.202.175: /* Построение из суффиксного массива */

2016-04-29T22:15:36Z

‎Построение из суффиксного массива

91.151.202.175: /* Построение из суффиксного массива */

2016-04-29T22:14:37Z

‎Построение из суффиксного массива

91.151.202.175: /* Построение суффиксного массива и массива lcp из суффиксного дерева */

2016-04-29T22:09:50Z

‎Построение суффиксного массива и массива lcp из суффиксного дерева

← Предыдущая		Версия 16:41, 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 Майкл Наки].
−	\|}
−
	[[Суффиксный бор\|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' (англ. ''compressed suffix tree''), рассматриваемое далее.		[[Суффиксный бор\|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' (англ. ''compressed suffix tree''), рассматриваемое далее.

← Предыдущая		Версия 03:27, 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 Майкл Наки].
		+	\|}
		+
	[[Суффиксный бор\|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' (англ. ''compressed suffix tree''), рассматриваемое далее.		[[Суффиксный бор\|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' (англ. ''compressed suffix tree''), рассматриваемое далее.

@@ Строка 76: / Строка 76: @@
       '''int''' v <span style="color:Green">// индекс текущей позиции </span>
-  go[0] = '''new''' Vertex
+  go[0] = '''new''' Vertex <span style="color:Green">// массив из пустых Vertex (можно все поля положить -1), размер массива -- количество символов в алфавите </span>
   count = 0        <span style="color:Green">// номер последней вершины, созданной в дереве (глобальная переменная)</span>
   '''for''' i = 0 '''to''' n   <span style="color:Green">// для каждого символа строки</span>
@@ Строка 90: / Строка 90: @@
               finish = go[cur][s[l]].r
               hasCut = ''false''
-              '''for''' j = start '''to''' finish       <span style="color:Green">// для каждого символа на ребре из текущей вершины</span>
+              '''for''' j = start '''to''' finish and l + j - start < n      <span style="color:Green">// для каждого символа на ребре из текущей вершины</span>
                   '''if''' (s[l + j - start] != s[j]) <span style="color:Green">// если нашли не совпадающий символ</span>
                       <span style="color:Green">// создаем вершину на ребре</span>
                       old = go[cur][s[l]]
-                      createVertex(cur, l, j - 1)
+                      createVertex(cur, l, j)
                       go[count][s[j]].v = old
-                      go[count][s[j]].r = j
+                      go[count][s[j]].l = j
-                      go[count][s[j]].l = finish
+                      go[count][s[j]].r = finish
                       createVertex(count, l + j - start, r)
                       hasCut = ''true''

@@ Строка 84: / Строка 84: @@
       cur = 0
       '''while''' (l < r)
-          '''if''' (go[cur][s[l]].v = -1)         <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span>
+          '''if''' (go[cur][s[l]].v == -1)         <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span>
               createVertex(cur, l, r)       <span style="color:Green">// создаем новую вершину</span>
           '''else'''

@@ Строка 60: / Строка 60: @@
 # У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем число внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.
-# У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n - 1</tex> листьями, число внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n - 1</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n</tex>.
+# У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n</tex> листьями, число внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n + 1</tex>.
 }}

@@ Строка 137: / Строка 137: @@
         '''return''' added
      '''else'''
-        '''if''' previous.parent.depth < lcp:                         <font color=green> // Нужно разрезать ребро </font>
+        '''if''' previous.parent.depth < lcp                          <font color=green> // Нужно разрезать ребро </font>
            inserted = '''Node'''(prevous.parent, lcp)
            previous.parent.children.pop()

@@ Строка 179: / Строка 179: @@
 Тогда суффиксный массив строится из суффиксного дерева [[Обход в глубину, цвета вершин| обходом в глубину]] в указанном порядке.
-Пусть длина строки <tex>length</tex>, глубина листа в символах <tex>depth</tex>, тогда номер суффикса <tex>i = length - depth</tex>.
+Пусть длина строки <tex>\mathtt{length}</tex>, глубина листа в символах <tex>\mathtt{depth}</tex>, тогда номер суффикса <tex>\mathtt{i = length - depth}</tex>.
-Для заполнения массива <tex>lcp</tex> нам понадобится вершина <tex>minNode</tex>, которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет [[Сведение задачи LCA к задаче RMQ| наименьший общий предок]] этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно <tex>lcp = minNode.depth</tex> символов.
+Для заполнения массива <tex>lcp</tex> нам понадобится вершина <tex>\mathtt{minNode}</tex>, которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет [[Сведение задачи LCA к задаче RMQ| наименьший общий предок]] этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно <tex>\mathtt{lcp = minNode.depth}</tex> символов.
 <code>

@@ Строка 127: / Строка 127: @@
 # Вставить новую вершину как сына вершины с глубиной <tex>lcp</tex>.
-В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>\mathtt {parent}</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>\mathtt{children}</tex>, глубину вершины в символах от корня <tex>depth</tex>.
+В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>\mathtt {parent}</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>\mathtt{children}</tex>, глубину вершины в символах от корня <tex>\mathtt{depth}</tex>.
 Соответственно, конструктор вершины имеет вид <code>Node(Node parent, '''int''' depth)</code>.
@@ Строка 153: / Строка 153: @@
 </code>
-В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>maxDepth</tex>.
+В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>\mathtt{maxDepth}</tex>.
 Тогда ребро <tex>s[start, end]</tex> определяется так:

@@ Строка 185: / Строка 185: @@
 <code>
   '''int''' curPos = 0
-  Node minNode = root
+  '''Node''' minNode = root
   <font color=green>// Для заполнения нужно вызвать dfs(root) </font>
-  '''void''' dfs(Node n):
+  '''void''' dfs('''Node''' n):
      '''if''' n.children.size == 0
         suf[curPos] = length - n.depth