Métriques de similarité de chaîne en Python

Question

Je souhaite trouver une similarité de chaîne entre deux chaînes. This page a des exemples de certains d'entre eux. Python a une implémnetation de Levenshtein algorithm. Y a-t-il un meilleur algorithme, (et espérons une bibliothèque python), sous ces contraintes.

1. Je veux faire des correspondances floues entre les chaînes. par exemple, les correspondances ('Bonjour, Tout le monde', 'bonjour, tout le monde') devraient être vraies
2. Les faux négatifs sont acceptables, les faux positifs, sauf dans des cas extrêmement rares, ne le sont pas.
3. Ceci est fait dans un réglage non temps réel, donc la vitesse n'est pas (beaucoup) préoccupante.
4. [Modifier] Je compare plusieurs chaînes de mots.

Quelque chose d'autre que la distance de Levenshtein (ou le rapport de Levenshtein) serait un meilleur algorithme pour mon cas?

Answer 1

Il y a une grande ressource pour les mesures de similarité de chaîne à l'Université de Sheffield. Il a une liste de diverses métriques (au-delà de simplement Levenshtein) et a des implémentations open-source d'entre eux. On dirait que beaucoup d'entre eux devraient être faciles à adapter en Python.

http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

est ici un peu de la liste:

• distance de Hamming
• Levenshtein
• la distance Needleman-Wunch ou vendeurs algorithme
• et beaucoup d'autres ...

Answer 2

C'est ce que vous voulez dire?

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy']) 
['apple', 'ape'] 
>>> import keyword 
>>> get_close_matches('wheel', keyword.kwlist) 
['while'] 
>>> get_close_matches('apple', keyword.kwlist) 
[] 
>>> get_close_matches('accept', keyword.kwlist) 
['except'] 

regard sur http://docs.python.org/library/difflib.html#difflib.get_close_matches

Answer 3

Je sais que ce n'est pas la même chose, mais cela est assez proche:

>>> import difflib 
>>> a = 'Hello, All you people' 
>>> b = 'hello, all You peopl' 
>>> seq=difflib.SequenceMatcher(a=a.lower(), b=b.lower()) 
>>> seq.ratio() 
0.97560975609756095 

Vous pouvez faire cela en fonction

def similar(seq1, seq2): 
    return difflib.SequenceMatcher(a=seq1.lower(), b=seq2.lower()).ratio() > 0.9 

>>> similar(a, b) 
True 
>>> similar('Hello, world', 'Hi, world') 
False 

Answer 4

J'utiliser la distance Levenshtein, ou la distance Damerau soi-disant (qui prend en compte les transpositions) plutôt que les choses difflib pour deux raisons (1) "assez rapide" (algo de programmation dynamique) et "whoooosh" (bit-bashing) le code C est disponible et (2) le comportement bien compris Levenshtein vérifie l'inégalité du triangle et peut donc être utilisé, par exemple, un arbre Burkhard-Keller. Seuil: vous ne devez traiter comme "positif" que les cas où la distance < (1 - X) * max (len (string1), len (string2)) et ajuster X (le facteur de similarité) en fonction de vous. Une façon de choisir X est d'obtenir un échantillon de correspondances, de calculer X pour chacune, d'ignorer les cas où X < disons 0.8 ou 0.9, puis de trier le reste dans l'ordre décroissant de X et de les inverser et d'insérer le résultat correct. mesure du coût de l'erreur pour divers niveaux de X.

NB Votre exemple de singe/pomme a la distance 2, donc X est 0.6 ... Je n'utiliserais qu'un seuil aussi bas que 0.75 si je cherchais désespérément quelque chose et que j'avais une forte pénalité négative-négative

Answer 5

Je sais que ce n'est pas la même chose mais vous pouvez ajuster le ratio pour filtrer les chaînes qui ne sont pas assez similaires et retourner la correspondance la plus proche de la chaîne que vous recherchez.

Peut-être seriez-vous plus intéressé par les métriques de similarité sémantique.

https://www.google.com/search?client=ubuntu&channel=fs&q=semantic+similarity+string+match&ie=utf-8&oe=utf-8

Je me rends compte que vous avez dit vitesse n'est pas un problème, mais si vous traitez beaucoup de chaînes pour votre algorithme le ci-dessous est très utile.

def spellcheck(self, sentence): 
    #return ' '.join([difflib.get_close_matches(word, wordlist,1 , 0)[0] for word in sentence.split()]) 
    return ' '.join([ sorted({ Levenshtein.ratio(x, word):x for x in wordlist }.items(), reverse=True)[0][1] for word in sentence.split() ]) 

Son environ 20 fois plus rapide que le difflib.

https://pypi.python.org/pypi/python-Levenshtein/

importation Levenshtein

Answer 6

Cet extrait calculera le difflib, les valeurs de similarité Levenshtein, Sørensen et Jaccard pour deux chaînes. Dans l'extrait ci-dessous, j'étais en train d'itérer sur un tsv dans lequel les chaînes d'intérêt occupaient les colonnes [3] et [4] du tsv. (pip install python-Levenshtein et pip install distance):

import codecs, difflib, Levenshtein, distance 

with codecs.open("titles.tsv","r","utf-8") as f: 
    title_list = f.read().split("\n")[:-1] 

    for row in title_list: 

     sr  = row.lower().split("\t") 

     diffl = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio() 
     lev  = Levenshtein.ratio(sr[3], sr[4]) 
     sor  = 1 - distance.sorensen(sr[3], sr[4]) 
     jac  = 1 - distance.jaccard(sr[3], sr[4]) 

     print diffl, lev, sor, jac