Просмотр кода страницы Дерево палиндромов

{{Структура данных
| изобретена = [[2015]]
| построение худшее = <math>O(n \log \sigma)</math>
| память худшая = <math>O(n)</math>
}}

'''Дерево палиндромов''' ({{Lang-en|palindromic tree}}, также ''овердрево''<ref>{{Sfn-текст|Рубинчик|2016|страницы=6—9}}</ref>, {{Lang-en|eertree}}) — [[структура данных]], предназначенная для хранения и обработки [[палиндром]]ных подстрок некоторой [[Строка (программирование)|строки]]. Была предложена учёными из [[Уральский федеральный университет|Уральского федерального университета]] Михаилом Рубинчиком и Арсением Шуром в 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> используются следующие обозначения<ref>{{Sfn-текст|Rubinchik, Shur|2018|pp=1—2}}</ref>:

* Строка <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> (то есть состоящим из единственного символа). Вершина называется ''чётной'', если ей соответствует палиндром чётной длины, и ''нечётной'' в противном случае. Из определения следует, что дуги в дереве палиндромов проходят только между вершинами с одинаковой чётностью. С точки зрения префиксных деревьев данная структура может быть описана следующим образом<ref name=":0">{{Sfn-текст|Rubinchik, Shur|2018|pp=2—6}}</ref>:

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

Количество вершин в дереве палиндромов не превосходит <math>n+2</math>, что является прямым следствием следующей леммы<ref name=":1">{{Sfn-текст|Watanabe et al.|2019|pp=432—434}}</ref>:

{{Теорема|У строки <math>S</math> длины <math>n</math> может быть не больше <math>n</math> различных непустых палиндромных подстрок. Более того, после приписывания некоторого символа <math>c</math> в конец строки количество ''различных'' подпалиндромов данной строки может увеличиться не больше, чем на <math>1</math>.}}
{{Доказательство|Данное утверждение следует из следующих фактов:
# Если палиндром <math>u</math> — суффикс палиндрома <math>v</math>, то он также является его префиксом;
# Если палиндромы <math>u</math> и <math>v</math> — суффиксы строки <math>w</math> и <math>|u| < |v|</math>, то <math>u</math> встречается в <math>w</math> хотя бы два раза (как префикс и как суффикс <math>v</math>);
# У любой строки <math>w</math> может быть не больше одного уникального (встречающегося в <math>w</math> всего один раз) суффикс-палиндрома.

Последнее свойство по сути эквивалентно лемме, так как все новые подстроки, которые появляются при дописывании очередного символа к строке, должны быть её суффиксами<ref>{{Sfn-текст|Droubay et al.|2001|pp=542—546}}</ref>.}}
Помимо обычных дуг, которые служат переходами для префиксного дерева, для каждой вершины дерева палиндромов определяется ''суффиксная ссылка'', которая ведёт из вершины <math>v</math> в вершину <math>u</math>, соответствующую наибольшему собственному (не равному всей строке <math>v</math>) суффикс-палиндрому <math>v</math>. При этом суффиксная ссылка из «мнимой» вершины не определена, а из пустой вершины по определению ведёт в «мнимую». Суффиксные ссылки образуют дерево с корнем в «мнимой» вершине и играют важную роль в построении дерева палиндромов<ref name=":0" />.

== Построение ==
Как и многие другие строковые структуры, дерево палиндромов строится [[Итерация (математика)|итеративно]]. Изначально оно состоит лишь из вершин, соответствующих пустой и мнимой строкам. Затем структура постепенно перестраивается при наращивании строки по одному символу. Так как при добавлении одного символа в строке появляется не более одного нового палиндрома, перестройка дерева в худшем случае потребует добавления одной новой вершины и суффиксной ссылки к ней. Для определения возможной новой вершины в ходе построения дерева поддерживается указатель {{Math|last}} на вершину, соответствующую наибольшему из текущих суффикс-палиндромов<ref name=":0" />.

Все суффикс-палиндромы строки достижимы по суффиксным ссылкам из {{Math|last}}, поэтому для определения нового суффикс-палиндрома (именно он будет соответствовать новой вершине, если таковая появится) необходимо переходить по суффиксным ссылкам {{Math|last}}, пока не обнаружится, что символ, предшествующий текущему суффикс-палиндрому, совпадает с символом, который был приписан к строке. Более формально, пусть <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|last}}, можно определить, может ли он быть расширен до <math>P</math> путём сравнения символов <math>s_{k-|Q|-1}</math> и <math>s_k</math>. Когда соответствующий суффикс-палиндром <math>Q</math> был найден, следует проверить, присутствует ли в дереве палиндромов переход из соответствующей ему вершины по символу <math>s_k</math><ref name=":0" />.

Если такой переход есть, то <math>P</math> уже встречался в строке ранее и соответствует вершине, в которую ведёт этот переход. В противном случае необходимо создать для него новую вершину и провести переход по <math>s_k</math> из <math>Q</math>. Затем следует определить суффиксную ссылку для <math>P</math>, которая соответствует второму максимальному суффикс-палиндрому <math>S_{1,k}</math>. Для того, чтобы её найти, следует продолжать обход суффиксных ссылок {{math|last}}, пока не встретится вторая вершина <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>, весь процесс может быть описан следующим [[Псевдокод (язык описания алгоритмов)|псевдокодом]]<ref name=":0" />:

 {{math|'''функция''' find_link(v):}}
     {{math|'''пока''' s<sub>k-len(v)-1</sub> ≠ s<sub>k</sub>:}}
         {{math|'''присвоить''' v {{=}} link(v)}}
     {{math|'''вернуть''' v}}
 
 {{math|'''функция''' add_letter(c):}}
     {{math|'''присвоить''' k {{=}} k + 1}}
     {{math|'''определить''' s<sub>k</sub> {{=}} c}}
     {{math|'''определить''' q {{=}} find_link(last)}}
     {{math|'''если''' δ(q, c) не определено:}}
         {{math|'''определить''' p {{=}} new_vertex()}}
         {{math|'''определить''' len(p) {{=}} len(q) + 2}}
         {{math|'''определить''' link(p) {{=}} δ(find_link(link(q)), c)}}
         {{math|'''определить''' δ(q, c) {{=}} p}}
     {{math|'''присвоить''' last {{=}} δ(q, c)}}

Здесь предполагается, что изначально дерево описывается лишь двумя вершинами с длинами <math>0</math> и <math>-1</math> соответственно с суффиксной ссылкой из первой вершины во вторую. В переменной {{Math|last}} хранится вершина, соответствующая наибольшему суффикс-палиндрому текущей строки, изначально она указывает на вершину нулевой строки. Также предполагается, что <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|find_link}} уменьшает длину {{Math|last}}, а второго — длину {{Math|link(last)}}, которые между последовательными вызовам {{Math|add_letter}} могут увеличиться только на единицу. Таким образом, суммарное время работы {{Math|find_link}} не превосходит <math>O(n)</math>, а общее время, требуемое для выполнения <math>n</math> вызовов {{Math|add_letter}}, можно оценить как <math>O(n \log \sigma)</math><ref name=":0" />. Расход памяти у данной структуры в худшем случае линейный, однако если рассматривать усреднённый размер структуры по всем строкам заданной длины <math>n</math>, средний расход памяти будет порядка <math>O(\sqrt{n \sigma})</math><ref>{{sfn-текст|Rubinchik, Shur|2016|p=1}}</ref>.

== Модификации ==
Одновременно с введением данной структуры данных Рубинчик и Шур также предложили ряд модификаций, позволяющих расширить область задач, решаемых деревом палиндромов. В частности, был предложен метод, позволяющий с той же асимптотикой построить общее дерево палиндромов для множества строк <math>S_1, S_2, \dots, S_k</math>. Такая модификация позволяет решать те же задачи, рассматриваемые в контексте множества строк — например, найти наибольший общий подпалиндром всех строк или число различных подпалиндромов всех строк в совокупности. Другой предложенной модификацией стал вариант построения дерева, при котором на добавление одного символа требуется <math>O(\log n)</math> времени ''в худшем случае'' (а не <math>O(\log \sigma)</math> ''[[Амортизационный анализ|амортизированно]]'', как это происходит в стандартном построении) и <math>O(1)</math> памяти. Такой подход позволяет обеспечить {{Iw|Персистентная структура данных|частичную персистентность||Persistent data structure}} дерева, при которой можно в произвольные моменты времени откатывать добавление последнего символа. Кроме того, была предложена полностью персистентная версия дерева, позволяющая обратиться и дописать символ к любой из сохранённых ранее версий за <math>O(\log n)</math> времени и памяти в худшем случае<ref>{{Sfn-текст|Rubinchik, Shur|2018|p=6—11}}</ref>.

В 2019 году Ватанабе с коллегами разработали на основе дерева палиндромов структуру данных, называемую {{Math|e<sup>2</sup>rtre<sup>2</sup>}}, для работы с подпалиндромами строк, заданных [[Кодирование длин серий|кодированием длин серий]]<ref name=":1" />, а в 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> памяти<ref>{{Sfn-текст|Mieno et al.|2020}}</ref>.

== Применения ==
Дерево палиндромов даёт множество возможных применений для получения теоретически быстрых и практически легко реализуемых алгоритмов для решения ряда комбинаторных задач в программировании и математической кибернетике<ref>{{Sfn-текст|Рубинчик|2016|страницы=75—76}}</ref>.

Одной из задач, для которых была разработана данная структура, является подсчёт различных подпалиндромов в строке {{Iw|Онлайн-алгоритм|в режиме онлайн||Online algorithm}}. Она может быть поставлена следующим образом: к изначально пустой строке поочерёдно приписывается по одному символу. На каждом шаге необходимо вывести число различных подпалиндромов в данной строке. С точки зрения дерева палиндромов это эквивалентно тому, чтобы на каждом шаге вывести количество нетривиальных вершин в структуре. Линейное решение для оффлайн-версии данной задачи было представлено в 2010 году<ref>{{sfn-текст|Groult|2010}}</ref>, а оптимальное решение со временем исполнения <math>O(n \log \sigma)</math> для онлайн-версии было найдено в 2013 году<ref>{{sfn-текст|Kosolobov et al.|2013}}</ref>. Указанное решение, однако, использовало две «тяжеловесные» структуры данных — аналог [[алгоритм Манакера|алгоритма Манакера]], а также [[суффиксное дерево]]. Дерево палиндромов же, с одной стороны, имеет ту же асимптотику в худшем случае, а с другой — является значительно более легковесной структурой<ref name=":0" />.

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

== Примечания ==
{{Примечания|30em}}

== Литература ==
{{refbegin}}
* {{ВД-Источник|Q90824086|ref=Рубинчик|pages=|volume=|issue=}}
* {{ВД-Источник|Q90835213|ref=Droubay et al.|pages=|volume=|issue=}}
* {{ВД-Источник|Q96738845|ref=Groult|pages=|volume=|issue=}}
* {{ВД-Источник|Q96738920|ref=Kosolobov et al.|pages=|volume=|issue=}}
* {{ВД-Источник|Q96655649|ref=Mieno|pages=|volume=|issue=}}
* {{ВД-Источник|Q96718109|ref=Rubinchik, Shur|pages=|volume=|issue=}}
* {{ВД-Источник|Q90726647|ref=Rubinchik, Shur|pages=|volume=|issue=}}
* {{ВД-Источник|Q90737123|ref=Watanabe et al.|pages=|volume=|issue=}}
* {{ВД-Источник|Q97016349|pages=|volume=|issue=|ref=Glen et al.}}
* {{ВД-Источник|Q97016369|pages=|volume=|issue=|ref=Rukavicka}}{{refend}}

== Ссылки ==
* {{Cite web|url=https://neerc.ifmo.ru/wiki/index.php?title=Дерево_палиндромов|title=Дерево палиндромов|website=Вики-конспекты ИТМО}}
{{Строки}}

[[Категория:Структуры данных]]
[[Категория:Строковые алгоритмы]]
{{Хорошая статья|Математика}}