Encuentra la métrica de similitud entre dos cadenas

284

¿Cómo obtengo la probabilidad de que una cadena sea similar a otra cadena en Python?

Quiero obtener un valor decimal como 0.9 (que significa 90%), etc. Preferiblemente con Python y biblioteca estándar.

p.ej

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

similar("Apple","Mango") #would have a lower prob.
python probability similarity metric tenstar
fuente
66
No creo que "probabilidad" sea el término correcto aquí. En cualquier caso, consulte stackoverflow.com/questions/682367/…
NPE
1
La palabra que está buscando es razón, no probabilidad.
Inbar Rose
1
Echa un vistazo a la distancia de Hamming .
Diana
2
La frase es 'métrica de similitud' , pero hay múltiples métricas de similitud (Jaccard, Cosine, Hamming, Levenshein, etc.) que se dicen, por lo que debe especificar cuál. Específicamente, desea una métrica de similitud entre cadenas; @hbprotoss enumeró varios.
smci

Respuestas:

543

Hay un construido en.

from difflib import SequenceMatcher

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

Utilizándolo:

>>> similar("Apple","Appel")
0.8
>>> similar("Apple","Mango")
0.0
Inbar Rose
fuente
43
Vea esta gran respuesta comparando SequenceMatchervs python-Levenshteinmódulo. stackoverflow.com/questions/6690739/…
ssoler
1
Artículo y herramienta interesantes
Anthony Perot el
77
Recomiendo ver todo el documento difflib docs.python.org/2/library/difflib.html hay un get_close_matchesincorporado, aunque me pareció sorted(... key=lambda x: difflib.SequenceMatcher(None, x, search).ratio(), ...)más confiable, con sorted(... .get_matching_blocks())[-1] > min_matchcontroles personalizados
ThorSummoner
2
@ThorSummoner llama la atención sobre una función muy útil ( get_closest_matches). Es una función de conveniencia que puede ser lo que está buscando, ¡también conocido como los documentos! En mi aplicación en particular, estaba haciendo algunas comprobaciones básicas de errores / informes al usuario que proporcionaban datos incorrectos, y esta respuesta me permite informarles las posibles coincidencias y cuál era la "similitud". Sin embargo, si no necesitas mostrar la similitud, definitivamente echa un vistazoget_closest_matches
svenevs
Esto funcionó perfectamente. Simple y efectivo. Gracias :)
Karthic Srinivasan
46

Solución # 1: Python incorporado

use SequenceMatcher de difflib

pros : biblioteca nativa de python, no necesita paquete adicional.
contras : demasiado limitado, existen muchos otros buenos algoritmos para la similitud de cadenas.

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

Solución # 2: medusa biblioteca de

Es una muy buena biblioteca con buena cobertura y pocos problemas. admite:
- Distancia de Levenshtein - Distancia de
Damerau-Levenshtein
- Distancia de
Jaro - Distancia de Jaro-Winkler
- Comparación del enfoque de clasificación de partidos
- Distancia de Hamming

Pros : fácil de usar, gama de algoritmos compatibles, probado.
contras : biblioteca no nativa.

ejemplo : 

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

Fuzzy Wuzzyes un paquete que implementa la distancia de Levenshtein en python, con algunas funciones de ayuda para ayudar en ciertas situaciones en las que es posible que desee que dos cadenas distintas se consideren idénticas. Por ejemplo:

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

Puedes crear una función como:

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
fuente
pero similar ('appel', 'apple') es más alto que similar ('appel', 'ape')
tenstar el
1
Su función comparará una cadena dada con otras picaduras. Quiero una forma de devolver la cadena con la relación de similitud más alta
answerSeeker
1
@SaulloCastro, if self.similar(search_string, item.text()) > 0.80:funciona por ahora. Gracias,
answerSeeker
9

La distancia del paquete incluye la distancia de Levenshtein:

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

La construcción SequenceMatcheres muy lenta en entradas grandes, así es como se puede hacer con 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
fuente
5

Tenga en cuenta que difflib.SequenceMatcher solo encuentra la subsecuencia de coincidencia contigua más larga, esto a menudo no es lo que se desea, por ejemplo:

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

Encontrar la similitud entre dos cadenas está estrechamente relacionado con el concepto de alineación de secuencia por pares en bioinformática. Hay muchas bibliotecas dedicadas para esto, incluyendo biopython . Este ejemplo implementa el algoritmo Needleman Wunsch :

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

El uso de biopython u otro paquete de bioinformática es más flexible que cualquier parte de la biblioteca estándar de python, ya que hay muchos esquemas y algoritmos de puntuación diferentes disponibles. Además, puede obtener las secuencias coincidentes para visualizar lo que está sucediendo:

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

Puede encontrar la mayoría de los métodos de similitud de texto y cómo se calculan en este enlace: https://github.com/luozhouyang/python-string-similarity#python-string-similarity Aquí algunos ejemplos;

  • Normalizado, métrico, similitud y distancia.

  • Similitud y distancia (normalizadas)

  • Distancias métricas

  • Herpes zóster (n-gram) basado en similitud y distancia
  • Levenshtein
  • Levenshtein normalizado
  • Levenshtein ponderado
  • Damerau-Levenshtein
  • Alineación de cadena óptima
  • Jaro-Winkler
  • Subsecuencia común más larga
  • Subsecuencia común más larga métrica
  • N-Gram
  • Algoritmos basados ​​en tejas (n-gram)
  • Q-Gram
  • Similitud de coseno
  • Índice Jaccard
  • Coeficiente de dados de Sorensen
  • Coeficiente de superposición (es decir, Szymkiewicz-Simpson)
Miguel
fuente