Distance d'édition sur les arbres

En informatique théorique, en biochimie et aussi dans des applications en vision par ordinateur la distance d'édition d'arbres (en anglais tree edit distance est une mesure qui évalue, en termes de nombre de transformations élémentaires, le nombre d'opérations nécessaires et leur coût pour passer d'un arbre à un autre. C'est une notion qui étend, aux arbres, la distance d'édition (ou distance de Levenshtein) entre chaînes de caractères.

Plusieurs variantes de cette notion existent, en fonction e la nature des arbres que l'on considère. En toute généralité, ce sont des arbres abstraits ; de façon plus restrictive, on considère des arbres plans, c'est-à-dire tels que les sommets voisins d'un sommet sont ordonnés. Plus particulier encore est le cas des arbres plans enracinés : un tel arbre est composé d'une racine et d'une suite ordonnée de sous-arbres. C'est ce cas qui est détaillé ci-dessous. Un exposé de synthèse est donné par un article de Benjamin Paaßen sur arxiv

Les opérations élémentaires de transformations d'arbres sont, comme pour les chaînes de caractères, la suppression, l'insertion et le renommage, appliqués à un nœud d'un arbre.

Notations

On considère les arbres comme des structures récursives : un arbre $A$ est composé d'un nœud racine $r$, et d'une forêt $F$ qui est une suite d'arbres. La distance d'édition de deux arbres $A$ et $A'$ est le nombre minimum d'insertions, suppressions ou renommages de nœuds, noté $\delta (A,A')$, nécessaires pour transformer $A$ en $A'$.

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

Soient $A=r(F)$ et $A'=r'(F')$ deux arbres non vides. Le calcul de $\delta (A,A')$ se fait comme suit :

$\delta (A,A')=\min\{(c_{i}(r')+\delta (A,F'),(c_{s}(r)+\delta (F,A'),(c_{r}(r,r')+\delta (F,F')\}$

Le coût du calcul de la distance d'édition sur les arbres se fait grâce à une distance d'édition sur les forêts, toujours notée $\delta$. Le calcul de la distance d'édition sur les forêts peut se faire deux manières, en privilégiant la gauche ou la droite : le calcul s'applique à deux suite d'arbres, notées $A\circ T$ et $A'\circ T$, où $A$ et $A'$ sont des arbres et $T$ et $T'$ les restes de suites. En posant $A=r(F)$ et $A'=r(F')$, les stratégies sont :

• à gauche :

$\delta (A\circ T,A'\circ T')=\min \left\{{\begin{array}{ll}c_{i}(r')+\delta (A\circ T,F'\circ T');\\c_{s}(r)+\delta (F\circ T,A'\circ T');\\\delta (A,A')+\delta (T,T');\end{array}}\right.$

• à droite :

$\delta (T\circ A,T'\circ A')=\min \left\{{\begin{array}{ll}\delta (T\circ A,T'\circ F')+c_{i}(r');\\\delta (T\circ F,T'\circ A')+c_{s}(r);\\\delta (T,T')+\delta (A,A')\end{array}}\right.$

Une stratégie de décomposition est une succession de choix entre une décomposition à gauche ou une décomposition à droite. Chaque algorithme basé sur une décomposition a dans le pire des cas une complexité en temps au moins en $\Omega (n\log(n)m\log(m))$. Des algorithmes de programmation dynamique peuvent être étudiés avec la stratégie de décomposition. Deux stratégies parmi les plus utilisées sont celles de Zhang-Shasha (1989) et celle de Klein (1998) :

Zhang-Shasha

La stratégie de décomposition de {Zhang-Shasha}} consiste à utiliser systématiquement la décomposition à 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 $A$ et $A'$ de taille $n$ est en $O(n^{4})$.

D’autre part, la complexité en place de cet algorithme est en $O(n^{2})$.

Klein

La stratégie de décomposition de Klein utilise une notion de chemin lourd. Le choix de la décomposition est « à gauche » si le premier fils droit de A est sur le chemin lourd et « à droite » dans les autres cas.

La complexité en temps de cet algorithme est en $O(n^{3}\log(n))$.

Développement

Un algorithme pour calculer une distance d'édition sur les arbres basée sur la stratégie de décomposition de Dulucq et Touzet a été proposé par Demaine et ses coauteurs: Cet algorithme a une complexité en temps dans le pire des cas en $O(n^{3})$ et en $O(n^{2})$ pour la complexité en espace.

Bibliographie

• Benjamin Paaßen, « Revisiting the tree edit distance and its backtracing: A tutorial », Supplementary material for the ICML 2018 paper: Tree Edit Distance Learning via Adaptive Symbol Embeddings,‎ 26 octobre 2018 (arXiv https://arxiv.org/abs/1805.06869).
• Serge Dulucq et Hélène Touzet, « Tree edit diatance analysis », dans Combinatorial Pattern Matching CPM 2003, Springer, coll. « Lecture Notes in Computer Science 2676 », 2003 (ISSN 0302-9743, DOI 10.1007/3-540-44888-8_7, présentation en ligne), p. 83-95.
• K. Zhang et D. Shasha, « Simple fast algorithms for the editing distance between trees and related problems », SIAM Journal of Computing, vol. 18, n^o 4,‎ 1989, p. 1245–1262.
• Philip N. Klein, « Computing the edit-distance between unrooted ordered trees », Proceedings of 6th European Symposium on Algorithms,,‎ 1998, p. 91-102 (lire en ligne, consulté le 13 janvier 2019).