python - Python 3.6 SequenceMatcher().get_matching_blocks() 如何工作？

Question

我正在尝试使用 SequenceMatcher.ratio()获取两个字符串的相似度:"86418648"和 "86488648" :

>>> SequenceMatcher(None,"86418648","86488648").ratio()
0.5

返回的比率为 0.5 ，这比我预期的要低得多，因为两个字符串中只有一个字符不同。

似乎该比率是根据匹配块计算的。所以我试着运行 SequenceMatcher.get_matching_blocks() :

>>> SequenceMatcher(None,"86418648","86488648").get_matching_blocks()
[Match(a=4, b=0, size=4), Match(a=8, b=8, size=0)]

但我预计结果是:

[Match(a=0, b=0, size=3), Match(a=4, b=4, size=4), Match(a=8, b=8, size=0)]

谁能帮忙解释为什么它与前 3 个数字不匹配 "864" ?

Answer 1

SequenceMatcher.get_matching_blocks()通过重复应用 SequenceMatcher.find_longest_match() 起作用到两个序列的尚未匹配的块。

引用 find_longest_match() 的文档字符串:

Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
    alo <= i <= i+k <= ahi
    blo <= j <= j+k <= bhi
and for all (i',j',k') meeting those conditions,
    k >= k'
    i <= i'
    and if i == i', j <= j'

In other words, of all maximal matching blocks, return one that
starts earliest in a, and of all those maximal matching blocks that
start earliest in a, return the one that starts earliest in b.

在两个序列的情况下 a = "86418648"和 b = "86488648" ，最长的块在 a匹配 b 中的块是单例 8648在 a[4] , 最早的匹配在 b是两个此类可能匹配项中的第一个，位于 b[0] .

一旦确定了这场比赛，就不再有任何进一步的比赛，根据 guarantee由 SequenceMatcher.get_matching_blocks() 提供, “三元组在 i 和 j 中单调递增” .

例如，匹配尚未匹配的 864在 a[0]与迄今为止无与伦比的 864在 b[4]将要求 i 随着 j 的增加而减少(反之亦然)，这违反了上述保证。