Algorithmic complexity of difflib

[dg-pb]

Took some time to explore possible improvements to the “Gestalt Pattern Matching for file diffs”.

---

First, let me introduce simple example that I will reference later.
(Line-by-line case is named (L) diff_key in tables below.)

Before:

def foo1(a, b):
    a += 1
    b += 1
    return a + b

def foo2(a, b):
    a += 2
    b += 2
    return a + b

def foo3(a, b):
    c = a + b
    d = c + a * b
    r = sum(range(d))
    return r

After:

def foo3(a, b):
    c = a + b
    d = c + a * b
    r = sum(range(d))
    return r
#
def foo1(a, b):
    a += 1
    b += 1
    return a + b
#
def foo2(a, b):
    a += 2
    b += 2
    return a + b

The issue with difflib is that it greedily captures block of length 5, giving up 2 blocks of length 4.

---

First of all, patience diff.

From my preliminary testing it does not seem to be working well in conjunction with block approach of difflib.

Its not that it doesn’t do what it promises.
Which is - “I will improve quality at the expense of less matches”.

So it does give a good compromise when used in conjunction with Myers diff (non-contiguous LCS) as Myers diff is unrestricted algorithm that optimizes at fines granularity, which for diff quality can be a bit overkill. Thus, the opportunity for “patient” preprocessing.

But difflib’s block approach already “sacrifices” a great number of matches for the sake of contiguous blocks. Thus, when used in conjunction with “patience diff”, the final result does seem to sacrifice too many matches in total.

Having that said, patience diff does correct the simple example above:

• (C) means raw strings - character by character comparison
• (L) means strings are split into lines
• Numbers are: total_number_of_match_points -how_much_it_is_lower_than_LLCS
• (L) diff_key case is the simple example above as presented - line-by-line
• Rest of cases can be found in: Code Diff Test Cases · GitHub
• Gestalt == difflib(autojunk=False)

case	Myer/LLCS	patient Myer	Gestalt	patient Gestalt
(C) diff_key ( 194, 196)	143	82 -61	82 -61	82 -61
(L) diff_key ( 15, 15)	8	8 0	5 -3	8 0
(C) diff_mid1 ( 537, 533)	335	335 0	326 -9	326 -9
(L) diff_mid1 ( 28, 27)	11	11 0	11 0	11 0
(C) diff_mid2 (2907, 2907)	2139	2000 -139	1827 -312	1717 -422
(L) diff_mid2 ( 128, 128)	73	63 -10	72 -1	63 -10
(C) diff_mid3 (3139, 3139)	2266	2266 0	1329 -937	1329 -937
(L) diff_mid3 ( 131, 131)	63	62 -1	50 -13	62 -1
(L) diff_lib (2085, 2380)	1930	1929 -1	1926 -4	1929 -1
-----
Total:	6968	6756 -212	5628 -1340	5527 -1441
Avg % diff:	0%	7.17%	17.89%	13.53%
Runtime (s):	0.473	0.276	0.046	0.042

Although avg % diff is better due to perfectly fixing the (L) diff_key, the total number of matches suffers. On the other hand, when it is used with Myer, the cost seems much more acceptable.

Which brings me to the next thing.

---

Alternatively, there is another idea, which might be more suitable for difflib’s block approach.

Skew fix.:

1. Once LCSUB/block is calculated, check its “skew” (skewed if in very different positions in 2 sequences) and calculate couple alternatives accordingly (or not).
2. For each candidate calculate 2 nearby LCSUBS/blocks. So several candidates, 3 LCSUBs/blocks each.
3. Then take best (which is now 3 blocks) and recurse in gaps.

At worst case, runs at 3x premium.
However, in practice, it is ~30% extra runtime.
This is due to:

1. Automaton is being reused for calculations on same (blo, bhi) ranges and this can partially exploit it.
2. Gestalt approach is in a way quicksort and this approach often nudges matches to be more “centered”. Thus, often results in more balanced split points.

It fixes the example case above in the same way as patience diff does.
However, as opposed to reducing number of matches in other cases, it (mostly) improves upon them as well:

case	Myer/LLCS	patient Myer	Gestalt	patient Gestalt	Gestalt SkewFix
(C) diff_key ( 194, 196)	143	82 -61	82 -61	82 -61	110 -33
(L) diff_key ( 15, 15)	8	8 0	5 -3	8 0	8 0
(C) diff_mid1 ( 537, 533)	335	335 0	326 -9	326 -9	328 -7
(L) diff_mid1 ( 28, 27)	11	11 0	11 0	11 0	11 0
(C) diff_mid2 (2907, 2907)	2139	2000 -139	1827 -312	1717 -422	1842 -297
(L) diff_mid2 ( 128, 128)	73	63 -10	72 -1	63 -10	72 -1
(C) diff_mid3 (3139, 3139)	2266	2266 0	1329 -937	1329 -937	1329 -937
(L) diff_mid3 ( 131, 131)	63	62 -1	50 -13	62 -1	51 -12
(L) diff_lib (2085, 2380)	1930	1929 -1	1926 -4	1929 -1	1926 -4
-----
Total:	6968	6756 -212	5628 -1340	5527 -1441	5677 -1291
Avg % diff:	0%	7.17%	17.89%	13.53%	11.23%
Runtime (s):	0.466	0.272	0.043	0.064	0.083

[tim.one (Tim Peters)]

@dg-pb

Took some time to explore possible improvements to the “Gestalt Pattern Matching for file diffs”.

I think may be a bottomless I can’t afford the time to step into. You always present a lot of data, but it’s sometimes unclear to me what the data is showing. Like:

Numbers are: total_length -how_much_it_is_lower_than_LLCS

• total_length of what? Lines in the diff? Characters in the diff? Total number of characters or lines that matched?
• I don’t believe you ever said what “LLCS” means. Probably not the plural of limited liability corporations, which was Google’s best guess

|(C) diff_key ( 194, 196)|

What does “( 194, 196)” mean in that?

And so on.

It’s just a major time sink for me to try to out-guess these things. I’m sure they’re saying things worth knowing, and appreciate your time and good efforts, but I just can’t block out the time to fill in the gaps.

So I’ll stick to higher-level things here:

First, let me introduce simple example that I will reference later.
(Line-by-line case is named (L) diff_key in tables below.)

Again it would help if you spelled out why the example is interesting.

In this case, there were two 4-line functions, and one 5-line function at the end. The function at the end was moved to the top. The functions are separated by “junk” in both cases (blank lines before, lone “#” after, but that seems irrelevant).

difflib synchs on the 5-line function, but could have synched instead on the two 4-line functions.

I’ll note that a more expansive notion of matching would include a “move” operation as a primitive (in addition to insert, delete, and replace) - but that’s hard to present in the linear “top to bottom” form of a diff.

First of all, patience diff.

From my preliminary testing it does not seem to be working well in conjunction with block approach of difflib.

Its not that it doesn’t do what it promises.
Which is - “I will improve quality at the expense of less matches”.

So it does give a good compromise when used in conjunction with Myers diff (non-contiguous LCS) as Myers diff is unrestricted algorithm that optimizes at fines granularity, which for diff quality can be a bit overkill. Thus, the opportunity for “patient” preprocessing.

Yes, difflib’s current idea of “high-value synch point” is “longest contiguous junk-free match”. The “patience” approach’s is “appears uniquely” (or in the (IMO better) more general “histogram” approach, “appears rarely”). Note that “unique” (or “rarely”) automatically avoids synching on junk.

Both ways catch human eyeballs, one because of sheer bulk, the other because of rarity.

…
Having that said, patience diff does correct the simple example above:

Although the example was a pretty degenerate case for patience: the only lines that weren’t unique were junk lines and return a + b. Patience left very little for Meyers to do. And patience on its own can’t really be usefully applied recursively, because it already got what it could from unique/rare characters at the top level.

Alternatively, there is another idea, which might be more suitable for difflib’s block approach.

Which I’m not getting into at this time. DIfflib was driven by dissatisfaction with real-life diffs produced by Unixy tools at the time. So was “patience”/“histogram”. They both appear to be do well at addressing those, and an entirely different approach than difflib’s is theoretically on the table too - but not for me at this time.

Yet another approach I’ve seen is to live with pure Meyers, but post-process its output to “deobfuscate” its sometimes too-fine-grained view of the world.

However, as you’ve shown now, it is possible to make diffllib’s “longest contiguous” approach run “almost always” in practical linear time. That will never be so for Meyers.

[dg-pb]

@tim.one

• I don’t believe you ever said what “LLCS” means. Probably not the plural of limited liability corporations, which was Google’s best guess

It is difficult to communicate as the 2 terms are very similar and there isn’t a clear agreed abbreviation (at least as far as I know).

1. LCS (Longest Common Subsequence) - non-contiguous alignment
2. LCSUB (Longest Common Substring) - single longest contiguous substring

Extra L prefix just means “Length of”.

@tim.one

total_length of what? Lines in the diff? Characters in the diff? Total number of characters or lines that matched?

So total_length is total number of match points.
It is neither LLCS, nor LLCSUB, but rather the number of single matching points in alignment - whatever it might be (as long as correct).

@tim.one

What does “( 194, 196)” mean in that?

These are lengths of 2 input sequences.

@tim.one

It’s just a major time sink for me to try to out-guess these things. I’m sure they’re saying things worth knowing, and appreciate your time and good efforts, but I just can’t block out the time to fill in the gaps.

Just give me a list of terms to explain: A, B, C, D and I am happy to.

@tim.one

And patience on its own can’t really be usefully applied recursively

I am just using it to pre-process once.
Then proceed to fill the gaps with whatever algorithm.

@tim.one

However, as you’ve shown now, it is possible to make diffllib’s “longest contiguous” approach run “almost always” in practical linear time. That will never be so for Meyers.

@tim.one

and an entirely different approach than difflib’s is theoretically on the table too - but not for me at this time.

Exactly. Thus the idea, which is a minor tweak of difflib’s approach as opposed to something entirely different.

Very simple. LCSUB is found starting at (i, j), ending at (i2, j2):

       i    i2
-------|----|--
     --|----|------
       j    j2

Check if it is skewed (as above). If yes, then align at i and j2 if positively skewed (i2 and j if negatively):

            A
     -------|----|--
     --|----|------

        1       2
     |------|------|

Calculate 2 extra candidates from ranges 1 and 2.

Now we have 3 LCSUB candidates.
All that is left is to decide which is the best.
Of course the original is longest so it doesn’t work by simply checking the length.
But we can go 1 recursion depth down for each of them and compare the sum of results -

sum(LLCSUB_candidate, LLCSUB_on_the_left, LLCSUB_on_the_right).

---

Most of the time this will have no impact.
However, when the matched block (LLCSUB) is very skewed, this can improve quality by a fair bit. Especially when kicks in at initial recursion levels.

[tim.one (Tim Peters)]

@dg-pb

It is difficult to communicate as the 2 terms are very similar and there isn’t a clear agreed abbreviation (at least as far as I know).

All the more reason not to use abbreviations at all, without spelling out what they mean.

1. LCS (Longest Common Subsequence) - non-contiguous alignment
2. LCSUB (Longest Common Substring) - single longest contiguous substring

Which, in my head, I call 'seq" and “str”. But that’s my private vocabulary to streamline my own internal dialogue - I hope never to use that when communicating with others.

Extra L prefix just means “Length of”.

All obvious to the most casual observer

Exactly. Thus the idea, which is a minor tweak of difflib’s approach as opposed to something entirely different.

Very simple. LCSUB is found starting at (i, j), ending at (i2, j2):

       i    i2
-------|----|--
     --|----|------
       j    j2

Check if it is skewed (as above). If yes, then align at i and j2 if positively skewed (i2 and j if negatively):

            A
     -------|----|--
     --|----|------

        1       2
     |------|------|

Calculate 2 extra candidates from ranges 1 and 2.

Now we have 3 LCSUB candidates.
All that is left is to decide which is the best.
Of course the original is longest so it doesn’t work by simply checking the length.
But we can go 1 recursion depth down for each of them and compare the sum of results -

sum(LLCSUB_candidate, LLCSUB_on_the_left, LLCSUB_on_the_right).

Most of the time this will have no impact.
However, when the matched block (LLCSUB) is very skewed, this can improve quality by a fair bit. Especially when kicks in at initial recursion levels.

I wouldn’t know, and can’t guess whether it’s of higher quality some of the time, always, or never. “Sum of total match points” isn’t something I think people are attuned to, neither to “balance”. They read diffs top to bottom, not from a bird’s eye view. A case can be made, though, for that they are attuned to “sum of total matches that fit on a screen”, and to the extent fiddling can improve that local measure, it’s probably a good thing.

OTOH, I’ve found over the years that people easily grasp the idea that difflib synchs on the longest contiguous junk-free match, period. Any complication to that mental model is unattractive on that ground just because it’s more complicated. So is making any change to results unattractive - difflib is old and stable code.

[dg-pb]

@tim.one

So is making any change to results unattractive - difflib is old and stable code.

Not considering this for anything close to defaults.

Why I brought this up is as I thought of possibility of adding it into new Matcher (turned off by default):

class NewSequenceMatcher(SequenceMatcherBase):
    def __init__(self, isjunk, a, b, skew_adjusted=False):
        pass

Also, thinking of not having autojunk=True argument at all. If people want autojunk, then the good old SequenceMatcher is the right choice.

Thus,
These would be equivalent in terms of result:

matcher = SequenceMatcher(autojunk=False)
new_matcher = NewSequenceMatcher()

SequenceMatcher offers performance optimization (by default):

SequenceMatcher(autojunk=True)

New sequence matcher offers quality improvement (by opt-in):

NewSequenceMatcher(skew_adjusted=True)

---

So:

1. Regarding autojunk not being in NewSequenceMatcher - I think this is good idea - would make code simpler. How does this sound for you?
2. Regarding skew_adjusted. Would need to generate some more proof on real diffs that show the value. But will very likely do that sooner or later, so just thought will share the idea a bit in advance.

[tim.one (Tim Peters)]

@dg-pb

Not considering this for anything close to defaults.

Good!

Why I brought this up is as I thought of possibility of adding it into new Matcher (turned off by default):

class NewSequenceMatcher(SequenceMatcherBase):
    def __init__(self, isjunk, a, b, skew_adjusted=False):
        pass

Ditto. skew_adjusted is like autojunk in the sense of “do something different that may improve diff quality by not wholly documented magic”. But such things should be off by default.

Also, thinking of not having autojunk=True argument at all. If people want autojunk, then the good old SequenceMatcher is the right choice.

autojunk was a failed experiment. Better not to propagate it into a new class.

So:

1. Regarding autojunk not being in NewSequenceMatcher - I think this is good idea - would make code simpler. How does this sound for you?

+1! Nuke that sucker

2. Regarding skew_adjusted. Would need to generate some more proof on real diffs that show the value. But will very likely do that sooner or later, so just thought will share the idea a bit in advance.

It’s an interesting idea. I can’t guess how it will turn out. It’s off to a good start, though, by focusing on “local” diff improvements. I think “histogram” does well because rare lines like

# Analyze the graph and raise CycleError if there's a cycle.

tend to “stick” to very distinct conceptual blocks of code during editing, and so synching on them prevents accidental “minimal edit distance” matches of identical lines of boilerplate code in surrounding distinct conceptual blocks.

Given such highly relevant synch pairs, though, I doubt it matters all that much which algorithm is used to do intra-block diffing. SequenceMatcher recurses on itself because it was already written

[dg-pb]

Did a bit more testing.
Brought in some complex and large diff files.

• Gestalt(aj=0) == difflib(autojunk=False)
• difflib(aj=1) == difflib(autojunk=True) (naturally)

case	Myers	Patient Myer	difflib(aj=1)	Gestalt(aj=0)	Gestalt SkewFix
(L) diff_key ( 15, 15)	8	8 0	5 -3	5 -3	8 0
(L) diff_mid1 ( 28, 27)	11	11 0	11 0	11 0	11 0
(L) diff_mid2 ( 128, 128)	73	63 -10	72 -1	72 -1	72 -1
(L) diff_mid3 ( 131, 131)	63	62 -1	50 -13	50 -13	57 -6
(L) difflib.py ( 2041, 2334)	1883	1882 -1	1878 -5	1879 -4	1879 -4
(L) linux_sched.c (11373, 11832)	10844	10839 -5	10793 -51	10837 -7	10844 0
(L) react.js ( 3555, 3337)	2631	2581 -50	2568 -63	2581 -50	2582 -49
(L) three.js (36282, 36793)	30688	30620 -68	25877 -4811	30588 -100	30601 -87
(L) webpack.js ( 2327, 3429)	929	886 -43	772 -157	899 -30	912 -17
-----
Total:	47130	46952 -178	42026 -5104	46922 -208	46966 -164
Avg % diff:	0%	2.46%	10.58%	7.25%	1.68%
Runtime (s):	30.257	0.225	0.54	0.468	0.572

Key points:

• For problems of size where speed matters, performance degradation of new methods compared to difflib(aj=1) is negligible (Gestalt(aj=0) without SkewFix can be even faster).
• Patient Myers (histogram) sacrifices 178 matches for the sake of quality.
• Gestalt(aj=0) is major improvement on difflib(autojunk=True)
• Gestalt SkewFix (hopefully) increases the quality, while at the same time bringing sacrificial match count down (naturally) to 164 (even lower than Patient Myers).

How do I think that it improves quality?
Think of a case:

lines1 = 'aa_bb_cc_dd_ee_xxx'
lines2 = 'xxx_aa+bb+cc+dd+ee'

It is the major weak point of Gestalt(aj=0).
It will match xxx and it will be it.

Gestalt SkewFix amends this weakness to a certain degree, which to my best estimate is sufficient in practice.

At the same time, it fully retains the core mechanism of matching by blocks.
It just considers few more combinations so to be a bit less greedy.

---

Also, I did individual case analysis by extracting more challenging piece from webpack.js ~300LOC.

Then produced html diff files.
And gave it to AI to investigate differences.

You can see them at: Wormhole - Simple, private file sharing
Markdown file with AI analysis is also there.

SkewFix seems to deliver on what is expected from it.

[tim.one (Tim Peters)]

@dg-pb

,…
How do I think that it improves quality?
Think of a case:

lines1 = 'aa_bb_cc_dd_ee_xxx'
lines2 = 'xxx_aa+bb+cc+dd+ee'

It is the major weak point of Gestalt(aj=0).
It will match xxx and it will be it.

Having trouble parsing that. Are those two blocks of six lines each? Where the lines are conceptually separated by some mix of underscores and plus signs?

If so:

• Weird
• Yes, the current scheme will just match the “xxx” line.

Gestalt SkewFix amends this weakness to a certain degree, which to my best estimate is sufficient in practice.

To what degree? Please spell out what it does instead.

…
And gave it to AI to investigate differences.

You can see them at: Wormhole - Simple, private file sharing
Markdown file with AI analysis is also there.

I urge those interested to follow the link and click on the .md file before it all disappears. The “AI analysis” is quite helpful, and makes what looks to be a good case for that pursuing “skew” is worthwhile, materially improving the human coherence of diffs locally in some cases.

SkewFix seems to deliver on what is expected from it.

Looks promsing, yes!

[dg-pb]

@tim.one

Having trouble parsing that. Are those two blocks of six lines each? Where the lines are conceptually separated by some mix of underscores and plus signs?

Each character is a line.
Same character represents identical lines.
Let’s remove + from lines 2 - same result anyway and more realistic.
So essentially, we removed some lines in between the blocks (_) and moved xxx to the beginning.
Quite realistic I think - removed some comment lines in between functions and moved one big function from end to start.

lines1 = 'aa_bb_cc_dd_ee_xxx'
lines2 = 'xxxaabbccddee'

@tim.one

To what degree? Please spell out what it does instead.

I will give code so to be exact.
Essentially, it looks for contiguous substrings in several appropriate regions that excludes current the region of current matched block.
Either by excluding it from sequence 1, sequence 2 or both.

i, j, k = x = _find(seq1, *current_ranges)
alo, ahi, blo, bhi = obj_or_range
i2 = i + k
j2 = j + k
# NOTE: -1 <= skew <= 1
skew = (i - alo) - (ahi - i2) + (bhi - j2) - (j - blo)
size1 = ahi - alo
size2 = bhi - blo
skew /= (size1 + size2)
if abs(skew) >= skew_fix:
    std_split = 0
    candidates = [x]
    if skew > 0:
        # ---------####--
        # --####---------
        candidates.append(_find(seq1, alo, i, j2, bhi))
        candidates.append(_find(seq1, i, ahi, j2, bhi))
        candidates.append(_find(seq1, alo, i, blo, j2))
    else:
        # --####---------
        # ---------####--
        candidates.append(_find(seq1, i2, ahi, blo, j))
        candidates.append(_find(seq1, alo, i2, blo, j))
        candidates.append(_find(seq1, i2, ahi, j, bhi))
    
    triples = []
    for candidate in candidates:
        triple = (
            _find(block_in_lower_region),
            candidate,
            _find(block_in_upper_region
        )
        triples.append(triple)

Then it goes on evaluating 2 nearby matches for each candidate - one on the left and one on the right - usual stuff.
So each candidate is 3 consecutively matched blocks.

Then the one which has the highest sum length of all 3 is picked.

So all 3 blocks of best candidate are picked.
Then recurse in gaps.

It really is just 1 step lookahead with few appropriate guesses

[tim.one (Tim Peters)]

@dg-pb

Each character is a line.
Same character represents identical lines.
Let’s remove + from lines 2 - same result anyway and more realistic.
So essentially, we removed some lines in between the blocks (_) and moved xxx to the beginning.
Quite realistic I think - removed some comment lines in between functions and moved one big function from end to start.

lines1 = 'aa_bb_cc_dd_ee_xxx'
lines2 = 'xxxaabbccddee'

OK - “lines” really have nothing to do with this - as far as the matcher is concerned, we can take those inputs exactly as given: sequences of characters.

I’m not asking about algorithm here, but about results. Here are the results we get today:

from difflib import SequenceMatcher
k = SequenceMatcher(None,
                    'aa_bb_cc_dd_ee_xxx',
                    'xxxaabbccddee',
                    autojunk=False)
for m in k.get_opcodes():
    print(m)

which displays

('delete', 0, 15, 0, 0)
('equal', 15, 18, 0, 3)
('insert', 18, 18, 3, 13)

So it matched all and only the “xxx” block.

What would it match under “skew” instead - not “how?”, but “what?”?

By eyeball, it you go on to compare ‘aa_bb_cc_dd_ee’ with ‘aabbccddee’, the longest contiguous match it can find is of length 2 instead (5 of them, of which the leftmost is ‘aa’). Regardless of whether ‘xxx’ is included in one of them too (in which cases the ‘xxx’ won’t match anything).

Longest common subsequence (not necessarily contiguous) would align the five blocks of two each in such cases, but unless I’m missing something fundamental, “skew” is sticking to longest common substring (contiguous). Or you’re doing multiple levels of trying to find better matches.

I’m not looking for details so much as conceptual clarity here. Complete results aid that.

[dg-pb]

@tim.one

but “what?”?

It’s output, in this case will be identical to Longest Common Non-contiguous subsequence:

   aa_bb_cc_dd_ee_xxx
xxxaa bb cc dd ee

After it finds xxx block, it tries alternatives.
One of them will inevitably be:

aa_bb_cc_dd_ee_xxx
aabbccddee

(s2 prefix removed ending at the end of xxx)
So it finds: aa

So we have 2 candidates:

1. xxx
2. aa

Now we evaluate 2 nearby matches for each:

1. xxx - nothing on the left, nothing on the right
2. aa - nothing on the left, but finds bb on he right

It chooses between xxx and aa + bb.
Picks aa + bb as combined length is longer.

[tim.one (Tim Peters)]

aa_bb_cc_dd_ee_xxx
xxxaabbccddee

If I’m following (unclear), the results will look like:

• insert ‘xxx’
• ‘aa’ is equal
• delete ‘_’
• ‘bb’ is equal
• delete ‘_’
• ‘cc’ is equal
• delete ‘_’
• ‘dd’ is equal
• delete ‘_’
• ‘ee’ is equal
• delete ‘_xxx’

Right or wrong?

And it’s not that you get that result “in one gulp”, but that skew aligns ‘aa’ and ‘bb’ at the start, pumping out the “insert ‘xxx’ first”, followed just by the parts that deal with ‘aa’ and ‘bb’.

Which leaves it with

_cc_dd_ee_xxx
ccddee

and then the rest works out just by matching leftmost blocks.

[dg-pb]

@tim.one

Right or wrong?

Right.

@tim.one

And it’s not that you get that result “in one gulp”, but that skew aligns ‘aa’ and ‘bb’ at the start, pumping out the “insert ‘xxx’ first”, followed just by the parts that deal with ‘aa’ and ‘bb’.

Precisely.

---

Furthermore, this is just one alternative.
It considers few more (the definite optimal list of these is still not final) and there is another important one:

      1/3       start of `xxx`
      |        |
aa_bb_cc_dd_ee_xxx
xxxaabbccddee
   |         +end
  end of xxx

# Leaving it with
cc_dd_ee_
aabbccddee

Which will match: cc
Then 2 surrounding ones will be: bb and dd
Thus it will pick combination bb + cc + dd of length 6 as the best one.
So it all boils down to strategy for picking alternative candidates to capture opportunity cost.

---

Furthermore, did a bit more testing and in terms of quality, the end result of this improvement is closer to Myers diff (Longest Common Non-contiguous Subsequence) than to histogram diff. But more structured due to its block orientation.

Without this improvement result of gestalt can still be similar in many cases.
However, its output is rather unreliable as there is uncertainty what to expect:

1. Something similar to Myers diff?
2. Or will it match large unbalanced block and skew the result?

So this improvement makes the quality of result more consistent.
Where result can be expected to be:

1. Similar to Myers diff in terms of number match points (naturally a bit lower)
2. Rough alignment is also similar to Myers diff. i.e. big gaps in similar places.
3. But the output is a bit cleaner due to its block oriented nature.

---

Patience / histogram method is a different breed all together.
Thus, in the same way as patience method interpolates gaps with Myers diff, it can use gestalt (with or without the improvement above (preferably with)) to do the same.

[tim.one (Tim Peters)]

@tim.one

About “leftmost”, @dg-pb,. which algorithm did you start from? Like just about everything else, there are many ways to approach building a suffix automaton (and I lost count of how many radically different ways are out there to build suffix arrays). Perhaps you started from a base that did address “leftmost”?

I ask because “leftmost guaranteed” doesn’t seem common. The bot wasn’t just making things up. For example, this appears to be an excellent introduction written by an actual human

Suffix Automaton - Algorithms for Competitive Programming

Scroll way down to the “First occurrence position” section and you’ll find a briefer version of the detailed account Gemini gave me.

Faintly made enough time to nail this down.

The referenced page, and Gemini, said a “first_pos” field had to added to each state. That’s in addition to the “everyone uses these” transition table, suffix link, and length (length of the path from the initial state to this state) fields.

s.first_pos is the smallest index is the string such that starting from the initial state ends up transitioning to state “s”. So pretty obviously is the leftmost starting position of the substring “s” represents. But nothing much can be inferred about any other paths that land on “s”.

Looks like @dg-pb added an “endpos” field instead. Same thing, really, but recording instead the ending index of the leftmost substring landing on “s”. Its starting index is thus just s.endpos + 1 - s.length.

So that’s how it manages to return the index of the leftmost occurrence in the SAM - but can’t know about other indices at which state “s” may match, so can’t do range-restricted searches.

ChatGPT-5 suggested to me that range restriction could be done by adding a field with a set recording all the ending indices of substrings landing on “s”.

But that’s nuts For example for string “xxxx”, the first state beyond the initial state would have to record {0, 1, ,2, 3}, and for the state after that, {1, 2, 3}, …, and so on. It can grow to a quadratic number of ints in all.

The bot went on to suggest ways that could likely greatly compress a naïve implementation of that, but that quickly got ever more complicated.

We agreed that, in this context, it would be better to just live with rebuilding the SAM, especially since the ranges being compared shrink as the process goes on.

[dg-pb]

For test cases above, I checked how long it takes to run full algorithm versus just calculating the first longest substring.

It is roughly 10x faster.

Which is the exactly how much slower Suffix Array runs than SAM.

Which is just a coincidence.

But for our application it means that using suffix array (modified for range queries hoping that it doesn’t make it slower) would mean much more complexity and very similar result.

---

Whether suffix array can even do it (while retaining performance) is another question.

It surely can not without some serious modifications.

[tim.one (Tim Peters)]

@dg-pb

Whether suffix array can even do it (while retaining performance) is another question.

It surely can not without some serious modifications.

Already sketched that range restriction requires “serious modifications” indeed when using suffix arrays. See earlier comments about “sliding window” - looking at just adjacent LCP entries can’t work. It requires looking at regions, of arbitrary size, in the LCP, and a special queue data structure that efficiently keeps track of “the smallest” value currently in the queue across arbitrary sequences of pushes and pops.

Don’t brush that off. ChatGPT says:

@ChatGPT-5

You’re circling exactly the right idea, and the good news is: yes, a sliding‑window over the suffix array + LCP array can solve the slice‑restricted LCS problem cleanly, with only moderate pain. The trick is to treat the suffix array as a sequence of “events” (suffixes from A or B), and the LCP array as the “edge weights” between adjacent events. Once you do that, the slice restrictions become a filtering problem rather than a structural one.

[much text omitted here]

3. Track the minimum LCP inside the window

This is the only nontrivial part. [emphasis added by Tim]
You need to maintain:

\min (LCP[L+1],\dots ,LCP[R])

as the window slides.

Seemingly everyone gets this wrong at first (including me). A window is not needed for unconstrained LCSubstring searches. And the bot overlooked a crucial fine point there: the LCP doesn’t contain values limited to the slice bounds. Accounting for that requires a distinct on-the-fly adjustment. Candidates must begin in their respective slice bounds, but their actual LCP values have to account for how much of the prefix “still fits” in the slice bounds. That may be smaller than the value in the LCP array. Easy, but also easy to overlook, and crucial.

“Sliding window” is delicate code, but is applied to many kinds of constrained problems with suffix arrays.

But I don’t want to talk about suffix arrays here anymore - gave up on that idea. SAMs are far superior on several measures for the task at hand.

[tim.one (Tim Peters)]

One last observation about suffix arrays: while they can solve range-restricted LCSubstring problems in linear time without rebuilding anything, the suffix and LCP arrays contain len(A) + len(B) + possibly_tiny_int_le2_depending entries throughout, no matter how narrow the slices currently of interest. So they spend ever more of their time “skipping over” irrelevant entries.

A form of which the current approach also suffers from: the b2j dict continues to hold the indices in seq2 for all non-junk characters, even as they become irrelevant. They’re skipped over one at a time as needed.

Because they’re in sorted order, a binary search could be used instead to find the first (if any) index relevant to the current slice bounds, but the few times I played with that, it complicated the code for no measurable speed gain. Most index lists are short.

[dg-pb]

@tim.one

One last observation about suffix arrays

Yes! And this is what SAM is good at!

It doesn’t care about how big s2 was built.
It runs find(s1) in O(len(s1)).

And one find iteration is tens of times faster than one build iteration.

Thus, I thought if it is possible to exploit it.

---

So even if built range is not exactly the the same…
But as long as query range is within the built range, we can do a quick check.

We can just query for longest substring on the larger (already built) range.
Then, if that result is in our actual query range, then it is the correct substring.

E.g.: We have SAM fully built for full range of.

s2 = 'aaa_bbbb_ccc'

We need to query 'aaa' within s2[0:4].

We query and get result: aaa @ s2[0:3].
As long as 0:3 is within 0:4, it is correct answer and no rebuilding needed.

---

And luckily, this suits our problem quite well and results in 30-35% faster runtime.

case	Myers	Patient Myer	difflib(aj=1)	Gestalt(aj=0)	Gestalt SkewFix
-----
Runtime Before (s):	30.647	0.472	0.501	0.501	0.61
Runtime After (s):	31.262	0.453	0.514	0.331	0.435

This is my final optimization.
(Hope it isn’t going to be the same with me here as with you and suffix arrays )

If better performance than that is needed, then C acceleration for SAM should result in 10-20x faster runtime.

[tim.one (Tim Peters)]

BTW, since I swore off talking about suffix arrays, here’s more

While they can efficiently handle range restrictions, one reason I didn’t pursue them is that I got stuck enforcing “leftmost maximal matches”. A combined (A+B) suffix array has the raw information needed to enforce that, but not in a way I was able to efficiently exploit. My chatbot tried several ways of its own today, and also struck out. Suffix arrays are wholly ordered lexicographically, nothing about index order.

You can do it by building a suffix array just for B, and then do repeated binary searches for suffixes of A (which is slower!), but then we’re also back to rebuilding B each time B’s conceptual slice changes, and building SAMs goes faster too than building suffix arrays.

[dg-pb]

@tim.one

building SAMs goes faster too than building suffix arrays

At least for pure Python implementations that I have, building Suffix Array takes as much time as doing full get_matching_blocks with SAM rebuilds.

And that was before the caching idea…