Подключаем к сайту орфокорректор. Орфонейрокорректор

Код для исправления ошибок в тексте

Подключаем к сайту орфокорректор. Орфонейрокорректор!

В статье про нейросети мы говорили, что они здорово справляются с машинным переводом и текстами. Настало время попробовать эти технологии на практике — будем подключать модуль орфокоррекции «Яндекс. Спеллер» к веб-странице. В результате введенный на странице текст будет автоматически проверяться орфокорректором.

Основные условия, по которым предоставляется «Спеллер», такие:

Этого вполне хватает для нашего частного проекта. Если вы захотите использовать «Спеллер» в профессиональных целях, почитайте полные условия.

Вот что мы сделаем:

Оформляем страницу

Возьмём наш стандартный шаблон:

Добавим на страницу заголовок, текст и поле ввода:

Вот что у нас получилось. Выглядит неопрятно, давайте добавим стилей.

Пишем скрипт проверки орфографии

Чтобы можно было обращаться к элементу на странице по имени, подключим jQuery. Если вы не знаете, зачем это нужно и как работает, — прочитайте нашу статью.

<script type=»text/javascript» src ></script>

Задача скрипта — ждать нажатия пробела или энтера, после чего отправить текст на проверку и получить назад готовые слова без ошибок. Как только скрипт получает от сервера Яндекса ответ — скрипт меняет текст в окне ввода на правильный.

Код пробела — 32, код энтера — 13. Получается, что нам нужно отслеживать нажатие каждой клавиши и смотреть, что именно нажалось. Если выпали нужные нам коды — запускаем скрипт проверки. Подробнее про отслеживание нажатых клавиш — в статье про редактор с автосохранением.

Сохраняем скрипт отдельным файлом script. js в той же папке, что и страница, и подключаем его в коде страницы:

<script type=»text/javascript»
src=»https://thecode. media/neurocorrector/script. js»></script>

Посмотрите на результат

Можно поиграть с нашей публичной версией на сайте mihailmaximov. ru. Она точно такая же, как мы описали в статье, и проверка идёт по каждому нажатию энтера или пробела. Если не хотите перегружать сервера Яндекса — сделайте проверку по кнопке.

Что дальше

Можно прикрутить этот орфокорректор к нашему текстовому редактору, и тогда вы сразу будете печатать текст почти без ошибок.

Если вы не укладываетесь в лимиты по количеству или объёму проверок, можно убрать автопроверку и добавить кнопку ручной проверки. Или сделать чекбокс, который будет отвечать за автокоррекцию.

А ещё можно добавить счётчик ошибок — он покажет, насколько аккуратно вы набираете текст.

Исправляем опечатки с учётом контекста

Недавно мне понадобилась библиотека для исправления опечаток. Большинство открытых спелл-чекеров (к примеру hunspell) не учитывают контекст, а без него сложно получить хорошую точность. Я взял за основу спеллчекер Питера Норвига, прикрутил к нему языковую модель (на базе N-грамм), ускорил его (используя подход SymSpell), поборол сильное потребление памяти (через bloom filter и perfect hash) а затем оформил всё это в виде библиотеки на C++ со swig биндингами для других языков.

Метрики качества

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

Генератор опечаток на вход принимает слово, на выходе даёт слово с некоторым количеством ошибок. Ошибки бывают следующих типов: замена одной буквы на другую, вставка новой буквы, удаление существующей, а также перестановка двух букв местами. Вероятности каждого из типа ошибок настраиваются отдельно, так же настраивается общая вероятность совершить опечатку (в зависимости от длины слова) и вероятность совершить повторную опечатку.

Пока что все параметры выбраны интуитивно, вероятность ошибки составляет примерно 1 на 10 слов, вероятность самого простого типа ошибки (замена одной буквы на другую) в 7 раз выше чем других типов ошибок.

У данной модели много недостатков — она не основывается на реальной статистике опечаток, не учитывает раскладку клавиатуры а также не склеивает и не разделяет слова. Тем не менее, для начального варианта её хватит. А в следующих версиях библиотеки модель будет улучшена.

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

Спеллчекер Питера Норвига

Питер Норвиг описал простой вариант спеллчекера. Для каждого слова генерируются все возможные варианты изменений (удаления + вставки + замены + перестановки), рекурсивно с глубиной <= 2. Получившиеся слова проверяются на наличие в словаре (хеш-таблица), среди множества подошедших вариантов выбирается тот, который встречается чаще всего. Подробней про этот спеллчекер можно почитать в оригинальной статье.

Основные недостатки данного спеллчекера — долгое время работы (особенно на длинных словах), отсутствие учёта контекста. Начнём с исправления последнего — добавим модель языка и вместо простой частоты встречаемости слов будем использовать оценку, возвращаемую языковой моделью.

Модель языка на основе N-грамм

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

N-граммная модель работает следующим образом. По тексту, используемому для обучения модели проходим окном размером в N слов и подсчитываем количество раз которые встретилось каждое сочетание (n-грамма). При запросе к модели — аналогичным образом проходим окном по предложению и считаем произведение вероятностей всех n-грамм. Вероятность встретить n-грамму оцениваем по количеству таких n-грамм в обучающем тексте.

Вероятность P(w1. wm) встретить предложение (w1. wm) из m слов примерно равна произведению всех n-грамм размера n, из которых состоит это предложение:

Вероятность каждой из n-граммы определяется через количество раз, которое встретилась эта n-грамма по отношению к количеству раз, которое встретилась такая же n-грамма но без последнего слова:

На практике в чистом виде такую модель не используют, так как у неё есть следующая проблема. Если какая-то n-грамма не встречалась в обучающем тексте — всё предложение сразу же получит нулевую вероятность. Для решения этой проблемы используют один из вариантов сглаживания (smoothing). В простом виде это добавление единицы к частоте встречаемости всех n-грамм, в более сложном — использование n-грамм более низкого порядка при отсутствии n-граммы высокого порядка.

Самая популярная техника сглаживания — Kneser–Ney smoothing. Однако она требует для каждой n-граммы хранить дополнительную информацию, а выигрыш по сравнению с более простым сглаживанием получился не сильный (по крайней мере в экспериментах с небольшими моделями, до 50 миллионов n-грамм). Для простоты в качестве сглаживания будем считать вероятность каждой n-граммы как произведение n-грамм всех порядков, например для триграмм:

Теперь, имея модель языка, будем выбирать среди кандидатов на исправление опечаток того, для которого модель языка с учетом контекста будет выдавать наилучшую оценку. Кроме того, добавим к оценке небольшой штраф за изменение исходного слова, чтобы избежать большого числа ложных срабатываний. Изменение данного штрафа позволяет регулировать процент ложных срабатываний: например, в текстовом редакторе можно оставить процент ложных срабатываний выше, а для автоматического исправления текстов — ниже.

SymSpell

Следующая проблема спеллчекера Норвига — низкая скорость работы для случаев, когда кандидатов не нашлось. Так, на слове из 15 букв алгоритм работает около секунды, такой производительности вряд ли хватит для практического использования. Один из вариантов ускорения производительности — алгоритм SymSpell, который, по заверению авторов, работает в миллион раз быстрее. SymSpell работает по следующему принципу: для каждого слова из словаря в отдельный индекс добавляются удаления, а точнее — все слова, получившиеся из исходного путём удаления одной или нескольких букв (обычно 1 и 2), со ссылкой на оригинальное слово. В момент поиска кандидатов для слова делаются аналогичные удаления и проверяется их наличие в индексе. Такой алгоритм корректно обрабатывает все случаи ошибок — замены букв, перестановки, добавления и удаления.

Для примера рассмотрим замену (в примере будем учитывать только расстояние 1). Пусть в оригинальном словаре содержится слово «тест«. А мы набрали слово “темт”. В индексе будут находится все удаления слова “тест”, а именно: ест, тст, тет, тес. Для слова “темт” удаления будут: емт, тмт, тет, емт. Удаление “тет” содержится в индексе, значит слову с опечаткой “темт” соответствует слово “тест”.

Perfect Hash

Следующая проблема — потребление памяти. Модель, обученная на тексте из двух миллионов предложений (миллион из википедии + миллион из новостных текстов) занимала 7 Гб оперативки. Примерно половину этого объёма использовала языковая модель (n-граммы с частотой встречаемости) а другую половину — индекс для SymSpell. С таким потреблением памяти прикладное использование становилось не очень практичным.

Уменьшать размер словаря не хотелось, так как начинало заметно проседать качество. Как оказалось — это не новая проблема. В научных статьях предлагаются разные пути решения проблемы потребления памяти языковой моделью. Один из интересных подходов (описанный в статье Efficient Minimal Perfect Hash Language Models) — использовать perfect hash (а точнее, алгоритм CHD) для хранения информации об n-граммах. Perfect hash — это такой хеш, который не даёт коллизий на фиксированном наборе данных. При отсутствии коллизий пропадает необходимость в хранении ключей, так как нет нужды их сравнивать. В результате, можно держать в памяти массив, равный количеству n-грамм, в котором хранить их частоту встречаемости. Это даёт очень сильную экономию памяти, так как сами n-грамм-ы занимают сильно больше места чем их частоты встречаемости.

Но есть одна проблема. При использовании модели в неё будут приходить n-граммы, которые ни разу не встречались в обучающем тексте. Как следствие, perfect hash будет возвращать хеш какой-то другой, существующей n-граммы. Чтобы решить эту проблему, авторы статьи для каждой n-граммы предлагают дополнительно хранить другой хеш, по которому можно будет сравнить совпадают ли n-граммы или нет. В случае если хеш различается — данной n-граммы не существует и следует считать частоту встречаемости нулевой.

Например, у нас есть три n-граммы: n1, n2, n3, которые встретились 10, 15 и 3 раза, а также n-грамма n4 которая не встречалась в исходном тексте:

Мы завели массив, в котором храним частоты встречаемости, а также дополнительный хеш. Используем значение perfect-hash-а в качестве индекса массива:

Предположим, нам встретилась n-грамма n1. Её perfect-hash равен 1, а second-hash 42. Мы идём в массив по индексу 1, и сверяем хеш который там лежит. Он совпадает, значит частота n-граммы 10. Теперь рассмотрим n-грамму n4. Её perfect-hash также равен 1, но second-hash равен 18. Это отличается от хеша который лежит по индексу 1, значит частота встречаемости 0.

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

Сама частота встречаемости так же была закодирована более компактно, из 32-битных чисел в 16-битные, путём нелинейного квантования. Мелкие числа соответствовали как 1 к 1, более крупные как 1 к 2, 1 к 4, и т. д. На итоговых метриках квантование опять же никак не сказалось.

Скорее всего, можно запаковать и хеш, и частоты встречаемости ещё сильней — но это уже в следующих версиях. В текущем варианте модель ужалась до 260 Мб — более чем в 10 раз, без какой либо просадки качества.

Bloom Filter

Кроме модели языка оставался ещё индекс от алгоритма SymSpell, который также занимал кучу места. Над ним пришлось подумать немного дольше, так как готовых решений под это не существовало. В научных статьях про компактное представление языковой модели часто использовался bloom-фильтр. Казалось, что и в этой задаче он может помочь. Применить bloom-фильтр в лоб не удавалось — для каждого слова из индекса с удалениями нам нужны были ссылки на оригинальное слово, а bloom фильтр не позволяет хранить значения, только проверять факт наличия. С другой стороны — если bloom фильтр скажет что такое удаление есть в индексе — мы можем восстановить для него оригинальное слово выполняя вставки и проверяя их в индексе. Итоговая адаптация алгоритма SymSpell получилась следующей:

Будем хранить все удаления слов из оригинального словаря в bloom-фильтре. При поиске кандидатов будем вначале делать удаления от исходного слова на нужную глубину (аналогично SymSpell). Но, в отличии от SymSpell, следующим шагом для каждого удаления будем делать вставки, и проверять получившееся слово в оригинальном словаре. А индекс с удалениями, хранящийся в bloom-фильтре, будем использовать чтобы пропускать вставки для тех удалений, которые в нём отсутствуют. В этом случае ложные срабатывания нам не страшны — мы просто выполним немного лишней работы.

Производительность получившегося решения практически не замедлилась, а используемая память сократилась очень существенно — до 140 Мб (примерно в 25 раз). В итоге общий размер памяти сократился с 7 Гб до 400 Мб.

Результаты

В таблице ниже приведены результаты для английского текста. Для обучения использовались 300К предложений из википедии и 300К предложений из новостных текстов (тексты взяты здесь). Исходная выборка была разбита на 2 части, 95% использовалось для обучения, 5% для оценки. Результаты:

JamSpell — получившийся в итоге спелл-чекер. Dummy — корректор который ничего не делает, приведён для того чтобы было понятно какой процент ошибок в исходном тексте. Norvig — спелл-чекер Питера Норвига. Hunspell — один из самых популярных open-source спелл-чекеров. Для чистоты эксперимента — так же была проведена проверка на художественном тексте. Метрики по тексту «Приключения Шерлока Холмса»:

JamSpell показал лучшее качество и производительность по сравнению со спеллчекерами Hunspell и Норвига в обоих тестах, как в кейсе с одним кандидатом, так и в кейсе с лучшими 7 кандидатами.

В следующей таблице приведены метрики для разных языков и для обучающей выборки разных размеров:

Итоги

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

Исходники доступны на github, под MIT лицензией. Библиотека написана на C++, биндинги для других языков доступны через swig. Пример использования в python:

Дальнейшие доработки — улучшение качества языковой модели, уменьшение потребления памяти, добавление возможности обрабатывать склеивания и разделения слов, поддержка особенностей разных языков. Если кто-то захочет поучаствовать в улучшении библиотеки — буду рад вашим pull-реквестам.

Исправление орфографии в Python с помощью TextBlob

Первая программа, реализующая проверку орфографии, была написана в 1971 году для DEC PDP-10. Названный SPELL, он был способен выполнять только простые сравнения слов и обнаруживать различия в одной или двух буквах. По мере развития аппаратного и программного обеспечения появляются и средства проверки орфографии. Современные средства проверки правописания способны обрабатывать морфологию и использовать статистику для улучшения предложений.

Python предлагает множество модулей для этих целей, что делает написание простой проверки орфографии легким 20-минутным испытанием.

Одной из этих библиотек является TextBlob, которая используется для обработки естественного языка и предоставляет интуитивно понятный API для работы.

В этой статье мы рассмотрим, как реализовать исправление орфографии в Python с помощью TextBlob.

Установка

Во-первых, нам нужно установить TextBlob, поскольку он не предустановлен. Откройте консоль и установите его с помощью pip:

Это должно установить все, что нам нужно для этого проекта. По окончании установки вывод консоли должен включать что-то вроде:

TextBlob построен на основе NLTK, поэтому он также поставляется с установкой.

Функция correct()

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

Это полный орфографических ошибок текст, почти в каждом слове. Давайте напишем простой скрипт, используя TextBlob, чтобы исправить эти ошибки и распечатать их обратно в консоль:

Затем мы запускаем функцию correct() в этом экземпляре для исправления орфографии.

После запуска приведенного выше сценария вы должны получить примерно такой результат:

Насколько верна коррекция орфографии TextBlob?

Следующий фрагмент кода представляет собой простой сценарий, который проверяет, насколько хорошо TextBlob исправляет ошибки, на основе этого примера:

Теперь, используя эти две функции, давайте проведем быстрый анализ:

Запустив его, вы распечатаете:

Как мы видим, методу correct удалось уменьшить процент орфографических ошибок с 60,6% до 15,9%, что довольно неплохо, однако есть небольшая загвоздка. Он исправил 54,7% слов, так почему все еще остается 15,9% ошибок?

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

Обучающий TextBlob с настраиваемыми наборами данных

Что, если вы хотите проверить орфографию на другом языке, который не поддерживается TextBlob из коробки? Или, может быть, вы хотите быть немного точнее? Что ж, может быть способ добиться этого. Все сводится к тому, как работает проверка орфографии в TextBlob.

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

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

Обратите внимание, что это может быть медленнее, поэтому проверяйте орфографию слово за словом, так как сброс огромных объемов данных может привести к сбою:

И теперь это приведет к:

Это исправляет примерно 2 из 3 слов с ошибками, что довольно хорошо, учитывая запуск без особого контекста.