Hochleistungs-Fuzzy-String-Vergleich in Python, Levenshtein oder Difflib verwenden [geschlossen]

127

Ich mache eine Normalisierung der klinischen Nachricht (Rechtschreibprüfung), bei der ich jedes gegebene Wort mit einem medizinischen Wörterbuch mit 900.000 Wörtern vergleiche. Ich bin mehr besorgt über die zeitliche Komplexität / Leistung.

Ich möchte einen Fuzzy-String-Vergleich durchführen, bin mir aber nicht sicher, welche Bibliothek ich verwenden soll.

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

In diesem Beispiel geben beide die gleiche Antwort. Denken Sie, dass beide in diesem Fall gleich abschneiden?

Maggie
quelle

Antworten:

152

Falls Sie an einem schnellen visuellen Vergleich der Ähnlichkeit von Levenshtein und Difflib interessiert sind, habe ich beide für ~ 2,3 Millionen Buchtitel berechnet:

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

Ich habe dann die Ergebnisse mit R aufgezeichnet:

Geben Sie hier die Bildbeschreibung ein

Streng für Neugierige habe ich auch die Ähnlichkeitswerte Difflib, Levenshtein, Sørensen und Jaccard verglichen:

library(ggplot2)
require(GGally)

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

ggpairs(difflib)

Ergebnis: Geben Sie hier die Bildbeschreibung ein

Die Difflib / Levenshtein-Ähnlichkeit ist wirklich sehr interessant.

Bearbeiten 2018: Wenn Sie daran arbeiten, ähnliche Zeichenfolgen zu identifizieren, können Sie auch Minhashing ausprobieren - hier finden Sie eine großartige Übersicht . Minhashing ist erstaunlich, wenn es darum geht, Ähnlichkeiten in großen Textsammlungen in linearer Zeit zu finden. Mein Labor hat hier eine App zusammengestellt, die die Wiederverwendung von Text mithilfe von Minhashing erkennt und visualisiert: https://github.com/YaleDHLab/intertext

duhaime
quelle
2
Das ist super cool! Wie sehen Sie das dann? Ist Levenshtein nur schlecht für Titel-Saiten?
Ulf Aslak
3
Es hängt wirklich davon ab, was Sie in Ihrer Ähnlichkeitsmetrik erfassen
möchten
2
Ich denke, einige der Meinungsverschiedenheiten zwischen Difflib und Levenshtein lassen sich möglicherweise aufgrund der von Difflib verwendeten Autojunk-Heuristik erklären. Was passiert, wenn Sie es deaktivieren?
Michael
2
Das ist eine gute Frage. Der Autojunk-Filter wird nur wirksam, wenn die Anzahl der Beobachtungen> 200 ist, daher bin ich mir nicht sicher, ob dieser bestimmte Datensatz (Buchtitel) stark betroffen gewesen wäre, aber es lohnt sich, ihn zu untersuchen ...
duhaime
2
@duhaime, danke für diese detaillierte Analyse. Ich bin neu in solchen Handlungen und habe keine Ahnung, wie ich sie interpretieren soll. Wie heißen die Handlungen, damit ich sie nachschlagen und etwas über sie erfahren kann?
Zach Young
104
  • difflib.SequenceMatcher verwendet den Ratcliff / Obershelp- Algorithmus und berechnet die doppelte Anzahl übereinstimmender Zeichen geteilt durch die Gesamtzahl der Zeichen in den beiden Zeichenfolgen.

  • Levenshtein verwendet den Levenshtein-Algorithmus , der die minimale Anzahl von Änderungen berechnet, die erforderlich sind, um eine Zeichenfolge in die andere umzuwandeln

Komplexität

SequenceMatcher ist die quadratische Zeit für den schlimmsten Fall und hat ein Verhalten im erwarteten Fall, das in komplizierter Weise davon abhängt, wie viele Elemente die Sequenzen gemeinsam haben. ( von hier )

Levenshtein ist O (m * n), wobei n und m die Länge der beiden Eingabezeichenfolgen sind.

Performance

Gemäß dem Quellcode des Levenshtein-Moduls: Levenshtein hat eine gewisse Überlappung mit Difflib (SequenceMatcher). Es werden nur Zeichenfolgen unterstützt, keine beliebigen Sequenztypen, andererseits ist es viel schneller.

Ghassen Hamrouni
quelle
Vielen Dank für die Info. Ich habe weitere Details hinzugefügt. Hier ist es: I am doing clinical message normalization (spell check) in which I check each given word against 900,000 word medical dictionary. I am more concern about the time complexity/performance.Glauben Sie, dass beide in diesem Fall gleich abschneiden?
Maggie