Métricas de similitud de cadenas en Python

Question

Quiero encontrar la similitud de cadenas entre dos cadenas. This página tiene ejemplos de algunos de ellos. Python tiene una implementación de Levenshtein algorithm. ¿Hay algún algoritmo mejor (y, con suerte, una biblioteca de Python) bajo estas restricciones?

1. Quiero hacer coincidencias difusas entre cadenas. Por ejemplo, las coincidencias ('Hola, toda tu gente', 'hola, todo tu pueblo') deberían devolver verdadero
2. Los falsos negativos son aceptables, falsos positivos, excepto en casos extremadamente raros, no.
3. Esto se realiza en un ajuste no en tiempo real, por lo que la velocidad no es (mucho) motivo de preocupación.
4. [Editar] Estoy comparando cadenas de varias palabras.

¿Sería algo mejor que la distancia Levenshtein (o la relación Levenshtein) un mejor algoritmo para mi caso?

Answer 1

Hay un gran recurso para las métricas de similitud de cadenas en la Universidad de Sheffield. Tiene una lista de varias métricas (más allá de Levenshtein) y tiene implementaciones de código abierto de ellas. Parece que muchos de ellos deberían ser fáciles de adaptar a Python.

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

Aquí hay un poco de la lista:

• distancia de Hamming
• distancia Levenshtein
• Needleman-Wunch distancia o vendedores Algoritmo
• y muchos más ...

Answer 2

¿Es eso lo que quieres decir?

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

vistazo a http://docs.python.org/library/difflib.html#difflib.get_close_matches

Answer 3

me doy cuenta que no es la misma cosa, pero esto es lo suficientemente cerca:

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

Usted puede hacer esto como una función

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

me gustaría utilizar Levenshtein distancia, o la denominada distancia Damerau (que toma en cuenta las transposiciones) en lugar de las cosas difflib por dos razones (1) "lo suficientemente rápido" (algo de programación dinámica) y "whoooosh" (bit-bashing) código C está disponible y (2) comportamiento bien entendido, por ejemplo Levenshtein satisface la desigualdad del triángulo y, por lo tanto, puede usarse en, por ejemplo, un árbol de Burkhard-Keller.

Umbral: debe tratar como "positivo" solo aquellos casos donde la distancia < (1 - X) * max (len (string1), len (string2)) y ajustar X (el factor de similitud) a usted. Una forma de elegir X es obtener una muestra de coincidencias, calcular X para cada una, ignorar los casos en los que X < decir 0,8 o 0,9, luego ordenar el resto en orden descendente de X e insertarlos en el resultado correcto y calcular algunos medida del costo de los errores para varios niveles de X.

NB Su ejemplo de simio/manzana tiene una distancia 2, por lo que X es 0.6 ... Solo usaría un umbral tan bajo como 0.75 si estuviera buscando desesperadamente algo y tenía una alta pena de falso negativo

Answer 5

Sé que esto no es el mismo, pero se puede ajustar la relación de filtrar las cadenas que no son lo suficientemente similares y devolver el valor más cercano a la cadena que está buscando.

Quizás esté más interesado en las métricas de similitud semántica.

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

que se dan cuenta de que dicha velocidad no es un problema, pero si está procesando una gran cantidad de las cuerdas para su algoritmo de la de abajo es muy útil.

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() ]) 

Es aproximadamente 20 veces más rápido que difflib.

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

importación Levenshtein

Answer 6

Este fragmento calculará el difflib, valores de similitud Levenshtein, Sørensen y Jaccard por dos cuerdas. En el siguiente fragmento, estaba iterando sobre un tsv en el que las cadenas de interés ocupaban las columnas [3] y [4] del tsv. (pip install python-Levenshtein y 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