Автоматизация, Программирование

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

Время прочтения: 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)

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

Советуем почитать