Similar::Algorithms::Myers
Myers' diff algorithm.
- time:
O((N+M)D) - space
O(N+M)
See the original article by Eugene W. Myers describing it.
The implementation of this algorithm is based on the implementation by Brandon Williams.
Heuristics
At present this implementation of Myers' does not implement any more advanced heuristics that would solve some pathological cases. For instance passing two large and completely distinct sequences to the algorithm will make it spin without making reasonable progress. Currently the only protection in the library against this is to pass a deadline to the diffing algorithm.
For potential improvements here see similar#15.
Class methods
The conquer part of a divide-and-conquer strategy.
Myers' diff algorithm.
Diff old, between indices old_range and new between indices new_range.
Myers' diff algorithm with deadline.
Diff old, between indices old_range and new between indices new_range.
This diff is done with an optional deadline that defines the maximal execution time permitted before it bails and falls back to an approximation.
A Snake is a sequence of diagonal edges in the edit graph. Normally
a snake has a start end end point (and it is possible for a snake to have
a length of zero, meaning the start and end points are the same) however
we do not need the end point which is why it's not implemented here.
The divide part of a divide-and-conquer strategy. A D-path has D+1 snakes some of which may be empty. The divide step requires finding the ceil(D/2) + 1 or middle snake of an optimal D-path. The idea for doing so is to simultaneously run the basic algorithm in both the forward and reverse directions until furthest reaching forward and reverse paths starting at opposing corners 'overlap'.