Comparaison de chaînes floues hautes performances en Python, utilisez Levenshtein ou difflib [fermé]

Je fais la normalisation des messages cliniques (vérification orthographique) dans laquelle je vérifie chaque mot donné par rapport au dictionnaire médical de 900 000 mots. Je suis plus préoccupé par la complexité du temps / les performances.

Je veux faire une comparaison floue de chaînes, mais je ne suis pas sûr de la bibliothèque à utiliser.

Option 1:

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

Result: 0.625

Option 2:

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

Result: 0.625

Dans cet exemple, les deux donnent la même réponse. Pensez-vous que les deux fonctionnent de la même manière dans ce cas?

Au cas où vous seriez intéressé par une comparaison visuelle rapide de la similitude entre Levenshtein et Difflib, j'ai calculé les deux pour ~ 2,3 millions de titres de livres:

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

J'ai ensuite tracé les résultats avec R:

Pour les curieux, j'ai également comparé les valeurs de similarité Difflib, Levenshtein, Sørensen et Jaccard:

library(ggplot2)
require(GGally)

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

ggpairs(difflib)

Résultat:

La similitude Difflib / Levenshtein est vraiment très intéressante.

Édition 2018: Si vous travaillez sur l'identification de chaînes similaires, vous pouvez également consulter minhashing - il y a un excellent aperçu ici . Minhashing est incroyable pour trouver des similitudes dans de grandes collections de texte en temps linéaire. Mon laboratoire a mis en place une application qui détecte et visualise la réutilisation de texte à l'aide de minhashing ici: https://github.com/YaleDHLab/intertext

• difflib.SequenceMatcher utilise l' algorithme Ratcliff / Obershelp , il calcule le nombre doublé de caractères correspondants divisé par le nombre total de caractères dans les deux chaînes.

• Levenshtein utilise l' algorithme de Levenshtein, il calcule le nombre minimum de modifications nécessaires pour transformer une chaîne en une autre

Complexité

SequenceMatcher est le temps quadratique pour le pire des cas et a un comportement de cas attendu dépendant d'une manière compliquée du nombre d'éléments que les séquences ont en commun. ( d'ici )

Levenshtein est O (m * n), où n et m sont la longueur des deux chaînes d'entrée.

Performance

Selon le code source du module Levenshtein: Levenshtein a un certain chevauchement avec difflib (SequenceMatcher). Il ne prend en charge que les chaînes, pas les types de séquence arbitraires, mais d'un autre côté, c'est beaucoup plus rapide.