Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #9460

Re: difflib-like library supporting moved blocks detection?

Show all headers | View raw

In article <mailman.1002.1310591600.1164.python-list@python.org>
Vlastimil Brom  <vlastimil.brom@gmail.com> wrote:
>I'd like to ask about the availability of a text diff library, like
>difflib, which would support the detection of moved text blocks.

If you allow arbitrary moves, the "minimal edit distance" problem
(string-to-string edit) becomes substantially harder.  If you only
allow insert, delete, or in-place-substitute, you have what is
called the "Levenshtein distance" case.  If you allow transpositions
you get "Damerau-Levenshtein".  These are both solveable with a
dynamic programming algorithm.  Once you allow move operations,
though, the problem becomes NP-complete.

See http://pages.cs.brandeis.edu/~shapird/publications/JDAmoves.pdf
for instance.  (They give an algorithm that produces "usually
acceptable" results in polynomial time.)
-- 
In-Real-Life: Chris Torek, Wind River Systems
Intel require I note that my opinions are not those of WRS or Intel
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W)  +1 801 277 2603
email: gmail (figure it out)      http://web.torek.net/torek/index.html

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

difflib-like library supporting moved blocks detection? Vlastimil Brom <vlastimil.brom@gmail.com> - 2011-07-13 23:13 +0200
  Re: difflib-like library supporting moved blocks detection? Chris Torek <nospam@torek.net> - 2011-07-14 04:47 +0000
    Re: difflib-like library supporting moved blocks detection? Vlastimil Brom <vlastimil.brom@gmail.com> - 2011-07-15 23:49 +0200

csiph-web