Python Difflib的SequenceMatcher无法找到最长公共子串

Question

我想使用difflib.SequenceMatcher从两个字符串中提取最长公共子串。我不确定是我发现了一个bug还是我误解了find_longest_match的文档。这是我觉得令人困惑的地方：

换句话说，在所有最大匹配块中，返回在a中最早开始的块，并在所有最大匹配块中，返回在a中最早开始的块中最早开始的b块。

(https://docs.python.org/3.5/library/difflib.html#difflib.SequenceMatcher.find_longest_match)

比较字符串X this is a test和this is a test X，子串X实际上是一个最大块：它不能被扩展（即，它是包含最大的）。此外，它是文本A中第一个这样的最大块。但它肯定不是最长的公共子串。我强烈怀疑这不是find_longest_match应该找到的。

事实上，在这个例子中，find_longest_match确实找到了最长的公共子串：

>>> l = len("X this is a test")
>>> matcher = difflib.SequenceMatcher(None, "X this is a test", "this is a test X")
>>> matcher.find_longest_match(0, l, 0, l)
Match(a=2, b=0, size=14)

然而，似乎我可以使用其他一些字符串来引发上述“查找第一个最大块”的行为（如果我缩短它们，示例会出现问题）：

>>> s1 = "e-like graph visualization using a spanning tree-driven layout technique with constraints specified by layers and the ordering of groups of nodes within layers. We propose a new method of how the orde"
>>> s2 = "itree graph visualization using a spanning tree-driven layout technique with constraints speci ed by layers and the ordering of groups of nodes within layers. We propose a new method of how the drivin"
>>> matcher = difflib.SequenceMatcher(None, s1, s2)
>>> matcher.find_longest_match(1, 149, 5, 149)
Match(a=1, b=47, size=1)

在这种情况下，它将第一个-与s1 [1]中的-匹配到s2 [47]中的-，就是这样。 最长公共子串可能是以graph visualization using…开头的内容。

我是否发现了一个错误，或者有另一种可能的解释可以描述这种行为？

我正在Ubuntu上使用Python 3.5.2。

- Lukas Barth

Answer 1

好的，我明白了。如果有人遇到同样的问题： SequenceMatcher有一个名为autojunk的参数，它会做一些奇怪的事情：

该启发式方法计算每个单独项在序列中出现的次数。如果一个项目的重复（第一个之后）占序列的1％以上，并且序列至少有200个项目，那么这个项目就被标记为“流行”，并且作为目的序列匹配时的垃圾进行处理。

据我所知，匹配器永远不会找到包含任何“垃圾”的匹配项。不确定为什么这是有用的，但默认情况下已启用。这也解释了为什么当我缩短字符串时，上面的示例将会失败。但是，它确实大大加快了最长公共子序列搜索速度。

因此，总结一下：您可能希望在构造函数中传递autojunk=False。

- Lukas Barth

---

对于我来说，即使设置 'autojunk=False'，'find_longest_match（）'也根本不会给出最长的匹配。因此，我不得不获取所有匹配项，并使用循环选择最大的匹配项。 - Rizvi Hasan

然而，文档中表示“将 None 传递给 isjunk 等效于传递 lambda x: False；换句话说，没有元素被忽略”。他们应该明确提到，尽管对第一个参数传递了 None，但仍然会忽略元素通过 autojunk 算法。 - kristianp