# Algorithmic complexity of difflib **URL:** \ **Category:** Ideas\ **Created:** [January 21, 2026, 2:02am UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844 "2026-01-21T02:02:32Z")\ **Posts on this page:** 17\ **Page:** 7
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 14, 2026, 7:41pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/123 "2026-03-14T19:41:40Z")
> [@dg-pb](#): > > I consider `seq1` as base and `seq2` as version, thus getting earlier match in `seq2` is somewhat desirable. Meaning checking `h` of `seq1` in table of `seq2` first. I don’t know that makes any real difference. I just like to define the result of ambiguous cases 😉,. In the absence of cyclic extensions, I can see one “reason” to favor matching “earliest in version” when the lengths are equal: `base` is usually shorter than `version` (many kinds of files grow much more often than they shrink), so you want to advance to the end of `base` as early as possible. Incrementing its current index by the match length is “better” for that purpose than incrementing some earlier index in `base`. But that’s too glib to convince even me 😉. ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [March 14, 2026, 8:56pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/124 "2026-03-14T20:56:42Z")
> [@tim.one](#): > > implications of “k-cyclic” extensions Did some quick testing: > **CODE: \`delta\_burns\_rec** > > ```python > def delta_burns_rec(seq1, seq2, nrec=2, **kwds): > assert nrec > 0 > all_matches = [] > while 1: > matches = delta_burns(seq1, seq2, **kwds) > all_matches.append(matches) > nrec -= 1 > if nrec: > if not isinstance(seq1, list): > seq1 = list(seq1) > seq2 = list(seq2) > for i, j, k in matches: > seq2[j:j+k] = [_VOID] * k > else: > break > it = iter(all_matches) > matches0 = next(it) > for matches in it: > matches0.extend(matches) > if len(all_matches) != 1: > matches0.sort(key=lambda x: x[1]) > return matches0 > > ``` | | Delta Size (B) | Time (µs) | Peak (kB) | | --- | --- | --- | --- | | Reichenberger | 1200 | 92,392 | 280 | | Git | 1700 | 15,603 | 130 | | Single | 2700 | 5,601 | 130 | | Burns | 3045 | 5,181 | 85 | | Burns Cyclic | 3045 | 5,181 | 85 | | Burns Rec2 | 2700 | 16,248 | 170 | | SAM | 1200 | 6,060 / 13,229 | 1412 / 546 | Minor quality improvement. Doesn’t seem to be worth it. * * * Much better would be to find new ways to further reduce SAM’s memory. E.g. with 32bit ints. SAM’s memory becomes 376 kB. ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 14, 2026, 9:34pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/125 "2026-03-14T21:34:29Z")
Another possibility for the non-cyclic linear-time version: if matches are found of sufficient length in both sequences, record them both. Set the new i to the max new i either of them suggest, and likewise for j. Fraught with dangers, which I’ll gloss over, but in the example it would record both the `b` and the `c` blocks correctly on the same outer-loop iteration. > [@dg-pb](#): > > Much better would be to find new ways to further reduce SAM’s memory. > E.g. with 32bit ints. SAM’s memory becomes 376 kB. The killer attraction of the linear-time version is bounded memory use regardless of sequence length (the hash tables are the only large data structures, and they can never grow to hold more entries than the Rabin-Karp modulus), But giant files are niche cases I don’t expect CPyhon will ever cater to out of the box. So, yes, cutting SAM’s RAM use is the only thing of real value here 🙂 But your test cases apparently barely crack a megabyte even using boxed CPython ints - and using flat lists of ints was a great improvement over the earlier schemes that built per-node collections of ints. Exploiting that most nodes only have one transition gave another great improvement (most nodes don’t need the memory burden of “a dict” at all). I doubt there are other similarly straightforward big wins to be had, and at some point you have to say “good enough!” and leave it be, lest the code become incomprehensible. If it’s _that_ important, recode it in C, where using native machine ints is dead easy and obvious. Or maybe in Rust? That would be a hoot for sure 😉. ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [March 14, 2026, 11:08pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/126 "2026-03-14T23:08:41Z")
> [@tim.one](#): > > if matches are found of sufficient length in both sequences, record them both. Set the new i to the max new i either of them suggest, and likewise for j. Nice one! again. 1. If same match found, pick whichever 2. if non-overlapping, take both 3. if overlapping, pick longest one and trim the other. If trimmed match \>= nprfx, take the trimmed as well For case at hand +1 match for both cyclic and not: ```python >>> seq1 = "aaaabbbbccccdddd" >>> seq2 = "ddddccccbbbbaaaa" >>> delta_burns(seq1, seq2, cyclic=False) [(8, 4, 4), (4, 8, 4)] >>> delta_burns(seq1, seq2, cyclic=True) [(8, 4, 4), (4, 8, 4), (0, 12, 4)] ``` Not a common thing in real applications, but nice to have. ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 15, 2026, 6:00am UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/127 "2026-03-15T06:00:53Z")
Ya - that’s the idea. If’s a lot of fiddly checking, though, and I don’t want to bother with it. As an aside, my favorite bot has a repeated track record of failing to find very simple counter-examples to its optimistic speculations (although I ask it to speculate, as that sometimes leads in interesting directions). In this case it thought there may “be reasons” for why partial overlaps couldn’t occur. I found it annoying to think about 😉, but found a very simple one quickly enough. With prefix length 2, ``` S: bab T: aba ``` When i=j=0, `ba` is added to S’s table and `ab` to T’s. When they advance to 1, `ab` is added to S’s table and `ba` to T’s. S’s new prefix `ab` is found in T at index 0, and T’s new prefix `ba` in S’s at index 0. So the matches are (0, 1, 2) and (1, 0, 2). Partial overlap already! I swear the bot laughed 😉 ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 15, 2026, 8:45pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/128 "2026-03-15T20:45:25Z")
Another twist for the linear-time approach. Hash functions aren’t perfect, and collisions _will_ happen. The paper realized that, but didn’t offer a coherent solution, and I think gave up too soon on an obvious, practical approach: map a hash to a _list_ of indices at which that hash appears. And it’s worse than the paper seems to acknowledge. It’s not just false positives that can hurt. Even with perfect hashing, only the first instance of a given prefix will be recorded in a table. You match starting there, or not at all. Which is sold as “a feature”, but is really more a consequence of ensuring worst-case O(1) memory consumption. But it’s still O(1) if collision lists are capped at a fixed max length, or even recorded in a fixed capacity deque, discarding the oldest entry as needed (deque’s `maxsize=`). With a Rabin-Karp modulus near a million, restricting to just one entry is a minor memory burden. When matching, the first entry in a list that gives a “good enough” match can be taken, or probably better the longest match found across all entries. So long as the lists have a max length, still linear time. Gonzo complications could include fancy schemes to find the best overall match length across all non-overlapping possibilities across both sequences. Anyway, the bare idea is easy to code and can help. I haven’t pursued it seriously, though, and probably won’t. In my fiddling with applying this to files of Python code (viewed as sequences of lines), with prefix len 4, the largest (unrestricted-length) list seen had 6 entries (so 5 collisions). None of these were due to false positives. All were due to repetitions of the same prefix within a sequence. CORRECTION: there were two false positives total.in a different run. Because `hash()` is used to feed Rabin-Karp “an int” to work with when sequence elements are strings, it’s not consistent across runs (“hash randomization” for strings). ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [March 16, 2026, 12:26am UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/129 "2026-03-16T00:26:31Z")
> [@tim.one](#): > > map a hash to a _list_ of indices at which that hash appears. This is what original Reichenberg’s does, just without cap. And as far as I have gathered, what git uses is original Reichenberg with lists capped at 64. Prioritising early matches. Which makes it linear as well. * * * I have the same parameter for Burns & Long. I suppose it should help a bit - haven’t tested. > [@tim.one](#): > > discarding the oldest entry as needed Oldest or newest? 🙂 ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 16, 2026, 2:59am UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/130 "2026-03-16T02:59:22Z")
> [@dg-pb](#): > > > [@tim.one](#): > > > > map a hash to a _list_ of indices at which that hash appears. > > This is what original Reichenberg’s does, just without cap. In part, yes. Gemini tells me git’s binary diff is based on XDelta, and for files of byte sizes M and N: - Time complexity O(M + N) - Space complexity O(M) > [@](#): > > And as far as I have gathered, what git uses is original Reichenberg with lists capped at 64. Prioritising early matches. > Which makes it linear as well. As before, it’s not linear-time that’s the killer advantage of Burns & Long, but bounded memory use regardless of input sizes. There are a lot of algorithms now that produce copy/insert binary delta “patches”, but they may or may not have much else in common with Reichenberg’s early effort. > [@](#): > > I suppose it should help a bit - haven’t tested. Neither have I. But we’re not in the delta business, while tools like git are. I take it on faith that they’ve had many more eyeballs looking at the problem space, over much more time, and with far more testing data, than we’ll ever have. But, surprise: I didn’t know what the “git” line referred to when it showed up in one of your recent tables. But it was one of the slowest, despite that it was competing with Python code. Mysteries abound 😉 > [@](#): > > > [@](#): > > > > discarding the oldest entry as needed > > Oldest or newest? 🙂 In context, oldest. I was talking about a deque then. One of the tradeoffs. A minor advantage of deques is that you can pass a max size to the constructor and then forget about it. For example, my Rabin-Karp class never explicitly pops anything. The outgoing int is retrieved via `d[0]`, and is discarded by magic when the incoming int is appended. ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 16, 2026, 3:14am UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/131 "2026-03-16T03:14:28Z")
> [@tim.one](#): > > None of these were due to false positives. All were due to repetitions of the same prefix within a sequence. And there’s “a reason” for that. The two biggest files were collections of Python code I’ve collected over the years, one for Python2 and another for Python3. It’s often the case that a snippet is refined over time, with older versions not removed but preserved in `if 0:` blocks (which the compiler throws away). Quirky but useful 😉 So the same lines of code can appear over and over in the same file. There’s very little duplication between the two files, but repeated partial blocks are common within a file. So it never actually helped to check against all prefixes sharing the same hash (and, indeed, the same prefix). They overwhelmingly never matched cross-file at all. There were a few cross-file duplicates, like ```py def gcd(a, b): while b: a, b = b, a%b return a ``` Tiny stuff like that. But I was surprised to find a substantial block of 73 duplicated lines. I have no memory of writing that code even once - or of what it’s trying to accomplish 🤣. ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [March 16, 2026, 4:18am UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/132 "2026-03-16T04:18:02Z")
> [@tim.one](#): > > it’s not linear-time I think it is, just higher constants. 1. Compute hashes of seq1. Store lists up to 64 length for same hash value 2. Iterate through seq2 and when match, pick the best one from list found in hashtable of seq1 So (1) is clearly a single pass. For 2. We have O(length2 + 64 length1). So not in the same sense as Burns and Long, but theoretically linear time. > [@tim.one](#): > > I didn’t know what the “git” line referred to It referred to Reichenberg with hashlists of length 64. Exactly the above. I probed AI, it found me constants in source. Not sure how accurate this is, but this was a best rough estimate to what they do. This isn’t actually running git’s code, same pure Python code. > [@tim.one](#): > > A minor advantage of deques In spirit of Long & Burn, which doesn’t override if it already exists, I instead did: ```python if len(entry) < hash_max: entry.append(i) ``` It kind of makes sense from POV that earlier matches have higher probability of catching longer runs as they start earlier. But keeping recent ones might result in more of them. Again, would need to test it. But for now I will follow Long and Burns (and git) - as you said, they should have reasons. ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 16, 2026, 4:47am UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/133 "2026-03-16T04:47:33Z")
> [@dg-pb](#): > > > [@tim.one](#): > > > > it’s not linear-time > > I think it is, just higher constan Miscommunication - I wasn’t disputing that. More context: > As before, **it’s not linear-time** that’s the killer advantage of Burns & Long, but bounded memory use regardless of input sizes It wasn’t saying anything wasn’t linear-time, just that linear-time isn’t _the_ strongest selling point for Burns & Long - O(1) memory use is. As to memory use, the scheme you have in mind can be considered as O(1) space too, although it may be a stretch. I appreciate the clarification that the “git” line was actually referring to an informed guess about git’s approach to large binary files, but coded in Python. That explains a whole lot about the results 🙂 And I have no real guess about whether tossing older or newer hash collisions would give better results overall. I’m personally sticking to lists (toss newer ones), just because they’re lighter-weight data structures in Python, and overheads add up when there’s one for each hash code seen. ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [March 16, 2026, 8:29pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/134 "2026-03-16T20:29:40Z")
An observation: Full-blown Reichenberg takes a sequence, and for every contiguous subsequence of length `nprfx` maps its hash code to a list of all the starting indices that have the same prefix hash code. What if `nprfx` is 1? Then the “rolling hash” machinery is pointless, and it’s just mapping a sequence element’s hash code on its own to a list of all indices who elements’ hash codes are the same. And if the elements are themselves hashable by Python, it can be made exact (no false positives) just by using the element itself as the dict key. Python’s dict machinery then ensures that unequal elements with the same internal hash code resolve to different internal dict entries. Which, if you squint just a little, is exactly what difflib is currently doing with its `b2j` dict: mapping an element to a list of all indices at which it appears. They’re still not the same, but they rhyme 😉 It’s interesting how pragmatics can drive decisions. Reichenberg just wouldn’t be used with such small `nprfx`. It’s aimed at byte-level differencing, and a “copy 1 byte” output would consume more space than just including the byte verbatim in a block “insert these bytes” output. “Minimum match length” makes sense for them. With larger alphabets, difflib very much wants _not_ to preclude matching on a single element - indeed, at the limit, “element appears uniquely” is a high-value synch point for human eyes, and “appears rarely” is the heart of git’s “patience” and “histogram” higher-level text difference partitioning. difflib pretty much sucks at byte-level differencing, for “can become very slow” reasons (often “fixed” by autojunk, but at high cost in diff quality). It’s mondo cool that SAM has no “very slow” cases regardless of alphabet size. ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [March 21, 2026, 7:05pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/135 "2026-03-21T19:05:33Z")
> [@tim.one](#): > > It’s mondo cool that SAM has no “very slow” cases regardless of alphabet size. SAM is a structure that keeps on giving. It can do multi-pattern string search in at least 3 different ways. Two forward (compile patterns) and one reverse (compile text and search anything in it). Taking minimum between these ends up in line (or in extreme cases much better) than Aho Corasick with similar optimisation level. Furthermore, without additional structures it can be optimised along the lines of [DAWG-MATCH](https://web.archive.org/web/20240422031547/https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=d106a045f5a6b5dae3ef9d128c14a6a548364403). Aho needs additional mini DAWG structure, while SAM can take the role of both components. This gets complex and isn’t worth to do for pure Python implementation, but just a peek into possibilities. * * * To get back to `difflib` work. I think extensibility PR is valuable on its own. However, I am thinking whether new `class` is needed for Automaton-based Gestalt. Another possibility would be to use Automaton for `autojunk=False` - no one uses it with this parameter turned off now anyway (or isn’t this true?). It would be cleaner in a sense that there is 1 class that does Gestalt. Creating a new one that gives exactly same results as current matcher with `autojunk=False` does feel a bit… excessive (for single methodology). This would also solve the issue where people try to turn `autojunk` off. ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [August 8, 2026, 3:37pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/136 "2026-08-08T15:37:48Z")
## Update. Table below for various diff cases represents scores based on scoring function f(blocks) = \sum\_i^n \text{len}(block\_i)^{1.3} Thus, it is not a sheer individual matched line count (for which naturally exact LCS algorithm delivers optimal result), but a metric biased towards retaining large blocks, which is the main idea behind readable diffs by using `difflib`’s Gestalt pattern matching approach. Results would look much better for greedy [`Gestalt`](https://en.wikipedia.org/wiki/Gestalt_pattern_matching) methodology with higher powers in the formula above – without quality improvements `Gestalt`’s optimization function can be thought of as f(blocks) = \sum\_i^n \text{len}(block\_i)^{p\rightarrow\infty}. While `p=1.3` is adequately conservative and captures the real quality benefit by keeping the balance between amount of data matched and large block bias. It can be interpreted according to this equality: `c^p == (0.9c)^p + (0.2c)^p` - i.e. block of size `c` has the same value as 2 blocks: one of size `0.9c` and another of size `0.2c`. Table explanation: 1. `case` column: `name (length_of_seq1, length_of_seq2)` 2. `algorithm` column: values are scores according to f(blocks) = \sum\_i^n \text{len}(block\_i)^{1.3}. Number on the right of it is difference of this score compared to the one `Base`. 3. `avg % diff` = \frac{\sum \frac{f(alg\_i) - f(Base\_i)}{f(Base\_i)}}{\text{number of cases}} 4. `total % diff` is percentage difference of aggregate summed scores compared to `Base` 6 Algorithms: 1. `base` - standard exact LCS (implementation - bit vector) 2. `Patient Myer` - runs patience/histogram and defaults to (1) when runs out of options 3. `difflib(aj=1)` - SequenceMatcher(autojunk=True) 4. `difflib(aj=0)` - SequenceMatcher(autojunk=True) 5. `Gestalt2` - O(n) time / O(n) space optimization of `difflib(aj=0)`. As it can be seen, its results are identical are identical to `difflib(aj=0)`. 6. `Gestalt2B` - (5), but with `balancing=True`, which is an integrated and improved “Skew Fix” feature from earlier discussion which aims to amend issues of greedy commitment. So far it seems that it manages to retain complexity while delivers bigger quality improvement compared to initial version. | case | Base | Patient Myer | difflib(aj=1) | difflib(aj=0) | Gestalt2 | Gestalt2B | | --- | --- | --- | --- | --- | --- | --- | | [L] diff\_key ( 30, 30) | 32 | 32 0 | 28 -4 | 28 -4 | 28 -4 | 28 -4 | | [L] diff\_mid1 ( 56, 54) | 34 | 34 0 | 34 0 | 34 0 | 34 0 | 34 0 | | [L] diff\_mid2 ( 256, 256) | 297 | 301 4 | 240 -57 | 298 1 | 298 1 | 298 1 | | [L] diff\_mid3 ( 262, 262) | 224 | 226 2 | 105 -119 | 132 -92 | 132 -92 | 226 2 | | [L] difflib.py ( 4082, 4650) | 16865 | 16865 0 | 16874 9 | 16876 11 | 16876 11 | 16880 15 | | [L] linux\_sched.c (22746, 23664) | 92266 | 92266 0 | 92349 83 | 92486 220 | 92486 220 | 92494 228 | | [L] react.js ( 7110, 6674) | 16602 | 16602 0 | 16510 -92 | 16541 -61 | 16541 -61 | 16542 -60 | | [L] three.js (72564, 73586) | 288327 | 288354 27 | 147526 -140801 | 288779 452 | 288779 452 | 288883 556 | | [L] webpack.js ( 4654, 6858) | 3020 | 3020 0 | 2679 -341 | 2996 -24 | 2996 -24 | 3012 -8 | | [L] difflib PR ( 4206, 4582) | 13352 | 13352 0 | 13347 -5 | 13623 271 | 13623 271 | 13625 273 | | | | | | | | | | Total: | 431019 | 431052 33 | 289692 -141327 | 431793 774 | 431793 774 | 432022 1003 | | Avg % diff: | 0% | 0.22% | -14.54% | -5.19% | -5.19% | -0.93% | | Total % diff: | 0% | 0.01% | -32.79% | 0.18% | 0.18% | 0.23% | | Runtime (s): | 2.582 | 2.489 | 1.719 | 138.369 | 0.761 | 0.903 | * * * ## Performance Here are aggregate timings for datasets above scaled by a factor of 4 (`difflib(aj=0)` is removed as it is uncertain when it would complete): | Algorithm | Runtime (s) | | --- | --- | | Base (Bit Vector LCS) | 27.757 | | Patient Myer | 37.997 | | difflib(aj=1) | 27.527 | | Gestalt2 | 3.383 | | Gestalt2B | 3.989 | * * * ## Quality improvement of `Gestalt2B`. It is rather simple idea, which surprisingly manages to improve results in some properly tricky cases. The core issue that it solves is likely best represented by this: ```python seq1 = 'aaaa+bbbb+cccc+dddd+eeee+ffff' seq2 = 'bbbb-cccc-dddd-eeee-ffff-aaaa' print(gestalt2(seq1, seq2, balancing=0, aligns=False)) # [(0, 25, 4)] print(gestalt2(seq1, seq2, balancing=1, aligns=False)) # [(5, 0, 4), (10, 5, 4), (15, 10, 4), (20, 15, 4), (25, 20, 4)] ``` It also covers (to a reasonable degree) cases where the problem at hand is pure LCS: ```python seq1 = '_a ___a_bcd_____ a_ef_g__' seq2 = 'cb+e+d+++af+g++' print(gestalt2(seq1, seq2, balancing=0, aligns=False)) # [(1, 9, 1), (18, 10, 1), (20, 12, 1)] print(gestalt2(seq1, seq2, balancing=1, aligns=False)) # [(7, 1, 1), (9, 5, 1), (15, 9, 1), (18, 10, 1), (20, 12, 1)] ``` * * * ## To sum up I have been working on more complex methods to achieve quality. However, I am content with what I have arrived here – it is unlikely that quality improvements of more complex methods would justify needed complexity and inevitable difference in performance – the above delivers reasonable and reliable quality with incredible performance. No fallbacks, no hybrid strategies, just original gestalt pattern matching with a bit of situational awareness. Implementation is manageable – (not counting `SuffixAutomaton` and some general utilities) it is roughly 300LOC (of which ~30% is “skew\_fix” quality improvement). I am pleased with the results. Thank you to everyone who participated and followed - this was one of the most enjoyable discussions over my time here. ---
**Author:** ![pf\_moore](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/pf_moore/32/35_2.png) [@pf\_moore](https://discuss.python.org/u/pf_moore)\ **Post date:** [August 8, 2026, 4:41pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/137 "2026-08-08T16:41:01Z")
> [@dg-pb](#): > > Thank you to everyone who participated and followed - this was one of the most enjoyable discussions over my time here. Cool. For those of us who have been following with interest, but haven’t understood all the technical details, do you intend to publish the resulting code as a library on PyPI and/or submit it as a PR to the stdlib? No pressure - I don’t have an immediate need for this, I’m just curious 🙂 ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [August 8, 2026, 6:24pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/138 "2026-08-08T18:24:43Z")
> [@pf\_moore](#): > > do you intend to publish the resulting code as a library on PyPI and/or submit it as a PR to the stdlib? Intent was always to improve `difflib`. There is a standing [PR](https://github.com/python/cpython/pull/145210) which adds composability so that new matchers can be used with all utilities there. So that is the 1st step. After that is done, I had 2 trajectories: 1. PR1 for improved utilities and a bit of preparation, then PR2 with SAM based matcher above. 2. Improving existing `SequenceMatcher` so that the issues with default matcher are reduced to a minimum. See [Improvement on current `difflib.SequenceMatcher` algorithm](https://discuss.python.org/t/improvement-on-current-difflib-sequencematcher-algorithm/106221) Will see how this goes. From my experience things are moving rather slowly when it comes to algorithms. ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [August 8, 2026, 8:14pm UTC](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844/139 "2026-08-08T20:14:44Z")
TLDR: Quality adjustment is doing its job quite well. * * * Ran comparisons against exact algorithm `O(n^3)` that optimizes exact f(p)=\sum \text{len}(\text{block}\_i)^p with different powers. Used 2 different metrics to determine closest matching power in terms of achieved results: 1. Order-oblivious distribution comparison 2. actual `sum(size^p for size in blocks)` I looked at averages across 14 datasets. And both metrics agree on a **flat optimum spanning roughly p≈1.3–1.75**. This is where `exact_optimizer(p)` results match `gestalt2`’s results best. Exact peaks at: | closest matching powers | distribution ratio | sum(len^p) | | --- | --- | --- | | balancing=False | p=6.0 | p=100.0 (max in the test) | | balancing=True | p=1.4 | p=1.75 | It is reassuring that despite `balancing` being a correction mechanism that largely stays dormant, its actions have an intended effect. It uses `power=1.3` to make decisions and the fact that it has such global effect means that it chooses good time to act. Of course, given the nature of methodology it will inevitably have variance in its effect and even the odd extreme fail case, but all in all I think this suggests strong possibility of this being worthwhile. [Previous page](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844.md?page=6)