Détecter des différences entre les structures en arbre
Ce n'est plus un CS question, mais une question intéressante :
Disons que nous avons 2 structures en arbre avec plus ou moins les mêmes nœuds réorganisé. Comment voulez-vous trouver
- tout
- dans un certain sens, minimale
la séquence des opérations
MOVE(A, B)
- déplace Un nœud sous le nœud B (avec l'ensemble de la sous-arborescence)INSERT(N, B)
- insère un nouveau nœud N sous le nœud BDELETE (A)
- supprime le nœud (avec l'ensemble de la sous-arborescence)
qui transforme un arbre à l'autre.
Il peut évidemment y avoir des cas où une telle transformation n'est pas possible, trivial être root avec Un enfant de B la racine de B avec Un enfant, etc.). Dans de tels cas, l'algorithme serait tout simplement de livrer un résultat "pas possible".
Encore plus spectaculaire version est une généralisation pour les réseaux, c'est à dire lorsque nous supposons qu'un nœud peut se produire plusieurs fois dans l'arbre (effectivement le fait d'avoir plusieurs "parents"), tandis que les cycles sont interdits.
Avertissement : Ceci est pas des devoirs à faire, en fait il s'agit d'un réel problème d'entreprise et je l'ai trouvé assez intéressant demandais si quelqu'un connais une solution.
MOVE(A,B)
semblent être les mêmes queINSERT(A,B)
siA
n'a pas d'enfants. Ce qui se passe pour les enfants deA
si l'on neINSERT(A,B)
? (vont-ils être rattachés àA
parent ?)- la différence est que, INSÉRER signifie vraiment d'un nouveau nœud, qui n'était pas dans l'arbre (donc n'ayant pas d'enfant, du moins pas dans l'état d'origine où il n'était même pas présent). Se DÉPLACER sur l'autre main est vraiment un mouvement, c'est à dire déplacer le nœud y compris ses enfants
- Cela sonne comme vous avez besoin de détecter graphique-isomorphisme. La partie sur la transformation me rappelle de la Levenshtein, qui peut parfaitement être résolu en O(n*m) à l'aide de la programmation dynamique. Peut-être que ces pointeurs vous aider.
- Avez-vous jamais trouver une solution? En regardant l'article de wikipédia et des liens je ne vois pas un algorithme de n'importe où. Je voudrais faire cela en javascript où je sais déjà à l'origine des opérations qui ont fait les deux arbres différents, mais aurait comme pour produire une option diff: par exemple, si une partie de l'arbre a été taillés et puis re-greffé à la même place, elle permettrait d'optimiser à aucun changement.
- avez-vous trouvé quelque chose d'utile? J'ai regarder pour la même alhoritm de changements de réduction dans l'arbre.
- Des sons proches de ce qu'est un OS/outil 3ème partie a à faire pour comparer des dossiers de fichiers.
Vous devez vous connecter pour publier un commentaire.
Il n'est pas seulement un article de Wikipédia sur le graphique isomorphisme (comme Space_C0wb0y points) mais aussi un article dédié sur le graphique isomorphisme problème. Il a une section
Solved special cases
pour qui polynôme de temps des solutions sont connues. Des arbres est l'un d'entre eux et il cite les deux références suivantes:Vous n'étiez pas clair, si vous étiez la comparaison de l'arbre de syntaxe abstraite pour le code source, les documents XML interprétées comme des arbres, ou d'un autre type d'arbre.
Il y a un certain nombre de textes portant sur la comparaison de l'arbre de syntaxe et de calcul des distances minimales par divers moyens. Les idées doivent être pertinentes.
Un papier de bonne qualité est Changement De Distillation, qui tente de comparer le code source pour les deux l'arbre de syntaxe abstraite et de signaler une différence minime. Le livre parle d'une méthode spécifique, et également breifly mentionne (et fournit des références) à une variété de techniques similaires.
Quelques-uns de ces algorithmes sont effectivement réalisés dans les outils disponibles pour la comparaison du texte source. Notre Smart Differencer est l'un d'entre eux.
Bien que cette question est ancienne, je vais ajouter un couple de plus les références et les algorithmes ci-dessous:
Des Documents XML
En outre, il existe des bibliothèques et des cadres sur GitHub (en javascript) qui mettent en œuvre de comparaison de structures arborescentes par exemple des applications gérant des données JSON ou XML Arbres (e.g pour le côté client MVC/MVVM):
Dans le cas de gens trouvent cette question et besoin de quelque chose de mis en œuvre pour Node.js ou le navigateur, je suis en fournissant un lien et un exemple de code pour une application que j'ai écrit que vous pouvez trouver sur github ici: ( https://github.com/hoonto/jqgram.git ), fondés sur le PyGram code Python (https://github.com/Sycondaman/PyGram).
C'est un arbre d'une distance d'édition rapprochement algorithme, mais il est beaucoup, beaucoup plus rapide que d'essayer de trouver la véritable distance d'édition. Le rapprochement effectue en O(n log n) en temps et O(n) l'espace alors que la vraie distance d'édition est souvent O(n^3) ou O(n^2) à l'aide d'algorithmes connus pour la vraie distance d'édition. Voir le document académique à partir de laquelle le PQ-Gramme de l'algorithme, il vient: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)
Donc à l'aide d'jqgram:
Exemple:
Et qui vous donne un nombre entre 0 et 1. Le plus proche de zéro, plus étroitement liés les deux arbres à jqgram. Une solution pourrait être d'utiliser jqgram à l'étroit dans plusieurs étroitement liés arbres, parmi de nombreux arbres, compte tenu de sa vitesse, puis utiliser la vraie distance d'édition sur les quelques arbres restants que vous avez besoin de prendre un coup d'inspection, et pour que vous puissiez trouver python implémentations de référence ou le port de la Zhang & Shasha algorithme par exemple.
Noter que le lfn et cfn paramètres spécifient la façon dont chaque arbre doit déterminer l'étiquette du nœud noms et les enfants de tableau pour chaque racine de l'arbre de façon indépendante, de sorte que vous pouvez faire des choses funky comme comparer un objet à un navigateur DOM par exemple. Tout ce que vous devez faire est de fournir à ces fonctions avec chaque racine et jqgram fera le reste, en appelant votre lfn et cfn fonctions fournies pour construire les arbres. Donc, dans ce sens, il est (à mon avis en tout cas) beaucoup plus facile à utiliser que PyGram. De Plus, son Javascript, afin de l'utiliser côté client ou côté serveur!
AUSSI, pour répondre à l'égard de cycle de détection, découvrez la méthode clone à l'intérieur de jqgram, il y a le cycle de détection de là, mais le crédit pour cela va à l'auteur de nœud-clone à partir de laquelle cette pièce a été légèrement modifiée, et inclus.