example - Métricas de similitud de cadenas en Python
python text similarity algorithm (6)
Quiero encontrar similitud de cadena entre dos cadenas. This página tiene ejemplos de algunos de ellos. Python tiene una implementación del algoritmo Levenshtein . ¿Hay un algoritmo mejor (y, con suerte, una biblioteca de python), bajo estos límites?
- Quiero hacer partidos difusos entre cadenas. Por ejemplo, las coincidencias (''Hola, todos ustedes'', ''hola, todos ustedes, gente'') deben devolver True.
- Los falsos negativos son aceptables, los falsos positivos, excepto en casos extremadamente raros, no lo son.
- Esto se realiza en un entorno no en tiempo real, por lo que la velocidad no es (mucho) motivo de preocupación.
- [Editar] Estoy comparando cadenas de varias palabras.
¿Sería un algoritmo mejor para mi caso algo más que la distancia de Levenshtein (o la proporción de Levenshtein)?
¿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'']
visite http://docs.python.org/library/difflib.html#difflib.get_close_matches
Este fragmento calculará los valores de similitud de difflib, Levenshtein, Sørensen y Jaccard para dos cadenas. 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
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 solo 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 algoritmo de vendedores
- y muchos más...
Me doy cuenta de que no es lo mismo, 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
Puedes 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
Sé que esto no es lo mismo, pero puedes ajustar la proporción para filtrar las cadenas que no son lo suficientemente similares y devolver la coincidencia más cercana a la cadena que estás buscando.
Tal vez usted estaría más interesado en las métricas de similitud semántica.
Me doy cuenta de que dijo que la velocidad no es un problema, pero si está procesando muchas de las cadenas para su algoritmo, lo que sigue 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 el difflib.
https://pypi.python.org/pypi/python-Levenshtein/
importación Levenshtein
Utilizaría la distancia de Levenshtein, o la llamada distancia de Damerau (que tiene en cuenta las transposiciones) en lugar de las cosas de difflib por dos razones (1) "lo suficientemente rápido" (programación dinámica algo) y "whoooosh" (ataque de bits) C el código está disponible y (2) el 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) para adaptarse a usted. Una forma de elegir X es obtener una muestra de coincidencias, calcular X para cada una, ignorar los casos donde X <diga 0.8 o 0.9, luego ordenar el resto en orden descendente de X e intercambiarlas con una bola ocular, insertar el resultado correcto y calcular algunos Medida del costo de errores para varios niveles de X.
NB: su ejemplo de simio / manzana tiene una distancia de 2, entonces X es 0.6 ... Yo solo usaría un umbral tan bajo como 0.75 si estuviera buscando algo desesperadamente y tuviera una alta penalización de falso negativo