Package: diffutils Version: 1:3.2-2 Severity: wishlist Dear Maintainers,
I think it would be nice to have support for the "patience diff" algorithm in GNU diff. Git's xdiff/xpatience.c summarizes it well: /* * The basic idea of patience diff is to find lines that are unique in * both files. These are intuitively the ones that we want to see as * common lines. * * The maximal ordered sequence of such line pairs (where ordered means * that the order in the sequence agrees with the order of the lines in * both files) naturally defines an initial set of common lines. * * Now, the algorithm tries to extend the set of common lines by growing * the line ranges where the files have identical lines. * * Between those common lines, the patience diff algorithm is applied * recursively, until no unique line pairs can be found; these line ranges * are handled by the well-known Myers algorithm. */ The following resources might be helpful: * A short write-up in plain language: <http://alfedenzo.livejournal.com/170301.html> * An explanation of Patience's motivation (including links to pathological non-patience diffs) from the creator: <http://bramcohen.livejournal.com/73318.html> * The algorithm for which it is named: <http://en.wikipedia.org/wiki/Patience_sorting#Algorithm_for_finding_a_longest_increasing_subsequence> * The original implementation, as part of Codeville: Get the source from <http://snapshot.debian.org/package/codeville> and look at Codeville/diff.py and Codeville/lcsmatch.py OR see: <https://github.com/SamB/debian-codeville/blob/master/Codeville/diff.py> <https://github.com/SamB/debian-codeville/blob/master/Codeville/lcsmatch.py> * The GNU Bazaar port of the Codeville code, which seems to be where it was decided to call this "Patience Diff": <http://bazaar.launchpad.net/~bzr-pqm/bzr/bzr.dev/view/head:/bzrlib/patiencediff.py> <http://bazaar.launchpad.net/~bzr-pqm/bzr/bzr.dev/view/head:/bzrlib/_patiencediff_py.py> <http://bazaar.launchpad.net/~bzr-pqm/bzr/bzr.dev/view/head:/bzrlib/_patiencediff_c.c> - Mailing list archives for the relevant time period: <https://lists.ubuntu.com/archives/bazaar/2006q2/thread.html> * The Git implementation, xdiff/xpatience.c: <https://github.com/gitster/git/blob/master/xdiff/xpatience.c> (Implementations are listed in chronological order.) -- Hi! I'm a .signature virus! Copy me into your ~/.signature to help me spread! -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org
