<story><title>The Myers diff algorithm: part 1</title><url>https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/</url></story><parent_chain></parent_chain><comment><author>akoboldfrying</author><text>Good to see this interesting and very fundamental topic getting attention, and looking forward to the next post, where hopefully the algorithm&amp;#x27;s cleverness will be explored.&lt;p&gt;&amp;gt;It does this by being greedy, that is trying to consume as many lines that are the same before making a change (therefore avoiding the “wrong end” problem), and also by preferring deletions over insertions when given a choice, so that deletions appear first.&lt;p&gt;Not really. The algorithm guarantees to find an alignment&amp;#x2F;diff&amp;#x2F;edit script of minimal length, but whether it prefers the &amp;quot;leftmost&amp;quot; such alignment (&amp;quot;wrong-end&amp;quot; here and in many similar cases in source code) or the &amp;quot;rightmost&amp;quot; (&amp;quot;right-end&amp;quot; here) is not a crucial aspect of how it works. The preference can be switched by reversing both inputs before diffing and then reversing the output afterwards -- but that&amp;#x27;s also the case for any other algorithm that solves this problem optimally.&lt;p&gt;Myers&amp;#x27;s algorithm is greedy in another sense, however: It greedily hunts first for a solution in which no edits are necessary, then solutions in which 1 edit (insertion or deletion) is necessary, then 2, etc., terminating as soon as it finds a solution. Clearly this leads to an optimal (smallest-possible) diff. It also means that it takes time proportional to the &lt;i&gt;amount of difference&lt;/i&gt; between the two inputs, which is the clever part: This is what makes it much faster than other approaches in the common case where the two inputs are highly similar.</text></comment>
<story><title>The Myers diff algorithm: part 1</title><url>https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/</url></story><parent_chain></parent_chain><comment><author>teabee89</author><text>A while ago I discovered the lesser known Tichy diff algorithm that seems to preserve more context and is better suited for big code refactors: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.researchgate.net&amp;#x2F;publication&amp;#x2F;220439403_The_String-to-String_Correction_Problem_With_Block_Moves&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.researchgate.net&amp;#x2F;publication&amp;#x2F;220439403_The_Strin...&lt;/a&gt; via &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;bryanpendleton.blogspot.com&amp;#x2F;2010&amp;#x2F;04&amp;#x2F;more-study-of-diff-walter-tichys-papers.html&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;bryanpendleton.blogspot.com&amp;#x2F;2010&amp;#x2F;04&amp;#x2F;more-study-of-di...&lt;/a&gt;</text></comment>