Алгоритм Колусси — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 2: Строка 2:
 
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
 
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
  
Обозначим <tex>Kmp</tex> [[Префикс-функция|префикс-функцию]]. При этом она должна быть определена для <tex>x[0] \dots x[m-1]</tex> и иметь значение <tex>-1</tex> по умолчанию.
+
Обозначим за <tex>\mathrm{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'') строки, после соответствующего сдвига префикс шаблона будет все ещё совпадать с периодом текста, поэтому нет необходимости в повторной проверке.
  
 
{{Определение
 
{{Определение
Строка 13: Строка 29:
 
}}
 
}}
  
 +
Если <tex>\mathrm{Kmin}(i) \neq 0</tex>, то периодичность шаблона <tex>x</tex> заканчивается в позиции <tex>i</tex>.
 +
 +
Очевидно, что для <tex>0 < i < m</tex> позиция <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 < i < m</tex> <tex>h[i]</tex> ненасыщенная и <tex>h[i] > h[i+1]</tex> для <tex>nd < i < m-1</tex>.
 +
 +
{{Определение
 +
|definition=
 +
Обозначим за <tex>\mathrm{Rmin}(i)</tex> наименьший период шаблона <tex>x</tex> большего, чем <tex>i</tex>.
 +
}}
 +
 +
{{Определение
 +
|definition=
 +
Обозначим за <tex>\mathrm{Rmin}(i)</tex> наименьший период шаблона <tex>x</tex> большего, чем <tex>i</tex>.
 +
}}
  
 
==Псевдокод==
 
==Псевдокод==

Версия 16:31, 8 июня 2014

Алгоритм

Отметим, что нумерация символов строк и элементов массива у нас начинается с [math]0[/math].

Обозначим за [math]\mathrm{Kmp}[/math] префикс-функцию. При этом она должна быть определена для [math]x[0] \dots x[m-1][/math] и иметь значение [math]-1[/math] по умолчанию.

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


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


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


Такая стратегия предоставляет, как минимум, 2 преимущества:

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


Определение:
Для всех [math]i[/math] таких, что [math]0 \leqslant i \leqslant m-1[/math] выполняется:
[math]\mathrm{Kmin}(i) = \begin{cases} d, & \mbox{if } d \gt 0\ and\ x[0 \dots i-1-d]=x[d \dots i-1]\ and\ x[i-d] \neq x[i]\\ 0, & \mbox{otherwise} \end{cases}[/math]


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

Очевидно, что для [math]0 \lt i \lt m[/math] позиция [math]i[/math]:

  • насыщенная, если [math]\mathrm{Kmin}(i-1) \neq 0[/math]
  • ненасыщенная, иначе

Обозначим за [math]nd+1[/math] количество насыщенных позиций в шаблоне [math]x[/math].

Массив [math]h[/math] содержит первые [math]nd+1[/math] насыщенных позиций в возрастающем порядке и затем [math]m-nd-1[/math] ненасыщенных в убывающем порядке, т.е.

  • для всех [math]0 \leqslant i \leqslant nd[/math] [math]h[i][/math] насыщенная позиция и [math]h[i] \lt h[i+1][/math] для [math]0 \leqslant i \lt nd[/math].
  • для всех [math]nd \lt i \lt m[/math] [math]h[i][/math] ненасыщенная и [math]h[i] \gt h[i+1][/math] для [math]nd \lt i \lt m-1[/math].


Определение:
Обозначим за [math]\mathrm{Rmin}(i)[/math] наименьший период шаблона [math]x[/math] большего, чем [math]i[/math].


Определение:
Обозначим за [math]\mathrm{Rmin}(i)[/math] наименьший период шаблона [math]x[/math] большего, чем [math]i[/math].


Псевдокод

Наивный вариант

  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

Явная реализация по определению, очевидно, работает за [math]O(m^2)[/math] и требует [math]O(m)[/math] памяти.

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

  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
           hmax[q] = hmax[q - k] + k
           q++
        k = q
        if k == i + 1
           i = k
     return hmax

На каждой итерации цикла увеличивается либо переменная [math]i[/math], либо [math]k[/math] (или переменная [math]q[/math], которая используется в конечном счете для обновления [math]k[/math]). Поскольку [math]i = 1[/math] и [math]k = 1[/math] в начале и [math]i \lt k = m + 1[/math] в конце алгоритма, количество итераций алгоритма не превосходит [math]2 \cdot m[/math]. Следовательно функция требует [math]O(m)[/math] времени и памяти.

Функция для построения массива [math]\mathrm{Kmin}[/math].

  int[] buildKmin(int[] hmax, int m)
     int kmin[m]
     for i = m .. 1
        if hmax[i] < m
           kmin[hmax[i]] = i
     return kmin

Функция для построения массива [math]\mathrm{Rmin}[/math].

  int[] buildRmin(int[] hmax, int[] kmin, int m)
     int rmin[m]
     int r = 0
     for i = m - 1 .. 0
        if hmax[i + 1] == m
           // [math]r[/math] — первое число большее, чем [math]i[/math] и такое, что шаблон имеет период [math]r[/math]
           r = i + 1
        if kmin[i] == 0
           rmin[i] = r
        else
           rmin[i] = 0
     return rmin

Функция для построение массива [math]\mathrm{Shift}[/math].

  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

Функция для построения массива [math]\mathrm{Next}[/math].


Асимптотики

  • 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 [math]O(m)[/math] time and space complexity;
  • searching phase in [math]O(n)[/math] time complexity;
  • performs [math]3/2n[/math] text character comparisons in the worst case.

Сравнение с другими алгоритмами

Достоинства

  • Поиск выполняется за [math]O(n)[/math] в отличие от алгоритма Кнута-Морриса-Пратта, поиск в котором занимается [math]O(n+m)[/math], что помогает уменьшить константу при [math]m~n[/math].
  • Фаза предобработки выполняется за [math]O(m)[/math] в отличие от алгоритма Бойера-Мура, где в наилучшем случае можно получить время [math]O(n+|\Sigma|)[/math], что плохо при больших алфавитах.

Недостатки

  • Сложность реализации.

Источники

  • COLUSSI L., 1991, Correctness and efficiency of the pattern matching algorithms, Information and Computation 95(2):225-251.
  • Colussi algorithm
  • Colussi.ppt