|
|
| (не показана 1 промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
| {{Структура данных
| | '''Дерево палиндромов''' — [[структура данных]], предназначенная для хранения и обработки [[палиндром]]ных подстрок некоторой [[Строка (программирование)|строки]]. Была предложена учёными из [[Уральский федеральный университет|Уральского федерального университета]] Михаилом Рубинчиком и Арсением Шуром в 2015 году. Представляет собой два [[Префиксное дерево|префиксных дерева]], собранных из правых «половинок» палиндромных подстрок чётной и нечётной длины соответственно. Структура [[О-нотация|занимает]] <math>O(n)</math> памяти и может быть построена за время <math>O(n \log \sigma)</math>, где <math>n</math> — длина строки, а <math>\sigma</math> — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие. |
| | изобретена = [[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> — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие. | |
|
| |
|
| == Обозначения == | | == Обозначения == |
| Строка 23: |
Строка 17: |
|
| |
|
| == Структура дерева == | | == Структура дерева == |
| В обозначениях выше, ''дерево палиндромов'' строки <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>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>, что является прямым следствием следующей леммы<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=Вики-конспекты ИТМО}}
| |
| {{Строки}}
| |
| | |
| [[Категория:Структуры данных]] | | [[Категория:Структуры данных]] |
| [[Категория:Строковые алгоритмы]]
| |
| {{Хорошая статья|Математика}}
| |
Дерево палиндромов — структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки. Была предложена учёными из Уральского федерального университета Михаилом Рубинчиком и Арсением Шуром в 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] используются следующие обозначения<ref>Шаблон:Sfn-текст</ref>:
- Строка [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] (то есть состоящим из единственного символа). Вершина называется чётной, если ей соответствует палиндром чётной длины, и нечётной в противном случае. Из определения следует, что дуги в дереве палиндромов проходят только между вершинами с одинаковой чётностью.
Вычислительная сложность
Сложность алгоритма может варьировать в зависимости от структур данных, в которых хранится таблица переходов в дереве.
Применения
Дерево палиндромов даёт множество возможных применений для получения теоретически быстрых и практически легко реализуемых алгоритмов для решения ряда комбинаторных задач в программировании и математической кибернетике
