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