SequenceMatcher của Difflib - Công bằng tùy chỉnh

Question

Tôi đã cố gắng tạo hiệu ứng lồng nhau hoặc đệ quy với SequenceMatcher.

Mục tiêu cuối cùng là so sánh hai chuỗi, cả hai có thể chứa các phiên bản của các loại khác nhau.

Ví dụ, trình tự có thể là:

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

Thông thường, SequenceMatcher sẽ xác định chỉ [1] như một tiểu trình tự chung cho l1 và l2.

Tôi muốn SequnceMatcher được áp dụng hai lần cho trường hợp chuỗi, do đó "Foo" và "Fo" sẽ được coi là bình đẳng, cũng như "Bar" và "Bak", và các tiểu chuỗi chung dài nhất sẽ có độ dài 3 [1, Foo/Fo, Bar/Bak]. Tức là, tôi muốn SequenceMatcher được tha thứ hơn khi so sánh các thành viên chuỗi.

Những gì tôi cố gắng làm là viết một wrapper cho built-in Class 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 

Edit: có lẽ một cách thanh lịch hơn là:

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

Bằng cách này, sau đây là có thể được thực hiện:

>>> 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 

Vì vậy, rõ ràng là nó hoạt động, nhưng tôi có cảm giác xấu về việc ghi đè số hàm băm. Khi nào băm được sử dụng? Nó có thể trở lại và cắn tôi ở đâu?

bang tài liệu

SequenceMatcher của những điều sau đây:

Đây là một lớp học linh hoạt để so sánh các cặp trình tự của bất kỳ loại, chừng nào các yếu tố tự là hashable.

Và theo định nghĩa hashable yếu tố được yêu cầu phải thực hiện các yêu cầu sau đây: đối tượng

Hashable mà so sánh tương đương phải có cùng giá trị băm.

Ngoài ra, tôi có cần ghi đè cmp không?

Tôi rất muốn nghe về các giải pháp khác mà bạn nghĩ đến.

Cảm ơn.

Answer 1

Giải pháp của bạn không tệ - bạn cũng có thể xem xét việc làm việc lại SequenceMatcher để đệ quy áp dụng khi các phần tử của một chuỗi có thể lặp lại được, với một số logic tùy chỉnh. Đó sẽ là một nỗi đau. Nếu bạn chỉ muốn tập con này của chức năng của SequenceMatcher, việc viết một công cụ tìm khác biệt có thể không phải là một ý tưởng tồi.

Ghi đè __hash__ để làm cho "Foo" và "Fo" bằng nhau sẽ gây ra va chạm trong từ điển (bảng băm) và như vậy. Nếu bạn thực sự chỉ quan tâm đến 2 ký tự đầu tiên và được thiết lập bằng cách sử dụng SequenceMatcher, trả lại cls.super(self[2:]) có thể là cách để thực hiện.

Tất cả những gì đã nói, đặt cược tốt nhất của bạn có thể là công cụ tìm khác biệt một lần. Tôi có thể phác thảo ra những điều cơ bản của một cái gì đó như thế nếu bạn quan tâm. Bạn chỉ cần biết những ràng buộc trong hoàn cảnh nào (không phải chuỗi tiếp tục luôn bắt đầu trên phần tử đầu tiên, loại điều đó).