SequenceMatcher de Difflib - Égalité personnalisée

Question

J'ai essayé de créer un effet imbriqué ou récursif avec SequenceMatcher. Le but final est de comparer deux séquences, les deux pouvant contenir des instances de différents types.

Par exemple, les séquences peuvent être:

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

Normalement, SequenceMatcher identifie uniquement [1] en tant que sous-séquence commune pour L1 et L2.

Je voudrais SequnceMatcher à appliquer deux fois pour les instances de chaîne, de sorte que "Foo" et "Fo" seront considérés comme égaux, ainsi que "Bar" et "Bak", et la sous-séquence plus longue commune sera d'une longueur de 3 [1, Foo/Fo, Bar/Bak]. C'est-à-dire, je voudrais que SequenceMatcher soit plus indulgent lors de la comparaison des membres de la chaîne.

Ce que j'ai essayé de faire est d'écrire un wrapper pour la classe intégrée 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: peut-être une façon plus élégante est:

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

En faisant cela, ce qui suit est rendu possible:

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

Donc, évidemment, cela fonctionne, mais j'ai un mauvais pressentiment à propos de la dérogation fonction de hachage. Quand le hash est-il utilisé? Où peut-il revenir et me mordre?

états de documentation de SequenceMatcher de ce qui suit:

Ceci est une classe souple pour comparer des paires de séquences de tout type, tant que les éléments de séquence sont hashable.

Et par définition hashable éléments sont nécessaires pour satisfaire à l'exigence suivante:

objets HASHABLE qui doivent être égaux ont la même valeur de hachage.

De plus, dois-je remplacer cmp ainsi?

J'aimerais beaucoup entendre parler d'autres solutions qui me viennent à l'esprit.

Merci.

Answer 1

Votre solution n'est pas mauvaise - vous pouvez également essayer de retravailler le SequenceMatcher pour appliquer récursivement lorsque les éléments d'une séquence sont eux-mêmes itérables, avec une certaine logique personnalisée. Ce serait une sorte de douleur. Si vous ne voulez que ce sous-ensemble des fonctionnalités de SequenceMatcher, écrire un outil de comparaison personnalisé n'est peut-être pas non plus une mauvaise idée.Remplacer __hash__ pour faire et "Fo" égaux entraînera des collisions dans les dictionnaires (tables de hachage) et autres. Si vous n'êtes littéralement intéressé que par les deux premiers caractères et que vous utilisez SequenceMatcher, retourner cls.super(self[2:]) pourrait être la solution. Tout ce qui a été dit, votre meilleur pari est probablement un outil de comparaison unique. Je peux esquisser les bases de quelque chose comme ça si vous êtes intéressé. Vous avez juste besoin de savoir quelles sont les contraintes dans les circonstances (la sous-séquence commence-t-elle toujours par le premier élément, ce genre de chose).