Высокопроизводительное сравнение нечетких строк в Python, используйте Levenshtein или difflib

Я занимаюсь нормализацией клинических сообщений (проверка орфографии), в которой я проверяю каждое данное слово по медицинскому словарю в 900 000 слов. Меня больше беспокоит сложность времени/производительность.

Я хочу сделать нечеткое сравнение строк, но я не уверен, какую библиотеку использовать.

Опция 1:

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

Result: 0.625

Вариант 2:

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

Result: 0.625

В этом примере оба дают одинаковый ответ. Как вы думаете, оба работают одинаково в этом случае?

Ответ 1

В случае, если вы заинтересованы в быстром визуальном сравнении сходства Левенштейна и Диффлиба, я рассчитал оба для ~ 2,3 миллиона названий книг:

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

Затем я нанес на график результаты с R:

Строго для любопытных я также сравнил значения сходства Диффлиба, Левенштейна, Серенсена и Жакара:

library(ggplot2)
require(GGally)

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

ggpairs(difflib)

Результат:

Сходство Диффлиба/Левенштейна действительно довольно интересно.

Редактирование 2018 года: если вы работаете над определением похожих строк, вы также можете проверить минхэширование - здесь отличный обзор. Minhashing удивительно находит сходства в больших текстовых коллекциях за линейное время. Моя лаборатория собрала приложение, которое обнаруживает и визуализирует повторное использование текста, используя minhashing здесь: https://github.com/YaleDHLab/intertext

Ответ 2

difflib.SequenceMatcher использует алгоритм Ratcliff/Obershelp, который вычисляет удвоенное количество совпадающих символов, деленное на общее количество символов в две строки.
Левенштейн использует алгоритм Левенштейна, он вычисляет минимальное количество изменений, необходимых для преобразования одной строки в другую

Сложность

SequenceMatcher представляет собой квадратичное время для наихудшего случая и имеет ожидаемое поведение, зависящее сложным образом от того, сколько элементов имеют общие последовательности. (отсюда)

Левенштейн - это O (m * n), где n и m - длина двух входных строк.

Производительность

В соответствии с исходным кодом модуля Levenshtein: Левенштейн имеет некоторое перекрытие с difflib (SequenceMatcher). Он поддерживает только строки, а не произвольные типы последовательностей, но, с другой стороны, намного быстрее.