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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:21:40Z

rollbackEdits.php mass rollback

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

2022-09-01T05:24:31Z

Alice в 22:10, 21 мая 2016

2016-05-21T22:10:33Z

Alice в 22:00, 21 мая 2016

2016-05-21T22:00:20Z

Внесённые изменения

Shersh: переименовал Алгоритм Фарача в Алгоритм Фараха

2016-05-21T10:18:52Z

переименовал Алгоритм Фарача в Алгоритм Фараха

Alice в 01:18, 21 мая 2016

2016-05-21T01:18:13Z

Alexey Katsman: /* Минусы алгоритма Фарача */

2015-06-16T18:25:38Z

‎Минусы алгоритма Фарача

Alexey Katsman в 18:24, 16 июня 2015

2015-06-16T18:24:52Z

Alexey Katsman в 15:55, 16 июня 2015

2015-06-16T15:55:05Z

Alexey Katsman: /* Шаг 5: удаление двойных дуг */

2015-06-16T15:54:11Z

‎Шаг 5: удаление двойных дуг

← Предыдущая		Версия 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 Майкл Наки].
−	\|}
−
	'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике.		'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике.
	Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.		Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.

← Предыдущая		Версия 05:24, 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 Майкл Наки].
		+	\|}
		+
	'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике.		'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево\|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике.
	Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.		Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.

@@ Строка 4: / Строка 4: @@
 == Описание алгоритма ==
-Идея алгоритма заключается в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.
+Идея алгоритма состоит в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.
 Алгоритм Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).
@@ Строка 102: / Строка 102: @@
 Разберём дуги по порядку:
-# расслоение находится на расстоянии <tex>2</tex> от корня, то есть дуга не расслаивается.
+# Расслоение находится на расстоянии <tex>2</tex> от корня, то есть дуга не расслаивается.
-# конец является родителем вершин <tex>2</tex>, <tex>7</tex>. Родитель <tex>3</tex>, <tex>8</tex> после слияния дуги <tex>(1)</tex>, находится на глубине <tex>2</tex> символа. Значит, дуга <tex>(2)</tex> расслаивается на глубине <tex>3</tex> символа, то есть также не расслаивается. Дугу <tex>(2)</tex> нужно вычислять после обработки дуги <tex>(1)</tex>, потому что конец дуги <tex>(1)</tex> после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.
+# Конец является родителем вершин <tex>2</tex>, <tex>7</tex>. Родитель <tex>3</tex>, <tex>8</tex> после слияния дуги <tex>(1)</tex>, находится на глубине <tex>2</tex> символа. Значит, дуга <tex>(2)</tex> расслаивается на глубине <tex>3</tex> символа, то есть также не расслаивается. Дугу <tex>(2)</tex> нужно вычислять после обработки дуги <tex>(1)</tex>, потому что конец дуги <tex>(1)</tex> после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.
-# конец является родителем <tex>2</tex>, <tex>9</tex>. Родитель <tex>3</tex>, <tex>10</tex> находится на расстоянии <tex>3</tex>, а наше расслоение на расстоянии <tex>4</tex>, то есть сливается первый символ двойной дуги. Дугу <tex>(3)</tex> надо вычислять после дуги <tex>(2)</tex>. Потому что если на дуге <tex>(2)</tex> появится разветвление, то компоненты дуги <tex>(3)</tex> придётся растащить по разным веткам дерева и сравнивать их будет не нужно.
+# Конец является родителем <tex>2</tex>, <tex>9</tex>. Родитель <tex>3</tex>, <tex>10</tex> находится на расстоянии <tex>3</tex>, а наше расслоение на расстоянии <tex>4</tex>, то есть сливается первый символ двойной дуги. Дугу <tex>(3)</tex> надо вычислять после дуги <tex>(2)</tex>. Потому что если на дуге <tex>(2)</tex> появится разветвление, то компоненты дуги <tex>(3)</tex> придётся растащить по разным веткам дерева и сравнивать их будет не нужно.
-# конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.
+# Конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.
-# конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5)</tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслоения.
+# Конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5)</tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслоения.
 [[Файл:Treestep5_2.jpg|thumb|center|650px|Итоговое дерево строки <tex>10010010101000</tex>]]

@@ Строка 1: / Строка 1: @@
-'''Алгоритм Фарача (Martin Farach,(1997))''' {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике.
+'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике.
-Важно помнить, что алгоритм скорее теоретический, чем практический, а основная ценность его заключается в том, что размер алфавита может быть произвольным.
+Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.
 == Описание алгоритма ==
@@ Строка 6: / Строка 6: @@
 Идея алгоритма заключается в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.
-Алгоритм Фарача будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).
+Алгоритм Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).
 === Шаг 1: суффиксное дерево для сжатой строки===
 [[Файл:tree101232.png|thumb|300px|суффиксное дерево для сжатой строки]]
 * Строка <tex>s</tex> разбивается на пары подряд идущих символов: <tex> \langle 12\rangle \langle 11\rangle  \langle 12\rangle \langle 21\rangle \langle 22\rangle \langle 21\rangle </tex>
-*: (если символов нечетное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>)
+*: (если символов нечетное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>).
-* Пары сортируются устойчивой сотрировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.
+* Пары сортируются устойчивой сортировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.
 * Удаляются копии: <tex> \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle </tex>.
-* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11 \rangle -(0), \langle 12\rangle -(1), \langle 21\rangle - (2), \langle 22\rangle-(3)</tex>
+* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11 \rangle -(0), \langle 12\rangle -(1), \langle 21\rangle - (2), \langle 22\rangle-(3)</tex>.
-* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>
+* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>.
-* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом:
+* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом.
-* рекурсия не продолжается, если строка имеет длину <tex>1</tex>: суффиксное дерево строится тривиально.
+* Рекурсия не продолжается, если строка имеет длину <tex>1</tex>: суффиксное дерево строится тривиально.
 === Шаг 2: построение чётного дерева ===
@@ Строка 113: / Строка 113: @@
 В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.
-==Минусы алгоритма Фарача==
+==Минусы алгоритма Фараха==
 Данный алгоритм является больше теоретическим, нежели практическим. Как можно было заметить, основная идея
@@ Строка 127: / Строка 127: @@
 == Источники информации ==
 *[http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf Optimal suffix tree construction with large alphabets ]
-*[http://www.proteus2001.narod.ru/gen/txt/11/farach.html  Суффиксное дерево {{---}} Алгоритм фарача]
+*[http://www.proteus2001.narod.ru/gen/txt/11/farach.html  Суффиксное дерево {{---}} Алгоритм Фараха]
 *[http://books.google.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y  Computing Patterns in Strings]
 *[https://github.com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree  Chris Parjaszewski's implementation]

@@ Строка 118: / Строка 118: @@
 алгоритма довольно проста и понятна. И хоть он и является асимптотически оптимальным, на практике его используют
 довольно редко. Это связано с тем, что алгоритм весьма сложен для реализации, по сравнению с другими алгоритмами
-построения суффиксы деревьев, а также требует достаточно большой объем памяти.
+построения суффиксных деревьев, а также требует достаточно большой объем памяти.
 ==См. также==

← Предыдущая	Версия 10:18, 21 мая 2016
(нет различий)

@@ Строка 110: / Строка 110: @@
 [[Файл:Treestep5_2.jpg|thumb|center|650px|итоговое дерево]]
-Дерево строится рекурсивно, каждый раз длина строки уменьшается в два раза, а все фазы работают линейно.
+Дерево строится рекурсивно, каждый раз длина строки уменьшается вдвое, а все фазы работают линейно.
 В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.