Algorithm for computing unordered tree edit distance

Question

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.

Answer 1

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!

Answer 2

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.