Высокопроизводительное сравнение нечетких строк в Python, используйте Левенштейн или diffflib [закрыто]

130

Я выполняю нормализацию клинических сообщений (проверку орфографии), в которой я проверяю каждое данное слово по медицинскому словарю на 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

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

Мэгги
источник

Ответы:

154

Если вас интересует быстрое визуальное сравнение сходства Левенштейна и Difflib, я рассчитал оба для ~ 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:

введите описание изображения здесь

Строго для любопытных я также сравнил значения схожести Difflib, Levenshtein, Sørensen и Jaccard:

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

duhaime
источник
2
Это супер круто! Что ты думаешь об этом тогда? Левенштейн просто плох для строк длиной в заголовок?
Ульф Аслак
3
Это действительно зависит от того, что вы пытаетесь уловить в своей метрике сходства ...
Duhaime
2
Я думаю, что некоторые разногласия между difflib и levenshtein могут быть объяснены эвристикой autojunk, используемой difflib. Что будет, если отключить?
Майкл
2
Это хороший вопрос. Фильтр autojunk вступает в силу только в том случае, если количество наблюдений> 200, поэтому я не уверен, сильно ли повлиял бы на этот конкретный набор данных (названия книг), но его стоит изучить ...
Duhaime
2
@duhaime, спасибо за подробный анализ. Я новичок в подобных сюжетах и ​​понятия не имею, как их интерпретировать. Как называются сюжеты, чтобы я мог найти их и узнать о них?
Зак Янг
104
  • diffflib.SequenceMatcher использует алгоритм Ratcliff / Obershelp , он вычисляет удвоенное количество совпадающих символов, деленное на общее количество символов в двух строках.

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

сложность

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

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

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

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

Гассен Хамруни
источник
Большое спасибо за информацию. Я добавил больше деталей. вот оно: как 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.вы думаете, в этом случае оба действуют одинаково.
Maggie