Myers diff algorithm vs Hunt–McIlroy algorithm

by

  • The Myers algorithm is a “divide and conquer algorithm”: it works by finding recursively the central match of two sequences with the smallest edit script. Once this is done only the match is memorized, and the two subsequences preceding and following it are compared again recursively until there is nothing more to compare. Finding the central match is done by matching the ends of sub-sequences as far as possible, and any time it is not possible, augment the edit script by 1, scanning each furthest position attained up to there for each diagonal and see how far again matches can go, if a match encounter a match of the other end, the algorithm just found the central match. This approach has the advantage to occupy O(m+n) memory, and executes in O(nd), d being the edit script complexity.

  • The Hunt and McIlroy approach compute matches in the whole file, and indexes them into so called k-candidates. k being the LCS length. The LCS is augmented progressively by finding matches that fall within proper ordinates (following a rule explained in their paper). While doing this each path is memorized. The problem with the approach is that it does more job than necessary: it memorizes all the paths, O(mn) memory in the worst case, and o(mn log m) for the time complexity.

The Myers algorithm mostly wins because it does not memorize the paths while working, and does not need to “foresee” where to go, doing so it can concentrate at any time only on the furthest positions it could reach with an edit script of smallest complexity. This “smallest complexity” ensures that what is found is the LCS, and not memorizing through which path it went until it found a match uses less memory. Not trying to compute all matches ahead of time avoids their storage, and make them a benefit at match time rather than a memory hog.

More Related Contents:

  1. Diff Algorithm? [closed]
  2. Algorithm to beat Strassen’s Algorithm
  3. What does O(log n) mean exactly?
  4. How do I search for a number in a 2d array sorted left to right and top to bottom?
  5. Generate an integer that is not among four billion given ones
  6. Find duplicates in an array, without using any extra space
  7. How to generate Sudoku boards with unique solutions
  8. Time complexity of Euclid’s Algorithm
  9. How to round floats to integers while preserving their sum?
  10. Modulus power of big numbers
  11. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  12. Maximize the rectangular area under Histogram
  13. Compute social distance between two users
  14. Efficient algorithm for ordering different types of objects
  15. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  16. How to find two most distant points?
  17. Smooth spectrum for Mandelbrot Set rendering
  18. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  19. Sorting an array with minimal number of comparisons
  20. Determining if two line segments intersect? [duplicate]
  21. Fastest algorithm for circle shift N sized array for M position
  22. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  23. How to find distance from the latitude and longitude of two locations?
  24. Randomly choosing from a list with weighted probabilities
  25. Planar Graph Layouts
  26. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  27. How do I find the median of numbers in linear time using heaps?
  28. Finding rectangles in a 2d block grid
  29. Check if array B is a permutation of A
  30. Algorithm to list all unique permutations of numbers contain duplicates

Leave a Comment