title: Diffing more quickly
body: <p>I'm working on diffing large binary files.  I've implemented the celebrated Myers Diff algorithm, which produces a minimal diff.  However, it is O(ND), so to diff two very different 1 MB files, I expect to take time 1 million squared = 1 trillion.  That's not good!</p>
  
  <p>What I'd like is an algorithm that produces a potentially non-minimal diff, but does it much faster.  I know that one must exist, because Beyond Compare does it.  But I don't know how!</p>
  
  <p>To be sure: There are tools like xdelta or bdiff, but these produce a patch meant for computer consumption, which is different than a human-consumable diff.  A patch is concerned with transforming one file into another, so it can do things like copying from previous parts of the file.  A human-consumable diff is there to visually show the differences, and can only insert and delete.  For example, this transform:</p>
  
  <p>"puddi" -> "puddipuddipuddi"</p>
  
  <p>would produce a small patch of "copy [0,4] to [5,9] and to [10, 14]", but a larger diff of "append 'puddipuddi'".  I'm interested in algorithms that produce the larger diff.</p>
  
  <p>Thanks!</p>