Comparação de strings difusos de alto desempenho em Python, use Levenshtein ou difflib [closed]

Estou fazendo a normalização de mensagens clínicas (verificação ortográfica), na qual verifico cada palavra contra o dicionário médico de 900.000 palavras. Estou mais preocupado com a complexidade / desempenho do tempo.

Quero fazer uma comparação de strings difusos, mas não tenho certeza de qual biblioteca usar.

Opção 1:

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

Result: 0.625

Opção 2:

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

Result: 0.625

Neste exemplo, ambos dão a mesma resposta. Você acha que os dois desempenham o mesmo nesse caso?

Caso você esteja interessado em uma rápida comparação visual da semelhança entre Levenshtein e Difflib, calculei ambos para aproximadamente 2,3 milhões de títulos de livros:

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

Em seguida, plotei os resultados com R:

Estritamente para os curiosos, também comparei os valores de similaridade Difflib, Levenshtein, Sørensen e Jaccard:

library(ggplot2)
require(GGally)

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

ggpairs(difflib)

Resultado:

A semelhança de Difflib / Levenshtein é realmente bastante interessante.

Edição de 2018: se você estiver trabalhando na identificação de sequências semelhantes, também poderá conferir o meu código - há uma ótima visão geral aqui . O Minhashing é incrível ao encontrar semelhanças em grandes coleções de texto em tempo linear. Meu laboratório montou um aplicativo que detecta e visualiza a reutilização de texto usando minhashing aqui: https://github.com/YaleDHLab/intertext

• difflib.SequenceMatcher usa o algoritmo Ratcliff / Obershelp , que calcula o número dobrado de caracteres correspondentes dividido pelo número total de caracteres nas duas seqüências.

• Levenshtein usa o algoritmo Levenshtein que calcula o número mínimo de edições necessárias para transformar uma string em outra

Complexidade

O SequenceMatcher é um período quadrático para o pior caso e o comportamento do caso esperado depende de uma maneira complicada de quantos elementos as seqüências têm em comum. ( daqui )

Levenshtein é O (m * n), onde n e m são o comprimento das duas seqüências de entrada.

atuação

De acordo com o código-fonte do módulo Levenshtein: Levenshtein tem alguma sobreposição com difflib (SequenceMatcher). Ele suporta apenas strings, não tipos de sequência arbitrários, mas, por outro lado, é muito mais rápido.