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

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?

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:

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:

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

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