Distance d'édition sur les arbres

Soit l et $l^\prime$ des nœuds racines, F et $F^\prime$ des forêts (un ensemble d'arbre) ordonnées. On définit l(F) et $l^\prime(F^\prime)$ comme étant des arbres de taille n et m, avec comme nœuds racines respectifs l et $l^\prime$. Les fils directs de l et $l^\prime$ sont les nœuds racines des forêts respectives F et $F^\prime$. La distance d'édition $\delta_{arbre}(l(F),l^\prime(F^\prime))$ est le coût minimum d'opérations élémentaires consistant en la suppression, l'insertion et le renommage d'un nœud, pour transformer l(F) en $l^\prime(F^\prime)$. La première version de cette distance fut proposée par Tai dont la complexité en temps et en espace pour le pire des cas est en O(n⁶).

De plus l'opérateur $\circ$ permet de concaténer un arbre à une forêt. Le calcul d'une distance d'édition sur arbre est similaire au calcul sur les chaînes. Cependant le choix de l'ordre des récursions peut changer la complexité temporelle du calcul de manière significative.

Stratégie de décomposition

Dans l'article \cite{dulucq2003ate} les auteurs ont proposé un cadre d'étude sur l'ensemble des algorithmes de programmation dynamique pour calculer la distance d'édition sur les arbres.

Le calcul de la distance d'édition sur les arbres $\delta_{arbre}(l(F),l^\prime(F^\prime))$ se fait grâce à une distance d'édition sur les forêts δ_foret.

$\delta_{arbre}(l(F),l^\prime(F^\prime)) = min \left\{ \begin{array}{ll} c_{insertion}(l^\prime) + \delta_{\text{foret}}(l(F),F^\prime);\\ c_{suppression}(l) + \delta_{\text{foret}}(F,l^\prime(F^\prime));\\ c_{renomage}(l, l^\prime) + \delta_{\text{foret}}(F,F^\prime); \end{array} \right.$

Le calcul de la distance d'édition sur les forêts peut se faire deux manières :

• à gauche :  :$\delta_{\text{foret}}(l(F) \circ T,l^\prime(F^\prime) \circ T^\prime) = min \left\{ \begin{array}{ll} c_{\text{insertion}}(l^\prime) + \delta_{\text{foret}}(l(F) \circ T, F^\prime \circ T^\prime);\\ c_{\text{suppression}}(l) + \delta_{\text{foret}}(F \circ T, l^\prime(F^\prime) \circ T^\prime);\\ \delta_{arbre}(l(F), l^\prime(F^\prime)) + \delta_{\text{foret}}(T,T^\prime); \end{array} \right.$
• ou à droite :  :$\delta_{\text{foret}}( T \circ l(F) , T^\prime \circ l^\prime(F^\prime)) = min \left\{ \begin{array}{ll} \delta_{\text{foret}}( T \circ l(F), T^\prime \circ F^\prime) + c_{\text{insertion}}(l^\prime);\\ \delta_{\text{foret}}(T \circ F, T^\prime \circ l^\prime(F^\prime)) + c_{\text{suppression}}(l);\\ \delta_{\text{foret}}(T,T^\prime) + \delta_{arbre}(l(F), l^\prime(F^\prime)) \end{array} \right.$

Une << stratégie de décomposition >> est succession de choix entre une décomposition à gauche ou une décomposition à droite. Plus formellement si nous définissons l'ensemble des sous-forêts de F, $\mathcal{SF}(F)$ et l'ensemble des choix de décomposition {droite,gauche}, alors une stratégie S pour le calcul de $\delta_{\text{foret}}(F,F^\prime)$ est défini comme l'application $\mathcal{SF}(F) \times \mathcal{SF}(F^\prime) \longrightarrow^{S} \{\mathrm{droite} , \mathrm{gauche\}}$.

L'ensemble des algorithmes basés sur cette décomposition ont au moins dans le pire des cas une complexité temporelle en Ω(n.m.log(n).log(m)).

Les algorithmes de programmation dynamique peuvent être étudiés avec la stratégie de décomposition. Nous allons nous intéresser aux deux stratégies les plus utilisées :

• Zhang - Shasha (1989) et
• Klein (1998).

Zhang - Shasha

La stratégie de décomposition S_Zhang-Shasha utisée par Zhang et Shasha est simple car elle est toujours à gauche.

$\forall x,y \in \mathcal{SF}(F) \times \mathcal{SF}(F^\prime) \; S_{\text{Zhang-Shasha}}(x,y) = \mathrm{gauche}$

Zhang et Shasha ont montré que la complexité en temps de leur algorithme pour le calcul de la distance d’édition de deux arbres T et $T^\prime$ est en O(n⁴). D’autre part, la complexité spatiale de cet algorithme est en $O(\vert T \vert.\vert T^\prime \vert) = O(n^2)$.

Klein

Une façon d'expliquer la stratégie de décomposition S_Klein de Klein est d'utiliser la notion de chemin lourd \cite{demaine2007oda}. Le choix de la décomposition est << gauche >> si le premier nœud de f est sur le chemin lourd et << droit >> dans les autres cas.

$\forall x ,y \in \mathcal{SF}(F) \times \mathcal{SF}(F^\prime) \; S_{Klein}(x,y) = \left\{ \begin{array}{ll} \text{gauche si le premier fils droit de x est sur un chemin lourd,}\\ \text{droite sinon.} \end{array} \right.$

La complexité temporelle, dans le pire des cas, de cet algorithme est en O(n³log(n)).

Demaine

Dans \cite{demaine2007oda} les auteurs ont proposé un algorithme pour calculer une distance d'édition sur les arbres basée sur la stratégie de décomposition de Dulucq et Touzet. Cet algorithme a une complexité temporelle dans le pire des cas en O(n³) et en O(n²) pour la complexité spatiale.