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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:29Z

rollbackEdits.php mass rollback

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

2022-09-01T03:32:44Z

146.120.76.217: Добавление необходимого ограничения в улучшенный вариант buildHmax: i < m.

2020-04-28T06:39:41Z

Добавление необходимого ограничения в улучшенный вариант buildHmax: i < m.

146.120.76.217: Добавление необходимого ограничения: i < m в функцию buildHMax.

2020-04-28T06:38:06Z

Добавление необходимого ограничения: i < m в функцию buildHMax.

Shersh: /* Источники информации */ добавлена категория

2016-02-02T11:52:36Z

‎Источники информации: добавлена категория

188.162.65.81: /* Псевдокод */

2014-06-14T19:57:05Z

‎Псевдокод

Kabanov в 22:53, 13 июня 2014

2014-06-13T22:53:22Z

Kabanov: /* Псевдокод */

2014-06-13T19:27:57Z

‎Псевдокод

Kabanov в 19:26, 13 июня 2014

2014-06-13T19:26:30Z

Kabanov в 18:25, 13 июня 2014

2014-06-13T18:25:25Z

← Предыдущая		Версия 16:42, 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 Майкл Наки].
−	\|}
−
	Алгоритм, разработанный Ливио Колусси, профессором итальянского университета Padova, и опубликованный им в 1991 году, является продолжением работы над оптимизацией [[Алгоритм Кнута-Морриса-Пратта\|алгоритма Кнута-Морриса-Пратта]]. Предназначен для поиска одной подстроки в одном тексте.		Алгоритм, разработанный Ливио Колусси, профессором итальянского университета Padova, и опубликованный им в 1991 году, является продолжением работы над оптимизацией [[Алгоритм Кнута-Морриса-Пратта\|алгоритма Кнута-Морриса-Пратта]]. Предназначен для поиска одной подстроки в одном тексте.

← Предыдущая		Версия 03:32, 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 Майкл Наки].
		+	\|}
		+
	Алгоритм, разработанный Ливио Колусси, профессором итальянского университета Padova, и опубликованный им в 1991 году, является продолжением работы над оптимизацией [[Алгоритм Кнута-Морриса-Пратта\|алгоритма Кнута-Морриса-Пратта]]. Предназначен для поиска одной подстроки в одном тексте.		Алгоритм, разработанный Ливио Колусси, профессором итальянского университета Padova, и опубликованный им в 1991 году, является продолжением работы над оптимизацией [[Алгоритм Кнута-Морриса-Пратта\|алгоритма Кнута-Морриса-Пратта]]. Предназначен для поиска одной подстроки в одном тексте.

@@ Строка 119: / Строка 119: @@
        '''int''' k = 1
        '''while''' k <= m
-          '''while''' x[i] == x[i - k]
+          '''while''' i < m and x[i] == x[i - k]
              i++
           hmax[k] = i

@@ Строка 106: / Строка 106: @@
        '''for''' k = 1 .. m
           '''int''' i = k
-          '''while''' x[i] == x[i - k]
+          '''while''' i < m and x[i] == x[i - k]
              i++
           hmax[k] = i
@@ Строка 179: / Строка 179: @@
           next[i] = nhd0[h[i] - kmin[h[i]]]
        '''for''' i = nd + 1 .. m - 1
-            next[i] = nhd0[m - rmin[h[i]]]
+         next[i] = nhd0[m - rmin[h[i]]]
        next[m] = nhd0[m - rmin[h[m - 1]]]
        '''return''' next

← Предыдущая		Версия 11:52, 2 февраля 2016
Строка 243:		Строка 243:
	[[Категория: Дискретная математика и алгоритмы]]		[[Категория: Дискретная математика и алгоритмы]]
	[[Категория: Поиск подстроки в строке]]		[[Категория: Поиск подстроки в строке]]
		+	[[Категория: Точный поиск]]

@@ Строка 120: / Строка 120: @@
        '''while''' k <= m
           '''while''' x[i] == x[i - k]
-             i++;
+             i++
           hmax[k] = i
           '''int''' q = k + 1
@@ Строка 127: / Строка 127: @@
              q++
           k = q
-          if k == i + 1
+          '''if''' k == i + 1
              i = k
        '''return''' hmax

@@ Строка 3: / Строка 3: @@
 ==Алгоритм==
 Алгоритм сравнивает символы шаблона <tex>x</tex> один за другим с символами исходной строки <tex>y</tex>. Для сдвигов шаблона относительно исходной строки применяются вспомогательные функции, описанные ниже.
 Обозначим за <tex>\mathrm{Kmp}</tex> {{---}} [[Префикс-функция|префикс-функцию]], но при этом она определена для <tex>x[0] \dots x[m-1]</tex> и имеет значение <tex>-1</tex> по умолчанию.
@@ Строка 8: / Строка 10: @@
 Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
-Множество всех позиций шаблона разделим на два (дизъюнктных) непересекающихся множества. Тогда каждая попытка сравнения шаблона с исходной строкой после очередного сдвига состоит из двух случаев.
+Множество всех позиций шаблона разделим на два дизъюнктных множества. Тогда каждая попытка сравнения шаблона с исходной строкой после очередного сдвига состоит из двух случаев.
 {{Определение
 |definition=
-В первом случае сравнения выполняются слева направо с символами текста, выровненными с шаблоном в позиции, для которой значение функции <tex>\mathrm{Kmp}(i)</tex> строго больше <tex>-1</tex>. Такие позиции будем называть '''насыщенными''' (''noholes'').
+В первом случае сравнения выполняются слева направо с символами текста, выровненными с шаблоном в позиции, для которой значение функции <tex>\mathrm{Kmp}(i)</tex> строго больше <tex>-1</tex>. Такие позиции будем называть '''насыщенными''' (англ. ''noholes'').
 }}
 {{Определение
 |definition=
-Во втором случае будут производиться сравнения в оставшихся позициях справа налево. Такие позиции будем называть '''ненасыщенными''' (''holes'').
+Во втором случае будут производиться сравнения в оставшихся позициях справа налево. Такие позиции будем называть '''ненасыщенными''' (англ. ''holes'').
 }}
@@ Строка 48: / Строка 50: @@
 {{Определение
 |definition=
-Обозначим за <tex>\mathrm{first}(u)</tex> наименьший число <tex>v</tex> такое, что <tex>u \leqslant h[v]</tex>.
+Обозначим за <tex>\mathrm{first}(u)</tex> наименьшее число <tex>v</tex> такое, что <tex>u \leqslant h[v]</tex>.
 }}
-Теперь рассмотрим 2 случаях, возможных при очередной попытке сравнения шаблона с подстрокой из текста. Допустим, что шаблон <tex>x</tex> выровнен с подстрокой <tex>y[j \dots j+m-1]</tex>.
+Теперь рассмотрим 2 случая, возможных при очередной попытке сравнения шаблона с подстрокой из текста. Допустим, что шаблон <tex>x</tex> выровнен с подстрокой <tex>y[j \dots j+m-1]</tex>.
 === Первый случай ===
@@ Строка 67: / Строка 69: @@
 Теперь рассмотрим ситуацию, когда <tex>x[h[k]]=y[j+h[k]]</tex> для <tex>0 \leqslant k < r</tex> и <tex>x[h[r]] \neq y[j+h[r]]</tex> для <tex>nd \leqslant r < m</tex>.
-Пусть <tex>j' = j + \mathrm{R_{min}}(h[r])</tex> позиций вправо.
+Пусть <tex>j' = j + \mathrm{R_{min}}(h[r])</tex>.
-Тогда нет вхождений шаблона <tex>x</tex>, начиная с <tex>y[j \dots j']</tex> и <tex>x</tex> может быть сдвинут на <tex>\mathrm{R_{min}}(h[r])</tex>.
+Тогда нет вхождений шаблона <tex>x</tex>, начиная с <tex>y[j \dots j']</tex> и <tex>x</tex> может быть сдвинут на <tex>\mathrm{R_{min}}(h[r])</tex> позиций вправо.
 Кроме того равенство <tex>x[0 \dots m-1-\mathrm{R_{min}}(h[r])]=y[j' \dots j+m-1]</tex> означает, что сравнения могут продолжены с символов <tex>x[h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex>.
@@ Строка 107: / Строка 109: @@
              i++
           hmax[k] = i
-       return hmax
+       '''return''' hmax
 Явная реализация по определению, очевидно, работает за <tex>O(m^2)</tex> и требует <tex>O(m)</tex> памяти.
@@ Строка 150: / Строка 152: @@
           '''else'''
              rmin[i] = 0
-       return rmin
+       '''return''' rmin
 Функция для построение массива <tex>\mathrm{shift}</tex>.
@@ Строка 182: / Строка 184: @@
 Основная функция алгоритма Колусси.
-    '''void''' COLUSSI('''char'''[] x, '''char'''[] y):
+    '''function''' colussi('''char'''[] x, '''char'''[] y):
        '''int''' n = length(y)
        '''int''' m = length(x)
@@ Строка 233: / Строка 235: @@
 ===Недостатки===
 * Сложность реализации.
 ==Источники==
 * COLUSSI L., 1991, Correctness and efficiency of the pattern matching algorithms, Information and Computation 95(2):225-251.
 * [http://www-igm.univ-mlv.fr/~lecroq/string/node10.html Colussi algorithm]

@@ Строка 98: / Строка 98: @@
 ==Псевдокод==
 Функция для построения массива <tex>\mathrm{H_{max}}</tex>.
 '''Наивный вариант'''
     '''int'''[] buildHmax('''char'''[] x, '''int''' m):

@@ Строка 62: / Строка 62: @@
 Кроме того равенство <tex>x[h[k]]=y[j’+h[k]]</tex> для всех <tex>k : 0 \leqslant k < \mathrm{first}(h[r]-\mathrm{K_{min}}(h[r]))</tex> означает, что сравнения могут продолжены с символов <tex>x[h[\mathrm{first}(h[r] - \mathrm{K_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(h[r]-\mathrm{K_{min}}(h[r]))]]</tex>.
-[[Файл:colussi-algorithm-1.png|450px|thumb|center|Насыщенная позиция.]]
+[[Файл:colussi-algorithm-1.png|450px|thumb|center|Несовпадение в насыщенной позиции. Насыщенные позиции обозначены черными кругами и сравниваются слева направо.]]
 === Второй случай ===
@@ Строка 73: / Строка 73: @@
 Кроме того равенство <tex>x[0 \dots m-1-\mathrm{R_{min}}(h[r])]=y[j' \dots j+m-1]</tex> означает, что сравнения могут продолжены с символов <tex>x[h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex>.
-[[Файл:colussi-algorithm-2.png|450px|thumb|center|Ненасыщенная позиция.]]
+[[Файл:colussi-algorithm-2.png|450px|thumb|center|Несовпадение в ненасыщенной позиции. Ненасыщенные позиции обозначены белыми кругами и сравниваются справа налево.]]
 === Предварительные вычисления ===

@@ Строка 53: / Строка 53: @@
 Теперь рассмотрим 2 случаях, возможных при очередной попытке сравнения шаблона с подстрокой из текста. Допустим, что шаблон <tex>x</tex> выровнен с подстрокой <tex>y[j \dots j+m-1]</tex>.
-=== Первая случай ===
+=== Первый случай ===
 Рассмотрим случай, когда <tex>x[h[k]]=y[j+h[k]]</tex> для <tex>0 \leqslant k < r < nd</tex> и <tex>x[h[r]] \neq y[j+h[r]]</tex>.
@@ Строка 61: / Строка 61: @@
 Кроме того равенство <tex>x[h[k]]=y[j’+h[k]]</tex> для всех <tex>k : 0 \leqslant k < \mathrm{first}(h[r]-\mathrm{K_{min}}(h[r]))</tex> означает, что сравнения могут продолжены с символов <tex>x[h[\mathrm{first}(h[r] - \mathrm{K_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(h[r]-\mathrm{K_{min}}(h[r]))]]</tex>.
 === Второй случай ===
@@ Строка 70: / Строка 72: @@
 Кроме того равенство <tex>x[0 \dots m-1-\mathrm{R_{min}}(h[r])]=y[j' \dots j+m-1]</tex> означает, что сравнения могут продолжены с символов <tex>x[h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex>.
 === Предварительные вычисления ===
@@ Строка 126: / Строка 130: @@
 Функция для построения массива <tex>\mathrm{K_{min}}</tex>.
-    '''int'''[] buildKmin('''int'''[] hmax, '''int''' m)
+    '''int'''[] buildKmin('''int'''[] hmax, '''int''' m):
        '''int''' kmin[m]
        '''for''' i = m .. 1
@@ Строка 134: / Строка 138: @@
 Функция для построения массива <tex>\mathrm{R_{min}}</tex>.
-    '''int'''[] buildRmin('''int'''[] hmax, '''int'''[] kmin, '''int''' m)
+    '''int'''[] buildRmin('''int'''[] hmax, '''int'''[] kmin, '''int''' m):
        '''int''' rmin[m]
        '''int''' r = 0
@@ Строка 148: / Строка 152: @@
 Функция для построение массива <tex>\mathrm{shift}</tex>.
-    '''int'''[] buildShift('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m)
+    '''int'''[] buildShift('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m):
        '''int''' shift[m + 1]
        '''for''' i = 0 .. nd
@@ Строка 158: / Строка 162: @@
 Функция для построения массива <tex>\mathrm{next}</tex>.
-    '''int'''[] buildNext('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m)
+    '''int'''[] buildNext('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m):
        <font color="green">// Вычисление массива <tex>\mathrm{nhd0}</tex></font>
        '''int''' nhd0[m]
@@ Строка 177: / Строка 181: @@
 Основная функция алгоритма Колусси.
-    '''void''' COLUSSI('''char'''[] x, '''char'''[] y)
+    '''void''' COLUSSI('''char'''[] x, '''char'''[] y):
        '''int''' n = length(y)
        '''int''' m = length(x)