Making a good diff algorithm
I've always wanted to explore the topic of diff in depth, but so far haven't been able to. I have some links that I've stashed; hopefully they will be useful.<p>I believe the classic for typical textual diff is this article by Myers, whose algorithm is still the default in git: <a href="http://link.springer.com/article/10.1007/BF01840446" rel="nofollow">http://link.springer.com/article/10.1007/BF01840446</a><p>Git has two other diff algorithms, patience and histogram: <a href="http://alfedenzo.livejournal.com/170301.html" rel="nofollow">http://alfedenzo.livejournal.com/170301.html</a> <a href="https://github.com/git/git/commit/8c912eea94a2138e8bc608f7c390eb0b313effb0" rel="nofollow">https://github.com/git/git/commit/8c912eea94a2138e8bc608f7c3...</a><p>For binary/executable code, I believe Colin Percival's bsdiff is the best: <a href="http://www.daemonology.net/bsdiff/" rel="nofollow">http://www.daemonology.net/bsdiff/</a> although he hints that his thesis contains a better algorithm.<p>For just executables, however, I think Google Chrome uses Courgette, which actually performs disassembly first: <a href="https://www.chromium.org/developers/design-documents/software-updates-courgette" rel="nofollow">https://www.chromium.org/developers/design-documents/softwar...</a><p>Also useful is libxdiff, which is a C library offering various diff utilities: <a href="http://www.xmailserver.org/xdiff-lib.html" rel="nofollow">http://www.xmailserver.org/xdiff-lib.html</a>