Difflib的SequenceMatcher -自定义等式

Question

我一直试图用SequenceMatcher创建一个嵌套的或递归的效果。

最后的目标是比较两个序列，它们都可能包含不同类型的实例。

例如，序列可以是：

l1 = [1, "Foo", "Bar", 3]
l2 = [1, "Fo", "Bak", 2]

通常情况下，SequenceMatcher只将1作为l1和l2的一个公共子序列.

I希望SequnceMatcher两次应用于字符串实例，这样"Foo"和"Fo"将被认为是相等的，"Bar"和"Bak"也是一样的，最长的公共子序列的长度为3 [1, Foo/Fo, Bar/Bak]。也就是说，我希望SequenceMatcher在比较string成员时更宽容一些。

我尝试为内置的str类编写一个包装器：

from difflib import SequenceMatcher
class myString:
    def __init__(self, string):
        self.string = string
    def __hash__(self):
        return hash(self.string)
    def __eq__(self, other):
        return SequenceMatcher(a=self.string, b=self.string).ratio() > 0.5

编辑:也许更优雅的方法是：

class myString(str):
    def __eq__(self, other):
        return SequenceMatcher(a=self, b=other).ratio() > 0.5

通过这样做，可以做到以下几点：

>>> Foo = myString("Foo")
>>> Fo = myString("Fo")
>>> Bar = myString("Bar")
>>> Bak = myString("Bak")
>>> l1 = [1, Foo, Bar, 3]
>>> l2 = [1, Fo, Bak, 2]
>>> SequenceMatcher(a=l1, b=l2).ratio()
0.75

因此，显然它正在工作，但我对重写散列函数有一种不好的感觉。什么时候使用哈希？它能从哪里回来咬我？

SequenceMatcher的文件规定如下：

这是一个灵活的类，用于比较任何类型的序列对，只要序列元素是可选的。

从定义上讲，要满足以下要求，就需要具备可理解的元素：

比较相等的可访问对象必须具有相同的哈希值。

此外，我还需要覆盖cmp吗？

我很想听听其他的解决方案。

谢谢。

Answer 1

您的解决方案不错--您还可以考虑重新工作SequenceMatcher，以便在序列的元素本身是可迭代的情况下，使用一些自定义逻辑递归地应用。那会是种痛苦。如果您只想要SequenceMatcher功能的这个子集，那么编写一个定制的diff工具也可能不是个坏主意。

重写__hash__以使"Foo"和"Fo"相等将导致字典(哈希表)等方面的冲突。如果您只对前两个字符感兴趣，并且已经开始使用SequenceMatcher，那么返回cls.super(self[2:])可能是最好的选择。

所有这些，你最好的选择可能是一个一次性的差异工具。如果你有兴趣的话，我可以勾勒出这类东西的基本原理。您只需要知道环境中的约束是什么(子序列总是从第一个元素开始，这类事情)。