Pregunta Comparación de cadenas difusas en Python, confundido con qué biblioteca usar [cerrado]


Quiero hacer una comparación de cadenas difusas, pero estoy confundido 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 haciendo la normalización del mensaje clínico (revisión ortográfica) en la cual reviso cada palabra dada contra el diccionario médico de 900,000 palabras. Me preocupa más el tiempo de complejidad / rendimiento.

¿Crees que ambos funcionan igual en este caso?


73
2017-07-14 08:56


origen


Respuestas:


En caso de que esté interesado en una comparación visual rápida de similitudes entre 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:

enter image description here

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: enter image description here

La similitud de Difflib / Levenshtein realmente es bastante interesante.

Edición de 2018: si estás trabajando en la identificación de cadenas similares, también puedes echar un vistazo a minhashing: hay una gran visión general aquí. Minhashing es increíble al encontrar similitudes en colecciones de texto grandes en mucho más tiempo que O (n ** 2) tiempo. Mi laboratorio creó una aplicación que detecta y visualiza la reutilización de texto usando minhashing aquí: https://github.com/YaleDHLab/intertext


85
2017-07-06 01:11



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

  • Levenshtein utiliza Algoritmo de Levenshtein calcula la cantidad mínima de ediciones necesarias para transformar una cadena en la otra

Complejidad

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

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

Actuación

De acuerdo con la código fuente del módulo de 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.


82
2017-07-14 09:05