22

我对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
4

2 回答 2

19

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。这是来自的确切源代码difflib.py：

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。

于 2017-08-02T10:06:23.130 回答
7

我的回答没有提供观察到的问题的确切细节，但包含对松散定义的差异方法可能会发生此类事情的一般解释。

基本上一切都归结为这样一个事实，在一般情况下，

  1. 可以从给定的一对字符串中提取多个相同长度的公共子序列，并且

  2. 对于人类专家来说，较长的公共子序列可能比较短的子序列更不自然。

由于您对这种特殊情况感到困惑，让我们分析以下一对字符串的常见子序列识别：

  • my stackoverflow mysteries
  • mystery

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

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

但是，最长的匹配完全覆盖两个字符串中较短的一个，如下所示：

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

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

因此，对差异算法进行了调整，以使其输出更能满足最终用户的需求。因此，它们在数学上并不是 100% 优雅的，因此不具备您对纯学术（而不是实用）工具所期望的属性。

的文档SequenceMatcher包含相应的注释：

class difflib.SequenceMatcher

这是一个灵活的类，用于比较任何类型的序列对，只要序列元素是可散列的。基本算法早于 Ratcliff 和 Obershelp 在 1980 年代后期以双曲线名称“格式塔模式匹配”发布的算法，并且比它更高级一些。这个想法是找到不包含“垃圾”元素的最长连续匹配子序列（Ratcliff 和 Obershelp 算法不处理垃圾）。然后将相同的想法递归地应用于匹配子序列左侧和右侧的序列片段。 这不会产生最少的编辑序列，但会产生对人们“看起来正确”的匹配。

于 2017-08-02T10:26:04.600 回答