Comparación de cadenas difusas de alto rendimiento en Python, use Levenshtein o difflib [cerrado]

127

Estoy haciendo normalización de mensajes clínicos (revisión ortográfica) en la que verifico cada palabra con el diccionario médico de 900,000 palabras. Me preocupa más la complejidad / rendimiento del tiempo.

Quiero hacer una comparación de cadenas difusa, pero no estoy seguro de qué biblioteca usar.

Opción 1:

import Levenshtein
Levenshtein.ratio('hello world', 'hello')

Result: 0.625

Opcion 2:

import difflib
difflib.SequenceMatcher(None, 'hello world', 'hello').ratio()

Result: 0.625

En este ejemplo, ambos dan la misma respuesta. ¿Crees que ambos se desempeñan igual en este caso?

Maggie
fuente

Respuestas:

152

En caso de que esté interesado en una comparación visual rápida de la similitud de Levenshtein y Difflib, calculé ambos para ~ 2.3 millones de títulos de libros:

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

Luego tracé los resultados con R:

ingrese la descripción de la imagen aquí

Estrictamente para los curiosos, también comparé los valores de similitud de Difflib, Levenshtein, Sørensen y Jaccard:

library(ggplot2)
require(GGally)

difflib <- read.table("similarity_measures.txt", sep = " ")
colnames(difflib) <- c("difflib", "levenshtein", "sorensen", "jaccard")

ggpairs(difflib)

Resultado: ingrese la descripción de la imagen aquí

La similitud de Difflib / Levenshtein realmente es bastante interesante.

Edición de 2018: si está trabajando en la identificación de cadenas similares, también puede consultar minhashing: aquí hay una excelente descripción general . Minhashing es sorprendente para encontrar similitudes en grandes colecciones de texto en tiempo lineal. Mi laboratorio creó una aplicación que detecta y visualiza la reutilización de texto usando minhashing aquí: https://github.com/YaleDHLab/intertext

duhaime
fuente
2
¡Esto es súper genial! ¿Cuál es tu opinión sobre esto entonces? ¿Levenshtein es malo para las cadenas de título?
Ulf Aslak
3
Realmente depende de lo que intentes capturar en tu métrica de similitud ...
duhaime
2
Creo que algunos de los desacuerdos entre difflib y levenshtein pueden explicarse debido a la heurística de autojunk utilizada por difflib. ¿Qué sucede si lo deshabilita?
Michael
2
Buena pregunta. El filtro autojunk sólo tiene efecto si el número de observaciones es> 200, así que no estoy seguro de si este conjunto de datos en particular (títulos de libros) habría sido muy afectada, pero la investigación de la pena ...
duhaime
2
@duhaime, gracias por este análisis detallado. Soy nuevo en este tipo de tramas y no tengo idea de cómo interpretarlas. ¿Cómo se llaman las tramas, para que pueda buscarlas y conocerlas?
Zach Young
104
  • difflib.SequenceMatcher utiliza el algoritmo Ratcliff / Obershelp , calcula el número duplicado de caracteres coincidentes dividido por el número total de caracteres en las dos cadenas.

  • Levenshtein utiliza el algoritmo de Levenshtein , calcula el número mínimo de ediciones necesarias para transformar una cadena en la otra

Complejidad

SequenceMatcher es el tiempo cuadrático para el peor de los casos y el comportamiento del caso esperado depende de manera complicada de cuántos elementos tienen en común las secuencias. ( desde aquí )

Levenshtein es O (m * n), donde nym son la longitud de las dos cadenas de entrada.

Actuación

Según el código fuente del módulo Levenshtein: Levenshtein tiene cierta superposición con difflib (SequenceMatcher). Solo admite cadenas, no tipos de secuencia arbitrarios, pero por otro lado es mucho más rápido.

Ghassen Hamrouni
fuente
Muchas gracias por la información. He agregado más detalles. aquí está: I am doing clinical message normalization (spell check) in which I check each given word against 900,000 word medical dictionary. I am more concern about the time complexity/performance.¿Crees que ambos funcionan igual en este caso?
Maggie