Привет, Хабр!

Меня зовут Антон Черниговский, я участник профессионального сообщества NTA.

В публикации расскажу, как при решении задачи нечеткого сравнения строк, среди разных инструментов сравнения (по косинусному сходству, по сходству Левенштейна, по сходству Джаро‑Винклера) был выбран лучший вариант нечеткого сопоставления. Сравнение инструментов производилось исходя из скорости выполнения, правильности сравнения и простоты реализации, с помощью библиотек rapidfuzz и sklearn.

Описание проблемы

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

Проблема: на входе большое количество сканов документов в pdf-формате, которые с помощью Adobe FineReader переведены в текстовые документы формата docx и необходимо произвести некоторую классификацию. К счастью тренировать NLP-модель для этого не потребуется, т.к. документы легко классифицируются по содержанию в них конкретной фразы и нам остается лишь определить есть ли эта фраза в документе. С другой стороны, мы ещё далеки от идеального будущего, в котором computer vision правильно распознает даже скан плохого качества, и поэтому текст в формат docx трансформировался с ошибками. Например, фраза «объект залога» может превратиться в «обb ект%алога».

Задача: написать функцию, которая определяет есть ли в документе определенная формулировка, с учетом неправильного преобразования текста.

С чего начнём?

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

• сравнение по косинусному сходству;

• сравнение по сходству Левенштейна;

• сравнение по сходству Джаро‑Винклера.

Критерии, по которым предстоит выбрать лучший вариант:

• скорость выполнения (документов довольно много, нужно находить подстроку за разумное время);

• правильность сравнения (нечеткое сравнение на то и нечеткое, потому что требуется некая экспертная оценка того, как отрабатывает критерий сравнения);

• простота реализации.

Кратко о сути метрик

Сходство по Левенштейну

За основу берется расстояние Левенштейна — редакционное расстояние между словами, грубо говоря, сколько нужно сделать изменений символов в одном слове (строке), чтобы получить другое слово (строку). В стандартном варианте три вида изменений символа: вставка; удаление; замена. В библиотеке rapidfuzz используется модифицированная версия этой метрики.

Сходство Джаро-Винклера

За основу берется расстояние Джаро (d), задается коэффициент масштабирования (p), не превышающий 0.25 и считается длина совпадающего префикса (комитет — комок; тут l = 3).

Получается следующая формула:

Расстояние Джаро считается следующим образом:

Где:

• m — сумма точных и неточных совпадений (неточное совпадение — если буквы в словах совпадают, но в разных позициях);

• t — количество неточных совпадений деленное на 2;

• |s₁| и |s₂| — длины первой и второй строки соответственно.

Косинусное сходство

Для вычисления необходимо сначала произвести векторизацию строки, в качестве токена для векторизации могут выступать буквы, слова, предложения. В нашем случае будут использоваться буквы. Пример: два слова baba и abba, в сумме уникальных букв 2, соответственно мы имеем двумерное пространство. Пусть первая ось — это ось буквы a, вторая ось — это ось буквы b. Получаем два вектора baba — [2,2] и abba — [2,2], абсолютно идентичные векторы и косинусное сходство между словами равно 1 (нужно вычислить косинус между векторами). Если строка состоит только из кириллицы, максимальная размерность пространства будет равна 33 по количеству букв в алфавите.

Как будем тестировать?

На помощь нам придут python‑библиотеки rapidfuzz и sklearn.

Со sklearn, я думаю, почти все знакомы, а rapidfuzz — это улучшенная версия thefuzz (fuzzywuzzy) написанная на C++, у которой есть API на многих языках, в том числе python, она априори быстрее чем thefuzz и обладает расширенным функционалом: присутствуют дополнительные метрики, например, сходство Джаро‑Винклера, которое нам ещё пригодится. Теперь перейдем к вопросу тестирования.

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

Правильность: сделаем несколько тестовых кейсов; измерим ключевые метрики, находящиеся в диапазоне от 0 до 1:

• короткие строки, отличающиеся незначительно (орфографически);

• короткие строки, значительно отличающиеся друг от друга (орфографически);

• длинные строки, незначительно отличающиеся друг от друга (орфографически);

• длинные строки, отличающиеся друг от друга значительно (орфографически);

• строки, различающиеся порядком слов;

• строки, различающиеся количеством слов.

Простота реализации: будет сравниваться сложность процесса сравнения. Не буду лукавить, ещё до написания функций я понимал, что реализация сравнения по косинусному расстоянию будет немного сложнее, т.к. метрики Левенштейна и Джаро‑Винклера работают напрямую со строками, а косинусное расстояние с векторами.

Чтение файла docx

Чуть не упустил один важный момент. Искать подстроку нужно в файле docx, соответственно текст из файла нужно как-то извлечь. С этим поможет библиотека python-docx. Перевести содержимое файла docx в строку python, позволит нижеследующий код.

import docx

def get_text(filename: str) -> str:
    """Функция извлекает текст из docx файла по указанному пути"""
    # создаем объект документа
    doc = docx.Document(filename)
    # создаем пустой список куда будут помещаться параграфы
    fulltext = []
    # перебираем все параграфы в документе
    for p in doc.paragraphs:
        # из каждого параграфа берем текст и добавляем его в список
        fulltext.append(p.text)
    # соединяем все тексты параграфов в единую строку
    return '\n'.join(fulltext)

Об алгоритме поиска подстроки

Сначала на словах обсудим алгоритм поиска похожей подстроки:

• Извлекаем текст из файла.

• Используем технику «скользящего окна». «Окно» размером с искомую строку проходит по всему документу и на каждом сдвиге вычисляется метрика (для косинусного сходства на каждом сдвиге нужно ещё делать векторизацию).

• Там, где метрика достигла максимального значения, вероятнее всего, находится наша искомая строка.

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

Код, демонстрирующий реализацию функций для сравнения по скорости, расположен в репозитории на github и под спойлерами.

from sklearn.metrics.pairwise import cosine_similarity
from sklearn.feature_extraction.text import CountVectorizer

def str_to_vecs(text, target):
    """Функция трансформирует заданные строки в вектора"""
    # в качестве токенов для векторизации выступают буквы
    vectorizer = CountVectorizer(analyzer='char')
    vectorizer = vectorizer.fit_transform([text, target])
    text_vec, target_vec = vectorizer.toarray()[0], vectorizer.toarray()[1]
    return text_vec, target_vec

def cos_sim_vecs(vec1, vec2):
    """Функция вычисляет косинусное сходство для двух заданных векторов"""
    vec1 = vec1.reshape(1, -1)
    vec2 = vec2.reshape(1, -1)   
    return cosine_similarity(vec1, vec2)[0][0]

def cos_check(text, target):
    # переменная для отслеживания максимального косинусного сходства
    score = 0
    # переменная для отслеживания положения строки похожей на искомую
    pos = 0
    # убеждаемся что текст больше искомой строки 
    assert len(text) > len(target)
    # "скользящим окном" размером с искомую строку проходим по всему тексту и вычисляем метрику
    for i in range(len(text) - len(target)):
        # векторизируем искомую строку и срез текста
        text_vec, target_vec = str_to_vecs(text[i: i + len(target)], target)
        # вычисляем косинусное сходство на данном срезе
        current_score = cos_sim_vecs(text_vec, target_vec)
        # если текущая метрика больше чем все предыдущие считаем что мы нашли похожую строку
        if current_score > score:
            score = current_score
            pos = i
    return score, text[pos: pos + len(target)]

import rapidfuzz.distance.JaroWinkler as JW

def jw_check(text, target):
    """Функция аналогична косинусному сходству только без векторизации"""
    score = 0
    pos = 0
    assert len(text) > len(target)
    for i in range(len(text) - len(target)):
        current_score = JW.normalized_similarity(text[i: i + len(target)], target)
        if current_score > score:
            score = current_score
            pos = i
    return score, text[pos: pos + len(target)]

from rapidfuzz import fuzz

def lev_check(text, target):
    """Функция фналогична косинусному сходству только без векторизации"""
    score = 0
    pos = 0
    assert len(text) > len(target)
    for i in range(len(text) - len(target)):
        # делим метрику на 100, т.к. данная метрика находится в пределах от 0 до 100
        current_score = fuzz.ratio(text[i: i + len(target)], target)/100
        if current_score > score:
            score = current_score
            pos = i
    return score, text[pos: pos + len(target)]

Ниже представлена таблица сравнения по времени обработки одного документа.

В плане производительности с С++ трудно бороться. Джаро‑Винклер быстрее косинусного сходства в 652 раза, а Левенштейн в 758 раз. Функцию косинусного сходства нужно сильно оптимизировать, если это вообще имеет смысл. Сильно с выводами торопиться не стоит, у косинусного сходства есть еще туз в рукаве, из сути данной метрики я предполагал, что она должна хорошо отработать случаи, где слова поменяны местами.

Что получилось в итоге можно посмотреть в таблицах ниже.

Я сделал следующий промежуточный вывод. Косинусное сходство хорошо определяет похожие строки разной длины, с разным порядком слов и даже с пропущенными словами, но есть один неприятный нюанс: чем длиннее сравниваемые строки — тем больше коэффициент косинусного сходства (даже если строки не похожи). Для конкретно моей задачи это может стать определяющим фактором. К слову, Джаро‑Винклер и Левенштейн отработали случаи с разным порядком и количеством слов вполне достойно.

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

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

Выводы

• Функции, основанные на rapidfuzz работают на порядки быстрее, чем функция, основанная на косинусном сходстве, если необходимо обработать большой пул больших документов, лучше не пользоваться метрикой косинусного сходства.

• Для косинусного сходства сложно эмпирически подобрать порог нахождения подстроки в тексте: особенно если ищем длинную подстроку.

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

• Реализация косинусного сходства немного сложнее из‑за дополнительного этапа векторизации.

В конечном счете выбор сделан в пользу сходства по Левенштейну, с порогом равным 0,7. Библиотека rapidfuzz хорошо показала себя, весь пул входных документов был обработан за 2 — 3 минуты.

Буду рад, если мой пост пригодятся для решения ваших задач!