{"id":14279,"url":"\/distributions\/14279\/click?bit=1&hash=4408d97a995353c62a7353088166cda4ded361bf29df096e086ea0bbb9c1b2fc","title":"\u0427\u0442\u043e \u0432\u044b\u0431\u0435\u0440\u0435\u0442\u0435: \u0432\u044b\u0435\u0445\u0430\u0442\u044c \u043f\u043e\u0437\u0436\u0435 \u0438\u043b\u0438 \u0437\u0430\u0435\u0445\u0430\u0442\u044c \u0440\u0430\u043d\u044c\u0448\u0435?","buttonText":"","imageUuid":""}
Машинное обучение
NTA

Поиск совпадений

Как сопоставить данные большого объема? В этой статье я хочу поделиться практикой решения задачи, когда данные совпадают по косвенным признакам и имеют различную структуру. Например, поиск совпадений адресов из внешних источников с внутренними базами данных. Для этого я использовал язык программирования Python и алгоритм Расстояния Левенштейна.

Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — это измерение, показывающее отличие между парой рядом стоящих знаков. Ее можно определить в виде минимума операций (вставки, удаления, замены), необходимых для преображения второй последовательности символов (слова, слов) в первую. Всем затратам на операции присваивается числовое значение. Расстояние Левенштейна для ‘а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 можно ограничить количество отображаемых данных.

Купить рекламу Отключить

У нас есть два типа данных:

Далее используем 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)

Осталось только применить вышеуказанный алгоритм для всех данных. Попробуйте и у Вас получится!

5 показов
1.2K открытий
0
Комментарии
Написать комментарий...
-3 комментариев
Раскрывать всегда