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

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

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

Спасибо :)

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

...

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

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

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


python string fuzzy-search fuzzy-comparison
person significance    schedule 04.03.2011    source источник

Ответы (4)


arrow_upward
1
arrow_downward

Да.

google("python levenshtein")
person John Machin    schedule 04.03.2011

arrow_upward
1
arrow_downward

difflib.get_close_matches должен работать.

person mgautierfr    schedule 04.03.2011

arrow_upward
0
arrow_downward

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

from difflib import context_diff

a = 'acaacbaaca'
b = 'accabcaacc'

print ''.join(context_diff(a,b))
person lafras    schedule 04.03.2011

arrow_upward
0
arrow_downward

Расстояние Левенштейна работает очень похоже на нечеткую стандартную функцию ratio(). 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
person sk8asd123    schedule 02.08.2013