Алгоритм Карккайнена-Сандерса — различия между версиями
| Строка 1: | Строка 1: | ||
Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время. | Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время. | ||
| − | == | + | == Базовая идея == |
| − | Алгоритм базируется на алгоритме Фараха построения суффиксного дерева за линейное время: | + | Алгоритм базируется на алгоритме Фараха<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> построения суффиксного дерева за линейное время: |
# Строим суффиксное дерево для суффиксов, начинающихся в четных позициях, рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины. | # Строим суффиксное дерево для суффиксов, начинающихся в четных позициях, рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины. | ||
# Строим суффиксное дерево для суффиксов, начинающихся в нечетных позициях за линейное время, используя результат для четных позиций. | # Строим суффиксное дерево для суффиксов, начинающихся в нечетных позициях за линейное время, используя результат для четных позиций. | ||
| Строка 9: | Строка 9: | ||
Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>. | Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>. | ||
| − | + | == Алгоритм == | |
| − | |||
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам. | Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам. | ||
| − | В случае суффиксного массива первый и второй шаги алгоритма делаются просто, а слияние становится очень сложным | + | В случае суффиксного массива первый и второй шаги алгоритма делаются просто, а слияние становится очень сложным <ref> D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. http://www.springerlink.com/content/568156021q45r320/</ref>. |
== Алгоритм skew == | == Алгоритм skew == | ||
| Строка 23: | Строка 22: | ||
{{TODO| t = впилить описание сливания }} | {{TODO| t = впилить описание сливания }} | ||
| + | |||
| + | == Ссылки == | ||
| + | <references /> | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Суффиксный массив]] | [[Категория: Суффиксный массив]] | ||
Версия 17:17, 28 марта 2012
Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения суффиксного массива за линейное время.
Содержание
Базовая идея
Алгоритм базируется на алгоритме Фараха[1] построения суффиксного дерева за линейное время:
- Строим суффиксное дерево для суффиксов, начинающихся в четных позициях, рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины.
- Строим суффиксное дерево для суффиксов, начинающихся в нечетных позициях за линейное время, используя результат для четных позиций.
- Сливаем суффиксные деревья за линейное время.
Получили асимптотическое уравнение , решением которого является .
Алгоритм
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам. В случае суффиксного массива первый и второй шаги алгоритма делаются просто, а слияние становится очень сложным [2].
Алгоритм skew
Изменим изначальный алгоритм следующим образом:
- Построим суффиксный массив для суффиксов, соответствующих не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.
- Построим суффиксный массив для суффиксов, соответствующих кратных трем позициям, используя результат первого шага за линейное время.
- Сливаем эти суффиксные массивы в один за линейное время.
Получили асимптотическое уравнение , решением которого также является (это видно из того, что сумма геометрической прогрессии с основанием равна ).
TODO: впилить описание сливания
Ссылки
- ↑ M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf
- ↑ D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. http://www.springerlink.com/content/568156021q45r320/
