Distance d'édition sur les arbres

Distance d'édition sur les arbres

Soit l et l^\prime des nœuds racines, F et F^\prime des forêts (un ensemble d'arbre) ordonnées. On définit l(F) et l^\prime(F^\prime) comme étant des arbres de taille n et m, avec comme nœuds racines respectifs l et l^\prime. Les fils directs de l et l^\prime sont les nœuds racines des forêts respectives F et F^\prime. La distance d'édition \delta_{arbre}(l(F),l^\prime(F^\prime)) est le coût minimum d'opérations élémentaires consistant en la suppression, l'insertion et le renommage d'un nœud, pour transformer l(F) en l^\prime(F^\prime). La première version de cette distance fut proposée par Tai dont la complexité en temps et en espace pour le pire des cas est en O(n6).

De plus l'opérateur \circ permet de concaténer un arbre à une forêt. 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é temporelle du calcul de manière significative.

Sommaire

Stratégie de décomposition

Dans l'article \cite{dulucq2003ate} les auteurs ont proposé un cadre d'étude sur l'ensemble des algorithmes de programmation dynamique pour calculer la distance d'édition sur les arbres.

Le calcul de la distance d'édition sur les arbres \delta_{arbre}(l(F),l^\prime(F^\prime)) se fait grâce à une distance d'édition sur les forêts δforet.

\delta_{arbre}(l(F),l^\prime(F^\prime)) = min \left\{ \begin{array}{ll} c_{insertion}(l^\prime) + \delta_{\text{foret}}(l(F),F^\prime);\\ c_{suppression}(l) + \delta_{\text{foret}}(F,l^\prime(F^\prime));\\ c_{renomage}(l, l^\prime) + \delta_{\text{foret}}(F,F^\prime); \end{array} \right.

Le calcul de la distance d'édition sur les forêts peut se faire deux manières :

  • à gauche :  : \delta_{\text{foret}}(l(F) \circ T,l^\prime(F^\prime) \circ T^\prime) = min \left\{ \begin{array}{ll} c_{\text{insertion}}(l^\prime) + \delta_{\text{foret}}(l(F) \circ T, F^\prime \circ T^\prime);\\ c_{\text{suppression}}(l) + \delta_{\text{foret}}(F \circ T, l^\prime(F^\prime) \circ T^\prime);\\ \delta_{arbre}(l(F), l^\prime(F^\prime)) + \delta_{\text{foret}}(T,T^\prime); \end{array} \right.
  • ou à droite :  : \delta_{\text{foret}}( T \circ l(F) , T^\prime \circ l^\prime(F^\prime)) = min \left\{ \begin{array}{ll} \delta_{\text{foret}}( T \circ l(F), T^\prime \circ F^\prime) + c_{\text{insertion}}(l^\prime);\\ \delta_{\text{foret}}(T \circ F, T^\prime \circ l^\prime(F^\prime)) + c_{\text{suppression}}(l);\\ \delta_{\text{foret}}(T,T^\prime) + \delta_{arbre}(l(F), l^\prime(F^\prime)) \end{array} \right.

Une << stratégie de décomposition >> est succession de choix entre une décomposition à gauche ou une décomposition à droite. Plus formellement si nous définissons l'ensemble des sous-forêts de F, \mathcal{SF}(F) et l'ensemble des choix de décomposition {droite,gauche}, alors une stratégie S pour le calcul de \delta_{\text{foret}}(F,F^\prime) est défini comme l'application \mathcal{SF}(F) \times \mathcal{SF}(F^\prime) \longrightarrow^{S} \{\mathrm{droite} , \mathrm{gauche\}} .

L'ensemble des algorithmes basés sur cette décomposition ont au moins dans le pire des cas une complexité temporelle en Ω(n.m.log(n).log(m)).

Les algorithmes de programmation dynamique peuvent être étudiés avec la stratégie de décomposition. Nous allons nous intéresser aux deux stratégies les plus utilisées :

  • Zhang - Shasha (1989) et
  • Klein (1998).

Zhang - Shasha

La stratégie de décomposition SZhang-Shasha utisée par Zhang et Shasha est simple car elle est toujours à gauche.

\forall x,y \in \mathcal{SF}(F) \times \mathcal{SF}(F^\prime) \; S_{\text{Zhang-Shasha}}(x,y) = \mathrm{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 T et T^\prime est en O(n4). D’autre part, la complexité spatiale de cet algorithme est en O(\vert T \vert.\vert T^\prime \vert) = O(n^2).

Klein

Une façon d'expliquer la stratégie de décomposition SKlein de Klein est d'utiliser la notion de chemin lourd \cite{demaine2007oda}. Le choix de la décomposition est << gauche >> si le premier nœud de f est sur le chemin lourd et << droit >> dans les autres cas.

\forall x ,y \in \mathcal{SF}(F) \times \mathcal{SF}(F^\prime) \; S_{Klein}(x,y) = \left\{ \begin{array}{ll} \text{gauche si le premier fils droit de x est sur un chemin lourd,}\\ \text{droite sinon.} \end{array} \right.

La complexité temporelle, dans le pire des cas, de cet algorithme est en O(n3log(n)).

Demaine

Dans \cite{demaine2007oda} les auteurs ont proposé un algorithme pour calculer une distance d'édition sur les arbres basée sur la stratégie de décomposition de Dulucq et Touzet. Cet algorithme a une complexité temporelle dans le pire des cas en O(n3) et en O(n2) pour la complexité spatiale.



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Distance d'édition sur les arbres de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Distance De Levenshtein — La distance de Levenshtein mesure la similarité entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre. Son nom provient de Vladimir… …   Wikipédia en Français

  • Distance de levenshtein — La distance de Levenshtein mesure la similarité entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre. Son nom provient de Vladimir… …   Wikipédia en Français

  • Distance de Levenshtein — La distance de Levenshtein mesure la similarité entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre. Son nom provient de Vladimir… …   Wikipédia en Français

  • Les Bronte — Les Brontë Anne, Emily et Charlotte Brontë, par leur frère Branwell (vers 1834). Lui même s était représenté, au milieu de ses sœurs, avant de s effacer, pour ne pas surcharger le tableau. Les Brontë sont une famille littéraire anglaise du… …   Wikipédia en Français

  • Les Brontë — Anne, Emily et Charlotte Brontë, par leur frère Branwell (vers 1834). Lui même s était représenté, au milieu de ses sœurs, avant de s effacer, pour ne pas surcharger le tableau. Les Brontë sont une famille littéraire anglaise du XIXe siècle …   Wikipédia en Français

  • Les bienveillantes — Auteur Jonathan Littell Genre Roman Pays d origine  France Éditeur Gallimard Collection Folio …   Wikipédia en Français

  • Les cinquante-trois stations de la route du Tōkaidō — Cinquante trois Stations du Tōkaidō Portrait de Hiroshige, le crâne rasé, à cinquante ans passés[N 1], par Kunisada. Les Cinquante trois Stations du …   Wikipédia en Français

  • Les Cinquante-trois Stations du Tōkaidō — Portrait de Hiroshige, le crâne rasé, à cinquante ans passés[N 1], par Kunisada. Les Cinquante trois Stations du Tōkaidō ( …   Wikipédia en Français

  • Les ramparts d'avignon — Avignon 43°57′00″N 4°49′01″E / 43.95, 4.81694 …   Wikipédia en Français

  • Les Bienveillantes — Pour les articles homonymes, voir Les Bienveillantes (homonymie). Les Bienveillantes Auteur Jonathan Littell Genre Roman Pays d origine …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”