separar - Comparación de cadenas difusas en Python, confundida con qué biblioteca usar

python separar string por caracter

Question

Quiero hacer una comparación de cadenas difusas, pero confuso con 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. Pero prefiero usar difflib . Cualquier sugerencia de expertos. Gracias.

Updated:

Estoy realizando la normalización de mensajes clínicos (corrección ortográfica) en la que verifico cada palabra dada con un diccionario médico de 900,000 palabras. Estoy más preocupado por la complejidad del tiempo / rendimiento.

¿Crees que ambos se comportan igual en este caso?

Answer 1

En caso de que esté interesado en una comparación visual rápida de la similitud de Levenshtein y Difflib, calculé ambos para aproximadamente 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 graficé 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 Difflib / Levenshtein realmente es bastante interesante.

Edición de 2018: si está trabajando en la identificación de cadenas similares, también puede revisar el minhashing. Aquí hay una gran descripción general . Minhashing es asombroso al encontrar similitudes en grandes colecciones de texto mucho más rápido que O (n ** 2). Mi laboratorio creó una aplicación que detecta y visualiza la reutilización de texto usando minhashing aquí: https://github.com/YaleDHLab/intertext

Answer 2

• difflib.SequenceMatcher utiliza el algoritmo Ratcliff/Obershelp que calcula el número duplicado de caracteres coincidentes dividido por el número total de caracteres en las dos cadenas.

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

Complejidad

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

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

Actuación

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