Время прочтения: 3 мин.
Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — это измерение, показывающее отличие между парой рядом стоящих знаков. Ее можно определить в виде минимума операций (вставки, удаления, замены), необходимых для преображения второй последовательности символов (слова, слов) в первую. Всем затратам на операции присваивается числовое значение. Расстояние Левенштейна для ‘аb’ и ‘ас’ как ‘ас’ ниже:
Поэтому выравнивание:
а с
а b
Длина символьной последовательности = 2
Число несоответствий(затрат) = 1
Расстояние Левенштейна равно 1, потому что для изменения «ас» в «аb» (или наоборот) потребует только одну затрату на операцию замены.
Таким образом получаем:
Расстояние = (Количество затрат) / (Длина символьной последовательности) = 0,5
1/2 = 0,5 Расстояние Левенштейна для Python выглядит следующим образом:
def distance(a, b):
"Расчет дистанции Левенштейна между «а» и «b»."
n, m = len(a), len(b)
if n > m:
a, b = b, a
n, m = m, n
current_row = range(n + 1)
for i in range(1, m + 1):
previous_row, current_row = current_row, [i] + [0] * n
for j in range(1, n + 1):
add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
if a[j - 1] != b[i - 1]:
change += 1
current_row[j] = min(add, delete, change)
return current_row[n]
(с) Материал из Викиучебника
Для Python существует большое количество бесплатных библиотек, для решения задачи будем использовать FuzzyWuzzy. FuzzyWuzzy — это библиотека соответствия строк. Другими словами, она говорит вам, насколько похожи два фрагмента текста (и некоторые другие функции).
from fuzzywuzzy import fuzz
В ней представлены такие функции как: Простое соотношение (ratio) – производит точное сравнение:
fuzz.ratio ("привет","Привет!")
>>> 77
fuzz.ratio ("привет","рпиавет!")
>>> 71
fuzz.ratio ("привет","привет!")
>>> 92
Частичное соотношение (partial_ratio), — производит «умное» сравнение с учетом возможных ошибок:
fuzz.partial_ratio ("привет","рпиавет!")
>>> 83
fuzz.partial_ratio ("привет","Привет!")
>>> 83
fuzz.partial_ratio ("привет","привет!")
>>> 100
Коэффициент сортировки (token_sort_ratio) производит сравнение с учетом возможных перестановок:
fuzz.ratio ("Мороз и солнце, день чудесный!", "День чудесный! Солнце и мороз")
>>> 44
fuzz.partial_ratio ("Мороз и солнце, день чудесный!", "День чудесный! Солнце и мороз")
>>> 60
fuzz.token_sort_ratio ("Мороз и солнце, день чудесный!", "День чудесный! Солнце и мороз")
>>> 100
Коэффициент соотношения (token_set_ratio) производит сравнение с учетом всех возможных изменений :
fuzz.token_sort_ratio ("Море и солнце, день чудесный!", "День чудесный! Солнце Солнце и мороз")
>>> 87
fuzz.token_set_ratio ("Море и солнце, день чудесный!", "День чудесный! Солнце Солнце и мороз")
>>> 95
Библиотека позволяет работать с данными из файлов и файлами (extract) и выводит данные от максимально до минимально похожих значений. При помощи limit можно ограничить количество отображаемых данных.
У нас есть два типа данных:
Данные 1 | Данные 2 |
г.Москва, ул. Мясницкая, д. 26А, стр.1 | улица Мясницкая, дом 26а, строение 1, город Москва |
г. Москва, ул.Оходный Ряд, дом 1 | |
дом 16, улица Льва Толстого, г. Москва | |
г. Москва, ул. Кожевническая, д.1, строение 1 |
Далее используем extractOne (показывает одно максимально похожее значение):
from fuzzywuzzy import fuzz
from fuzzywuzzy import process
A = "г.Москва, ул. Мясницкая, д. 26А, стр.1"
B = ["улица Мясницкая, дом 26а, строение 1, город Москва", " г. Москва, ул.Оходный Ряд, дом 1", " дом 16, улица Льва Толстого, г. Москва ", " г. Москва, ул. Кожевническая, д.1, строение 1"]
process.extractOne(A,B)
В результате получаем значение, максимально соответствующее искомому и коэффициент сравнения:
>>> (' 'улица Мясницкая, дом 26а, строение 1, город Москва', 78)
Осталось только применить вышеуказанный алгоритм для всех данных. Попробуйте и у Вас получится!