Есть ли реализация этого метода сопоставления строк в Python?

Question

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

Есть ли какая-либо реализация следующего подхода в python, или мне нужно попытаться свернуть свой собственный?

Спасибо:)

из Википедии :

...

Подход грубой силы будет заключаться в вычислить расстояние редактирования до P для всех подстроки T, а затем выберите подстрока с минимальным расстоянием. Однако этот алгоритм будет иметь время работы O (n3 м)

Лучшее решение [3] [4], использующее динамическое программирование, использует альтернативная формулировка проблема: для каждой позиции J в текст T и каждая позиция я в шаблон P, рассчитать минимальное редактирование расстояние между первым символы шаблона, пи и любой подстрока Tj ', j из T, которая заканчивается в положение j.

Какой самый эффективный способ применить это ко многим строкам?

Answer 1

Да.

google("python levenshtein")

Answer 2

difflib.get_close_matches должна выполнить работу.

Answer 3

Расстояние Левенштейна работает очень похоже на функцию нечеткого стандартного отношения ().fuzzywuzzy использует difflib http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

пример из документации по fuzzywuzzy: https://github.com/seatgeek/fuzzywuzzy

fuzz.ratio("this is a test", "this is a test!")
    96

Answer 4

difflib может быть ответом, например,

from difflib import context_diff

a = 'acaacbaaca'
b = 'accabcaacc'

print ''.join(context_diff(a,b))