I believe this article may have produced the same algorithm as [1] and [2] but applied to tree diffs [3] instead of string diffs. In particular, Myers' algorit

I believe this article may have produced the same algorithm as [1] and [2] but applied to tree diffs [3] instead of string diffs. In particular, Myers' algorithm [2] is generally considered the best general-purpose string diff today, and I bet he was doing A* search without realizing it. I would be very curious to find out if you could describe his algorithm as an A* search. A* search brought his algorithm's runtime down from O(N^2) to O(N•diffsize). Tree diffs are often O(N^3) or O(N^2•log(N)), and this A* search seems to have brought that down to O(N•log(N)•diffsize). The A* search seems to reduce the extra O(N or N^2) to O(diffsize)! I'm excited by the general use of A* to prune the dynamic programming search space. We might be onto a more general understanding of diffing. [1] https://www.google.com/patents/US7313555 https://www.google.com/patents/US7313555 [2] http://www.xmailserver.org/diff2.pdf http://www.xmailserver.org/diff2.pdf [3] http://www.sciencedirect.com/science/article/pii/S0304397505000174 http://www.sciencedirect.com/science/article/pii/S0304397505...