Module 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.

Functions

• diff
  Myers’ diff algorithm.
• diff_deadline
  Myers’ diff algorithm with deadline.