5 ms·
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.
by kccqzy 10y ago
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.
I believe the classic for typical textual diff is this article by Myers, whose algorithm is still the default in git: http://link.springer.com/article/10.1007/BF01840446 http://link.springer.com/article/10.1007/BF01840446
Git has two other diff algorithms, patience and histogram: http://alfedenzo.livejournal.com/170301.html http://alfedenzo.livejournal.com/170301.html https://github.com/git/git/commit/8c912eea94a2138e8bc608f7c390eb0b313effb0 https://github.com/git/git/commit/8c912eea94a2138e8bc608f7c3...
For binary/executable code, I believe Colin Percival's bsdiff is the best: http://www.daemonology.net/bsdiff/ http://www.daemonology.net/bsdiff/ although he hints that his thesis contains a better algorithm.
For just executables, however, I think Google Chrome uses Courgette, which actually performs disassembly first: https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...
Also useful is libxdiff, which is a C library offering various diff utilities: http://www.xmailserver.org/xdiff-lib.html http://www.xmailserver.org/xdiff-lib.html
- paulgb 10y agoFor people just wanting to get their feet wet and understand one of the simpler algorithms, I implemented a simple diff algorithm in Python a decade ago with code readability in mind and it's since been translated to a handful of languages. https://github.com/paulgb/simplediff/blob/master/python/simplediff/__init__.py https://github.com/paulgb/simplediff/blob/master/python/simp...
- aidos 10y agoLovely. Quick question, is this the sort of technique that used for general text diffing? I see you effectively tokenize the string using whitespace to split and then pass in 2 lists of tokens. Is that the way it's generally done, and you just choose a suitable tokenizer for your specific use-case?
- paulgb 10y agoUsually for source code, the diff is line-based. I didn't actually have a use case at the time, I just wanted to see if it would work.
- emmelaich 10y agoIt's worth mentioning courgette which is in the same space as bsdiff. It's used for updating Chrom{e,ium) https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...
- jessriedel 10y agoDoes anyone know much about prose diff? Very few diff apps work well with prose, and I wonder to what extent this is driven at the level of the algorithm.
- 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.
- js2 10y agoCourgette used to only work on Windows (PE/COFF) executables. It looks like it now also works on ELF x86 and ELF arm executables. But it doesn't seem to support ELF 64-bit, nor does it support mach-o (Mac) executables.
- avar 10y agoIn addition to the algorithms you mentioned git also has --diff-algorithm=minimal. This is just the XDF_NEED_MINIMAL flag to xdiff, so I'm unsure if it counts as a separate algorithm.