Как увеличить скорость исправления опечаток в 1000 раз? | OTUS
🚀 OTUS Fest 2021
Бесплатная образовательная онлайн-конференция для IT-специалистов.
Подробнее

Курсы

Программирование
Backend-разработчик на PHP
-9%
Алгоритмы и структуры данных
-9%
Team Lead
-6%
Архитектура и шаблоны проектирования Разработчик IoT
-13%
C# Developer. Professional
-9%
HTML/CSS
-11%
C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Java Developer. Basic C++ Developer. Professional Web-разработчик на Python MS SQL Server Developer Android Developer. Basic Разработчик программных роботов (RPA) на базе UiPath и PIX Microservice Architecture Unity Game Developer. Basic Разработчик голосовых ассистентов и чат-ботов React.js Developer Node.js Developer Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes JavaScript Developer. Basic Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Экспресс-курс «IaC Ansible»
-10%
Administrator Linux.Basic
-10%
Мониторинг и логирование: Zabbix, Prometheus, ELK
-10%
Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Administrator Linux. Professional
-6%
Дизайн сетей ЦОД
-13%
NoSQL Основы Windows Server MS SQL Server Developer Инфраструктурная платформа на основе Kubernetes Cloud Solution Architecture Highload Architect Разработчик голосовых ассистентов и чат-ботов VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool"
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Как увеличить скорость исправления опечаток в 1000 раз?

BigData_Deep_19.07_Site.png

Концептуально логика работы спеллчекеров (программ для поиска и исправления ошибок в тексте) такова: слово, содержащее ошибку, нужно заменить на максимально похожее на него слово из числа правильных (в словаре).

Для того, чтобы определить, какие слова «похожи», можно использовать, к примеру, расстояние Дамерау-Левенштейна. Если вкратце, то слово может отличаться от другого одним из четырёх способов: — вставка буквы, — удаление буквы, — замена буквы, — перестановка двух соседних букв.

Каждая такая операция добавляет единицу к расстоянию Дамерау-Левенштейна. Очевидно, что подходящих кандидатов может в итоге оказаться несколько — лучший вариант в этом случае выбирается с помощью модели языка, модели ошибок и так далее. Но основную сложность с вычислительной точки зрения составляет именно генерация и обработка большого числа кандидатов.

Рассмотрим подробнее этот аспект

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

Более рационален подход, сформулированный Питером Норвигом. Его уже можно применять в реальных приложениях. Идея состоит в том, чтобы сгенерировать для каждого слова из текста все возможные редакции с нужным расстоянием (например, два), а потом посмотреть, какие из получившихся редакций есть в словаре. Этот подход намного лучше, однако тоже достаточно затратен, что особенно ярко проявляется при использовании языков с большими алфавитами (так как генерация редакций основана на алфавите).

Альтернативный подход

Предлагаемый Вольфом Гарби (Wolf Garbe) способ основан на использовании симметричных удалений. Симметрия состоит в том, что кандидаты генерируются и на основании терминов словаря, и на основании целевого слова. На предварительном этапе для каждого термина создаются редакции с нужным расстоянием (с помощью только операции удаления символа) и включаются в словарь вместе с исходным термином. Эту операцию можно считать экономной, так как она выполняется только один раз.

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

7+<число букв в алфавите>*(7+1)+(<число букв в алфавите>-1)*7+(7-1)

А при увеличении максимального расстояния до 2, количество кандидатов может достигать десятков тысяч.

Почему это работает?

Для каждой редакции с удалением в словаре сохраняется исходный термин, из которого она была получена. При этом добавление символа в проверяемом слове с точки зрения изменения расстояния эквивалентно удалению символа в словарном слове и наоборот. Например, если в тексте встречается слово «домк» (добавлена буква «к»), одной из редакций с удалением будет правильный вариант «дом», который найдётся в словаре. С другой стороны, если в тексте пропущена буква («дм» вместо «дом»), то слово «дм» найдётся среди редакций с удалениями в словаре и опять же приведёт к слову «дом».

Используя подход Гарби (называнным им SymSpell), можно значительно увеличить скорость работы системы поиска/исправления опечаток, не усложняя её логику.

Есть вопрос? Напишите в комментариях!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться