Нечёткое сравнение строк: пойми меня, если сможешь

На естественном языке сказать об одном и том же факте можно бесконечным числом способов. Можно переставлять слова местами, заменять их на синонимы, склонять по падежам (если говорим о языке с падежами) и тд.

Необходимость определять схожесть двух фраз возникла при решении одной небольшой практической задачи. Я не использовал машинное обучение, не вил нейронные сети, но использовал простые метрики и собранную статистику для калибровки коэффициентов.

Результатом работы, описанием процесса, кодом на git'е готов поделиться с вами.

Итак, кратко задачу можно озвучить так: «С определенной периодичностью из различных источников приходят актуальные новости. Необходимо фильтровать их таким образом, чтобы на выходе не было двух новостей об одном и том же факте.»

Ограничения задачи

Задача имеет прикладной характер, необходимо задать ограничения:

1. Каждая новость состоит из заголовка и тела (содержания).
2. Заголовок — это осмысленное предложение на естественном языке, по которому человек может понять суть новости.
3. Заголовок имеет длину не более 100 символов. Он может состоять из любых символов, включая цифры, пунктуацию и спец.символов.
4. Максимальное количество новых новостей, которые могут появиться в промежуток 5 минут — 20 штук.
5. Новую новость необходимо сравнивать со всеми новостями, которые приходили за последние сутки.

16; Правительство внесло изменения в программу развития Курил 18; Кабмин увеличил финансирование федеральной программы развития Курил 19; Правительство увеличило финансирование программы развития Курил

6; Инженеры стали самыми востребованными на рынке труда 12; Названы самые востребованные в России профессии 20; Стали известны самые востребованные профессии в России 26; Инженеры признаны самыми востребованными на рынке труда в РФ 32; Инженеры стали самыми востребованными на рынке труда РФ в сентябре 51; Названы самые востребованные профессии в России 53; Минтруд назвал самые востребованные профессии в России

25; Сбербанк с 16 октября снижает ставки по потребительским кредитам 31; Сбербанк снизил процентные ставки по ряду кредитов 37; Сбербанк снизил ставки по ряду кредитов

0; В России выпустят собственную криптовалюту — крипторубль 5; Россия срочно создает крипторубль 27; В России займутся выпуском крипторубля 35; В России создадут свою криптовалюту 36; Россия начнет выпускать крипторубли 42; Россия выпустит собственную криптовалюту – крипторубль

Способы нечёткого сравнения строк

Опишу несколько методов для решения задачи определения степени схожести двух строк.

Возвращает число, которое показывает сколько нужно сделать операций (вставка, удаление или замена) для того, чтобы превратить одну строку в другую. Свойства: простая реализация; зависимость от порядка слов; на выходе число; которое надо с чем-то сравнить.

Разбивает тексты на шинглы (англ. — чешуйки), т.е цепочки по 10 слов (с пересечениями), применив к шинглам хеш-функции получает матрицы, которые и сравнивает между собой. Свойства: чтобы реализовать алгоритм надо подробно изучать мат.часть; работает на больших текстах; нет зависимости от порядка предложений.

здесь a — количество символов в первой строке, b — количество символов во второй строке, c — количество совпадающих символов. Свойства: прост в реализации; низкая точность, так как «abc» и «bca» для него одно и то же.

Комбинированных подход

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

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

Нормализация сравниваемых предложений Строки переводятся в нижний регистр, удаляются все символы, отличные от букв, цифр и пробела.

Выделение слов Словами считаются все последовательности символов без пробелов, которые имеют длину >= 3. Этим самым удаляются почти все предлоги, союзы и тд. — в какой степени это можно отнести к продолжению нормализации.

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

Здесь применяется коэффициент Танимото, но не к символам, а к кортежам из подряд идущих символов, причем кортежи составляются с нахлестом.

Применение коэффициента Танимото к заголовку Мы знаем сколько всего слов в каждом из предложений, знаем количество «нечётко совпадающих» слов и применяем к этому знакомую формулу.

Алгоритм был протестирован на сотнях заголовков в течении нескольких дней, результаты его работы визуально оказались вполне приемлемыми, но надо было оптимально подобрать следующие коэффициенты:

ThresholdSentence — порог принятия нечеткой эквивалентности всего предложения; ThresholdWord — порог принятия нечеткой эквивалентности между двумя словами; SubtokenLength — размер подстроки при сравнении двух слов (от 1 до MinWordLength)

Оценка качества работы алгоритмы

Для оценки качества работы были выделены 100 различных заголовков новостей, которые приходили друг за другом. Далее была размечена квадратная матрица 100x100, где я поставил 0, если заголовки были на разные темы и 1, если темы совпадали. Понимаю, что выборка небольшая и, возможно, не очень точно будет демонстрировать точность работы алгоритма, но меня на большее не хватило.

Теперь, когда есть образец, с которым можно сравнивать выход алгоритма, будем оценивать точность простой формулой — отношением правильных ответов к общему числу сравнений. Кроме того, как метрику, можно оценивать число ложных срабатываний.

Наилучшие результаты c точность 87% и числом ложных срабатываний 3% получаются при следующих параметрах: ThresholdSentence = 0.25, ThresholdWord = 0.45, SubtokenLength = 2;

Сравнение результатов работы алгоритма с моделью

Трактовать результаты можно так: Наилучшая точность и наименьшее число ошибок получается, если при сравнении слов считать длину подстрок равной 2 символам, при этом должно быть отношение количества совпадающих подстрок к количеству несовпадающих большим или равным 0.45, а два заголовка будут эквивалентными, если не менее четверти слов совпадали.

Если учитывать введенные ограничения, вполне корректные результаты. Конечно, искусственно можно придумать сколько угодно вариантов, на которых появятся ложные срабатывания.

Заключение

Истоки этой задачи лежат в том, что мне понадобилось организовать себе оперативную доставку актуальных новостей. Источники информации — СМИ, которые я постоянно читаю, сидя в интернете, теряя при этом уйму времени, отвлекаясь на ненужную информацию, лишние переходы по ссылкам. В результате родились несколько небольших каналов telegram и групп в контакте. Если вдруг кому-то будет интересно, ссылки есть в описании моего профиля.

Готовая реализация алгоритмы в виде библиотеки: SentencesFuzzyComparison.