3 ms·

I spent a bit of time learning the Myers Diff algorithm, (I made this page: https://blog.robertelder.org/diff-algorithm/ https://blog.robertelder.org/diff-algor

I spent a bit of time learning the Myers Diff algorithm, (I made this page: https://blog.robertelder.org/diff-algorithm/ https://blog.robertelder.org/diff-algorithm/) Like someone else said, I think the key is that you're not getting the shortest edit script, you're just getting a edit script. Interestingly, even git's implementation of diff (which uses a variant of the Myers Diff algorithm) doesn't actually find the shortest edit script by default. It has a hard-coded heuristic that just quits early if it finds a 'good enough' solution: https://github.com/git/git/blob/master/xdiff/xdiffi.c#L143 https://github.com/git/git/blob/master/xdiff/xdiffi.c#L143 Same this for unix diff (unless you specify the commandline flag to find shortest): https://github.com/Distrotech/diffutils/blob/distrotech-diffutils/lib/diffseq.h#L255 https://github.com/Distrotech/diffutils/blob/distrotech-diff... Having said that, if you're still confident that you've made an improvement, you can port the function to python and try it out as a test case in my unit test file that I wrote when I developed my variant of the Myers Diff algorithm: https://github.com/RobertElderSoftware/roberteldersoftwarediff/blob/master/myers_diff_and_variations.py https://github.com/RobertElderSoftware/roberteldersoftwaredi... On that topic, I'm pretty sure my variant of the Myers Diff algorithm is actually slightly faster/uses less memory than the original (I'd be happy to be proved wrong). At least, I've had my blog post up for a few years and no one has corrected me, but then again, I think the original paper has a few mistakes/obvious flaws and it still has hundreds of citations and no one has written much about improvements.

ridiculous_fish 7y ago
Nice work on your visualization! Thank you for rebutting the Fraser article; I came to the same conclusion as you (that Myers algorithm is in fact correct) but had never written it up. I wrote a vectorized Myers implementation for diffing binary files. Perhaps the most interesting aspect is the progress bar: it's not obvious how to create a monotonic progress estimate for Myers diff. https://github.com/ridiculousfish/HexFiend/blob/master/framework/sources/HFByteArrayEditScript.m https://github.com/ridiculousfish/HexFiend/blob/master/frame...
- robertelder 7y ago
  Cool. You've got a fairly impressive following on that tool. I wish more people took an interest in studying these sorts of algorithms. Most people assume that some genius figured out the optimal way to do things years ago, but more often than not if you spent a few weeks focusing on a specific paper/algorithm, you'll come up with ideas for improvement (although it might not always be in the way you initially expected). Sometimes the improvement is just figuring out a better way to explain it and that in itself can lead other people to create breakthroughs. I think there are still a few improvements that could be done the the Myers algorithms. One specifically, is that I'm pretty sure it's tail recursive. You won't get any big O improvements off of that, but less stack space is still an improvement. Plus better cache locality. I'd work on some demos, but too many things to do these days...
- smrq 7y ago
  Hey! You made the hex editor I use. Thanks! :)
pstch 7y ago
To anyone that wants to learn or understand the Myers Diff algorithm, the first link in the parent post has great interactive visualization, which also cover the various improvements made on it by robertelder. And by the way, thanks a lot for all this, it has helped me a lot !
- hombre_fatal 7y ago
  Wow, you weren't kidding. That's some good stuff.

ridiculous_fish 7y ago

Nice work on your visualization! Thank you for rebutting the Fraser article; I came to the same conclusion as you (that Myers algorithm is in fact correct) but had never written it up. I wrote a vectorized Myers implementation for diffing binary files. Perhaps the most interesting aspect is the progress bar: it's not obvious how to create a monotonic progress estimate for Myers diff. https://github.com/ridiculousfish/HexFiend/blob/master/framework/sources/HFByteArrayEditScript.m https://github.com/ridiculousfish/HexFiend/blob/master/frame...

robertelder 7y ago
Cool. You've got a fairly impressive following on that tool. I wish more people took an interest in studying these sorts of algorithms. Most people assume that some genius figured out the optimal way to do things years ago, but more often than not if you spent a few weeks focusing on a specific paper/algorithm, you'll come up with ideas for improvement (although it might not always be in the way you initially expected). Sometimes the improvement is just figuring out a better way to explain it and that in itself can lead other people to create breakthroughs. I think there are still a few improvements that could be done the the Myers algorithms. One specifically, is that I'm pretty sure it's tail recursive. You won't get any big O improvements off of that, but less stack space is still an improvement. Plus better cache locality. I'd work on some demos, but too many things to do these days...
smrq 7y ago
Hey! You made the hex editor I use. Thanks! :)

pstch 7y ago

To anyone that wants to learn or understand the Myers Diff algorithm, the first link in the parent post has great interactive visualization, which also cover the various improvements made on it by robertelder. And by the way, thanks a lot for all this, it has helped me a lot !

hombre_fatal 7y ago
Wow, you weren't kidding. That's some good stuff.