Trouver la métrique de similitude entre deux chaînes

284

Comment obtenir la probabilité qu'une chaîne soit similaire à une autre chaîne en Python?

Je veux obtenir une valeur décimale comme 0,9 (ce qui signifie 90%), etc. De préférence avec Python et bibliothèque standard.

par exemple

similar("Apple","Appel") #would have a high prob.

similar("Apple","Mango") #would have a lower prob.
python probability similarity metric tenstar
la source
6
Je ne pense pas que "probabilité" soit tout à fait le bon terme ici. Dans tous les cas, voir stackoverflow.com/questions/682367/…
NPE
1
Le mot que vous recherchez est rapport, pas probabilité.
Inbar Rose
1
Jetez un œil à la distance de Hamming .
Diana
2
L'expression est «métrique de similitude» , mais il existe plusieurs métriques de similitude (Jaccard, Cosine, Hamming, Levenshein, etc.), vous devez donc spécifier lesquelles. Plus précisément, vous voulez une métrique de similitude entre les chaînes; @hbprotoss en a répertorié plusieurs.
smci

Réponses:

545

Il y a un intégré.

from difflib import SequenceMatcher

def similar(a, b):
    return SequenceMatcher(None, a, b).ratio()

En l'utilisant:

>>> similar("Apple","Appel")
0.8
>>> similar("Apple","Mango")
0.0
Inbar Rose
la source
43
Voir cette excellente réponse comparant le module SequenceMatchervs. stackoverflow.com/questions/6690739/…python-Levenshtein
ssoler
1
Article et outil intéressants
Anthony Perot
7
Je recommanderais fortement de vérifier l'ensemble du doc difflib docs.python.org/2/library/difflib.html il y a un get_close_matchesintégré, bien que je trouve sorted(... key=lambda x: difflib.SequenceMatcher(None, x, search).ratio(), ...)plus fiable, avec des sorted(... .get_matching_blocks())[-1] > min_matchvérifications personnalisées
ThorSummoner
2
@ThorSummoner attire l'attention sur une fonction très utile ( get_closest_matches). C'est une fonction pratique qui peut être ce que vous cherchez, AKA a lu les documents! Dans mon application particulière, je faisais quelques vérifications / rapports d'erreurs de base à l'utilisateur fournissant une mauvaise entrée, et cette réponse me permet de leur signaler les correspondances potentielles et la "similitude". Si vous n'avez pas besoin d'afficher la similitude, consultez absolumentget_closest_matches
svenevs
Cela a parfaitement fonctionné. Simple et efficace. Merci :)
Karthic Srinivasan
46

Solution # 1: Python intégré

utiliser SequenceMatcher de difflib

avantages : bibliothèque native python, pas besoin de paquet supplémentaire.
inconvénients : trop limité, il existe tellement d'autres bons algorithmes pour la similitude des chaînes.

exemple : 
>>> from difflib import SequenceMatcher
>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75

Solution # 2: bibliothèque de méduses

c'est une très bonne bibliothèque avec une bonne couverture et peu de problèmes. il prend en charge:
- Distance Levenshtein - Distance
Damerau-Levenshtein
- Distance Jaro
Jaro - la Jaro-Winkler
- la comparaison de l'approche d'évaluation des correspondances
- la distance de Hamming

avantages : facile à utiliser, gamme d'algorithmes pris en charge, testé.
inconvénients : pas de bibliothèque native.

exemple : 

>>> import jellyfish
>>> jellyfish.levenshtein_distance(u'jellyfish', u'smellyfish')
2
>>> jellyfish.jaro_distance(u'jellyfish', u'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance(u'jellyfish', u'jellyfihs')
1
Iman Mirzadeh
la source
26

Fuzzy Wuzzyest un package qui implémente la distance de Levenshtein en python, avec quelques fonctions d'assistance pour vous aider dans certaines situations où vous pouvez souhaiter que deux chaînes distinctes soient considérées comme identiques. Par exemple:

>>> fuzz.ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    91
>>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    100
BLT
la source
9

Vous pouvez créer une fonction comme:

def similar(w1, w2):
    w1 = w1 + ' ' * (len(w2) - len(w1))
    w2 = w2 + ' ' * (len(w1) - len(w2))
    return sum(1 if i == j else 0 for i, j in zip(w1, w2)) / float(len(w1))
Saullo GP Castro
la source
mais similaire ('appel', 'apple') est plus élevé que similaire ('appel', 'ape')
tenstar
1
Votre fonction comparera une chaîne donnée avec d'autres piqûres. Je veux un moyen de renvoyer la chaîne avec le rapport de similitude le plus élevé
answerSeeker
1
@SaulloCastro, if self.similar(search_string, item.text()) > 0.80:fonctionne pour l'instant. Merci,
answerSeeker
9

La distance du forfait comprend la distance Levenshtein:

import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3
Enrique Pérez Herrero
la source
6

La fonction intégrée SequenceMatcherest très lente sur les grandes entrées, voici comment cela peut être fait avec diff-match-patch :

from diff_match_patch import diff_match_patch

def compute_similarity_and_diff(text1, text2):
    dmp = diff_match_patch()
    dmp.Diff_Timeout = 0.0
    diff = dmp.diff_main(text1, text2, False)

    # similarity
    common_text = sum([len(txt) for op, txt in diff if op == 0])
    text_length = max(len(text1), len(text2))
    sim = common_text / text_length

    return sim, diff
damio
la source
5

Remarque, difflib.SequenceMatcher ne trouve que la sous-séquence de correspondance contiguë la plus longue, ce n'est souvent pas ce qui est souhaité, par exemple:

>>> a1 = "Apple"
>>> a2 = "Appel"
>>> a1 *= 50
>>> a2 *= 50
>>> SequenceMatcher(None, a1, a2).ratio()
0.012  # very low
>>> SequenceMatcher(None, a1, a2).get_matching_blocks()
[Match(a=0, b=0, size=3), Match(a=250, b=250, size=0)]  # only the first block is recorded

Trouver la similitude entre deux chaînes est étroitement lié au concept d'alignement de séquence par paire en bioinformatique. Il existe de nombreuses bibliothèques dédiées à cela, y compris le biopython . Cet exemple implémente l' algorithme Needleman Wunsch :

>>> from Bio.Align import PairwiseAligner
>>> aligner = PairwiseAligner()
>>> aligner.score(a1, a2)
200.0
>>> aligner.algorithm
'Needleman-Wunsch'

L'utilisation de biopython ou d'un autre package bioinformatique est plus flexible que n'importe quelle partie de la bibliothèque standard de python car de nombreux schémas et algorithmes de notation différents sont disponibles. En outre, vous pouvez réellement obtenir les séquences correspondantes pour visualiser ce qui se passe:

>>> alignment = next(aligner.align(a1, a2))
>>> alignment.score
200.0
>>> print(alignment)
Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-
|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-
App-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-el
Chris_Rands
la source
0

Vous pouvez trouver la plupart des méthodes de similitude de texte et comment elles sont calculées sous ce lien: https://github.com/luozhouyang/python-string-similarity#python-string-similarity Voici quelques exemples;

  • Normalisé, métrique, similitude et distance

  • Similitude et distance (normalisées)

  • Distances métriques

  • Similitude et distance basées sur les bardeaux (n-gram)
  • Levenshtein
  • Levenshtein normalisé
  • Levenshtein pondéré
  • Damerau-Levenshtein
  • Alignement optimal des cordes
  • Jaro-Winkler
  • Conséquence commune la plus longue
  • Conséquence métrique la plus longue commune
  • N-Gram
  • Algorithmes basés sur des bardeaux (n-gramme)
  • Q-Gram
  • Similitude cosinus
  • Index Jaccard
  • Coefficient de Sorensen-Dice
  • Coefficient de chevauchement (c.-à-d. Szymkiewicz-Simpson)
Mike
la source