3
$\begingroup$

I am trying to compute the edit distance between two dendrograms, one produced from hierarchical clustering, and the other manually constructed from some tree structure. In this setting, the rename operations on leaves of the tree are not allowed, and renames of other nodes (parent nodes) is free.

The tree edit distance for rooted ordered trees has been well studied, but this problem should be considered for the case where input trees are unordered. For the general case, it is known that tree edit distance problem for unordered trees is NP-hard. However, I don't seem to find an algorithm to find the unordered tree edit distance.

Any pointers or insights into this problem is highly appreciated.

$\endgroup$

2 Answers 2

2
$\begingroup$

A student of ours recently looked into a dynamic programming A* algorithm for computing the unordered tree edit distance (although we adapted it for the ordered tree edit distance). I was not directly involved into this project, but as far as I know, this algorithm explores a search tree that represents all possible edit distances and stops exploring unpromising paths. This way it returns the tree edit distance in the end.

The student also implemented this A* algorithm, so it is not just a theoretical one.

Here's the link: http://ieeexplore.ieee.org/document/6630333/

Hope this helps!

$\endgroup$
0
$\begingroup$

This is an old question, but you should be using Zhang-Shasha edit distance.

The default implementation is zss: https://pypi.org/project/zss/1.1.4/

Here is a simple paper going over it. https://arxiv.org/abs/1805.06869#:~:text=Almost%2030%20years%20ago%2C%20Zhang,transform%20one%20tree%20into%20another.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.