title: Diff Algorithm?
body: <p>I've been looking like crazy for an explanation of a diff algorithm that works and is efficient.</p>
  
  <p>The closest I got is <a href="http://www.faqs.org/rfcs/rfc3284.html" rel="noreferrer">this link to RFC 3284</a> (from several Eric Sink blog posts), which describes in perfectly understandable terms the <em>data format</em> in which the diff results are stored. However, it has no mention whatsoever as to how a program would reach these results while doing a diff.</p>
  
  <p>I'm trying to research this out of personal curiosity, because I'm sure there must be tradeoffs when implementing a diff algorithm, which are pretty clear sometimes when you look at diffs and wonder "why did the diff program chose this as a change instead of that?"...</p>
  
  <p>Where can I find a description of an efficient algorithm that'd end up outputting VCDIFF?<br>
  By the way, if you happen to find a description of the actual algorithm used by SourceGear's DiffMerge, that'd be even better.</p>
  
  <p>NOTE: longest common subsequence doesn't seem to be the algorithm used by VCDIFF, it looks like they're doing something smarter, given the data format they use.</p>