Конспект: суффиксный массив, LCP и суффиксное дерево

Понятия

Суффикс - кусок текста от позиции i до конца. У текста длины n их n.

Суффиксный массив sa - номера начал суффиксов в порядке возрастания самих суффиксов. Хранит n чисел и ни одной строки.

LCP - lcp[i] равно числу первых символов, общих у суффиксов sa[i − 1] и sa[i].

Суффиксное дерево - сжатый бор всех суффиксов текста с завершающим символом $. Листьев n, развилок меньше n, рёбра хранят пары индексов.

Развилка - узел суффиксного дерева с двумя и более сыновьями; её строка встречается в тексте хотя бы дважды.

LCE двух позиций - длина общего продолжения; минимум LCP между рангами, O(1) разреженной таблицей. Применения: поиск с k ошибками и джокерами (k + 1 прыжок на сдвиг), тандемные повторы (LCE(i, i + p) ≥ p).

Что унести

banana
место    sa    суффикс    lcp
  0       5    a           0
  1       3    ana         1
  2       1    anana       3
  3       0    banana      0
  4       4    na          0
  5       2    nana        2

подстрока = начало суффикса  →  все вхождения образца стоят в sa ПОДРЯД

ПОИСК ПО МАССИВУ
кусок = t[sa[mid] : sa[mid] + m]            первые m символов суффикса, не весь суффикс
левая граница:   первое место, где кусок >= p
правая граница:  первое место, где кусок >  p
число вхождений = правая − левая;   позиции = sa[левая .. правая − 1], НЕ по порядку текста
цена: два двоичных поиска, около log₂ n кругов по m символов

ЧТО ЧИТАЕТСЯ ИЗ LCP БЕЗ ПОИСКА
самый длинный повтор              max lcp                      banana: 3, ana
число различных подстрок          n(n + 1) / 2 − Σ lcp          banana: 21 − 6 = 15
общая подстрока двух строк        по склейке a + "#" + b + "$":
                                  max lcp среди соседей ИЗ РАЗНЫХ строк
общее начало любых двух суффиксов минимум lcp на отрезке между ними

АЛГОРИТМ КАСАИ: суффиксы в порядке ТЕКСТА
у суффикса i с соседом сверху общих h  →  у суффикса i + 1 со своим соседом не меньше h − 1
сравнение начинается с h − 1, а не с нуля;   всего не больше 2n сравнений
"a" * 1000:   по определению 499 500,   Касаи 999

СУФФИКСНОЕ ДЕРЕВО banana$
(корень)
   ├ $                  6
   ├ a ┬ $              5
   │   └ na ┬ $         3
   │        └ na$       1
   ├ banana$            0
   └ na ┬ $             4
        └ na$           2

листья слева направо = суффиксный массив;   глубины развилок = значения LCP
поиск образца: спуск от корня, m сравнений, от n не зависит

Ловушки джокера

Сравнение с суффиксом целиком. Для an в banana выходит ноль вхождений: ana и anana «больше».

Позиции из массива приняты за упорядоченные. Для ana это 3, потом 1.

Индекс после правки текста. Дописанный символ меняет все суффиксы: в aa суффикс 1 меньше суффикса 0, в aab наоборот. Массив перестраивается.

Хранить суффиксы, а не номера. n² / 2 символов: пять миллиардов на сто тысяч.

Ранги в удвоении розданы по порядку. Равные пары обязаны получить равный ранг.

h = 0 вместо h − 1 в Касаи. Ответ верный, цена квадратичная.

Склейка без разделителей. xa и bxab дают «общую» xab, которой в первой строке нет.

Максимум LCP по всем соседям при поиске общей подстроки. Находит повтор внутри одной строки.

LCP с соседом сверху против LCP с соседом снизу. Две договорённости, индексы сдвинуты на единицу.

Дерево без $. Суффиксы-начала других суффиксов не получают листьев; счёт вхождений по листьям врёт.

Строки на рёбрах дерева. Квадратичная память. Ребро - два индекса.

Куда это ведёт

Суффиксный массив находит повторы, чтобы отвечать на запросы. Сжатие находит повторы, чтобы их не хранить. Следующая глава начинается с самого простого повтора - одинаковых символов подряд - и с вопроса, на который у поиска ответа не было: какой наименьший размер вообще достижим и откуда берётся этот предел. А суффиксный массив вернётся через главу: преобразование Барроуза-Уилера строится по нему.