SequenceMatcher.find_longest_match match expansion doesn't capture maximum range

[dg-pb]

Feature or enhancement

Proposal:

After match is found it is expanded both ways.
First for popular (autojunk), then for isjunk.

# NOTE `NOT isbjunk`
while besti > alo and bestj > blo and \
      not isbjunk(b[bestj-1]) and \
      a[besti-1] == b[bestj-1]:
    besti -= 1
    bestj -= 1
    bestsize += 1

while besti+bestsize < ahi and bestj+bestsize < bhi and \
      not isbjunk(b[bestj+bestsize]) and \
      a[besti+bestsize] == b[bestj+bestsize]:
    bestsize += 1

# NOTE: isbjunk
while besti > alo and bestj > blo and \
      isbjunk(b[bestj-1]) and \
      a[besti-1] == b[bestj-1]:
    besti -= 1
    bestj -= 1
    bestsize += 1

while besti+bestsize < ahi and bestj+bestsize < bhi and \
      isbjunk(b[bestj+bestsize]) and \
      a[besti+bestsize] == b[bestj+bestsize]:
    bestsize = bestsize + 1

However, the order of thee results in the situation where it does not capture what is possible if both were done in a single loop. I.e. maybe after isjunk, we can expand for popular again.

I think this should be done for both in one go. Simply:

while besti > alo and bestj > blo and a[besti-1] == b[bestj-1]:
    besti -= 1
    bestj -= 1
    bestsize += 1
lasti = besti + bestsize
lastj = bestj + bestsize
while lasti < ahi and lastj < bhi and a[lasti] == b[lastj]:
    lasti += 1
    lastj += 1
    bestsize += 1

This results in slightly wider match ranges for 2 test cases.

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

[tim-one]

I don't want to muddy the waters here. The code is written to "obviously implement" the intent: a wholly interesting (junk-free) match can be extended by junk on both ends. Period. That's clear.

I don't want to spend any time thinking about alternatives, partly because it's delicate, but mostly because I see no real point to it. It can change results. Changes to results require strong justification. and I see close to zero benefit from collapsing the loops.

I expect collapsing would be harmless overall - except that it would change results. So in absence of a "strong reason", I'm inclined to reject.

[dg-pb]

The code is written to "obviously implement" the intent: a wholly interesting (junk-free) match can be extended by junk on both ends. Period. That's clear.

Well, this is why I created this issue. The way I see it, extending it in one go while including all junk into account, not one by one category, captures the intent better and more directly.

It would be nice to remove a bit of that scary code. :)

I expect collapsing would be harmless overall - except that it would change results. So in absence of a "strong reason", I'm inclined to reject.

With this I agree. It would provide marginal improvement, but nothing substantial. The quality of result depends mostly on how optimal are the matches found, not how well the junk is expanded.

Theoretically, though:

string = 'abababcbababa'
popular = {'a'}
junk = {'b'}
match = 'c'
# with current it would expand only to:
'bcb'
# with merged it would capture the whole string (which is correct)

So there would be some performance and quality benefits.
But practical implications might be below the threshold of what is worth it.

Feel free to close the issue if you are convinced that this isn't worth it.

[tim-one]

I think you're overselling the potential benefits. The vast bulk of time is spent in the loop nest before, and finding a popular element in seq1 only costs a failed dict lookup.

BTW, I couldn't follow the example;. It's impossible to know what it would expand to without knowing both inputs. And the user doesn't know what's popular - autojunk makes it up on its own. Far as they're concerned, a is not junk, Which is the real reason for expanding by popular on both sides: to make the diff more intuitive for users.

[dg-pb]

But current code tries expanding popular.
Then it goes on trying to expand junk.
So it does attempt to expand everything that it can.
Just doesn't manage to do it properly.

---

string1 = 'abababccbababa'
string2 = 'abababccbababa' 
popular = {'a'}    # dynamically determined
junk = {'b'}        # user defined
match = 'cc'

With current it would expand only to: 'bccb'
Step 1. It tries expanding popular and finds nothing on both sides
Step 2. It tries expanding junk and finds b on each side

---

with merged loop it would capture the whole string.

---

Just pointing out the difference.

[tim-one]

Thanks! In the context of getting a full diff, though, it doesn't matter: get_matching_blocks() collapses adjacent "equal" blocks, so in the end the user sees an empty diff no matter how all-equal segments are partitioned

Anyway, in the absence of strong reason to change, I'm going to close this. Thank for your effort!

[tim-one]

But current code tries expanding popular.
Then it goes on trying to expand junk.
So it does attempt to expand everything that it can.

Last line not true. Already explained:

a wholly interesting (junk-free) match can be extended by junk on both ends. Period.

[dg-pb]

@tim-one. There is another nuance which might occasionally occur.

The case where no match was found still attempts to expand matches. Thus, no-block (0, 0, 0), might become something.

[tim-one]

Yes, just another instance of "longest junk-free match is extended on both sides to capture adjacent junk". Nothing special about an empty longest junk-free match. What would be the point in making a special case of that? By hypothesis, there is no non-junk at all that matched, so may as well include the junk that does match - make some progress.