Arbre palindromique

Modèle:Infobox Algorithme 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)$Modèle:Sfnp. 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\stackrel{a}{\to }v⟺v=aua$.

Ainsi, on a dans l'exemple, les arcs

$𝗍\stackrel{𝗋}{\to }𝗋𝗍𝗋\stackrel{𝖾}{\to }𝖾𝗋𝗍𝗋𝖾\stackrel{𝖾}{\to }𝖾𝖾𝗋𝗍𝗋𝖾𝖾$.

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 :

$𝖾𝖾𝗋𝗍𝗋𝖾𝖾\to 𝖾𝖾\to 𝖾\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\stackrel{a}{\to }a$.

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

$0\stackrel{a}{\to }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 montrerModèle:Sfnp 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.Modèle:Sfnp.

Bibliographie

• Modèle:Article
• Modèle:Article — version "journal" de l'article précédent
• Modèle:Article

Lien externe

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

Articles liés

• Palindrome
• Longueur palindromique d'un mot