TheFuzz (FuzzyWuzzy) — нечёткое сравнение строк

FuzzyWuzzy — это библиотека Python, предназначенная для нечёткого сравнения строк. Более подробно с алгоритмом сравнения можно ознакомится на википедии Расстояние Левенштейна.

Введение

Кейсов использования этой библиотеки множество, но я расскажу как использовал ее я. У меня есть небольшой сервис парсинга RSS лент из разных источников, после агрегации данных статьи отправляются ко мне на электронную почту и частенько получается так, что события происходящие в мире отражаются одновременно на нескольких ресурсах. В конечном итоге я получаю несколько разных вариантов одного и того же события у себя в новостях. Благодаря расстоянию Левенштейна я могу производить сверку заголовка новостной статьи с уже существующими новостями в моем хранилище и исключать дублирование контента. 

Установка

Существует два способа установки. Ручной и автоматический. Рассмотрим оба варианта.

С помощью pip

pip install fuzzywuzzy

С помощью setuptools

git clone git://github.com/seatgeek/fuzzywuzzy.git fuzzywuzzy
cd fuzzywuzzy
python setup.py install

Существует еще небольшой лайфхак, чтобы ускорить сравнение в 5-10 раз. Необходимо дополнительно установить библиотеку python-Levenshtein

pip install python-Levenshtein

Использование

Перед началом необходимо импортировать библиотеку в код.

from fuzzywuzzy import fuzz as f 
from fuzzywuzzy import process as p

Простое сравнение

Самое простой вариант сравнения, в результате мы получаем число — показатель сходства двух строк. Максимальный показатель — 100.

f.ratio("Строка для проверки", "Проверка строки")

41

Частичное сравнение

Данный тип сравнения ищет строку №1 в строке №2.

f.partial_ratio("Строка для проверки", "Строка для проверки расстояния Левенштейна")

100

Сравнение по токену

Слова сравниваются друг с другом независимо от регистра букв или порядка слов.

f.ratio("Строка для проверки", "Проверки для строка")

37

f.token_sort_ratio("Строка для проверки", "Проверки для строка")

100

Сравнение соотношения токенов

Отличается от предыдущего тем, что уравнивает строки в которых дублируются слова.

f.token_sort_ratio("Строка для проверки", "Строка Строка для проверки")

84

f.token_set_ratio("Строка для проверки", "Строка Строка для проверки")

100

Продвинутое сравнение 

Рассматривая исходный код данной библиотеки, я наткнулся на еще один метод сравнения строк. Почему-то в документации на github у автора этой библиотеки информации о нем нет. Этот тип сравнения подходит для большинства задач. Он не учитывает регистр букв и знаки препинания не разделяющие предложения. 

f.WRatio('Хлеб всему голова', '!ХлеБ ВСему ГОЛОВА!')

100

Сравнение со списком

Для пакетного сравнения текста со списком используется метод process. Для получения первого вхождения необходимо использовать метод extractOne.

list_var = ["Москва", "Магнитогорск", "Магадан", "Светлогорск", "Железногорск", "Медногорск"]
p.extractOne("Магнитогорск", list_var)

('Магнитогорск', 100)

p.extract("Магнитогорск", list_var, limit=3)

[('Магнитогорск', 100), ('Медногорск', 73), ('Светлогорск', 61)]

Заключение

Сегодня мы рассмотрели библиотеку FuzzyWuzzy, провели поэтапно все процессы использования от установки до написания программ и проверки использования алгоритмов расстояния Левенштейна.