"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")
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")