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  est composé d'un nœud racine , et d'une forêt  qui est une suite d'arbres. La distance d'édition de deux arbres  et  est le nombre minimum d'insertions, suppressions ou renommages de nœuds, noté , nécessaires pour transformer  en . 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  et  deux arbres non vides. Le calcul de  se fait comme suit :

 

où  (resp. , resp. ) 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 . 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  et , où  et  sont des arbres et  et  les restes des suites. En posant  et , les stratégies sont :
   
 à gauche : 
    
 à droite :      
    

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 . 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  et  est en , où  est la somme des tailles des deux arbres. D’autre part, la complexité en place de cet algorithme est en .

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 .

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  et en  pour la complexité en espace.

Notes et références

Bibliographie 
 .
 .
 .
 .

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

Arbre (structure de données)