Изменения
Добавление необходимого ограничения в улучшенный вариант buildHmax: i < m.
Алгоритм, разработанный Ливио Колусси, профессором итальянского университета Padova, и опубликованный им в 1991 году, является продолжением работы над оптимизацией [[Алгоритм Кнута-Морриса-Пратта|алгоритма Кнута-Морриса-Пратта]]. Предназначен для поиска одной подстроки в одном тексте.
==Алгоритм==
Алгоритм сравнивает символы шаблона <tex>x</tex> один за другим с символами исходной строки <tex>y</tex>. Для сдвигов шаблона относительно исходной строки применяются вспомогательные функции, описанные ниже. Пусть <tex>|y|=n</tex> и <tex>|x|=m</tex>. Обозначим за <tex>\mathrm{Kmp}</tex> {{---}} [[Префикс-функция|префикс-функцию]], но при этом она определена для <tex>x[0] \dots x[m-1]</tex> и имеет значение <tex>-1</tex> по умолчанию. Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>. Множество всех позиций шаблона разделим на два дизъюнктных множества. Тогда каждая попытка сравнения шаблона с исходной строкой после очередного сдвига состоит из двух случаев. {{Определение|definition=В первом случае сравнения выполняются слева направо с символами текста, выровненными с шаблоном в позиции, для которой значение функции <tex>\mathrm{Kmp}(i)</tex> строго больше <tex>-1</tex>. Такие позиции будем называть '''насыщенными''' (англ. ''noholes'').}} {{Определение|definition=Во втором случае будут производиться сравнения в оставшихся позициях справа налево. Такие позиции будем называть '''ненасыщенными''' (англ. ''holes'').}}
{{Определение
|definition=Обозначим за <tex>\mathrm{KminK_{min}}(i)= \min\{k : \ x[0 \dots i-1-k]=x[d \dots i-1]\ and\ x[i - k] \neq x[i]\}</tex>. Функция <tex>\mathrm{KmpK_{min}}(i)</tex> функцию, возвращающую количество прыжков определена для всех позиций <tex>i</tex>, которые являются полнымиу которых <tex>\mathrm{Kmp}(i) \neq -1</tex>.
}}
Если <tex>\mathrm{K_{min}}(i) \neq 0</tex>, то периодичность шаблона <tex>x</tex> заканчивается в позиции <tex>i</tex>.
Очевидно, что для <tex>0 < i < m</tex> позиция <tex>i</tex>:
* насыщенная, если <tex>\mathrm{K_{min}}(i-1) \neq 0</tex>,
* ненасыщенная, в остальных случаях.
Обозначим за <tex>nd+1</tex> количество насыщенных позиций в шаблоне <tex>x</tex>.
Массив <tex>h</tex> содержит первыми элементами <tex>nd+1</tex> насыщенных позиций в возрастающем порядке и затем <tex>m-nd-1</tex> ненасыщенных в убывающем порядке, т.е.
* для всех <tex>0 \leqslant i \leqslant nd</tex> <tex>h[i]</tex> насыщенная позиция и <tex>h[i] < h[i+1]</tex> для <tex>0 \leqslant i < nd</tex>.
* для всех <tex>nd < i < m</tex> <tex>h[i]</tex> ненасыщенная и <tex>h[i] > h[i+1]</tex> для <tex>nd < i < m-1</tex>.
{{Определение
|definition=Обозначим за <tex>\mathrm{RminR_{min}}(i)</tex> функцию, возвращающую наименьший из периодов период <tex>r</tex> шаблона<tex>x</tex> большего, которые больше позиции чем <tex>i</tex>, . Функция <tex>\mathrm{R_{min}}</tex> определена для всех позиций<tex>i</tex>, которые являются пустымиу которых <tex>\mathrm{Kmp}(i) = -1</tex>.
}}
{{Определение
|definition=Функция сдвига Обозначим за <tex>\mathrm{Shiftfirst}(i) = \begin{cases} \mathrm{Rmin}(iu)</tex> наименьшее число <tex>v</tex> такое, & \mbox{if } что <tex>u \mathrm{Kmp}(i) = -1\\ \mathrm{Kmin}(i), & \mbox{otherwise}\end{cases}leqslant h[v]</tex>.
}}
Теперь рассмотрим 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>.
Пусть <tex>j' = j + \mathrm{K_{min}}(h[r])</tex>.
Тогда нет вхождений шаблона <tex>x</tex>, начиная с <tex>y[j \dots j']</tex> и <tex>x</tex> может быть сдвинут на <tex>\mathrm{K_{min}}(h[r])</tex> позиций вправо.
Кроме того равенство <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|Несовпадение в насыщенной позиции. Насыщенные позиции обозначены черными кругами и сравниваются слева направо.]]
=== Второй случай ===
Теперь рассмотрим ситуацию, когда <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>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>.
[[Файл:colussi-algorithm-2.png|450px|thumb|center|Несовпадение в ненасыщенной позиции. Ненасыщенные позиции обозначены белыми кругами и сравниваются справа налево.]]
=== Предварительные вычисления ===
Для вычисления значений <tex>\mathrm{K_{min}}</tex> будем использовать вспомогательную функцию <tex>\mathrm{H_{max}}</tex>.
{{Определение
|definition=
Обозначим за <tex>\mathrm{H_{max}}</tex> функцию, для которой выполняется:
* <tex>x[k \dots \mathrm{H_{max}}(k)-1]=x[0 \dots \mathrm{H_{max}}(k)-k-1]</tex>,
* <tex>x[\mathrm{H_{max}}(k)] \neq x[\mathrm{H_{max}}(k)-k]</tex>.
}}
{{Определение
|definition=
Обозначим за <tex>\mathrm{nhd0}(i)</tex> количество насыщенных позиций строго меньших <tex>i</tex>.
}}
Теперь мы можем определить два функции <tex>shift</tex> и <tex>next</tex>:
* <tex>\mathrm{shift}(i)=\mathrm{K_{min}}(h[i])</tex> и <tex>\mathrm{next}(i)=\mathrm{nhd0}(h[i]-\mathrm{K_{min}}(h[i]))</tex> для всех <tex>i : i < nd</tex>;
* <tex>\mathrm{shift}(i)=\mathrm{R_{min}}(h[i])</tex> и <tex>\mathrm{next}(i)=\mathrm{nhd0}(m-\mathrm{R_{min}}(h[i]))</tex> для всех <tex>i : nd \leqslant i < m</tex>;
* <tex>\mathrm{shift}(m)=\mathrm{R_{min}}(0)</tex> и <tex>\mathrm{next}(m)=\mathrm{nhd0}(m-\mathrm{R_{min}}(h[m-1]))</tex>.
Таким образом, при возникновении несовпадения между <tex>x[h[r]]</tex> и <tex>y[j+h[r]]</tex> окно сравнения должно быть сдвинуто на <tex>\mathrm{shift}(r)</tex> и сравнения могут быть продолжены с позиции <tex>h[\mathrm{next}(r)]</tex> шаблона <tex>x</tex>.
==Псевдокод==
Функция для построения массива <tex>\mathrm{H_{max}}</tex>.
'''Наивный вариант'''
'''for''' k = 1 .. m
'''int''' i = k
'''while''' i < m and x[i] == x[i - k]
i++
hmax[k] = i
'''return ''' hmax
Явная реализация по определению, очевидно, работает за <tex>O(m^2)</tex> и требует <tex>O(m)</tex> памяти.
'''int''' k = 1
'''while''' k <= m
'''while''' i < m and x[i] == x[i - k] i++;
hmax[k] = i
'''int''' q = k + 1
q++
k = q
'''if ''' k == i + 1
i = k
'''return''' hmax
На каждой итерации цикла увеличивается либо переменная <tex>i</tex>, либо <tex>k</tex> (или переменная <tex>q</tex>, которая используется в конечном счете для обновления <tex>k</tex>). Поскольку <tex>i = 1</tex> и <tex>k = 1</tex> в начале и <tex>i < k = m + 1</tex> в конце алгоритма, количество итераций алгоритма не превосходит <tex>2 \cdot m</tex>. Следовательно функция требует <tex>O(m)</tex> времени и памяти.
Функция для построения массива <tex>Kmin\mathrm{K_{min}}</tex>. '''int'''[] buildKmin('''int'''[] hmax, '''int''' m):
'''int''' kmin[m]
'''for''' i = m .. 1
'''return''' kmin
Функция для построения массива <tex>Rmin\mathrm{R_{min}}</tex>. '''int'''[] buildRmin('''int'''[] hmax, '''int'''[] kmin, '''int''' m):
'''int''' rmin[m]
'''int''' r = 0
'''for''' i = m - 1 .. 0
'''if''' hmax[i + 1] == m
<font color="green">// <tex>r</tex> {{---}} первое число большее, чем <tex>i</tex> и такое, что шаблон имеет период <tex>r</tex></font>
r = i + 1
'''if''' kmin[i] == 0
'''else'''
rmin[i] = 0
'''return ''' rmin Функция для построение массива <tex>\mathrm{shift}</tex>. '''int'''[] buildShift('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m): '''int''' shift[m + 1] '''for''' i = 0 .. nd shift[i] = kmin[h[i]] '''for''' i = nd + 1 .. m - 1 shift[i] = rmin[h[i]] shift[m] = rmin[0] '''return''' shift Функция для построения массива <tex>\mathrm{next}</tex>. '''int'''[] buildNext('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m): <font color="green">// Вычисление массива <tex>\mathrm{nhd0}</tex></font> '''int''' nhd0[m] '''int''' s = 0 '''for''' i = 0 .. m - 1 nhd0[i] = s if kmin[i] > 0 ++s <font color="green">// Вычисление массива <tex>\mathrm{next}</tex></font> '''int''' next[m + 1] '''for''' i = 0 .. nd next[i] = nhd0[h[i] - kmin[h[i]]] '''for''' i = nd + 1 .. m - 1 next[i] = nhd0[m - rmin[h[i]]] next[m] = nhd0[m - rmin[h[m - 1]]] '''return''' next Основная функция алгоритма Колусси. '''function''' colussi('''char'''[] x, '''char'''[] y): '''int''' n = length(y) '''int''' m = length(x) <font color="green">// Предварительные вычисления</font> '''int'''[] hmax = buildHmax(x, m) '''int'''[] kmin = buildKmin(hmax, m) '''int'''[] rmin = buildRmin(hmax, kmin, m) <font color="green">// Построение массива <tex>h</tex></font> '''int''' h[m] '''int''' s = -1 '''int''' r = m '''for''' i = 0 .. m - 1 '''if''' kmin[i] == 0 h[--r] = i '''else''' h[++s] = i '''int''' nd = s '''int'''[] shift = buildShift(kmin, rmin, h, nd, m) '''int'''[] next = buildNext(kmin, rmin, h, nd, m) <font color="green">// Поиск подстроки</font> '''int''' i = 0 '''int''' j = 0 '''int''' last = -1 '''while''' j <= n - m '''while''' i < m '''and''' last < j + h[i] '''and''' x[h[i]] == y[j + h[i]] ++i '''if''' i >= m '''or''' last >= j + h[i] OUTPUT(j) i = m '''if''' i > nd last = j + m - 1 j += shift[i] i = next[i]
==Асимптотики==
* partitions the set of pattern positions into two disjoint subsets; the positions in the first set are scanned from left to right and when no mismatch occurs the positions of the second subset are scanned from right to left;* preprocessing phase in Фаза предварительных вычислений занимает <tex>O(m)</tex> time and space complexityвремени и памяти;* searching phase in В худшем случае поиск требует <tex>O(n)</tex> time complexity;сравнений. * performs где <tex>3n</2ntex> {{---}} длина исходного текста, <tex>m</tex> text character comparisons in the worst case.{{---}} длина шаблона
==Сравнение с другими алгоритмами==
===Достоинства===
* Поиск выполняется за <tex>O(n)</tex> в отличие от [[Алгоритм Кнута-Морриса-Пратта|алгоритма Кнута-Морриса-Пратта]], поиск в котором занимается <tex>O(n+m)</tex>, что помогает уменьшить константу при <tex>m \sim n</tex>.
* Фаза предобработки выполняется за <tex>O(m)</tex> в отличие от [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]], где в наилучшем случае можно получить время <tex>O(n+|\Sigma|)</tex>, что плохо при больших алфавитах.
===Недостатки===
* Сложность реализации. ==СсылкиИсточники информации==* 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]
* [http://alg.csie.ncnu.edu.tw/course/StringMatching/Colussi.ppt Colussi.ppt]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Точный поиск]]
