StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>An interesting real-world application of LIS is Patience Diff, a <a href="http://en.wikipedia.org/wiki/Diff" rel="nofollow">diffing</a> algorithm by <a href="http://en.wikipedia.org/wiki/Bram_Cohen" rel="nofollow">Bram Cohen</a> (the creator of BitTorrent) which is used in the <a href="http://bazaar.canonical.com/en/" rel="nofollow">Bazaar</a> version control system.</p> <p>The regular diff algorithm involves computing the LCS (<a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow">Longest Common Subsequence</a>) between two documents. While being efficient, this approach has a problem, which is -- the results often happen to be not quite human-friendly.</p> <p>A simple example of how a regular diff may fail:</p> <pre><code> void func1() { x += 1 +} + +void functhreehalves() { + x += 1.5 } void func2() { x += 2 } </code></pre> <p>The advantage of the Patience Diff algorithm is that it allows to compute the differences more accurately, in a manner more closely corresponding to how a human would perform.</p> <p>In the previous case Patience Diff spots the difference better:</p> <pre><code> void func1() { x += 1 } +void functhreehalves() { + x += 1.5 +} + void func2() { x += 2 } </code></pre> <p>In a nutshell, the algorithm is:</p> <ol> <li>Find unique lines which are common to both documents.</li> <li>Take all such lines from the first document and order them according to their appearance in the second document.</li> <li>Compute the LIS of the resulting sequence (by doing a <a href="http://en.wikipedia.org/wiki/Patience_sorting" rel="nofollow">Patience Sort</a>), getting the longest matching sequence of lines, a correspondence between the lines of two documents.</li> <li>Recurse the algorithm on each range of lines between already matched ones.</li> </ol> <p>Take a look at <a href="http://bazaar.launchpad.net/~bzr-pqm/bzr/bzr.dev/view/head:/bzrlib/_patiencediff_py.py" rel="nofollow">the code</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload