Distance d'édition sur les arbres

On considère les arbres comme des structures récursives : un arbre ${\displaystyle A=r(F)}$ est composé d'un nœud racine ${\displaystyle r}$, et d'une forêt ${\displaystyle F}$ qui est une suite d'arbres. La distance d'édition de deux arbres ${\displaystyle A}$ et ${\displaystyle A'}$ est le nombre minimum d'insertions, suppressions ou renommages de nœuds, noté ${\displaystyle \delta (A,A')}$, nécessaires pour transformer ${\displaystyle A}$ en ${\displaystyle 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é en temps du calcul de manière significative.

L'exposé qui suit est repris de l'article de Dulucq et Touzet[2]. Soient ${\displaystyle A=r(F)}$ et ${\displaystyle A'=r'(F')}$ deux arbres non vides. Le calcul de ${\displaystyle \delta (A,A')}$ se fait comme suit :

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

où ${\displaystyle c_{s}}$ (resp. ${\displaystyle c_{i}}$, resp. ${\displaystyle c_{r}}$) désigne le coût associé à la suppression (resp. insertion, resp. renommage) d'un nœud.

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 ${\displaystyle \delta }$. Le calcul de la distance d'édition sur les forêts peut se faire de deux manières, en privilégiant la gauche ou la droite : le calcul s'applique à deux suite d'arbres, notées ${\displaystyle A\circ T}$ et ${\displaystyle A'\circ T}$, où ${\displaystyle A}$ et ${\displaystyle A'}$ sont des arbres et ${\displaystyle T}$ et ${\displaystyle T'}$ les restes des suites. En posant ${\displaystyle A=r(F)}$ et ${\displaystyle A'=r(F')}$, les stratégies sont :

• à gauche :

${\displaystyle \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 :

${\displaystyle \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 ${\displaystyle \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) :

• 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 1805.06869).
• Serge Dulucq et Hélène Touzet, « Tree edit distance 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).

• « Compare your trees with ease » sur l'université de Salzbourg