Diff Algorithm? [closed]

by

An O(ND) Difference Algorithm and its Variations is a fantastic paper and you may want to start there. It includes pseudo-code and a nice visualization of the graph traversals involved in doing the diff.

Section 4 of the paper introduces some refinements to the algorithm that make it very effective.

Successfully implementing this will leave you with a very useful tool in your toolbox (and probably some excellent experience as well).

Generating the output format you need can sometimes be tricky, but if you have understanding of the algorithm internals, then you should be able to output anything you need. You can also introduce heuristics to affect the output and make certain tradeoffs.

Here is a page that includes a bit of documentation, full source code, and examples of a diff algorithm using the techniques in the aforementioned algorithm.

The source code appears to follow the basic algorithm closely and is easy to read.

There’s also a bit on preparing the input, which you may find useful. There’s a huge difference in output when you are diffing by character or token (word).

Good luck!

More Related Contents:

  1. Myers diff algorithm vs Hunt–McIlroy algorithm
  2. Efficient way to add element to sorted datastructure [closed]
  3. How to count the number of set bits in a 32-bit integer?
  4. Algorithm to return all combinations of k elements from n
  5. What is tail recursion?
  6. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  7. How do you detect Credit card type based on number?
  8. What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?
  9. Negative weights using Dijkstra’s Algorithm
  10. What’s the fastest algorithm for sorting a linked list?
  11. Need help in mod 1000000007 questions
  12. SICP example: Counting change, cannot understand
  13. How can I compute a Cartesian product iteratively?
  14. Quicksort: Iterative or Recursive
  15. How best to sum up lots of floating point numbers?
  16. Algorithm to tell if two arrays have identical members
  17. Quicksort vs heapsort
  18. finding a^b^c^… mod m
  19. Algorithm to find the most common substrings in a string
  20. Simplest way to get the top n elements of a Scala Iterable
  21. Find cycle of shortest length in a directed graph with positive weights
  22. How is 2D bin packing achieved programmatically?
  23. Optimizing Conway’s ‘Game of Life’
  24. Retrieving the top 100 numbers from one hundred million of numbers [duplicate]
  25. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  26. How do I find the median of numbers in linear time using heaps?
  27. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  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