4 ms·
Diffing means computing the longest common subsequence (LCS); the edit script is everything that's not part of the LCS. The proposed algorithm greedily finds a
by ridiculous_fish 7y ago
Diffing means computing the longest common subsequence (LCS); the edit script is everything that's not part of the LCS. The proposed algorithm greedily finds a matching element. However it may be that it would be better to skip this element, and not incorporate it into your sequence.
Consider the following sequences (here each letter represents a line).
AAAB
BAAA
Where the first one is "left" and the second one is "right".
The LCS is AAA. The minimal edit script from left to right is:
1. Insert B at beginning.
2. Delete B at end.
The proposed O(N) algorithm finds B as the first matching line, and thereby exhaust `left`. So it finds the common subsequence of just "B" and its edit script is:
1. Delete 3 As at beginning
2. Insert 3 As at end
which is longer.
- keithwhor 7y agoThanks! Yep, definitely not finding the LCS and associated edits with the current implementation. From my view right now, I'm basically going to have to use a suffix tree to efficiently find the LCS and go from there - which means it's likely that I'm just going to end up approaching Myers' algorithm.
- leshow 7y agoIs it subsequence or substring? Don't you want to find the longest common substring, i.e. contiguous block? I always understood subsequence to be non-contiguous.
- ruds 7y agoIt's subseqence. For instance, in ABXCDYEFGZ QARBCSTDEFG You want to find [Q]A[R]B(X)C[ST]D(Y)EFG(Z) ABCDEFG is the longest common subsequence, QRST are the additions and XYZ are the deletions.