Первая страница / Теория / Разное /

Суффиксные массивы

Голосование: 7, 4

Введение

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

Пусть задан текст T длины m. Нам нужно так подготовить текст T, чтобы потом за минимальное время находить вхождения образца P длины n в текст T. Хорошего результата можно достигнуть, если строить из текста T суффиксное дерево, но для поиска за O(n) суффиксное дерево требует большого количества памяти — O(m|Σ|), где |Σ| — мощность алфавита. В некоторых задачах о поиске подстрок алфавит очень велик (например, естественные языки с большими алфавитами, сравнение изображений, где алфавит — все возможные значения цвета пикселя) и иногда память, которую занимает суффиксное дерево, делает его неприемлемым. В 1993 году Манбер (Manber U.) и Майерс (Myers G.) предложили для решения задачи о подстроке структуру, названную суффиксным массивом, которая более рационально использует память и работает почти так же быстро, как суффиксные деревья.

Суффиксный массив

Пусть задана m-символьная строка T. Суффиксным массивом для T, обозначенным Pos, называется массив целых чисел от 1 до m, определяющих лексикографический порядок всех m суффиксов строки T.

Пример суффиксов и суффиксного массива для строки «абракадабра».
1 абракадабра Pos[0]=11 а
2 бракадабра Pos[1]=8 абра
3 ракадабра Pos[2]=1 абракадабра
4 акадабра Pos[3]=6 адабра
5 кадабра Pos[4]=4 акадабра
6 адабра Pos[5]=9 бра
7 дабра Pos[6]=2 бракадабра
8 абра Pos[7]=7 дабра
9 бра Pos[8]=5 кадабра
10 ра Pos[9]=10 ра
11 а Pos[10]=3 ракадабра

Каждый суффикс строки определяется своим номером. Первый суффикс — это сама строка, последний суффикс — последняя буква строки. Для хранения суффиксов нам надо хранить только их номера. В массиве Pos хранятся номера суффиксов так, что суффиксы с этими номерами стоят в лексикографическом порядке. Так как в суффиксном массиве Pos хранятся только целые числа, он не занимает много памяти — ровно m машинных слов, если в машинном слове не менее log2m битов. Это огромный плюс суффиксных массивов — их размер в памяти определяется только размерами текста T и никак не зависит от его алфавита, в отличие от суффиксных деревьев. Далее мы убедимся, что суффиксный массив можно использовать для поиска всех вхождений в T образца P за O(n+log2m). Если log2m имеет порядок O(n), то суффиксный массив будет работать не менее эффективно, чем суффиксное дерево.

Построение суффиксного массива

Упорядочим суффиксы по первой букве и занесём результат в Pos. Корзиной будем называть несколько соседних суффиксов с одинаковыми первыми буквами. Пока что суффиксы упорядочены только по первой букве и у суффиксов одной корзины одинаковая первая буква. Нужно сделать разбиение на корзины мельче, пока количество корзин не совпадёт с длиной m строки T. Последний суффикс (он же — последний символ строки T) перенесём на первое место в своей корзине. Затем пройдемся по массиву суффиксов Pos. Так как суффиксы отсортированы по первой букве, то для Pos[i] суффикса верно, что (Pos[i]−1)-ый суффикс будет первым в своей корзине. Обходим все суффиксы и для каждого предыдущий ему ставим на ближайшее к началу незанятое место в своей корзине. Новое место (Pos[i]−1)-го суффикса помечаем как «занятое». После этих операций в массиве Pos получится список суффиксов, отсортированный по первым двум буквам. Теперь будем считать, что одной корзине принадлежат суффиксы с одинаковыми первыми двумя символами. Опять пройдёмся по массиву Pos. Так как суффиксы отсортированы по первым двум буквам, то для Pos[i] суффикса верно, что (Pos[i]−2)-ой суффикс будет первым в своей корзине. Теперь массив Pos упорядочен по первым четырём символам. Обновляем разбиения по корзинам, одной корзине принадлежат суффиксы с одинаковыми четырьмя первыми символами. Процесс продолжается, пока в каждой корзине не будет только один суффикс. Тогда мы и получим суффиксный массив Pos.

Как искать образец в строке с помощью суффиксного массива

Все вхождения образца P в текст T можно найти с помощью простого алгоритма. Если образец P входит в строку T, то он является префиксом какого-нибудь суффикса T. При этом все вхождения P в T, если они есть, в суффиксном массиве Pos будут находиться рядом. Например, образец «бра» находится в строке «абракадабра» начиная со второго и с девятого символа. «бра» — префикс 2-го и 9-го суффиксов слова «абракадабра», которые в суффиксном массиве Pos находятся рядом.

Таким образом, поиск вхождений P в T сводится к двоичному поиску в упорядоченном массиве. Сначала проверяется Pos[m ⁄ 2]. Если суффикс Pos[m ⁄ 2] лексикографически меньше, то первая позиция, где P входит в T, должна быть в первой половине Pos. Если суффикс Pos[m ⁄ 2] лексикографически больше, чем P, то первая позиция, где P входит в T, должна быть во второй половине Pos. На следующем шаге аналогично ищем P в половине массива Pos. И так далее, пока не найдём (если такие существуют) наименьший и наибольшей индексы imin и imax такие, что образец P входит в текст T в позициях Pos[imin], Pos[imin+1], …, Pos[imax]. Например, для T = «абракадабра» и P = «бра» imin = 5, imax = 6, образец входит в текст в позициях Pos[5] = 9 и Pos[6] = 2.

Время лексикографического сравнения P с суффиксом пропорционально длине их общего префикса и не превышает n, поэтому при использовании двоичного поиска в массиве Pos все вхождения образца P в текст T могут быть найдены за время O(nlogm). Для случайных строк метод работает за ожидаемое время O(n+logm), но на случай, если в T есть много длинных префиксов P, метод можно улучшить.

Простой ускоритель mlr

При двоичном поиске обозначим левую и правую границы текущего интервала поиска как L и R соответственно. В начале работы поиска L = 1, R = m. На каждой итерации идёт лексикографическое сравнение образца P с суффиксом Pos[(L+R) ⁄ 2]. Обозначим через l длину общего префикса Pos[L] и P, через r — длину общего префикса Pos[R] и P, а через mlr — минимум из l и r. Значение mlr приходится поддерживать при двоичном поиске. Зная значение mlr, мы можем ускорить лексикографическое сравнение P с Pos[(L+R) ⁄ 2], так как для любого числа i от L до R первые mlr символов в Pos[i] одинаковые и сравнение можно начинать не с начала, а с позиции mlr+1. Наихудшее время остаётся прежним — O(nlogm), однако Майерс и Манбер сообщают, что использование mlrO(n+logm).

Литература

  1. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер. с англ. И.В. Романовского. — СПб.: Невский Диалект, 2003.

Визуализаторы

  1. Островский А. Суффиксные массивы (2005)

Автор: Тимур Магомедов


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий