Arbre palindromique

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

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)Voir et modifier les données sur Wikidata
Date de découverte
Problème lié

Description

modifier

L'arbre palindrome pour un mot   de longueur   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   avec une place additionnelle en  [2]. Lorsque   est de longueur   sur un alphabet de taille   et est donnée on-line, l'arbre peut être construit en temps   et place  .

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   vers le sommet   étiqueté par la lettre   si   :

 .

Ainsi, on a dans l'exemple, les arcs

 .

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

 .

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

  • le sommet   qui est la racine de l'arbre ; les arcs sortant de ce sommet et étiqueté   ont pour extrémité le sommet   ; on a donc, pour tout symbole figurant dans  , l'arc
 .
  • Le sommet   qui représente le mot vide (qui est un palindrome) ; on a alors
 
si   est facteur de  . Le sommet   est le lien suffixe du sommet   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  .

Complexité

modifier

On peut montrer[2] que la construction de l'arbre palindromique peur se faire en temps   et place  . Des variantes ont été données notamment par Mieno, Watanabe et al.[3].

Notes et références

modifier
  1. (en) Mikhail Rubinchik et Arseny M. Shur, « Eertree : An efficient data structure for processing palindromes in strings », Journal européen de combinatoire, Elsevier, vol. 68,‎ , p. 249-265 (ISSN 0195-6698 et 1095-9971, DOI 10.1016/J.EJC.2017.07.021, arXiv 1506.04862, lire en ligne) 
  2. a et b Rubinchik et Shur (2018).
  3. Mieno, Watanabe et Nakashima (2022).

Bibliographie

modifier
  • 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 »,‎ , 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,‎ , 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,‎ , article no 106174 (DOI 10.1016/j.ipl.2021.106174, lire en ligne  )

Lien externe

modifier

Articles liés

modifier