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

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

<p>Here's the link: <a href="http://ieeexplore.ieee.org/document/6630333/" rel="nofollow noreferrer">http://ieeexplore.ieee.org/document/6630333/</a></p>

<p>Hope this helps!</p>

CC BY-SA 3.0
2017-08-28T07:55:15.873Z
2017-08-28T07:55:15.873Z
SX.
<p>This is an old question, but you should be using Zhang-Shasha edit distance.</p>
<p>The default implementation is zss: <a href="https://pypi.org/project/zss/1.1.4/" rel="nofollow noreferrer">https://pypi.org/project/zss/1.1.4/</a></p>
<p>Here is a simple paper going over it.
<a href="https://arxiv.org/abs/1805.06869#:%7E:text=Almost%2030%20years%20ago%2C%20Zhang,transform%20one%20tree%20into%20another" rel="nofollow noreferrer">https://arxiv.org/abs/1805.06869#:~:text=Almost%2030%20years%20ago%2C%20Zhang,transform%20one%20tree%20into%20another</a>.</p>

CC BY-SA 4.0
2020-09-10T19:55:46.900Z
2020-09-10T19:55:46.900Z
whenitrains
<p>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.</p>

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

<p>Any pointers or insights into this problem is highly appreciated.</p>

<graph-algorithms><tree><edit-distance>
Algorithm for computing unordered tree edit distance
Amir
# Algorithm for computing unordered tree edit distance

(Asked by: username_0 on 2017-08-25)

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.

**Tags:** graph-algorithms, tree, edit-distance

---

## 2 answers

### Answer by username_1 on 2017-08-28. Score: 2

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 by username_2 on 2020-09-10. Score: 0

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](https://arxiv.org/abs/1805.06869#:%7E:text=Almost%2030%20years%20ago%2C%20Zhang,transform%20one%20tree%20into%20another).


---

