algorithme de diff efficace pour les arbres et la distance de Levenshtein

J'ai récemment lu ce résumé des problèmes liés à la différence entre les arbres et cela m'a intéressé à savoir quel est l'état de l'art pour ce problème.

Supposons également qu'entre vos opérations d'édition autorisées se trouvent le nœud d'ajout / suppression traditionnel, le contenu d'édition, vous ajoutez les opérations étendues de la sous-arborescence copier / déplacer, cela rend-il le problème (de trouver un diff optimal) plus facile ou plus difficile?

L'article suivant décrit un algorithme légèrement plus efficace que Zhang-Shasha pour calculer la distance d'édition des arbres, ainsi qu'une preuve que leur algorithme est optimal (dans une certaine large classe d'algorithmes):

• Erik Demaine, Shay Mozes, Benjamin Rossman et Oren Weimann. Un algorithme de décomposition optimale pour la distance d'édition des arbres . ACM Transactions on Algorithms , 6 (1), 2009.

Une enquête utile sur le sujet, légèrement dépassée:

Philip Bille. Une enquête sur la distance d'édition des arbres et les problèmes associés . Informatique théorique, volume 337, numéros 1 à 3, pages 217 à 239, 2005.

Un article récent sur l'une des versions du problème:

Tatsuya Akutsu et al. Algorithmes exacts pour calculer la distance d'édition d'arbre entre les arbres non ordonnés . Informatique théorique, volume 412, numéros 4 à 5, pages 352 à 364, 2011.