Machine learning
NTA
56

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

Как сопоставить данные большого объема? В этой статье я хочу поделиться практикой решения задачи, когда данные совпадают по косвенным признакам и имеют различную структуру. Например, поиск совпадений адресов из внешних источников с внутренними базами данных. Для этого я использовал язык программирования 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)

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

Лайфхаки IT, проверенные решения для стандартных задач
{ "author_name": "NTA", "author_type": "editor", "tags": [], "comments": 0, "likes": 1, "favorites": 2, "is_advertisement": false, "subsite_label": "ml", "id": 149283, "is_wide": true, "is_ugc": false, "date": "Tue, 11 Aug 2020 11:43:44 +0300", "is_special": false }
Маркетинг
Как бизнесу заработать в соцсетях в 2020 году: полноценное руководство с прогнозами и примерами
Пошаговая рабочая стратегия продвижения бизнеса в соцсетях с медиапланом и примерами внедрения от директора «Студии…
Объявление на vc.ru
0
Комментариев нет
Популярные
По порядку

Комментарии

null