Применение библиотеки FuzzyWuzzy для нечёткого сравнения в Python. Расстояние Левенштейна (редакционное расстояние)

У него не было уверенности, что он правильно расслышал. От этого так много зависело! Но не переспрашивать же? (с) Борис Акунин. Весь мир театр.

Первые шаги

pip install fuzzywuzzy

pip install python-Levenshtein

from fuzzywuzzy import fuzz
from fuzzywuzzy import process

Функционал

a = fuzz.ratio('Привет мир', 'Привет мир')
print(a)
#Выводит в консоль: 100

a = fuzz.ratio('Привет мир', 'Привт кир')
print(a)
#Выводит в консоль: 84

a = fuzz.partial_ratio('Привет мир', 'Привет мир!')
print(a)
#Выводит в консоль: 100

a = fuzz.partial_ratio('Привет мир', 'Люблю колбасу, Привет мир')
print(a)
#Выводит в консоль: 100

a = fuzz.partial_ratio('Привет мир', 'Люблю колбасу, привет мир')
print(a) 

#Выводит в консоль: 90

a = fuzz.token_sort_ratio('Привет наш мир', 'мир наш Привет')
print(a)
#Выводит в консоль: 100

a = fuzz.token_sort_ratio('Привет наш мир', 'мир наш любимый Привет')
print(a)
#Выводит в консоль: 78

a = fuzz.token_sort_ratio('1 2 Привет наш мир', '1 мир наш 2 ПриВЕт')
print(a)
#Выводит в консоль: 100

a = fuzz.token_set_ratio('Привет наш мир', 'мир мир наш наш наш ПриВЕт')
print(a)
#Выводит в консоль: 100

a = fuzz.WRatio('Привет наш мир', '!ПриВЕт наш мир!')
print(a)
#Выводит в консоль: 100

a = fuzz.WRatio('Привет наш мир', '!ПриВЕт, наш мир!')
print(a)
#Выводит в консоль: 97

city = ["Москва", "Санкт-Петербург", "Саратов", "Краснодар", "Воронеж", "Омск", "Екатеринбург", "Орск", "Красногорск", "Красноярск", "Самара"]
a = process.extract("Саратов", city, limit=2)
# Параметр limit по умолчанию имеет значение 5
print(a)
#Выводит в консоль: [('Саратов', 100), ('Самара', 62)]

city = ["Москва", "Санкт-Петербург", "Саратов", "Краснодар", "Воронеж", "Омск", "Екатеринбург", "Орск", "Красногорск", "Красноярск", "Самара"]
a = process.extractOne("Краногрск", city)
print(a)
#Выводит в консоль: ('Красногорск', 90)

Применение

#открытие файла на рабочем столе
try:
    files = os.listdir('C:\\Users\\hartp\\Desktop\\')
    filestart = process.extractOne(namerec, files)
    if filestart[1] >= 80:
        os.startfile('C:\\Users\\hartp\\Desktop\\' + filestart[0])
    else:
        speak('Файл не найден')
except FileNotFoundError:
    speak('Файл не найден')

files = os.listdir('C:\\Users\\hartp\\Desktop\\')
print(files)
#Выводит в консоль: 'Visual Studio 2019.lnk', 'Visual Studio Code.lnk', 'WarThunder.lnk', 'WpfApp14', 'Yandex.lnk', 'Автобус.docx', 'Аэрофлот.txt', 'Для курсача.txt' и т.д.

city = ["Москва", "Санкт-Петербург", "Саратов", "Краснодар", "Воронеж", "Омск", "Екатеринбург", "Орск", "Красногорск", "Красноярск", "Самара"]
a = process.extractOne("Краногрск", city)
print(a)
#Выводит в консоль: ('Красногорск', 90)

Все дороги ведут к матану

Скрыл от людей, которые боятся математики

Если вам не интересна математика, то можете смело закрывать статью, так как сейчас будет мясо(нет). Сейчас постараюсь кратко и понятно донести смысл расстояния Левенштейна до таких же чайников, как и я.

Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — метрика, измеряющая разность между двумя последовательностями символов.
У нас есть две строки S1 размером i и S2 размером j
S1=vrhk
S2=rhgr

Существует только 3 операции:

1. Замена: r → v
2. Удаление: -r
3. Подстановка: rVhgr

Теперь создадим табличку для сравнения этих двух строк:



Откуда в таблице появились 0 и 1? Для превращения пустого символа в пустой символ нам никаких операций проводить не нужно (пишем в таблицу — «0»), а для превращения символа r в пустую строку, необходимо удалить r (одно действие, пишем в таблицу — «1»). С символом v аналогичная ситуация.

Для перехода rh в пустой символ необходимо сначала удалить h, а потом r (используется две операции), следовательно, таблица примет вид:



Теперь рассмотрим ситуацию превращения v в r (отмечена зелёным кругом на таблице).

Существует несколько путей, но мы выбираем наименьший — превращение пустого символа в v.

В ячейку заносим 1. Как так получилось? Мы представляем r как строку, которую нужно превратить в строку v. Перед r существует пустой символ, который мы заменяем на v, получая строку rv. Так как мы проверяем символы справа налево, то v совпадает с v.

Иная форма записи примера

Пришло время рассмотреть превращение v в rh



Самый удачный вариант — v мы заменяем на h и всё сводится к задаче превращения r в пустую строку.

Иная форма записи примера

Результат заносим в таблицу.



В сравнении vr с r нужно учесть, что последние символы совпадают, а это значит, что задача просто сводится до более простой, без изменения расстояния Левенштейна.

Иная форма записи примера

При преобразовании vrh в r достаточно удаления h и эта задача сводится к предыдущей (сравнение vr с r), следовательно расстояние будет равно 2

Иная форма записи примера

Как и в случае сравнения vr с r у нас совпадают окончание строк vrh и rh, следовательно, расстояние не изменится.



Заметьте, что vrh и rhg идентичны с нашим предыдущим преобразованием, но с отличием в одну букву, которую просто необходимо убрать, именно из-за этого наше расстояние увеличивается на единицу (обратите внимание на стрелку).

Опираясь на все примеры, описанные выше, мы получаем кратчайшое редакционное расстояние (расстояние Левенштейна) между двумя строками — vrhk и rhgr.

Благодарю всех за внимание! Надеюсь данная статья кому-нибудь окажется полезной.