Wydajne porównanie rozmytych ciągów znaków w Pythonie, użyj Levenshtein lub difflib [zamknięte]

128

Robię kliniczną normalizację komunikatów (sprawdzanie pisowni), w której sprawdzam każde słowo ze słownikiem medycznym 900 000 słów. Bardziej interesuje mnie złożoność czasowa / wydajność.

Chcę zrobić rozmyte porównanie ciągów, ale nie jestem pewien, której biblioteki użyć.

Opcja 1:

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

Result: 0.625

Opcja 2:

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

Result: 0.625

W tym przykładzie obie dają tę samą odpowiedź. Czy uważasz, że w tym przypadku obaj zachowują się podobnie?

Maggie
źródło

Odpowiedzi:

152

Jeśli interesuje Cię szybkie wizualne porównanie podobieństwa Levenshteina i Diffliba, obliczyłem oba dla ~ 2,3 miliona tytułów książek:

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

Następnie wykreśliłem wyniki za pomocą R:

wprowadź opis obrazu tutaj

Ściśle dla ciekawskich porównałem również wartości podobieństwa Diffliba, Levenshteina, Sørensena i Jaccarda:

library(ggplot2)
require(GGally)

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

ggpairs(difflib)

Wynik: wprowadź opis obrazu tutaj

Podobieństwo Difflib / Levenshtein jest naprawdę dość interesujące.

Edycja 2018: Jeśli pracujesz nad identyfikacją podobnych ciągów, możesz również sprawdzić minhashing - tutaj jest świetny przegląd . Minhashing jest niesamowity w znajdowaniu podobieństw w dużych zbiorach tekstów w czasie liniowym. Moje laboratorium stworzyło aplikację, która wykrywa i wizualizuje ponowne użycie tekstu za pomocą minhashing tutaj: https://github.com/YaleDHLab/intertext

duhaime
źródło
2
To jest super fajne! Co o tym sądzisz? Czy Levenshtein jest po prostu zły dla ciągów o długości tytułu?
Ulf Aslak
3
To naprawdę zależy od tego, co próbujesz uchwycić w swoim wskaźniku podobieństwa ...
duhaime,
2
Myślę, że część rozbieżności między difflib a levenshteinem można wytłumaczyć heurystyką autojunk używaną przez difflib. Co się stanie, jeśli go wyłączysz?
Michael
2
To dobre pytanie. Filtr autojunk działa tylko wtedy, gdy liczba obserwacji jest> 200, więc nie jestem pewien, czy ten konkretny zestaw danych (tytuły książek) zostałby znacznie dotknięty, ale warto to zbadać ...
duhaime
2
@duhaime, dziękuję za tę szczegółową analizę. Jestem nowy w tego rodzaju wątkach i nie mam pojęcia, jak je interpretować. Jak nazywają się wątki, abym mógł je sprawdzić i dowiedzieć się o nich?
Zach Young,
104
  • difflib.SequenceMatcher używa algorytmu Ratcliff / Obershelp i oblicza podwojoną liczbę pasujących znaków podzieloną przez całkowitą liczbę znaków w dwóch ciągach.

  • Levenshtein używa algorytmu Levenshtein, który oblicza minimalną liczbę zmian potrzebnych do przekształcenia jednego ciągu znaków w drugi

Złożoność

SequenceMatcher to kwadratowy czas dla najgorszego przypadku i ma zachowanie oczekiwanego przypadku zależne w skomplikowany sposób od liczby elementów wspólnych sekwencji. ( stąd )

Levenshtein to O (m * n), gdzie n i m to długość dwóch ciągów wejściowych.

Występ

Zgodnie z kodem źródłowym modułu Levenshtein: Levenshtein w pewnym stopniu pokrywa się z difflib (SequenceMatcher). Obsługuje tylko łańcuchy, a nie dowolne typy sekwencji, ale z drugiej strony jest znacznie szybszy.

Ghassen Hamrouni
źródło
Dziękuję bardzo za informacje. Dodałem więcej szczegółów. oto jest: 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.Czy uważasz, że w tym przypadku obaj działają podobnie.
Maggie,