Repository navigation
difflib.SequenceMatcher not matching long sequences #47235
Description
| BPO | 2986 |
|---|---|
| Nosy | @tim-one, @warsaw, @birkenfeld, @terryjreedy, @jcea, @pitrou, @bitdancer |
| PRs | |
| Superseder | |
| Files |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = 'https://github.com/terryjreedy'
closed_at = <Date 2010-11-25.20:23:36.839>
created_at = <Date 2008-05-27.20:29:56.025>
labels = ['type-bug', 'library', 'docs']
title = 'difflib.SequenceMatcher not matching long sequences'
updated_at = <Date 2019-11-07.16:24:52.380>
user = 'https://bugs.python.org/hagna'bugs.python.org fields:
activity = <Date 2019-11-07.16:24:52.380>
actor = 'python-dev'
assignee = 'terry.reedy'
closed = True
closed_date = <Date 2010-11-25.20:23:36.839>
closer = 'terry.reedy'
components = ['Documentation', 'Library (Lib)']
creation = <Date 2008-05-27.20:29:56.025>
creator = 'hagna'
dependencies = []
files = ['17001', '18171', '18719', '19538', '19569', '19675']
hgrepos = []
issue_num = 2986
keywords = ['patch']
message_count = 37.0
messages = ['67428', '84387', '84446', '84449', '93438', '103660', '108636', '108856', '109090', '109442', '109507', '109636', '109639', '109654', '110251', '110261', '111372', '111425', '112116', '112120', '112490', '115335', '115419', '115787', '120713', '120927', '120939', '120992', '121079', '121596', '121662', '121697', '121902', '122335', '122337', '122338', '122401']
nosy_count = 19.0
nosy_names = ['tim.peters', 'barry', 'georg.brandl', 'terry.reedy', 'jcea', 'jimjjewett', 'sjmachin', 'gjb1002', 'ggenellina', 'pitrou', 'rtvd', 'vbr', 'LambertDW', 'hodgestar', 'hagna', 'r.david.murray', 'eli.bendersky', 'janpf', 'mrotondo']
pr_nums = ['17082']
priority = 'high'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = '10534'
type = 'behavior'
url = 'https://bugs.python.org/issue2986'
versions = ['Python 2.6', 'Python 3.1', 'Python 2.7', 'Python 3.2']
Activity
hagna commentedon May 27, 2008
The following code shows no matches though the strings clearly match.
birkenfeld commentedon Mar 29, 2009
Tim, I think you've had some enlightening comments about difflib issues
in the past.
mrotondo commentedon Mar 30, 2009
From the source, it seems that there is undocumented behavior to
SequenceMatcher which is causing this error. If b is longer than 200
characters, it will consider any element x in b that takes up more than
1% of it's contents as "popular", and thus junk.
So, in this case, difflib is treating each individual digit as an
element of your sequences, and each one takes up more than 1% of the
complete sequence b. Therefore, each one is "popular", and therefore
ignored.
A snippet which demonstrates this:
Up til i=200, the strings match, but afterwards they do not because "a"
is "popular".
Strangely, if you get rid of the "b" at the beginning of b, they
continue to match at lengths greater than 200. This may be a bug, I'll
keep looking into it but someone who knows more should probably take a
look too.
The comments from difflib.py say some interesting things:
# b2j also does not contain entries for "popular" elements, meaning
# elements that account for more than 1% of the total elements, and
# when the sequence is reasonably large (>= 200 elements); this can
# be viewed as an adaptive notion of semi-junk, and yields an enormous
# speedup when, e.g., comparing program files with hundreds of
# instances of "return NULL;"
This seems to mean that you won't actually get an accurate diff in
certain cases, which seems odd. At the very least, this behavior should
probably be documented. Do people think it should be changed to get rid
of the "popularity" heuristic?
bitdancer commentedon Mar 30, 2009
On Mon, 30 Mar 2009 at 00:40, Mike Rotondo wrote:
A better way, I think, would be to provide a way to turn
it off (and then document it, of course).
pitrou commentedon Oct 2, 2009
The popularity heuristic could be tuned to depend on the number N of
distinct elements in the sequence, and kick in if an element appears say
more than 1/(N**0.5) of the time.
vbr commentedon Apr 19, 2010
I just stumbled on some seemingly different unexpected behaviour of
difflib.SequenceMatcher, but it turns out, it may have the same cause, i.e. the "popular" heuristics.
I hopefully managed to replicate it on an illustrative sample text - in as included in the attached file. (I also mentioned this issue in hte python-list
http://mail.python.org/pipermail/python-list/2010-April/1241951.html but as there were no replies I eventually found, this might be more appropriate place.)
Both strings differ in a minimal way, each having one extra character
in a "strategic" position, which probably meets some pathological case
for difflib.
Instead of just reporting the insertion and deletion of these single
characters (which works well for most cases - with most other
positions of the differing characters), the output of the
SequenceMatcher decides to delete a large part of the string in
between the differences and to insert the almost same text after that.
The attached code simply prints the results of the comparison with the
respective tags, and substrings. No junk function is used.
I get the same results on Python 2.5.4, 2.6.5, 3.1.1 on windows XPp SP3.
I didn't find any plausible mentions of such cases in the documentation, but after some searching I found several reports in the bug tracker mentioning the erroneous output of SequenceMatcher on longer repetitive sequences.
besides this
http://bugs.python.org/issue2986
e.g.
http://bugs.python.org/issue1711800
http://bugs.python.org/issue4622
http://bugs.python.org/issue1528074
In my case, disabling the "popular" heuristics as mentioned by John Machin in
http://bugs.python.org/issue1528074#msg29269
seems to have solved the problem; with a modified version of difflib containing:
the comparison catches the differences in the test strings as expected - i.e. one character addition and deletion only. It is likely, that some other use cases for difflib may rely on the "popular"-heuristics but it also seems useful to have some control over this behaviour, which might not be appropriate in all cases.
(The issue seems to be the same in python 2.5, 2.6 and 3.1.)
regards,
vbr
terryjreedy commentedon Jun 25, 2010
This appears to be one of at least three duplicate issues: bpo-1528074, bpo-2986, and bpo-4622. I am closing two, leaving 2986 open, and merging the nearly disjoint nosy lists. (If no longer interested, you can delete yourself from 2986.) bpo-1711800 appears to be slightly different (if not, it could be closed also.)
Whether or not a new feature is ever added (earliest, now, 3.2), it appears that the docs need improvement to at least explain the current behavior. If someone who understands the issue could open a separate doc issue (for 2.6/7/3.1/2) with a suggested addition, that would be great.
terryjreedy commentedon Jun 28, 2010
The discussion on bpo-152807 references two other closed tracker issues:
bpo-1678339 Test case that currently fails
bpo-1678345 Patch to change behavior - rejected because crippled behavior is supposedly intentional and removing the change would slow things down.
The patch simply removes the internal heuristic. I think a better patch would be to make it optional, with a tunable popularity threshold.
I say 'supposedly intentional' because the code comments only justify the popularity hack for code line comparison and give no indication of awareness that it disables SequenceMatcher for general purpose use, and in particular, for non-toy finite character set comparisons of the type (ascii) used in all the examples.
elibendersky commentedon Jul 2, 2010
The new "junk heuristic" has been added to difflib.py in SVN revision 26661 in 2002 (which is, incidentally, the last revision to modify difflib.py). Its commit log says:
---------------------------------------------
Mostly in SequenceMatcher.{__chain_b, find_longest_match}:
This now does a dynamic analysis of which elements are so frequently
repeated as to constitute noise. The primary benefit is an enormous
speedup in find_longest_match, as the innermost loop can have factors
of 100s less potential matches to worry about, in cases where the
sequences have many duplicate elements. In effect, this zooms in on
sequences of non-ubiquitous elements now.
While I like what I've seen of the effects so far, I still consider
this experimental. Please give it a try!
---------------------------------------------
29 remaining items
terryjreedy commentedon Nov 12, 2010
r86437 - correct and replicate version-added message
elibendersky commentedon Nov 20, 2010
Terry, when is the deadline for producing the patch for 3.2? Perhaps we should at least submit the 2.7 patch for now so that it goes in for sure?
hodgestar commentedon Nov 20, 2010
I made the minor changes needed to get Eli Bendersky's patch to apply against 3.2. Diff attached.
terryjreedy commentedon Nov 20, 2010
Deadline is probably next Fri. However I will apply this or slight revision thereof in a couple of days to make sure this much is in. I have to fixup some work stuff today.
elibendersky commentedon Nov 21, 2010
Simon's patch fix for 3.2 looks good to me - applies cleanly to py3k and tests pass.
terryjreedy commentedon Nov 25, 2010
Since I am not sure I will be able to do any more before the 3.2b1 feature freeze, I went ahead with the minimal patch after checking the differences from the 2.7 version and redoing the Misc/News entry.
(I suspect putting a new entry immediately after the appropriate heading, instead of between other headings, is probably least likely to fatally conflict with intervening changes.) r86745 Thank you Eli and Simon.
Leaving this open for possible further changes.
hodgestar commentedon Nov 25, 2010
My vote is that this bug be closed and a new feature request be opened. Failing that, it would be good to have a concise description of what else we would like done (and the priority should be downgraded, I guess).
elibendersky commentedon Nov 25, 2010
Terry, I agree with Simon re closing and opening a new feature request. This issue has too much baggage in it, and you we always link to it. A new feature request should be opened strictly for 3.2
If you want I can close this issue and open a new one, but I'm waiting for your approval.
terryjreedy commentedon Nov 25, 2010
Agreed. bpo-10534. This is really a 'follow-on' rather than 'superseder',
but the forward reference should be easy for anyone to find.