Making a good diff algorithm
prettydiff.com
prettydiff.com
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
Git has two other diff algorithms, patience and histogram: http://alfedenzo.livejournal.com/170301.html 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/ 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/softwar...
Also useful is libxdiff, which is a C library offering various diff utilities: http://www.xmailserver.org/xdiff-lib.html
https://github.com/paulgb/simplediff/blob/master/python/simp...
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?
It's used for updating Chrom{e,ium)
https://www.chromium.org/developers/design-documents/softwar...
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.
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.
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.
My specific use case was a document tweaked for two different audiences, and I've been able to make changes in one version and rebase the other version on top of it relatively easily.
From the simple perspective, using a fixed width line in a prose markup language that is mostly whitespace agnostic like Markdown creates okay diffs in a line-based diff tool.
I did some work with tokenized diffs: https://github.com/WorldMaker/tokdiff
That particular tool/experiment uses the Pygments tokenizer used for syntax highlighting and produces interesting somewhat semantically meaningful code diffs. I think the same principles would apply if you used something like a part of speech tagger on prose.
From a different approach, I put some effort into better line-based and file-based diffs of Inform 7 which is a prose format that is less whitespace agnostic than Markdown and also built as a single monolithic file, by converting it to an intermediate format.
The code that does this is here: https://github.com/WorldMaker/APrincessOfMoons/blob/master/i...
That works by splitting the file at things that resembles headers, converting newlines to pilcrows (the paragraph symbol), and essentially reformatting to more of a fixed width format. (All of which is trivially reversible.)
You can see the commits in that repository as an example of what the intermediate format looks and diffs like.
That format handler is written as a plugin to a venerable tool I wrote called musdex: https://github.com/WorldMaker/musdex
I wrote that to better source control zip files as the contents of their zip rather than a binary blob, by letting the zip/unzip operations be automatable as a part of source control operations (pre- and post-commit hooks). This I've used for some of the modern file formats like .docx which are built as zip files of XML files and other assets. For instance, you want write the document in Word, interacting with the .docx, and source control its XML contents. That too gives more useful diffs than source controlling the .docx on its own.
in the same way that one-sentence-per-line
gives you much more fine-grained diffs than
one-paragraph-per-line, notching it down to
one-phrase-per-line gives the best results.
a simple javascript routine can do that split,
and then rejoin the lines after you do a diff.
i've written this up extensively, to no notice.
http://zenmagiclove.com/simple/breaker.html
https://github.com/bbirdiman/breakerbreaker
***
i've since found that a dozen changes suffice:
replace ". " -- with -- ". \n"
replace ", " -- with -- ", \n"
replace "? " -- with -- "? \n"
replace "! " -- with -- "! \n"
replace ": " -- with -- ": \n"
replace "; " -- with -- "; \n"
replace ") " -- with -- ") \n"
replace "] " -- with -- "] \n"
replace "} " -- with -- "} \n"
replace "-- " -- with -- "-- \n"
replace "' " -- with -- "' \n"
replace '" ' -- with -- '" \n'
***
and, of course, to revert those changes,
you simply change " \n" to " " and boom.http://git.661346.n2.nabble.com/Bram-Cohen-speaks-up-about-p...
> minimal logic
As the port demonstrates, Patience has very little logic - especially if you remove the optimizations.
[1]: https://github.com/jcdickinson/difflib/blob/master/DiffLib/P...
I'd also say it might beat the OP alghorithm in performances under certain assumption (i.e large writes vs scan read performances)
It was a very significant improvement in speed a few years ago — though with time I've gotten more RAM faster than bigger files to run diff on, and I haven't had any difficulty with the regular Linux diff for a long time.
The table will be {a :(1,1), b :(1,1), ...} because each line appears in both files exactly once.
do {
c = a;
d = b;
// first pass a=0, b=0
// the lines aren't equal, they're "1" and "a" so we pass this case.
if (one[a] === two[b]) {
equality();
} else {
//one[0] is "1", matching 1:(1,1)
//two[0] is "a", matching a:(1,1)
if (table[one[a]].two < 1 && table[two[b]].one < 1) {
//can't get here
replaceUniques();
} else if (table[one[a]].two < 1 && one[a + 1] !== two[b + 2]) {
// 1:(1,1) cdr not less than 1, so this is out
deletion();
} else if (table[two[b]].one < 1 && one[a + 2] !== two[b + 1]) {
// a:(1,1) car not less than 1, so this is out
insertion();
} else if (table[one[a]].one - table[one[a]].two === 1 && one[a + 1] !== two[b + 2]) {
// 0 === one[a+1] !== two[b+2]
// === "2" !== "c"
// === true
deletionStatic();
} else if (table[two[b]].two - table[two[b]].one === 1 && one[a + 2] !== two[b + 1]) {
// 0 === one[a+2] !== two[b+1]
// === "3" !== "b"
// === true
insertionStatic();
} else {
// so we're stuck replacing.
replacement();
}
}
a += 1;
b += 1;
} while (a < lena && b < lenb);
(although i didn't run it, i could have screwed up my interpretation)
in my limited experience, diff is very hard.
edit
fixed a couple typos in the comments.
yeah, three deletes and three inserts showing at least 3 lines of equality is preferable. ideally it'd show a single edit, move of 3 lines, but that's really hard to do.
a,b,c,1,2,3,x,y,z and x,y,z,1,2,3,a,b,c shows 9 differences. the 1,2,3 part at least should be a straight up match.
if each line is unique that replace implementation just trucks down through the whole file.
And the little folding button does indeed fold all nine lines.
When I instead try [a,b,c,1,2,3,x,y,z] against [a,b,c,1,2,3,a,b,c] it only shows "Number of differences: 3 differences from 3 lines of code." and folds the first 6 and the last 3 lines.
The reason why it changes output after using square braces is because the tool is language aware. Before it could not guess at a programming language and so the input is text parsed into lines. After the language detection guesses this is JSON format and formally parses the input, beautifies it, and then compares the beautified output.
I already realize that if I am going to the trouble of parsing languages that it would be far more efficient to simply compare the parsed token lists instead of beautified text, but I haven't gotten there yet.
File 1,
a
b
c
1
2
3
x
y
z
x
y
z
1
2
3
a
b
c
Code type is set to auto. Presumed language is unknown.
Execution time: 0.013 seconds
Number of differences: 9 differences from 9 lines of code.A bit of a pickle.
The challenge I experienced with this is that either there are 6 changes (line for line comparison) or there are 3 lines the same and three lines moved, but three lines moved means a deletion of 3 lines from the first sample and 3 lines of insertion later in the second sample, which is still 6 differences. The output reads very differently, but the number of differences is identical, which is no change in precision.
I'm pretty sure exact diff in subquadratic time is therefore impossible. It's still a nice heuristic though.
Likewise – and perhaps most notoriously – simple line-based diffing does not suffice for diffing prose (natural language text), where knowledge of the broader context, markup (semantics in punctuation and document structure), and paragraph order are crucially important.
Besides the rudimentary one, used by Github (https://github.com/blog/1784-rendered-prose-diffs), I do not know of any production-ready prose-diffing implementation.
But here is an interesting proof of concept: http://www.gigamonkeys.com/tmp/test-diff.html
programs are self-contained entities, whereas prose often drags in multitudes of real-world context involving assumptions, motives, and other considerations.
a diff might inform you of an edit in chapter 2 where you changed a man's status from "divorced" to "widowed" (to make him appear more sympathetic), but it won't also remind you that you need to rewrite that section in chapter 25 where the man gets a phone-call from his former wife.
this type of thing happens a lot, in ways that are much more subtle than that silly example. and it's usually because the arc of the story is greater than (and different from) a simple sum of its pieces.
Swapping the order of two functions seems like an important thing for diff to do.
I imagine you get to linear time without much loss by heuristically throwing out chunks of the table where i is far from j.
The article raises an interesting question: can you improve this by using advantage of the fact that lines of code have a decent chance of being unique or nearly unique within a file?
No. Well, in theoretical time bound, no.
In practice, also no :)
On hackernews, maybe!
You can't just throw out unique lines, they may be in the middle of a replacement.
IE a e c
a d c
Note: edit distance is zero until unique line occurs :(
But what if you just start at the unique lines and edit distance from there, somehow ignoring the equal lines?
This is basically just transforming it into another problem with the same time bound, where that problem is "where is the next/previous point in the file where the streams misalign, if i assume it was aligned before point x".
Sadly, this problem is not any faster to solve. For simple proof, think of it this way: The unique line info just tells you, for sure, that the next alignment point is at least N characters away, where N is the line length, when you are staring at a given character. This is, at best, a constant factor faster, where the constant factor is the average line length * number of unique lines or something like that. It's actually just an application of the boyer-moore trick.
But it's still not theoretically faster, because edit distance is really just a stream alignment algorithm where, instead of stopping, you just keep counting how misaligned they are.
IE edit distance is already a measure of stream alignment, and it's already a very fast one.
Now, you could make a diff algorithm out of the above if you wanted. Find unique lines, or also lines with count mismatches between a and b (since they are at least adds or deletes). Starting from there, segment file into pieces by stream misalignment points. This is equivalent to splitting the file into segments, where each segment has the same edit distance.
While computing, hash each aligned segment to map to where it appears on each side (we need to know where it moved to, and this is a single O(N) pass anyway).
Now you know, for everything that moved, where it moved to, for everything that's the same, where they start and end being the same, etc. From that you can output add, remove, changed as you will.
If this sounds familiar, it's because it's what the algorithms do already for the most part, you are just starting the diff in a different place.
Edit distance can already be done in O(s * min(m,n )) time, where s is the maximum edit distance (which is still O(mn) if the file has completely changed). That's going to be hard to beat.
Truthfully, the real good stream alignment algorithms you would want to look at here at the various algorithms used to do gene sequence alignment :)
But it's not going to be faster unless you are diffing gigabytes of text. Only better in the sense that they use heuristics to do better than edit distance when there are multiple possible points of alignment for a given piece of text.
(IE diff falls down, among other places, where a piece of code could validly have been said to be duplicated to two places. Usually it will notice one of them, and consider the other a replacement or an add of brand new text. Using those algorithms, or the above would let you augment this by saying "it's not an add of really new text, I duplicated thing X to two new places")
[1] J. W. Hunt and T. G. Szymanski. A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5):350–353, 1977.
Note that these are all variants of general algorithm I posted, and more generally, variants of tricks used in boyer-moore (though hunt's work predates boyer-moore, that's the easiest way to describe it), which means they try to skip parts of the text they can prove can't match.
Because they can't always do so, they don't change the worst case time bound, only various other time bounds.
I originally tried a delete as you go approach to the hash map where you remove entries that were no longer needed, such as when both values (counts) for a given key reached 0. My thinking was that this would improve execution speed over the space of a very large table by gradually reducing the key space and thus reducing look up times. This thinking proved false against two 1.7mb code samples. Removing this set of instructions reduced execution time from an average of 0.95 seconds to an average of 0.71 seconds (on my machine and browser). It is simply more efficient to read from a large hash map than it is modify that hash map to improve reading efficiency.
A better approach, which I have not tried, would be to reduce writes to the hash map at the time of running through the second code sample, because you have already gone through the first code sample and not yet performed your formal analysis. To be efficient enough for a valid performance improvement though the analysis at this point would have to be tiny and yet somehow benefit for the formal analysis coming in the next step. The underlying assumption is that having a smaller hash map means fewer writes to memory. To be helpful to the next step of formal analysis the loop would have to achieve fewer iterations.
> The article raises an interesting question: can you improve this by using advantage of the fact that lines of code have a decent chance of being unique or nearly unique within a file?
As a code author I cannot predict user behavior and do not try. Instead I make assumptions upon that behavior and execute to these assumptions, whether or not they are valid. My assumption is that if a user wishes to compare unrelated things the number of differences sky-rockets, which means a bit more computation and temporary data. I suspect that if a user does this it is probably for some exploratory reason and thus are better prepare for the trivial increase in processing.
So various forms of lines that have been moved will always be shown as replacement, for example (I see someone else discovered this)
Most of the cost and complexity of existing diff algorithms is essentially stream alignment (that's what the the dynamic programming problem they solve tells them) , so yes, removing stream alignment will in fact, make your diff algorithm "simple" :)
The fix function is also just a hack for no real way to align streams on a per-character basis, so it has no way of, for example, maximally extending matches until it's done.
You could avoid a lot of what it does by not using lines as your basis, but characters instead.
The direct translation here would be:
1. build segments by starting at the beginning of both files, and incrementing one file until they match, and then incrementing the other until they stop matching (this gives you one or two segments, the mismatch, segment, which may be empty, but represents the part where they don't match, and the matched segment, which will be maximal instead of line split.
This is O( min of both file sizes), just like the current hash building.
You do have to keep track of the line number, but it doesn't change time bounds
2. hash/index the segments the same way you are hashing/indexing lines.
3. do rest of described algorithm.
the only upside/downside is you end up with partially changed lines (IE there may be more than one segment per line), but here you can detect that immediately (you can even just mark where this has happened while you build segments) and transform to replacements if that's what you want instead of trying to notice later that this is what happened.
IF you wanted super simple, but more accurate than this, you could do: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
Split file2 into x sized blocks. Use it as patterns you search against file1. Simple, and same worst case as naive edit distance.
Note that if you had a good enough rolling hash, you could do the same thing in O(N) time, by not doing the equality check in the hashtable, and instead just issuing replacement if it turned out you were wrong :)
I don't think it is -- it's full of the kind of features (complicated condition expressions, long chains of elses, hard-coded numbers) that, when I find myself writing them, suggest that I'm approaching the problem in the wrong way, because previous experiences make me associate that kind of code with lack of generality and corner-case bugs.
which is what most diff tools use. It is a simple and clear algorithm with no special cases once you get your head around it. It works in O(NxM) time, which seems like a reasonable lower bound (you need to compare everything to everything else to have a chance of getting the best alignment) although there are ways to do better with constraints.
(I remember one for gene alignment which broke N and M in two, recurse 4 times on each pairing, and then had a quick-ish way to put those together again. Can't remember the details though!)
A more optimized approach is 2 complete passes and a partial third pass without repetition. Achieving that optimization requires more logic up front to populate a smaller central analysis store and a different means of iterating through that container.
Most approaches, as I have seen them, don't achieve a fully optimized approach. While they may not have complete passes through data (after the required initial two) they tend to have numerous smaller passes in order to derive edit distances. This could be more efficient if these smaller passes never pass through the same data indexes/keys more than once and achieve a reduced total number of iterations. These approaches seem less straight forward to me and are misleading in terms of total statements of execution/iterations.
The only way to guarantee greater execution efficiency is to run through a checklist like this and compare clock times in similar execution contexts:
* total number of loop iterations
* fewer instructions
* instruction optimizations (compiler/interpreter dependent considerations)
If you are looking for something that isn't available please open a Github issue and I will triage it.
Working on a tool to calculate search relevancy and it would be nice to visual display to users the difference between two queries.