Алгоритм Колусси

2014-06-08T15:35:29Z

178.66.54.100: /* Алгоритм */

==Алгоритм==
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.

Обозначим за <tex>Kmp</tex> {{---}} [[Префикс-функция|префикс-функцию]], но при этом она определена для <tex>x[0] \dots x[m-1]</tex> и имеет значение <tex>-1</tex> по умолчанию.

Множество всех позиций шаблона разделим на два непересекающихся множества. Тогда каждая попытка сравнения шаблона с исходной строкой состоит из двух фаз.

{{Определение
|definition=
В первой фазе сравнения выполняются слева направо с символами текста, выровненными с шаблоном в позиции, для которой значение функции <tex>\mathrm{Kmp}(i)</tex> строго больше <tex>-1</tex>. Такие позиции будем называть '''насыщенными''' (''noholes'').
}}

{{Определение
|definition=
Вторая фаза состоит в сравнении в оставшихся позициях справа налево. Такие позиции будем называть '''ненасыщенными''' (''holes'').
}}

Такая стратегия предоставляет, как минимум, 2 преимущества:
* когда несовпадение появляется во время первой фазы, после соответствующего сдвига уже нет необходимости делать проверки в насыщенных позициях, которые были проверены на предыдущем шаге.
* когда несовпадение появляется во время второй фазы, это означает, что суффикс шаблона совпал с периодом (''factor'') строки, после соответствующего сдвига префикс шаблона будет все ещё совпадать с периодом текста, поэтому нет необходимости в повторной проверке.

{{Определение
|definition=
Обозначим за <tex>\mathrm{K_{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{K_{min}}</tex> для всех позиций <tex>i</tex>, у которых <tex>Kmp(i) \neq -1</tex>.
}}

Если <tex>\mathrm{Kmin}(i) \neq 0</tex>, то периодичность шаблона <tex>x</tex> заканчивается в позиции <tex>i</tex>.

Очевидно, что для <tex>0 позиция <tex>i</tex>:
* насыщенная, если <tex>\mathrm{Kmin}(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 <tex>h[i]</tex> ненасыщенная и <tex>h[i] > h[i+1]</tex> для <tex>nd .

{{Определение
|definition=
Обозначим за <tex>\mathrm{Rmin}(i)</tex> наименьший период шаблона <tex>x</tex> большего, чем <tex>i</tex>.
}}

{{Определение
|definition=
Обозначим за <tex>\mathrm{First}(u)</tex> наименьший число <tex>v</tex> такое, что <tex>u \leqslant h[v]</tex>.
}}

Допустим, что шаблон <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{Kmin}(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>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>.

== Вторая фаза ==
Теперь рассмотрим ситуацию, когда <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>.

== Предварительные вычисления ==
Для вычисления значений <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>.
}}

==Псевдокод==
'''Наивный вариант'''
'''int'''[] buildHmax('''char'''[] x, '''int''' m):
'''int''' hmax[m + 1]
'''for''' k = 1 .. m
'''int''' i = k
'''while''' x[i] == x[i - k]
i++
hmax[k] = i
return hmax
Явная реализация по определению, очевидно, работает за <tex>O(m^2)</tex> и требует <tex>O(m)</tex> памяти.

'''Улучшенный вариант'''

'''int'''[] buildHmax('''char'''[] x, '''int''' m):
'''int''' hmax[m + 1]
'''int''' i = 1
'''int''' k = 1
'''while''' k <= m
'''while''' x[i] == x[i - k]
i++;
hmax[k] = i
'''int''' q = k + 1
'''while''' hmax[q - k] + k 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>\mathrm{Kmin}</tex>.
'''int'''[] buildKmin('''int'''[] hmax, '''int''' m)
'''int''' kmin[m]
'''for''' i = m .. 1
'''if''' hmax[i] < m
kmin[hmax[i]] = i
'''return''' kmin

Функция для построения массива <tex>\mathrm{Rmin}</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
// <tex>r</tex> {{---}} первое число большее, чем <tex>i</tex> и такое, что шаблон имеет период <tex>r</tex>
r = i + 1
'''if''' kmin[i] == 0
rmin[i] = r
'''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>.

==Асимптотики==
* 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>3/2n</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]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]

Викиконспекты - Вклад участника [ru]

Алгоритм Колусси