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ć.
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
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.
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.
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.
źródło
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.