SequenceMatcher bug

[mcft]

BPO	33112
Nosy	@tim-one

^{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 = None
closed_at = <Date 2018-03-20.20:35:51.540>
created_at = <Date 2018-03-20.20:09:08.532>
labels = ['type-bug']
title = 'SequenceMatcher bug'
updated_at = <Date 2018-03-20.20:35:51.534>
user = 'https://bugs.python.org/mcft'

bugs.python.org fields:

activity = <Date 2018-03-20.20:35:51.534>
actor = 'tim.peters'
assignee = 'none'
closed = True
closed_date = <Date 2018-03-20.20:35:51.540>
closer = 'tim.peters'
components = []
creation = <Date 2018-03-20.20:09:08.532>
creator = 'mcft'
dependencies = []
files = []
hgrepos = []
issue_num = 33112
keywords = []
message_count = 2.0
messages = ['314163', '314165']
nosy_count = 2.0
nosy_names = ['tim.peters', 'mcft']
pr_nums = []
priority = 'normal'
resolution = 'duplicate'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue33112'
versions = ['Python 3.5']

[mcft]

difflib.SequenceMatcher fails to make a proper alignment between 2 sequences with only 3 single letter changes. Its performance is completely off with a similarity ratio of 0.16, in stead of the more accurate 0.99.

Here is a snippet to replicate the failure:
>>> aa_ref = 'MTLFTTLLVLIFERLFKLGEHWQLDHRLEAFFRRVKHFSLGRTLGMTIIAMGVTFLLLRALQGVLFNVPTLLVWLLIGLLCIGAGKVRLHYHAYLTAASRNDSHARATMAGELTMIHGVPAGCDEREYLRELQNALLWINFRFYLAPLFWLIVGGTWGPVTLMGYAFLRAWQYWLARYQTPHHRLQSGIDAVLHVLDWVPVRLAGVVYALIGHGEKALPAWFASLGDFHTSQYQVLTRLAQFSLAREPHVDKVETPKAAVSMAKKTSFVVVVVIALLTIYGALV'
>>> aa_seq = 'MTLFTTLLVLIFERLFKLGEHWQLDHRLEAFFRRVKHFSLGRTLCMTIIAMGVTFLLLRALQGVLFNVPTLLVWLLIGLLCIGAGKVRLHYHAYLTAASRNDSHAHATMAGELTMIHGVPAGCDEREYLRELQNALLWINFRFYLAPLFWLIVGGTWGPVTLMGYAFLRAWQYWLARYQTPHHRLQSGIDAVLHALDWVPVRLAGVVYALIGHGEKALPAWFASLGDFHTSQYQVLTRLAQFSLAREPHVDKVETPKAAVSMAKKTSFVVVVVIALLTIYGALV'
>>> sum(a!=b for a, b in zip(aa_ref, aa_seq))
3
>>> match = SequenceMatcher(a=aa_ref, b=aa_seq)
>>> match.ratio()
0.1619718309859155
>>> match.get_opcodes()
[('equal', 0, 43, 0, 43), ('delete', 43, 79, 43, 43), ('equal', 79, 81, 43, 45), ('replace', 81, 122, 45, 80), ('equal', 122, 123, 80, 81), ('replace', 123, 284, 81, 284)]

[tim-one]

Please see the response to bpo-31889. Short course: you need to pass autojunk=False to the SequenceMatcher constructor.