2 ms·
Pretty nice writeup, congrats. Tree diffing is super fun to code! (I've used it to animate between two different shader programs...) Applying A* is a great idea
by dahart 9y ago
Pretty nice writeup, congrats. Tree diffing is super fun to code! (I've used it to animate between two different shader programs...) Applying A* is a great idea.
Not sure if this will help anyone interested, but edit operations on trees have a couple more categories besides inserts & deletes that I think makes it hard to think about as a grid the same way you can with strings. I spent a lot of time boiling down the math notation in a paper on tree edit distance to a single diagram that visualizes the edit operations: https://www.dropbox.com/s/iubwg113mm7ey6q/treeEditDist.png?dl=0 https://www.dropbox.com/s/iubwg113mm7ey6q/treeEditDist.png?d...
This is a visualization of "T. Jiang, L. Wang, and K. Zhang. Alignment of trees- an alternative to tree edit. Theoretical Computer Science, 143(1):137–148, 1995."
The interesting part is the right side, comparing a forest of children to another forest of children, which happens when a node changes type, but the subnodes are identical.
Another critical piece in tree diff is whether the nodes are ordered or unordered. If you have an AST for a math expression, a "+" operation is unordered, and you may have to diff two plus nodes twice, once with the arguments swapped - which is represented on the left in my diagram.
ASTs with 3+ argument nodes also confound visualizing the edit search space on a grid.
After having implemented tree diff using careful dynamic programming with backtracking (https://sourceforge.net/p/blot/code/HEAD/tree/trunk/lib/function/align.cpp https://sourceforge.net/p/blot/code/HEAD/tree/trunk/lib/func...) I came to the conclusion that memoizing would be a lot easier and have the same complexity. And you get A* for free-ish if you add the cost function and skip comparing two sub-trees that are further away than the best answer you've found so far.