3 ms·
> I wonder to what extent this is driven at the level of the algorithm. Almost entirely. Most programming diff algorithms operate on a line-by-line basis. Tha
by nolemurs 10y ago
> I wonder to what extent this is driven at the level of the algorithm.
Almost entirely.
Most programming diff algorithms operate on a line-by-line basis. That means that a single character change in a line marks the whole line as changed. For prose, a single 'line' is usually a paragraph, so it's pretty obvious why they don't work well. You might check out gnu `wdiff` for what a word-by-word diff could look like. I haven't really looked into the area deeply, so I don't know what the state of the art is.
- rwmj 10y agoThis makes me wonder if anyone has implemented diff by comparing the Abstract Syntax Trees of the two code-bases. I guess it's probably easier than regular diff (assuming you've already got the ASTs from somewhere).
- nolemurs 10y agoI would think diffing trees would be necessarily more complex than diffing lines - you can think of the line-by-line description of a file as a tree with at most one child per node, so any algorithm for diffing trees should also automatically be able to diff lines. Tree diff algorithms definitely exist (I know React.js uses diffs on a virtual DOM to minimize operations), but I'm not sure what the state of the art is for those.
- Robin_Message 10y agoTree diff varies between O(N^2) and O(N^4) for simple solutions of varying complexity of matches possible, with a complex fully general algorithms coming in at O(N^2 log^2 N). Tree diff is harder because the range of operations is bigger. React.js cheats by insisting on keys for arrays so matching is much easier.
- deleted 10y ago[deleted]