Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 9 down vote accepted

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):

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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