Дерево палиндромов

Дерево палиндромов
Год изобретения	2015
Сложность в О-символике
В худшем случае Построение [math]\displaystyle{ O(n \log \sigma) }[/math] Расход памяти [math]\displaystyle{ O(n) }[/math]

Дерево палиндромов (англ. palindromic tree, также овердрево, англ. eertree) — структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки. Была предложена учёными из Уральского федерального университета Михаилом Рубинчиком и Арсением Шуром в 2015 году. Представляет собой два префиксных дерева, собранных из правых «половинок» палиндромных подстрок чётной и нечётной длины соответственно. Структура занимает [math]\displaystyle{ O(n) }[/math] памяти и может быть построена за время [math]\displaystyle{ O(n \log \sigma) }[/math], где [math]\displaystyle{ n }[/math] — длина строки, а [math]\displaystyle{ \sigma }[/math] — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие.

Обозначения

Пусть [math]\displaystyle{ S=s_1 s_2 \dots s_n }[/math] — некоторая строка, а [math]\displaystyle{ S^R = s_n s_{n-1} \dots s_1 }[/math] — обращённая строка [math]\displaystyle{ S }[/math]. При описании дерева палиндромов строки [math]\displaystyle{ S }[/math] используются следующие обозначения:

• Строка [math]\displaystyle{ S }[/math] называется палиндромом, если она читается одинаково слева направо и справа налево, то есть если [math]\displaystyle{ S = S^R }[/math].

• Подстрокой называют непрерывную подпоследовательность строки [math]\displaystyle{ S }[/math] и обозначают [math]\displaystyle{ S_{l,r} =s_l s_{l+1} \dots s_r }[/math].

• В частности, подстрока, у которой [math]\displaystyle{ l=1 }[/math], называется префиксом строки [math]\displaystyle{ S }[/math], а подстрока, у которой [math]\displaystyle{ r=n }[/math], — суффиксом строки [math]\displaystyle{ S }[/math].

• Палиндромной подстрокой (подпалиндромом) называют подстроку [math]\displaystyle{ S }[/math], которая является палиндромом. Если эта подстрока также является префиксом или суффиксом строки [math]\displaystyle{ S }[/math], то её называют префикс- или суффикс-палиндромом соответственно.

• Префиксным деревом называют корневое ориентированное дерево, дуги которого помечены символами таким образом, что из любой вершины [math]\displaystyle{ v }[/math] этого дерева исходит не больше одной дуги, помеченной данным символом.

• Каждой вершине префиксного дерева соответствует строка, равная конкатенации символов на пути из корня дерева в эту вершину.

Структура дерева

В обозначениях выше, дерево палиндромов строки [math]\displaystyle{ S }[/math] — это ориентированный граф, каждая вершина которого соответствует некоторому уникальному подпалиндрому строки и отождествляется с ним. Если у строки есть подпалиндромы [math]\displaystyle{ t }[/math] и [math]\displaystyle{ ctc }[/math], где [math]\displaystyle{ c }[/math] — некоторый символ алфавита, то в дереве палиндромов есть дуга, помеченная символом [math]\displaystyle{ c }[/math], из вершины, соответствующей [math]\displaystyle{ t }[/math], в вершину, соответствующую [math]\displaystyle{ ctc }[/math]. В таком графе у любой вершины может быть только одна входящая дуга. Для удобства также вводятся две служебные вершины, которые соответствуют палиндромам длины [math]\displaystyle{ 0 }[/math] (пустая строка) и [math]\displaystyle{ -1 }[/math] («мнимая» строка) соответственно. Дуги из пустой строки ведут в вершины, соответствующие палиндромам вида [math]\displaystyle{ cc }[/math], а из «мнимой строки» — в вершины, соответствующие палиндромам вида [math]\displaystyle{ c }[/math] (то есть состоящим из единственного символа). Вершина называется чётной, если ей соответствует палиндром чётной длины, и нечётной в противном случае. Из определения следует, что дуги в дереве палиндромов проходят только между вершинами с одинаковой чётностью. С точки зрения префиксных деревьев данная структура может быть описана следующим образом:

Вершины и дуги дерева палиндромов образуют два префиксных дерева, корни которых находятся в вершинах, задающих пустую и «мнимую» строки соответственно. При этом первое префиксное дерево составлено из правых половин подпалиндромов чётной длины, а второе — нечётной.

Количество вершин в дереве палиндромов не превосходит [math]\displaystyle{ n+2 }[/math], что является прямым следствием следующей леммы:

У строки [math]\displaystyle{ S }[/math] длины [math]\displaystyle{ n }[/math] может быть не больше [math]\displaystyle{ n }[/math] различных непустых палиндромных подстрок. Более того, после приписывания некоторого символа [math]\displaystyle{ c }[/math] в конец строки количество различных подпалиндромов данной строки может увеличиться не больше, чем на [math]\displaystyle{ 1 }[/math].

Доказательство

Данное утверждение следует из следующих фактов:

1. Если палиндром [math]\displaystyle{ u }[/math] — суффикс палиндрома [math]\displaystyle{ v }[/math], то он также является его префиксом;
2. Если палиндромы [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] — суффиксы строки [math]\displaystyle{ w }[/math] и [math]\displaystyle{ |u| \lt |v| }[/math], то [math]\displaystyle{ u }[/math] встречается в [math]\displaystyle{ w }[/math] хотя бы два раза (как префикс и как суффикс [math]\displaystyle{ v }[/math]);
3. У любой строки [math]\displaystyle{ w }[/math] может быть не больше одного уникального (встречающегося в [math]\displaystyle{ w }[/math] всего один раз) суффикс-палиндрома.

Последнее свойство по сути эквивалентно лемме, так как все новые подстроки, которые появляются при дописывании очередного символа к строке, должны быть её суффиксами.■

Помимо обычных дуг, которые служат переходами для префиксного дерева, для каждой вершины дерева палиндромов определяется суффиксная ссылка, которая ведёт из вершины [math]\displaystyle{ v }[/math] в вершину [math]\displaystyle{ u }[/math], соответствующую наибольшему собственному (не равному всей строке [math]\displaystyle{ v }[/math]) суффикс-палиндрому [math]\displaystyle{ v }[/math]. При этом суффиксная ссылка из «мнимой» вершины не определена, а из пустой вершины по определению ведёт в «мнимую». Суффиксные ссылки образуют дерево с корнем в «мнимой» вершине и играют важную роль в построении дерева палиндромов.

Построение

Как и многие другие строковые структуры, дерево палиндромов строится итеративно. Изначально оно состоит лишь из вершин, соответствующих пустой и мнимой строкам. Затем структура постепенно перестраивается при наращивании строки по одному символу. Так как при добавлении одного символа в строке появляется не более одного нового палиндрома, перестройка дерева в худшем случае потребует добавления одной новой вершины и суффиксной ссылки к ней. Для определения возможной новой вершины в ходе построения дерева поддерживается указатель last на вершину, соответствующую наибольшему из текущих суффикс-палиндромов.

Все суффикс-палиндромы строки достижимы по суффиксным ссылкам из last, поэтому для определения нового суффикс-палиндрома (именно он будет соответствовать новой вершине, если таковая появится) необходимо переходить по суффиксным ссылкам last, пока не обнаружится, что символ, предшествующий текущему суффикс-палиндрому, совпадает с символом, который был приписан к строке. Более формально, пусть [math]\displaystyle{ P }[/math] — максимальный суффикс-палиндром строки [math]\displaystyle{ S_{1,k} = s_1 s_2 \dots s_k }[/math], тогда либо [math]\displaystyle{ P=s_k }[/math], либо [math]\displaystyle{ P=s_k Q s_k }[/math], где [math]\displaystyle{ Q }[/math] — некоторый суффикс-палиндром [math]\displaystyle{ S_{1,k-1} }[/math]. Таким образом, перебирая [math]\displaystyle{ Q }[/math] среди суффиксных ссылок last, можно определить, может ли он быть расширен до [math]\displaystyle{ P }[/math] путём сравнения символов [math]\displaystyle{ s_{k-|Q|-1} }[/math] и [math]\displaystyle{ s_k }[/math]. Когда соответствующий суффикс-палиндром [math]\displaystyle{ Q }[/math] был найден, следует проверить, присутствует ли в дереве палиндромов переход из соответствующей ему вершины по символу [math]\displaystyle{ s_k }[/math].

Если такой переход есть, то [math]\displaystyle{ P }[/math] уже встречался в строке ранее и соответствует вершине, в которую ведёт этот переход. В противном случае необходимо создать для него новую вершину и провести переход по [math]\displaystyle{ s_k }[/math] из [math]\displaystyle{ Q }[/math]. Затем следует определить суффиксную ссылку для [math]\displaystyle{ P }[/math], которая соответствует второму максимальному суффикс-палиндрому [math]\displaystyle{ S_{1,k} }[/math]. Для того, чтобы её найти, следует продолжать обход суффиксных ссылок last, пока не встретится вторая вершина [math]\displaystyle{ Q }[/math], такая что [math]\displaystyle{ s_{k-|Q|-1}=s_k }[/math]; именно эта вершина и будет суффиксный ссылкой [math]\displaystyle{ P }[/math]. Если обозначить переход из вершины [math]\displaystyle{ v }[/math] по символу [math]\displaystyle{ c }[/math] как [math]\displaystyle{ \delta(v, c) }[/math], весь процесс может быть описан следующим псевдокодом:

функция find_link(v):
    пока sk-len(v)-1 ≠ sk:
        присвоить v = link(v)
    вернуть v

функция add_letter(c):
    присвоить k = k + 1
    определить sk = c
    определить q = find_link(last)
    если δ(q, c) не определено:
        определить p = new_vertex()
        определить len(p) = len(q) + 2
        определить link(p) = δ(find_link(link(q)), c)
        определить δ(q, c) = p
    присвоить last = δ(q, c)

Здесь предполагается, что изначально дерево описывается лишь двумя вершинами с длинами [math]\displaystyle{ 0 }[/math] и [math]\displaystyle{ -1 }[/math] соответственно с суффиксной ссылкой из первой вершины во вторую. В переменной last хранится вершина, соответствующая наибольшему суффикс-палиндрому текущей строки, изначально она указывает на вершину нулевой строки. Также предполагается, что [math]\displaystyle{ k }[/math] изначально равно [math]\displaystyle{ 0 }[/math] и в [math]\displaystyle{ s_0 }[/math] записан некоторый служебный символ, который не встречается в строке [math]\displaystyle{ s_1 s_2 \dots s_k }[/math].

Вычислительная сложность

Сложность алгоритма может варьировать в зависимости от структур данных, в которых хранится таблица переходов в дереве. В общем случае при использовании ассоциативного массива время, затрачиваемое на обращение к [math]\displaystyle{ \delta(q, c) }[/math], достигает [math]\displaystyle{ O(\log \sigma) }[/math], где [math]\displaystyle{ \sigma }[/math] — размер алфавита, из символов которого построена строка. Стоит заметить, что каждая итерация первого вызова find_link уменьшает длину last, а второго — длину link(last), которые между последовательными вызовам add_letter могут увеличиться только на единицу. Таким образом, суммарное время работы find_link не превосходит [math]\displaystyle{ O(n) }[/math], а общее время, требуемое для выполнения [math]\displaystyle{ n }[/math] вызовов add_letter, можно оценить как [math]\displaystyle{ O(n \log \sigma) }[/math]. Расход памяти у данной структуры в худшем случае линейный, однако если рассматривать усреднённый размер структуры по всем строкам заданной длины [math]\displaystyle{ n }[/math], средний расход памяти будет порядка [math]\displaystyle{ O(\sqrt{n \sigma}) }[/math].

Модификации

Одновременно с введением данной структуры данных Рубинчик и Шур также предложили ряд модификаций, позволяющих расширить область задач, решаемых деревом палиндромов. В частности, был предложен метод, позволяющий с той же асимптотикой построить общее дерево палиндромов для множества строк [math]\displaystyle{ S_1, S_2, \dots, S_k }[/math]. Такая модификация позволяет решать те же задачи, рассматриваемые в контексте множества строк — например, найти наибольший общий подпалиндром всех строк или число различных подпалиндромов всех строк в совокупности. Другой предложенной модификацией стал вариант построения дерева, при котором на добавление одного символа требуется [math]\displaystyle{ O(\log n) }[/math] времени в худшем случае (а не [math]\displaystyle{ O(\log \sigma) }[/math] амортизированно, как это происходит в стандартном построении) и [math]\displaystyle{ O(1) }[/math] памяти. Такой подход позволяет обеспечить частичную персистентность дерева, при которой можно в произвольные моменты времени откатывать добавление последнего символа. Кроме того, была предложена полностью персистентная версия дерева, позволяющая обратиться и дописать символ к любой из сохранённых ранее версий за [math]\displaystyle{ O(\log n) }[/math] времени и памяти в худшем случае.

В 2019 году Ватанабе с коллегами разработали на основе дерева палиндромов структуру данных, называемую e²rtre², для работы с подпалиндромами строк, заданных кодированием длин серий, а в 2020 году тот же состав авторов, совместно с Миено, разработали два алгоритма, позволяющих поддерживать дерево палиндромов на скользящем окне размера [math]\displaystyle{ d }[/math]. Первый из указанных алгоритмов требует [math]\displaystyle{ O(n \log \sigma) }[/math] времени и [math]\displaystyle{ O(d) }[/math] памяти, а второй — [math]\displaystyle{ O(n+d\sigma) }[/math] времени и [math]\displaystyle{ O(d\sigma) }[/math] памяти.

Применения

Дерево палиндромов даёт множество возможных применений для получения теоретически быстрых и практически легко реализуемых алгоритмов для решения ряда комбинаторных задач в программировании и математической кибернетике.

Одной из задач, для которых была разработана данная структура, является подсчёт различных подпалиндромов в строке в режиме онлайн. Она может быть поставлена следующим образом: к изначально пустой строке поочерёдно приписывается по одному символу. На каждом шаге необходимо вывести число различных подпалиндромов в данной строке. С точки зрения дерева палиндромов это эквивалентно тому, чтобы на каждом шаге вывести количество нетривиальных вершин в структуре. Линейное решение для оффлайн-версии данной задачи было представлено в 2010 году, а оптимальное решение со временем исполнения [math]\displaystyle{ O(n \log \sigma) }[/math] для онлайн-версии было найдено в 2013 году. Указанное решение, однако, использовало две «тяжеловесные» структуры данных — аналог алгоритма Манакера, а также суффиксное дерево. Дерево палиндромов же, с одной стороны, имеет ту же асимптотику в худшем случае, а с другой — является значительно более легковесной структурой.

Другим возможным применением данной структуры является перечисление палиндромно-богатых двоичных строк. Ранее было показано, что слово длины [math]\displaystyle{ n }[/math] может содержать не более [math]\displaystyle{ n+1 }[/math] различных палиндромов, палиндромно-богатыми называются слова, на которых данная оценка достигается. Понятие палиндромно-богатых слов было введено Эми Глен и коллегами в 2008 году. Рубинчик и Шур показали, что с помощью дерева палиндромов можно обнаружить все палиндромно-богатые слова, чья длина не превосходит [math]\displaystyle{ n }[/math] за [math]\displaystyle{ O(R) }[/math], где [math]\displaystyle{ R }[/math] — количество таких слов. Данный результат позволил увеличить количество известных членов последовательности A216264 в OEIS c 25 до 60. Полученные данные показали, что последовательность растёт значительно медленнее, чем это предполагалось ранее, а именно она ограничена сверху как [math]\displaystyle{ O(1,605^n) }[/math].

Ссылки

• Дерево палиндромов (неопр.). Вики-конспекты ИТМО.