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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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