Привет, VC!
Меня зовут Никита Экерт и я специалист в области Data Science. Часто в работе мне приходится сталкиваться с задачей text mining, при выполнении которой приходится использовать множество инструментов, в том числе производить поиск ошибок в тексте и их исправление. Ошибки можно разделить на следующие виды (таблица).
Существуют контекстно-независимые и контекстно-зависимые методы обнаружения и исправления ошибок. Я рассмотрю контекстно-независимый способ обнаружения и исправления опечаток и орфографических ошибок. Для выполнения этой задачи мне понадобится алгоритм нечеткого сравнения строк. Существует множество реализаций данных алгоритмов, однако базовый принцип у них похож – данные алгоритмы выявляют разницу между входным словом и словом из словаря и выдают на выходе информацию о том, на сколько они похожи. Так, выполнив проход по словарю, можно получить список слов, наиболее похожих на слово с опечаткой. Далее выбрать то слово, в котором разница будет минимальна и осуществить замену.
Итак, рассмотрю 4 популярных алгоритма нечеткого сравнения строк:
- алгоритм Хэмминга;
- редакционное расстояние Левенштейна;
- редакционное расстояние Дамерау-Левенштейна;
- расстояние Джаро-Винклера.
Алгоритм Хэмминга базируется на простом принципе – подсчет числа позиций, в которых соответствующие символы двух сравниваемых слов отличаются. Отсюда вытекают и минусы подобного решения – возможность сравнивать только слова одинаковой длины. Однако, реализовать его очень просто, можно обойтись без сторонних решений, но есть и библиотеки, упрощающие работу с данным алгоритмом. Устанавливаю библиотеку и использую нужный модуль. Алгоритм выводит значение, равное 1. Это значит, что строки отличаются друг от друга на 1 символ. При сравнении одинаковых строк вывод будет равен 0.
Алгоритм Левенштейна уже посложней, в его основе расчет количества операций, необходимых для преобразования одной строки в другую. Существует 3 таких операции:
- вставка символа (сыто → сытно);
- удаление символа (гидрант → гидрат);
- замена одного символа на другой (усвоить → освоить).
В алгоритме Дамерау-Левенштейна добавляется дополнительная операция транспозиции, позволяющая контролировать замену двух символов местами (прикрепить → рпикрепить). В данной реализации есть как и плюсы, так и минусы. Алгоритм позволяет сравнивать строки различной длины, его реализация все еще не является очень сложной, однако есть недостаток в виде долгого времени выполнения, которое при сравнении слова со словарем существенно усложняет анализ больших текстов. Для реализации в Python можно использовать ту же библиотеку.
Для использования алгоритма Дамерау-Левенштейна можно использовать библиотеку pyxDamerauLevenshtein.
Расстояние Джаро-Винклера основывается на поиске точных и неточных совпадений в анализируемых строках. Под точным совпадением подразумевается совпадение значения и порядкового номера символа, под неточным — совпадение значения и порядкового номера символа ± длина совпадений L. Если обратиться к формулам, то расстояние Джаро-Винклера вычисляется достаточно просто:
Расстояние Джаро (Dj) вычисляется следующим образом:
где me – точное совпадение символов в анализируемых строках
mf – неточное совпадение символов в анализируемых строках.
Зная расстояние Джаро, можно вычислить расстояние Джаро-Виклера (Djw):
где n – длина совпадающего префикса (количество первых совпадающих символов)
p – коэффициент масштабирования (по умолчанию равен 0,1).
Перейдем к преимуществам – это возможность сравнения строк разной длины, высокая скорость работы и выдача нормированного результата по умолчанию. Ниже представлен пример использования данного алгоритма в Python. Здесь результат выводится в другом формате: от 0 до 1, где 1 – это полное совпадение строк.
Расстояние Джаро-Винклера быстрее справляется с задачей, чем расстояние Левенштейна и Дамерау-Левенштейна и является более универсальным решением в сравнении с расстоянием Хэмминга. Это различие видно на приведенном графике, где в сравнении участвовали 3 алгоритма.
Очевидно, что использование алгоритма Джаро-Винклера является оптимальным с точки зрения скорости решением. Однако, бывают ситуации, когда расстояние Левенштейна более предпочтительно из-за выдачи ненормированного результата по умолчанию. В случае с расстоянием Левенштейна могу ввести дополнительные критерии оценивания, например, как это сделано в алгоритме Дамерау-Левенштейна, где введен контроль дополнительной операции транспозиции. Можно также устанавливать свои веса для каждой операции, например присвоить коэффициент отличный от единицы операции замены символов. Тогда и результат, выдаваемый алгоритмом будет отличаться, что может быть полезным при адаптации к конкретной задаче распознавания.
Что дальше? А дальше сравнение строк. Алгоритм прост: беру словарь русского языка, выбираю из анализируемого текста слова с опечатками и/или ошибками и сравниваю со словарем. Обязательно нужно установить пороговое значение, ниже которого слова из словаря не будут включаться в результирующую выборку, я использую от 0.7-0.8 до 1 . Желательно предварительно выполнить предобработку и лемматизацию текста для улучшения качества распознавания. Удачи при распознавании!