<p>A useful survey on the topic, slightly out of date:</p>

<p>Philip Bille. <a href="http://dx.doi.org/10.1016/j.tcs.2004.12.030">A survey on tree edit distance and related problems</a>. Theoretical Computer Science, Volume 337, Issues 1–3, Pages 217–239, 2005.</p>

<p>A recent paper on one of the versions of the problem:</p>

<p>Tatsuya Akutsu et al. <a href="http://dx.doi.org/10.1016/j.tcs.2010.10.002">Exact algorithms for computing the tree edit distance between unordered trees</a>. Theoretical Computer Science, Volume 412, Issues 4–5, Pages 352–364, 2011.</p>

CC BY-SA 3.0
2012-02-16T21:27:17.453Z
2012-02-16T21:27:17.453Z
Alexander Tiskin
<p>The following paper describes a slightly more efficient algorithm than Zhang-Shasha for computing tree edit distance, along with a proof that their algorithm is optimal (within a certain broad class of algorithms):</p>

<ul>
<li>Erik Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann.  <a href="http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf">An Optimal Decomposition Algorithm for Tree Edit Distance</a>.  <em>ACM Transactions on Algorithms</em>, 6(1), 2009.</li>
</ul>

CC BY-SA 3.0
2012-02-14T20:33:04.953Z
2012-02-14T20:33:04.953Z
Jeffε
<p>I've recently read <a href="http://useless-factor.blogspot.com/2008/01/matching-diffing-and-merging-xml.html">this summary</a> of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem. </p>

<p>Also, suppose that between your allowed edit operations are the traditional add/delete node, edit content you add the extended operations of copy/move subtree, does this makes the problem (of finding an optimal diff) easier or harder?</p>

<ds.algorithms><tree><edit-distance>
efficient diff algorithm for trees and Levenshtein distance
lurscher
# efficient diff algorithm for trees and Levenshtein distance

(Asked by: username_0 on 2012-02-14)

I've recently read [this summary](http://useless-factor.blogspot.com/2008/01/matching-diffing-and-merging-xml.html) of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem.

Also, suppose that between your allowed edit operations are the traditional add/delete node, edit content you add the extended operations of copy/move subtree, does this makes the problem (of finding an optimal diff) easier or harder?

**Tags:** ds.algorithms, tree, edit-distance


---

## 2 answers

### Answer by username_2 on 2012-02-14. Score: 16 | Accepted answer

The following paper describes a slightly more efficient algorithm than Zhang-Shasha for computing tree edit distance, along with a proof that their algorithm is optimal (within a certain broad class of algorithms):

* Erik Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann. [An Optimal Decomposition Algorithm for Tree Edit Distance](http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf). *ACM Transactions on Algorithms*, 6(1), 2009.


---

### Answer by username_1 on 2012-02-16. Score: 7

A useful survey on the topic, slightly out of date:

Philip Bille. [A survey on tree edit distance and related problems](http://dx.doi.org/10.1016/j.tcs.2004.12.030). Theoretical Computer Science, Volume 337, Issues 1–3, Pages 217–239, 2005.

A recent paper on one of the versions of the problem:

Tatsuya Akutsu et al. [Exact algorithms for computing the tree edit distance between unordered trees](http://dx.doi.org/10.1016/j.tcs.2010.10.002). Theoretical Computer Science, Volume 412, Issues 4–5, Pages 352–364, 2011.


---

