Difflib的SequenceMatcher - 自定义相等性

Question

Difflib的SequenceMatcher - 自定义相等性

7

我一直在尝试使用SequenceMatcher创建嵌套或递归效果。

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

例如，这些序列可以是：

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

通常情况下，SequenceMatcher 只会将 [1] 识别为 l1 和 l2 的公共子序列。

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

我尝试编写内置 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吗？

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

谢谢。

- YaronK

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- a p · Accepted Answer

你的解决方案并不差 - 你也可以考虑重新设计SequenceMatcher，以便在序列元素本身是可迭代的时候递归地应用一些自定义逻辑。这可能有点麻烦。如果你只想要SequenceMatcher的这个子集功能，编写一个自定义的diff工具也许不是一个坏主意。

覆盖__hash__使"Foo"和"Fo"相等将会在字典（哈希表）等数据结构中产生冲突。如果你只对前两个字符感兴趣并且决定使用SequenceMatcher，返回cls.super(self[2:])可能是一个不错的选择。

总之，你最好使用一次性的diff工具。如果你有兴趣，我可以简要介绍一下这样的工具的基本原理。你只需要知道在什么情况下有什么限制（例如子序列是否总是从第一个元素开始等）。