Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I've recently read this summary 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?
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):
A useful survey on the topic, slightly out of date:
Philip Bille. A survey on tree edit distance and related problems. 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. Theoretical Computer Science, Volume 412, Issues 4–5, Pages 352–364, 2011.
