Asger Ottar Alstrup wrote: > See > > http://arxiv.org/abs/0708.4288 > > for a recent ph.d. dissertation that contains a bunch of improved > algorithms for doing tree diffs, and much more.
Amazing review, thanks. On a fast read, I've found that the variant that perfectly fits our edition/CT capabilities is 1-degree, unit cost edit distance. Unfortunately the algorithm cited for this purpose [Sel77, Didn't look at it yet, though.] seems to have time and space complexity of O(|T1||T2|) which doesn't seem very practical (and by the way, this seems roughly similar to what you get with string edit distance in which insets are symbols of an extended alphabet with cost of substitution recursively defined as edit distance, using plain Levenshtein algorithm) A/
