Русская Википедия:Дерево палиндромов

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Дерево палиндромов (Шаблон:Lang-en, также овердрево, Шаблон:Lang-en) — структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки. Была предложена учёными из Уральского федерального университета Михаилом Рубинчиком и Арсением Шуром в 2015 году. Представляет собой два префиксных дерева, собранных из правых «половинок» палиндромных подстрок чётной и нечётной длины соответственно. Структура занимает <math>O(n)</math> памяти и может быть построена за время <math>O(n \log \sigma)</math>, где <math>n</math> — длина строки, а <math>\sigma</math> — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие.

Обозначения

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

• Строка <math>S</math> называется палиндромом, если она читается одинаково слева направо и справа налево, то есть если <math>S = S^R</math>.

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

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

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

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

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

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

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

Количество вершин в дереве палиндромов не превосходит <math>n+2</math>, что является прямым следствием следующей леммы:

Шаблон:Теорема Шаблон:Доказательство Помимо обычных дуг, которые служат переходами для префиксного дерева, для каждой вершины дерева палиндромов определяется суффиксная ссылка, которая ведёт из вершины <math>v</math> в вершину <math>u</math>, соответствующую наибольшему собственному (не равному всей строке <math>v</math>) суффикс-палиндрому <math>v</math>. При этом суффиксная ссылка из «мнимой» вершины не определена, а из пустой вершины по определению ведёт в «мнимую». Суффиксные ссылки образуют дерево с корнем в «мнимой» вершине и играют важную роль в построении дерева палиндромов.

Построение

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

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

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

Шаблон:Math
    Шаблон:Math
        Шаблон:Math
    Шаблон:Math

Шаблон:Math
    Шаблон:Math
    Шаблон:Math
    Шаблон:Math
    Шаблон:Math
        Шаблон:Math
        Шаблон:Math
        Шаблон:Math
        Шаблон:Math
    Шаблон:Math

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

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

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

Модификации

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

В 2019 году Ватанабе с коллегами разработали на основе дерева палиндромов структуру данных, называемую Шаблон:Math, для работы с подпалиндромами строк, заданных кодированием длин серий, а в 2020 году тот же состав авторов, совместно с Миено, разработали два алгоритма, позволяющих поддерживать дерево палиндромов на скользящем окне размера <math>d</math>. Первый из указанных алгоритмов требует <math>O(n \log \sigma)</math> времени и <math>O(d)</math> памяти, а второй — <math>O(n+d\sigma)</math> времени и <math>O(d\sigma)</math> памяти.

Применения

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

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

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

Литература

• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-Источник
• Шаблон:ВД-ИсточникШаблон:Refend

Ссылки

• Шаблон:Cite web