Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!tudelft.nl!txtfeed1.tudelft.nl!feeder2.cambriumusenet.nl!feed.tweaknews.nl!194.109.133.85.MISMATCH!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <ivlsca021vl@news2.newsguy.com>
References: <mailman.1002.1310591600.1164.python-list@python.org> <ivlsca021vl@news2.newsguy.com>
Date: Fri, 15 Jul 2011 23:49:53 +0200
Subject: Re: difflib-like library supporting moved blocks detection?
From: Vlastimil Brom <vlastimil.brom@gmail.com>
To: python-list@python.org
Content-Type: multipart/mixed; boundary=20cf307f35de2fb10304a822a114
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1081.1310766597.1164.python-list@python.org>
Lines: 140
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:9574

--20cf307f35de2fb10304a822a114
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

2011/7/14 Chris Torek <nospam@torek.net>:
> In article <mailman.1002.1310591600.1164.python-list@python.org>
> Vlastimil Brom =A0<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. =A0If you only
> allow insert, delete, or in-place-substitute, you have what is
> called the "Levenshtein distance" case. =A0If you allow transpositions
> you get "Damerau-Levenshtein". =A0These are both solveable with a
> dynamic programming algorithm. =A0Once you allow move operations,
> though, the problem becomes NP-complete.
>
> See http://pages.cs.brandeis.edu/~shapird/publications/JDAmoves.pdf
> for instance. =A0(They give an algorithm that produces "usually
> acceptable" results in polynomial time.)
> --
> In-Real-Life: Chris Torek, Wind River Systems
>
>
Thanks for the references and explanation!
I do realise the added complexity with taking the moves into account;
given that, my current needs and the usually satisfying results
obtained easily with difflib, I am not going to try to implement some
more complex diffing algorithm.
However, it turns out that the mentioned naive approach with just
recomparing the text additions and removals may be partially viable -
with some luck, i.e. given, the relevant segments are identified as
deletions and inserts and isolated by difflib in the first place (and
not subsumed under larger changes or split).

For illustration, the rough simplified code is attached (sorry for the
style and possible quirks...)
Just now the more similar text segments are just collected, it would
be also possible to sort them on their similarity ratio; the current
approach also allows to highlight potentially multiple moved segments.

Comments and suggestions are, of course, welcome,
                        regards,
                             vbr

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #

#! Python
# -*- coding: utf-8 -*-

import difflib
import itertools

def compare_moves(a, b, similarity_threshold=3D0.6):
    """
    Poor man's text comparison with simple moves check. Compares two
strings using difflib
    and additionally tries to detect moved blocks
    by comparing similar deleted and inserted segments with each other
- given the similarity_threshold.
    """

    seq_matcher =3D difflib.SequenceMatcher(isjunk=3DNone, a=3Da, b=3Db, au=
tojunk=3DFalse)
    diff_raw =3D [[tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2]] for tag, i1,
i2, j1, j2 in seq_matcher.get_opcodes()]

    deleted, inserted =3D {}, {}
    for tag, i1, i2, j1, j2 in seq_matcher.get_opcodes():
        if tag =3D=3D 'delete':
            deleted[(i1, i2)] =3D [tag, i1, i2, j1, j2, a[i1:i2]]
        elif tag =3D=3D 'insert':
            inserted[(i1, i2)] =3D [tag, i1, i2, j1, j2, b[j1:j2]]

    possibly_moved_blocks =3D []
    for deleted_item, inserted_item in
itertools.product(deleted.values(), inserted.values()):
        similarity_ratio =3D difflib.SequenceMatcher(isjunk=3DNone,
a=3Ddeleted_item[5], b=3Dinserted_item[5], autojunk=3DFalse).ratio()
        if similarity_ratio >=3D similarity_threshold:
            possibly_moved_blocks.append([deleted_item, inserted_item,
similarity_ratio])

    print diff_raw
    print possibly_moved_blocks


if __name__ =3D=3D "__main__":
    compare_moves("abcXYZdeABfghijklmnopABBCq",
"ABCDabcdeACfgXYXZhijklmnopq", similarity_threshold =3D 0.6)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # #
# output: #
[['insert', 0, 0, 0, 4, '', 'ABCD'], ['equal', 0, 3, 4, 7, 'abc',
'abc'], ['delete', 3, 6, 7, 7, 'XYZ', ''], ['equal', 6, 9, 7, 10,
'deA', 'deA'], ['replace', 9, 10, 10, 11, 'B', 'C'], ['equal', 10, 12,
11, 13, 'fg', 'fg'], ['insert', 12, 12, 13, 17, '', 'XYXZ'], ['equal',
12, 21, 17, 26, 'hijklmnop', 'hijklmnop'], ['delete', 21, 25, 26, 26,
'ABBC', ''], ['equal', 25, 26, 26, 27, 'q', 'q']]

[[['delete', 21, 25, 26, 26, 'ABBC'], ['insert', 0, 0, 0, 4, 'ABCD'],
0.75], [['delete', 3, 6, 7, 7, 'XYZ'], ['insert', 12, 12, 13, 17,
'XYXZ'], 0.8571428571428571]]

--20cf307f35de2fb10304a822a114
Content-Type: application/octet-stream; name="compare_moves.py"
Content-Disposition: attachment; filename="compare_moves.py"
Content-Transfer-Encoding: base64
X-Attachment-Id: f_gq5nqkel0

IyEgUHl0aG9uDQojIC0qLSBjb2Rpbmc6IHV0Zi04IC0qLQ0KDQppbXBvcnQgZGlmZmxpYg0KaW1w
b3J0IGl0ZXJ0b29scw0KDQpkZWYgY29tcGFyZV9tb3ZlcyhhLCBiLCBzaW1pbGFyaXR5X3RocmVz
aG9sZD0wLjYpOg0KICAgICIiIg0KICAgIFBvb3IgbWFuJ3MgdGV4dCBjb21wYXJpc29uIHdpdGgg
c2ltcGxlIG1vdmVzIGNoZWNrLiBDb21wYXJlcyB0d28gc3RyaW5ncyB1c2luZyBkaWZmbGliIA0K
ICAgIGFuZCBhZGRpdGlvbmFsbHkgdHJpZXMgdG8gZGV0ZWN0IG1vdmVkIGJsb2NrcyANCiAgICBi
eSBjb21wYXJpbmcgc2ltaWxhciBkZWxldGVkIGFuZCBpbnNlcnRlZCBzZWdtZW50cyB3aXRoIGVh
Y2ggb3RoZXIgLSBnaXZlbiB0aGUgc2ltaWxhcml0eV90aHJlc2hvbGQuDQogICAgIiIiDQoNCiAg
ICBzZXFfbWF0Y2hlciA9IGRpZmZsaWIuU2VxdWVuY2VNYXRjaGVyKGlzanVuaz1Ob25lLCBhPWEs
IGI9YiwgYXV0b2p1bms9RmFsc2UpDQogICAgZGlmZl9yYXcgPSBbW3RhZywgaTEsIGkyLCBqMSwg
ajIsIGFbaTE6aTJdLCBiW2oxOmoyXV0gZm9yIHRhZywgaTEsIGkyLCBqMSwgajIgaW4gc2VxX21h
dGNoZXIuZ2V0X29wY29kZXMoKV0NCg0KICAgIGRlbGV0ZWQsIGluc2VydGVkID0ge30sIHt9DQog
ICAgZm9yIHRhZywgaTEsIGkyLCBqMSwgajIgaW4gc2VxX21hdGNoZXIuZ2V0X29wY29kZXMoKToN
CiAgICAgICAgaWYgdGFnID09ICdkZWxldGUnOg0KICAgICAgICAgICAgZGVsZXRlZFsoaTEsIGky
KV0gPSBbdGFnLCBpMSwgaTIsIGoxLCBqMiwgYVtpMTppMl1dDQogICAgICAgIGVsaWYgdGFnID09
ICdpbnNlcnQnOg0KICAgICAgICAgICAgaW5zZXJ0ZWRbKGkxLCBpMildID0gW3RhZywgaTEsIGky
LCBqMSwgajIsIGJbajE6ajJdXQ0KDQogICAgcG9zc2libHlfbW92ZWRfYmxvY2tzID0gW10NCiAg
ICBmb3IgZGVsZXRlZF9pdGVtLCBpbnNlcnRlZF9pdGVtIGluIGl0ZXJ0b29scy5wcm9kdWN0KGRl
bGV0ZWQudmFsdWVzKCksIGluc2VydGVkLnZhbHVlcygpKToNCiAgICAgICAgc2ltaWxhcml0eV9y
YXRpbyA9IGRpZmZsaWIuU2VxdWVuY2VNYXRjaGVyKGlzanVuaz1Ob25lLCBhPWRlbGV0ZWRfaXRl
bVs1XSwgYj1pbnNlcnRlZF9pdGVtWzVdLCBhdXRvanVuaz1GYWxzZSkucmF0aW8oKQ0KICAgICAg
ICBpZiBzaW1pbGFyaXR5X3JhdGlvID49IHNpbWlsYXJpdHlfdGhyZXNob2xkOg0KICAgICAgICAg
ICAgcG9zc2libHlfbW92ZWRfYmxvY2tzLmFwcGVuZChbZGVsZXRlZF9pdGVtLCBpbnNlcnRlZF9p
dGVtLCBzaW1pbGFyaXR5X3JhdGlvXSkNCg0KICAgIHByaW50IGRpZmZfcmF3DQogICAgcHJpbnQg
cG9zc2libHlfbW92ZWRfYmxvY2tzDQoNCg0KaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoNCiAg
ICBjb21wYXJlX21vdmVzKCJhYmNYWVpkZUFCZmdoaWprbG1ub3BBQkJDcSIsICJBQkNEYWJjZGVB
Q2ZnWFlYWmhpamtsbW5vcHEiLCBzaW1pbGFyaXR5X3RocmVzaG9sZCA9IDAuNikNCg==
--20cf307f35de2fb10304a822a114--