title: Is there a diff-like algorithm that handles moving block of lines?
body: <p>The <code>diff</code> program, in its various incarnations, is reasonably good at computing the difference between two text files and expressing it more compactly than showing both files in their entirety.  It shows the difference as a sequence of inserted and deleted chunks of lines (or changed lines in some cases, but that's equivalent to a deletion followed by an insertion).  The same or very similar program or algorithm is used by <code>patch</code> and by source control systems to minimize the storage required to represent the differences between two versions of the same file.  The algorithm is discussed <a href="http://c2.com/cgi/wiki?DiffAlgorithm" rel="noreferrer">here</a> and <a href="http://en.wikipedia.org/wiki/Diff#Algorithm" rel="noreferrer">here</a>.</p>
  
  <p>But it falls down when blocks of text are <em>moved</em> within the file.</p>
  
  <p>Suppose you have the following two files, <code>a.txt</code> and <code>b.txt</code> (imagine that they're both hundreds of lines long rather than just 6):</p>
  
  <pre><code>a.txt   b.txt
  -----   -----
  1       4
  2       5
  3       6
  4       1
  5       2
  6       3
  </code></pre>
  
  <p><code>diff a.txt b.txt</code> shows this:</p>
  
  <pre><code>$ diff a.txt b.txt 
  1,3d0
  &lt; 1
  &lt; 2
  &lt; 3
  6a4,6
  &gt; 1
  &gt; 2
  &gt; 3
  </code></pre>
  
  <p>The change from <code>a.txt</code> to <code>b.txt</code> can be expressed as "Take the first three lines and move them to the end", but <code>diff</code> shows the complete contents of the moved chunk of lines twice, missing an opportunity to describe this large change very briefly.</p>
  
  <p>Note that <code>diff -e</code> shows the block of text only once, but that's because it doesn't show the contents of deleted lines.</p>
  
  <p>Is there a variant of the <code>diff</code> algorithm that (a) retains <code>diff</code>'s ability to represent insertions and deletions, and (b) efficiently represents moved blocks of text without having to show their entire contents?</p>