Comparaison de chaînes de caractères floues à haute performance en Python, utilisez Levenshtein ou difflib

Question

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

Je veux faire une comparaison floue de chaînes de caractères, 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 ont la même performance dans ce cas ?

Answer 1

Au cas où vous seriez intéressé par une comparaison visuelle rapide de la similarité 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 :

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

2018 edit : Si vous travaillez sur l'identification de chaînes de caractères similaires, vous pourriez également vérifier le minhashing - il y a un un bon aperçu ici . Le minhashing permet de trouver des similitudes dans de grandes collections de textes en temps linéaire. Mon laboratoire a créé une application qui détecte et visualise la réutilisation de textes en utilisant le minhashing : https://github.com/YaleDHLab/intertext

Answer 2

• difflib.SequenceMatcher utilise la fonction Ratcliff/Obershelp L'algorithme calcule le double du nombre de caractères correspondants divisé par le nombre total de caractères dans les deux chaînes.

• Levenshtein utilise Algorithme de Levenshtein il calcule le nombre minimum d'éditions nécessaires pour transformer une chaîne en une autre

Complexité

SequenceMatcher est un temps quadratique dans le pire des cas et a un comportement attendu qui dépend 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 les longueurs des deux chaînes d'entrée.

Performance

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