The Myers diff algorithm: part 1

Good to see this interesting and very fundamental topic getting attention, and looking forward to the next post, where hopefully the algorithm's cleverness will be explored. >It does this by being greedy, that is trying to consume as many lines that are the same before making a change (therefore avoiding the “wrong end” problem), and also by preferring deletions over insertions when given a choice, so that deletions appear first. Not really. The algorithm guarantees to find an alignment/diff/edit script…

There's also patience diff[1], which does a better job in some situations[2] (you might not normally see these inferior diffs because the diffs are massaged after the LCS algorithm). [1]: http://alfedenzo.livejournal.com/170301.html [2]: http://bramcohen.livejournal.com/73318.html

By the way, git also comes with other diff algorithms which may give cleaner diffs than the default one https://gist.github.com/roryokane/6f9061d3a60c1ba41237 Those alternative algorithms can be requested with command line flags like "git diff --histogram" or "git diff --patience". The default algorithm can also be changed via the git config file.