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

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
C# ASP.NET Core разработчик
-18%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP
-8%
Архитектура и шаблоны проектирования
-12%
Программист С Разработчик на Spring Framework MS SQL Server Developer AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Vue.js разработчик VOIP инженер Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив Azure
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux. Professional
-5%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться