Distance d'édition sur les arbres

En informatique théorique, en biochimie et aussi dans des applications, en vision par ordinateur par exemple, 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. Le distance aide à comparer par exemple la structure secondaire de l'ARN, ou des arbres phylogénétiques en biologie ou même pour guider les recommandations d'éditions aux étudiants dans des systèmes de tutorats intelligents.

Plusieurs variantes de cette notion existent, en fonction de 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.

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=r(F)$ 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é en temps du calcul de manière significative.

Stratégies de décomposition

L'exposé qui suit est repris de l'article de Dulucq et Touzet. 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')\}$

où $c_{s}$ (resp. $c_{i}$, resp. $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 $\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 suites d'arbres, notées $A\circ T$ et $A'\circ T'$, où $A$ et $A'$ sont des arbres et $T$ et $T'$ les restes des 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'$ est en $O(n^{4})$, où $n$ est la somme des tailles des deux arbres. 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))$.

Variante

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 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).

Lien externe

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