Arbre palindromique

Arbre palindromique

L'arbre palindromique ou arbre eertree pour le mot eertree. Les arcs directs sont en noir, liens suffixes sont pointillés et en rouge.

Découvreur ou inventeur	Mikhail Rubinchik (d)
Date de découverte	2015
Problème lié	Structure de données

Un arbre palindrome ou arbre palindromique, aussi appelé arbre eertree, est un graphe utilisé pour des algorithmes de combinatoire des mots.

Description

L'arbre palindrome pour un mot $S$ de longueur $n$ est une structure de donnée sous forme d'un graphe proche d'un arbre et qui représentent tous les palindromes distincts qui sont facteurs de $S$ avec une place additionnelle en $O(n)$. Lorsque $S$ est de longueur $n$ sur un alphabet de taille $\sigma$ et est donnée on-line, l'arbre peut être construit en temps $O(n\log \sigma )$ et place $O(n)$.

Les sommets du graphe représentent des palindromes, les arcs décrivent le passage d'un palindrome au suivant ou à un précédent.

Il y a deux types d'arcs, des arcs directs — qui sont les arcs d'un arbre — et des liens suffixes qui permettent de revenir en arrière.

Les arcs directs sont étiquetés par des symboles de l'alphabet. Il y a un arc direct du sommet $u$ vers le sommet $v$ étiqueté par la lettre $a$ si $v=aua$ :

$u\xrightarrow {a} v\iff v=aua$.

Ainsi, on a dans l'exemple, les arcs

${\mathsf {t}}\xrightarrow {\mathsf {r}} {\mathsf {rtr}}\xrightarrow {\mathsf {e}} {\mathsf {ertre}}\xrightarrow {\mathsf {e}} {\mathsf {eertree}}$.

Les liens suffixes sont des arcs qui vont d'un sommet $u$ au sommet $v$, où $v$ est le plus long suffixe palindrome propre de $u$. Dans l'exemple, les liens suffixes sont tracés en rouge. On a par exemple :

${\mathsf {eertree}}\ {\color {Red}\to }\ {\mathsf {ee}}\ {\color {Red}\to }\ {\mathsf {e}}\ {\color {Red}\to }\ 0$.

Deux sommets spéciaux sont ajoutés à la structure :

• le sommet $-1$ qui est la racine de l'arbre ; les arcs sortant de ce sommet et étiqueté $a$ ont pour extrémité le sommet $a$ ; on a donc, pour tout symbole figurant dans $S$, l'arc

$-1\xrightarrow {a} a$.

• Le sommet $0$ qui représente le mot vide (qui est un palindrome) ; on a alors

$0\xrightarrow {a} aa$

si $aa$ est facteur de $S$. Le sommet $0$ est le lien suffixe du sommet $-1$ et de lui-même.

La notation curieuse pour ces sommets particuliers est une conséquence de la numérotation des sommets de l'arbre, qui va de 1 jusqu'à un entier qui est aussi le nombre de palindromes figurant dans le mot $S$.

Complexité

On peut montrer que la construction de l'arbre palindromique peur se faire en temps $O(n\log \sigma )$ et place $O(n)$. Des variantes ont été données notamment par Mieno, Watanabe et al..

Bibliographie

• Mikhail Rubinchik et Arseny M. Shur, « EERTREE: An efficient data structure for processing palindromes in strings », Lecture Notes in Computer Science, vol. 9538 « Combinatorial Algorithms. IWOCA 2015 »,‎ 2016, p. 321-333 (DOI 10.1007/978-3-319-29516-9_27, arXiv 1506.04862)
• Mikhail Rubinchik et Arseny M. Shur, « EERTREE: An efficient data structure for processing palindromes in strings », European Journal of Combinatorics, vol. 68,‎ février 2018, p. 249-265 (DOI 10.1016/j.ejc.2017.07.021, arXiv 1506.04862) — version "journal" de l'article précédent
• Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, HideoBannai et MasayukiTakeda, « Palindromic trees for a sliding window and its applications », Information Processing Letters, vol. 173,‎ janvier 2022, article n^o 106174 (DOI 10.1016/j.ipl.2021.106174, lire en ligne )

Lien externe

• « Palindromic tree » ; blog sur adilet.org.
• « Palindromic Tree : Introduction & Implementation » ; sur geeksforgeeks.org.

Articles liés

• Palindrome
• Longueur palindromique d'un mot