Дерево палиндромов (, также овердрево, ) — структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки. Была предложена учёными из Уральского федерального университета Михаилом Рубинчиком и Арсением Шуром в 2015 году. Представляет собой два префиксных дерева, собранных из правых «половинок» палиндромных подстрок чётной и нечётной длины соответственно. Структура занимает памяти и может быть построена за время , где — длина строки, а — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие.
Обозначения Пусть — некоторая строка, а — обращённая строка . При описании дерева палиндромов строки используются следующие обозначения:
Строка называется палиндромом, если она читается одинаково слева направо и справа налево, то есть если .
Подстрокой называют непрерывную подпоследовательность строки и обозначают .
В частности, подстрока, у которой , называется префиксом строки , а подстрока, у которой , — суффиксом строки .
Палиндромной подстрокой (подпалиндромом) называют подстроку , которая является палиндромом. Если эта подстрока также является префиксом или суффиксом строки , то её называют префикс- или суффикс-палиндромом соответственно.
Префиксным деревом называют корневое ориентированное дерево, дуги которого помечены символами таким образом, что из любой вершины этого дерева исходит не больше одной дуги, помеченной данным символом.
Каждой вершине префиксного дерева соответствует строка, равная конкатенации символов на пути из корня дерева в эту вершину.
Структура дерева В обозначениях выше, дерево палиндромов строки — это ориентированный граф, каждая вершина которого соответствует некоторому уникальному подпалиндрому строки и отождествляется с ним. Если у строки есть подпалиндромы и , где — некоторый символ алфавита, то в дереве палиндромов есть дуга, помеченная символом , из вершины, соответствующей , в вершину, соответствующую . В таком графе у любой вершины может быть только одна входящая дуга. Для удобства также вводятся две служебные вершины, которые соответствуют палиндромам длины (пустая строка) и («мнимая» строка) соответственно. Дуги из пустой строки ведут в вершины, соответствующие палиндромам вида , а из «мнимой строки» — в вершины, соответствующие палиндромам вида (то есть состоящим из единственного символа). Вершина называется чётной, если ей соответствует палиндром чётной длины, и нечётной в противном случае. Из определения следует, что дуги в дереве палиндромов проходят только между вершинами с одинаковой чётностью. С точки зрения префиксных деревьев данная структура может быть описана следующим образом:
Количество вершин в дереве палиндромов не превосходит , что является прямым следствием следующей леммы:
Помимо обычных дуг, которые служат переходами для префиксного дерева, для каждой вершины дерева палиндромов определяется суффиксная ссылка, которая ведёт из вершины в вершину , соответствующую наибольшему собственному (не равному всей строке ) суффикс-палиндрому . При этом суффиксная ссылка из «мнимой» вершины не определена, а из пустой вершины по определению ведёт в «мнимую». Суффиксные ссылки образуют дерево с корнем в «мнимой» вершине и играют важную роль в построении дерева палиндромов.
Построение Как и многие другие строковые структуры, дерево палиндромов строится итеративно. Изначально оно состоит лишь из вершин, соответствующих пустой и мнимой строкам. Затем структура постепенно перестраивается при наращивании строки по одному символу. Так как при добавлении одного символа в строке появляется не более одного нового палиндрома, перестройка дерева в худшем случае потребует добавления одной новой вершины и суффиксной ссылки к ней. Для определения возможной новой вершины в ходе построения дерева поддерживается указатель на вершину, соответствующую наибольшему из текущих суффикс-палиндромов.
Все суффикс-палиндромы строки достижимы по суффиксным ссылкам из , поэтому для определения нового суффикс-палиндрома (именно он будет соответствовать новой вершине, если таковая появится) необходимо переходить по суффиксным ссылкам , пока не обнаружится, что символ, предшествующий текущему суффикс-палиндрому, совпадает с символом, который был приписан к строке. Более формально, пусть — максимальный суффикс-палиндром строки , тогда либо , либо , где — некоторый суффикс-палиндром . Таким образом, перебирая среди суффиксных ссылок , можно определить, может ли он быть расширен до путём сравнения символов и . Когда соответствующий суффикс-палиндром был найден, следует проверить, присутствует ли в дереве палиндромов переход из соответствующей ему вершины по символу .
Если такой переход есть, то уже встречался в строке ранее и соответствует вершине, в которую ведёт этот переход. В противном случае необходимо создать для него новую вершину и провести переход по из . Затем следует определить суффиксную ссылку для , которая соответствует второму максимальному суффикс-палиндрому . Для того, чтобы её найти, следует продолжать обход суффиксных ссылок , пока не встретится вторая вершина , такая что ; именно эта вершина и будет суффиксный ссылкой . Если обозначить переход из вершины по символу как , весь процесс может быть описан следующим псевдокодом:
Здесь предполагается, что изначально дерево описывается лишь двумя вершинами с длинами и соответственно с суффиксной ссылкой из первой вершины во вторую. В переменной хранится вершина, соответствующая наибольшему суффикс-палиндрому текущей строки, изначально она указывает на вершину нулевой строки. Также предполагается, что изначально равно и в записан некоторый служебный символ, который не встречается в строке .
Вычислительная сложность Сложность алгоритма может варьировать в зависимости от структур данных, в которых хранится таблица переходов в дереве. В общем случае при использовании ассоциативного массива время, затрачиваемое на обращение к , достигает , где — размер алфавита, из символов которого построена строка. Стоит заметить, что каждая итерация первого вызова уменьшает длину , а второго — длину , которые между последовательными вызовам могут увеличиться только на единицу. Таким образом, суммарное время работы не превосходит , а общее время, требуемое для выполнения вызовов , можно оценить как . Расход памяти у данной структуры в худшем случае линейный, однако если рассматривать усреднённый размер структуры по всем строкам заданной длины , средний расход памяти будет порядка .
Модификации Одновременно с введением данной структуры данных Рубинчик и Шур также предложили ряд модификаций, позволяющих расширить область задач, решаемых деревом палиндромов. В частности, был предложен метод, позволяющий с той же асимптотикой построить общее дерево палиндромов для множества строк . Такая модификация позволяет решать те же задачи, рассматриваемые в контексте множества строк — например, найти наибольший общий подпалиндром всех строк или число различных подпалиндромов всех строк в совокупности. Другой предложенной модификацией стал вариант построения дерева, при котором на добавление одного символа требуется времени в худшем случае (а не амортизированно, как это происходит в стандартном построении) и памяти. Такой подход позволяет обеспечить дерева, при которой можно в произвольные моменты времени откатывать добавление последнего символа. Кроме того, была предложена полностью персистентная версия дерева, позволяющая обратиться и дописать символ к любой из сохранённых ранее версий за времени и памяти в худшем случае.
В 2019 году Ватанабе с коллегами разработали на основе дерева палиндромов структуру данных, называемую , для работы с подпалиндромами строк, заданных кодированием длин серий, а в 2020 году тот же состав авторов, совместно с Миено, разработали два алгоритма, позволяющих поддерживать дерево палиндромов на скользящем окне размера . Первый из указанных алгоритмов требует времени и памяти, а второй — времени и памяти.
Применения Дерево палиндромов даёт множество возможных применений для получения теоретически быстрых и практически легко реализуемых алгоритмов для решения ряда комбинаторных задач в программировании и математической кибернетике.
Одной из задач, для которых была разработана данная структура, является подсчёт различных подпалиндромов в строке . Она может быть поставлена следующим образом: к изначально пустой строке поочерёдно приписывается по одному символу. На каждом шаге необходимо вывести число различных подпалиндромов в данной строке. С точки зрения дерева палиндромов это эквивалентно тому, чтобы на каждом шаге вывести количество нетривиальных вершин в структуре. Линейное решение для оффлайн-версии данной задачи было представлено в 2010 году, а оптимальное решение со временем исполнения для онлайн-версии было найдено в 2013 году. Указанное решение, однако, использовало две «тяжеловесные» структуры данных — аналог алгоритма Манакера, а также суффиксное дерево. Дерево палиндромов же, с одной стороны, имеет ту же асимптотику в худшем случае, а с другой — является значительно более легковесной структурой.
Другим возможным применением данной структуры является перечисление палиндромно-богатых двоичных строк. Ранее было показано, что слово длины может содержать не более различных палиндромов, палиндромно-богатыми называются слова, на которых данная оценка достигается. Понятие палиндромно-богатых слов было введено Эми Глен и коллегами в 2008 году. Рубинчик и Шур показали, что с помощью дерева палиндромов можно обнаружить все палиндромно-богатые слова, чья длина не превосходит за , где — количество таких слов. Данный результат позволил увеличить количество известных членов последовательности в OEIS c 25 до 60. Полученные данные показали, что последовательность растёт значительно медленнее, чем это предполагалось ранее, а именно она ограничена сверху как .
Примечания
Литература
Ссылки
Категория:Структуры данных Категория:Строковые алгоритмы