find_longest_match in SequenceMatcher

[koara]

Hello, it might be too late or too hot, but i cannot work out this
behaviour of find_longest_ma tch() in difflib.Sequenc eMatcher:

string1:
releasenotesfor wildmagicversio n01thiscdromcon tainstheinitial releaseofthesou rcecodethatacco mpaniesthebook" 3dgameenginedes ign:apracticala pproachtorealti mecomputergraph ics"thereareanu mberofknownissu esaboutthecodea stheseissuesare addressedtheupd atedcodewillbea vailableatthewe bsitehttp://wwwmagicsoftwar ecom/3dgameenginedes ignhtmlbugssugg estionsforimpro vementsandother correspondencec anbesenttosuppo rt@magicsoftwar ecomthecurrentk nownissuesare1m eshalgorithmfor continuouslevel ofdetailappears nottobeworkingb ase

string2:
releasenotesfor wildmagicversio n02updatefromve rsion01toversio n02ifyourcopyof thebookhasversi on01andifyoudow nloadedversion0 2fromthewebsite thenapplythefol lowingdirection sforinstallingt heupdateforalin uxinstallations eethesectionatt heendofthisdocu mentupdatedirec tionsassumingth atthetopleveldi rectoryiscalled magicreplacebyy ourtoplevelname youshouldhaveth eversion01conte ntsinthislocati on1deletethecon tentsofmagic\in clude2deletethe subdirectorymag ic\source\mgcap plication3delet etheobsoletefil es:amagic\sourc e\mgc

find_longest_ma tch(0,500,0,500 )=(24,43,10)="v ersion01t"

What? O_o Clearly there is a longer match, right at the beginning!
And then, after removal of the last character from each string (i found
the limit of 500 by trial and error -- and it looks suspiciously
rounded):

find_longest_ma tch(0,499,0,499 )=(0,0,32)="rel easenotesforwil dmagicversion0"


Is this the expected behaviour? What's going on?
Thank you for any ideas

[John Machin]

Re: find_longest_ma tch in SequenceMatcher


koara wrote:

Hello, it might be too late or too hot, but i cannot work out this
behaviour of find_longest_ma tch() in difflib.Sequenc eMatcher:
>
string1:

[snipped 500-byte string]

>
string2:
>

[snipped 500-byte string]

>
find_longest_ma tch(0,500,0,500 )=(24,43,10)="v ersion01t"
>
What? O_o Clearly there is a longer match, right at the beginning!
And then, after removal of the last character from each string (i found
the limit of 500 by trial and error -- and it looks suspiciously
rounded):

What limit? (a) My results [see below] (b) my inspection of the Python
version 2.4 source for the difflib module (c) what I know of the author
-- all tend to indicate that there is no hidden undocumented length
limit.

>
find_longest_ma tch(0,499,0,499 )=(0,0,32)="rel easenotesforwil dmagicversion0"
>
>
Is this the expected behaviour? What's going on?

My code: (koara.py)
8<---
strg1 =
r"""releasenote sforwildmagicve rsion01thiscdro mcontainstheini tialreleaseofth esourcecodethat accompaniestheb ook"3dgameengin edesign:apracti calapproachtore altimecomputerg raphics"therear eanumberofknown issuesaboutthec odeastheseissue sareaddressedth eupdatedcodewil lbeavailableatt hewebsitehttp://wwwmagicsoftwar ecom/3dgameenginedes ignhtmlbugssugg estionsforimpro vementsandother correspondencec anbesenttosuppo rt@magicsoftwar ecomthecurrentk nownissuesare1m eshalgorithmfor continuouslevel ofdetailappears nottobeworkingb ase"""
strg2 =
r"""releasenote sforwildmagicve rsion02updatefr omversion01tove rsion02ifyourco pyofthebookhasv ersion01andifyo udownloadedvers ion02fromtheweb sitethenapplyth efollowingdirec tionsforinstall ingtheupdatefor alinuxinstallat ionseethesectio nattheendofthis documentupdated irectionsassumi ngthatthetoplev eldirectoryisca lledmagicreplac ebyyourtoplevel nameyoushouldha vetheversion01c ontentsinthislo cation1deleteth econtentsofmagi c\include2delet ethesubdirector ymagic\source\m gcapplication3d eletetheobsolet efiles:amagic\s ource\mgc"""
import sys
print sys.version
from difflib import SequenceMatcher as SM
smo = SM(None, strg1, strg2)
print len(strg1), len(strg2)
print smo.find_longes t_match(0, 500, 0, 500)
print smo.find_longes t_match(0, 499, 0, 499)
print smo.find_longes t_match(0, 100, 0, 100)
print smo.find_longes t_match(1, 101, 1, 101)
print smo.find_longes t_match(2, 102, 2, 102)
8<---

The results on 4 python versions:

C:\junk>c:\pyth on24\python koara.py
2.4.3 (#69, Mar 29 2006, 17:35:34) [MSC v.1310 32 bit (Intel)]
500 500
(24, 43, 10)
(24, 43, 10)
(24, 43, 10)
(24, 43, 10)
(24, 43, 10)

C:\junk>c:\pyth on23\python koara.py
2.3.5 (#62, Feb 8 2005, 16:23:02) [MSC v.1200 32 bit (Intel)]
500 500
(24, 43, 10)
(24, 43, 10)
(24, 43, 10)
(24, 43, 10)
(24, 43, 10)

C:\junk>c:\pyth on22\python koara.py
2.2.3 (#42, May 30 2003, 18:12:08) [MSC 32 bit (Intel)]
500 500
(0, 0, 32)
(0, 0, 32)
(0, 0, 32)
(1, 1, 31)
(2, 2, 30)

C:\junk>c:\pyth on21\python koara.py
2.1.3 (#35, Apr 8 2002, 17:47:50) [MSC 32 bit (Intel)]
500 500
(0, 0, 32)
(0, 0, 32)
(0, 0, 32)
(1, 1, 31)
(2, 2, 30)

Looks to me like the problem has nothing at all to do with the length
of the searched strings, but a bug appeared in 2.3. What version(s)
were you using? Can you reproduce your results (500 & 499 giving
different answers) with the same version?

Anyway, as they say in the classics, "Take a number; the timbot will be
with you shortly."

Cheers,
John

[koara]

Re: find_longest_ma tch in SequenceMatcher

John Machin wrote:

--test results snip---
Looks to me like the problem has nothing at all to do with the length
of the searched strings, but a bug appeared in 2.3. What version(s)
were you using? Can you reproduce your results (500 & 499 giving
different answers) with the same version?

Hello John, thank you for investigating and responding!

Yes, I can reproduce the behaviour with different results within the
same version -- which is 2.4.3 (#69, Mar 29 2006, 17:35:34) [MSC v.1310
32 bit (Intel)]

The catch is to remove the last character, as i described in my
original post, as opposed to passing reduced length parameters to
find_longest_ma tch, which is what you did.

It is morning now, but i still fail to see the mistake i am making --
if it is indeed a bug, where do i report it?

Cheers!

[John Machin]

Re: find_longest_ma tch in SequenceMatcher

koara wrote:

John Machin wrote:

--test results snip---
Looks to me like the problem has nothing at all to do with the length
of the searched strings, but a bug appeared in 2.3. What version(s)
were you using? Can you reproduce your results (500 & 499 giving
different answers) with the same version?

>
Hello John, thank you for investigating and responding!
>
Yes, I can reproduce the behaviour with different results within the
same version -- which is 2.4.3 (#69, Mar 29 2006, 17:35:34) [MSC v.1310
32 bit (Intel)]
>
The catch is to remove the last character, as i described in my
original post, as opposed to passing reduced length parameters to
find_longest_ma tch, which is what you did.
>
It is morning now, but i still fail to see the mistake i am making --
if it is indeed a bug, where do i report it?
>

Further sniffing shows that we were both partially right/wrong:
There is a bug.
It is length-dependant.
It was introduced in Python 2.3.

If you want to, you can hack your copy of
<Python-2.4_installatio n_directory>/Lib/difflib.py
so that line 316 reads:
if 0:
instead of:
if n >= 200 and len(indices) * 100 n:

I'll report it.

Cheers,
John

[John Machin]

Re: find_longest_ma tch in SequenceMatcher


John Machin wrote:

koara wrote:

John Machin wrote:

There is a bug.
I'll report it.

Reported.
http://sourceforge.net/tracker/index...70&atid=105470

[koara]

Re: find_longest_ma tch in SequenceMatcher

Hello again John -- your hack/fix seems to work. Thanks a lot, now
let's hope timbot will indeed be here shortly with a proper fix =)