Pythons SequenceMatcher是如何工作的？

Question

SequenceMatcher根据论点的顺序返回了两个不同的答案，我对此感到有点困惑。为什么会这样呢？

示例

SequenceMatcher不是可交换的：

>>> from difflib import SequenceMatcher
>>> SequenceMatcher(None, "Ebojfm Mzpm", "Ebfo ef Mfpo").ratio()
0.6086956521739131

>>> SequenceMatcher(None, "Ebfo ef Mfpo", "Ebojfm Mzpm").ratio()
0.5217391304347826

Answer 1

SequenceMatcher.ratio内部使用SequenceMatcher.get_matching_blocks来计算比率，我将向您介绍这些步骤，看看是如何发生的：

SequenceMatcher.get_matching_blocks 描述匹配子序列的三元组返回列表。每个三元组都是(i, j, n)形式的，这意味着a[i:i+n] == b[j:j+n]。在i和j中，三元组是单调增加的。 最后一个三元组是一个虚拟的，其值为(len(a), len(b), 0)。它是n == 0中唯一的三重。If (i, j, n)和(i', j', n')在列表中是相邻的三元组，第二个不是列表中的最后一个三元组，然后是i+n != i'或j+n != j'；换句话说，相邻的三元组总是描述不相邻的相等块。

ratio内部使用SequenceMatcher.get_matching_blocks的结果，并对SequenceMatcher.get_matching_blocks返回的所有匹配序列的大小进行求和。

matches = sum(triple[-1] for triple in self.get_matching_blocks())

上面的行非常重要，因为上面表达式的结果用于计算比率。我们很快就会看到这一点，以及它如何影响比率的计算。

>>> m1 = SequenceMatcher(None, "Ebojfm Mzpm", "Ebfo ef Mfpo")
>>> m2 = SequenceMatcher(None, "Ebfo ef Mfpo", "Ebojfm Mzpm")

>>> matches1 = sum(triple[-1] for triple in m1.get_matching_blocks())
>>> matches1
7
>>> matches2 = sum(triple[-1] for triple in m2.get_matching_blocks())
>>> matches2
6

正如您所看到的，我们有7和6，这些只是get_matching_blocks返回的匹配子序列的和。这有什么关系？这是为什么，这个比率是以以下方式计算的(这是来自difflib源代码的)：

def _calculate_ratio(matches, length):
    if length:
        return 2.0 * matches / length
    return 1.0

length是len(a) + len(b)，其中a是第一个序列，b是第二个序列。

好吧，说够了，我们需要行动：

>>> length = len("Ebojfm Mzpm") + len("Ebfo ef Mfpo") 
>>> m1.ratio()
0.6086956521739131
>>> (2.0 * matches1 / length)  == m1.ratio()
True

同样适用于m2

>>> 2.0 * matches2 / length
0.5217391304347826 
>>> (2.0 * matches2 / length) == m2.ratio()
True

注意：并不是所有的 SequenceMatcher(None a,b).ratio() == SequenceMatcher(None b,a).ratio()都是False，有时它们可以是True

>>> s1 = SequenceMatcher(None, "abcd", "bcde").ratio()
>>> s2 = SequenceMatcher(None, "bcde", "abcd").ratio()
>>> s1 == s2
True

如果你想知道为什么，这是因为

sum(triple[-1] for triple in self.get_matching_blocks())

对于SequenceMatcher(None, "abcd", "bcde")和SequenceMatcher(None, "bcde", "abcd")都是相同的，这是3。

Answer 2

我的回答并没有提供观察到的问题的确切细节，但是包含了为什么这样的事情可能发生在松散定义的不同方法上的一般解释。

从本质上说，一切都归结于这样一个事实:在一般情况下，

1. 可以从给定的一对字符串中提取多个相同长度的公共子序列，并且
2. 在人类专家看来，较长的公共序列可能比较短的序列更不自然。

由于您对这种特殊情况感到困惑，让我们分析以下字符串上的公共子序列标识：

• my stackoverflow mysteries
• mystery

对我来说，自然的匹配是"MYSTER"，如下所示：

my stackoverflow MYSTERies
.................MYSTERy..

然而，最长的匹配完全覆盖了两个字符串中较短的字符串，如下所示：

MY STackovERflow mYsteries
MY.ST.....ER......Y.......

这种匹配的缺点是引入了多个匹配子块，而(较短的)自然匹配是连续的。

因此，对差分算法进行了调整，使它们的输出更符合最终用户的要求。因此，它们在数学上并不是100%优雅的，因此不具备您期望的纯学术性(而非实用性)工具的属性。

SequenceMatcher包含相应的注释：

class difflib.SequenceMatcher 这是一个灵活的类，用于比较任何类型的序列对，只要序列元素是可理解的。这一基本算法早在20世纪80年代末由拉特克利夫和奥伯舍普以“格式塔模式匹配”的双曲线名称出版，而且比这一算法稍有新鲜感。其思想是寻找最长的连续匹配子序列，其中不包含“垃圾”元素( Ratcliff和Obershelp算法不处理垃圾)。然后，同样的想法递归地应用到序列的左边和匹配子序列的右边。--这并不能产生最小的编辑序列，但往往会产生匹配的结果，在人们看来是“正确的”。

Answer 3

from difflib import SequenceMatcher

texto1 = 'BRASILIA~DISTRITO FEDERAL, DF'
texto2 = 'BRASILIA-DISTRITO FEDERAL, '

tamanho_texto1 = len(texto1)
tamanho_texto2 = len(texto2)
tamanho_tot = tamanho_texto1 + tamanho_texto2

tot = 0
if texto1 <= texto2:
    for x in range(len(texto1)):
        y = texto1[x]

        if y in texto2:
            tot += 1
else:
    for x in range(len(texto2)):
        y = texto2[x]

        if y in texto1:
            tot += 1
        
print('sequenceM = ',SequenceMatcher(None, texto1,     texto2).ratio())
print('Total calculado = ',2*tot/tamanho_tot)