8 ms·

The Myers diff algorithm: part 1

148 points by arunc 10y ago

jasode 10y ago
Fyi... a related wiki page about LCS (Longest Common Subsequence) with more diagrams and pseudocode: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem https://en.wikipedia.org/wiki/Longest_common_subsequence_pro...
amelius 10y ago
Any in-depth article on string diffs should mention alignment algorithms such as Smith Waterman [1] [1] https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...
- dekhn 10y ago
  All string diff algorithms in alignment derive from previous innovations on raw strings. SW is a derivative of NW, which itself (although the paper does not admit it) derives from the work done on edit distance in the mid 60s). It's actually interesting that this algorithm was rediscovered independently multiple times within a short time frame. Also, the "Myers" in the article has worked a bit with sequence alignment. He helped design the BLAST algorithm (with Altschul) as well as suffix arrays (with Manber), the algorithms that reassembled the human genome for Celera, and finally, dropped the ultimate bomb: https://academic.oup.com/bioinformatics/article/21/suppl_2/ii79/227189/The-fragment-assembly-string-graph https://academic.oup.com/bioinformatics/article/21/suppl_2/i...
  - Animats 10y ago
    All string diff algorithms in alignment derive from previous innovations on raw strings. For some applications, it's more useful to just take the hash of each line and compute line diffs from an array of hashes. Diff algorithms which ignore whitespace changes sometimes do this. Few algorithms recognize text re-ordering. This is a problem with Wikipedia diffs, where rearranging text is commonplace. Displaying the changes might require big arrows, but there's no problem with that today.
    - WalterGR 10y ago
      Few algorithms recognize text re-ordering. WinMerge[1] does. Unfortunately it's no longer under development. (I've been looking for an equally-capable tool for Macs but have found nothing...) Do you know which algorithms recognize reordering? [1] http://winmerge.org/ http://winmerge.org/
zamalek 10y ago
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 http://alfedenzo.livejournal.com/170301.html [2]: http://bramcohen.livejournal.com/73318.html http://bramcohen.livejournal.com/73318.html
shaftway 10y ago
I don't understand why there isn't a better code-aware diff tool available, like an AST diff. When I split a method up, or add an if statement, can't we detect that most of the code didn't change, it was just moved around? This is the biggest frustration to me when doing and sending code reviews, having to explain "I know it's a 5 thousand line change, but I really didn't change any of the logic, I just moved the class into a subclass which caused an indentation change."
- mmun 10y ago
  I get your point, but for the indentation case in particular you can use `git diff -w` or append `?w=1` to a github PR url.
  - shaftway 10y ago
    Except in Python where indentation changes are meaningful. def coalesce(*args): while args: next = args.pop() if next is not None: return next return None def coalesce(*args): while args: next = args.pop() if next is not None: return next return None
- lobster_johnson 10y ago
  I remember the incredibly elegant AST-based diffing in Eclipse (which I haven't used in about 10 years; I can only assume it's still fantastic), which showed you an outline of which classes, methods etc. have changed. AST-based diff naturally requires a parser for every language, and for some languages like C and C++ you need to bake preprocessor stuff (macros, ifdefs, includes etc.) into the node tree. But it's doable.
- tikhonj 10y ago
  I'm working on one on-and-off (more off than on lately) that compares parse trees to group related changes together and tries to do some high-level analysis (like finding moves). I finally got my core algorithm working reasonably well last year, but then started a new job and haven't had the energy to work on it more since—I'm hoping to get back to it in a month or two. Anyway, if you're curious, I have the code and a (very) rough write-up up on GitLab[1]. Keep in mind that it's very preliminary, and that my approach is by no means the only way to do this! There's been a fair amount of research on this in the software engineering community (ie SIGSOFT). I've looked through some of the existing papers, and there have been a range of algorithms and tools with different metrics, different levels of language-awareness and different capabilities. There's a lot to explore if you're curious. [1]: http://gitlab.com/tikhon/cow http://gitlab.com/tikhon/cow (The name is also a work in progress!)
flippant 10y ago
This is part of the Elixir standard library https://hexdocs.pm/elixir/List.html#myers_difference/2 https://hexdocs.pm/elixir/List.html#myers_difference/2 https://github.com/elixir-lang/elixir/blob/master/lib/elixir/lib/list.ex#L772 https://github.com/elixir-lang/elixir/blob/master/lib/elixir...
teabee89 10y ago
I strongly encourage people to read about the lesser-known Tichy diff algorithm too: https://bryanpendleton.blogspot.com/2010/04/more-study-of-diff-walter-tichys-papers.html https://bryanpendleton.blogspot.com/2010/04/more-study-of-di...
nachocab83 10y ago
Does anyone know a way to modify this algorithm to list out all the possible solutions? I asked something similar in stack overflow: http://softwareengineering.stackexchange.com/questions/342985/how-can-i-modify-the-myers-diff-algorithm-to-choose-between-different-answers http://softwareengineering.stackexchange.com/questions/34298...

148 points by arunc 10y ago

Fyi... a related wiki page about LCS (Longest Common Subsequence) with more diagrams and pseudocode: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem https://en.wikipedia.org/wiki/Longest_common_subsequence_pro...

amelius 10y ago

Any in-depth article on string diffs should mention alignment algorithms such as Smith Waterman [1] [1] https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

dekhn 10y ago
All string diff algorithms in alignment derive from previous innovations on raw strings. SW is a derivative of NW, which itself (although the paper does not admit it) derives from the work done on edit distance in the mid 60s). It's actually interesting that this algorithm was rediscovered independently multiple times within a short time frame. Also, the "Myers" in the article has worked a bit with sequence alignment. He helped design the BLAST algorithm (with Altschul) as well as suffix arrays (with Manber), the algorithms that reassembled the human genome for Celera, and finally, dropped the ultimate bomb: https://academic.oup.com/bioinformatics/article/21/suppl_2/ii79/227189/The-fragment-assembly-string-graph https://academic.oup.com/bioinformatics/article/21/suppl_2/i...
- Animats 10y ago
  All string diff algorithms in alignment derive from previous innovations on raw strings. For some applications, it's more useful to just take the hash of each line and compute line diffs from an array of hashes. Diff algorithms which ignore whitespace changes sometimes do this. Few algorithms recognize text re-ordering. This is a problem with Wikipedia diffs, where rearranging text is commonplace. Displaying the changes might require big arrows, but there's no problem with that today.
  - WalterGR 10y ago
    Few algorithms recognize text re-ordering. WinMerge[1] does. Unfortunately it's no longer under development. (I've been looking for an equally-capable tool for Macs but have found nothing...) Do you know which algorithms recognize reordering? [1] http://winmerge.org/ http://winmerge.org/

zamalek 10y ago

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 http://alfedenzo.livejournal.com/170301.html [2]: http://bramcohen.livejournal.com/73318.html http://bramcohen.livejournal.com/73318.html

shaftway 10y ago

I don't understand why there isn't a better code-aware diff tool available, like an AST diff. When I split a method up, or add an if statement, can't we detect that most of the code didn't change, it was just moved around? This is the biggest frustration to me when doing and sending code reviews, having to explain "I know it's a 5 thousand line change, but I really didn't change any of the logic, I just moved the class into a subclass which caused an indentation change."

mmun 10y ago
I get your point, but for the indentation case in particular you can use `git diff -w` or append `?w=1` to a github PR url.
- shaftway 10y ago
  Except in Python where indentation changes are meaningful. def coalesce(*args): while args: next = args.pop() if next is not None: return next return None def coalesce(*args): while args: next = args.pop() if next is not None: return next return None
lobster_johnson 10y ago
I remember the incredibly elegant AST-based diffing in Eclipse (which I haven't used in about 10 years; I can only assume it's still fantastic), which showed you an outline of which classes, methods etc. have changed. AST-based diff naturally requires a parser for every language, and for some languages like C and C++ you need to bake preprocessor stuff (macros, ifdefs, includes etc.) into the node tree. But it's doable.
tikhonj 10y ago
I'm working on one on-and-off (more off than on lately) that compares parse trees to group related changes together and tries to do some high-level analysis (like finding moves). I finally got my core algorithm working reasonably well last year, but then started a new job and haven't had the energy to work on it more since—I'm hoping to get back to it in a month or two. Anyway, if you're curious, I have the code and a (very) rough write-up up on GitLab[1]. Keep in mind that it's very preliminary, and that my approach is by no means the only way to do this! There's been a fair amount of research on this in the software engineering community (ie SIGSOFT). I've looked through some of the existing papers, and there have been a range of algorithms and tools with different metrics, different levels of language-awareness and different capabilities. There's a lot to explore if you're curious. [1]: http://gitlab.com/tikhon/cow http://gitlab.com/tikhon/cow (The name is also a work in progress!)

flippant 10y ago

This is part of the Elixir standard library https://hexdocs.pm/elixir/List.html#myers_difference/2 https://hexdocs.pm/elixir/List.html#myers_difference/2 https://github.com/elixir-lang/elixir/blob/master/lib/elixir/lib/list.ex#L772 https://github.com/elixir-lang/elixir/blob/master/lib/elixir...

teabee89 10y ago

I strongly encourage people to read about the lesser-known Tichy diff algorithm too: https://bryanpendleton.blogspot.com/2010/04/more-study-of-diff-walter-tichys-papers.html https://bryanpendleton.blogspot.com/2010/04/more-study-of-di...

nachocab83 10y ago

Does anyone know a way to modify this algorithm to list out all the possible solutions? I asked something similar in stack overflow: http://softwareengineering.stackexchange.com/questions/342985/how-can-i-modify-the-myers-diff-algorithm-to-choose-between-different-answers http://softwareengineering.stackexchange.com/questions/34298...