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

Недавно мне понадобилась библиотека для исправления опечаток. Большинство открытых спелл-чекеров (к примеру 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-реквестам.

Пиши неправильно, а потом исправляй: 10 лучших бесплатных онлайн-сервисов для проверки правописания

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

10 лучших бесплатных онлайн-сервисов для проверки правописания

Один из удобных бесплатных сервисов, который есть в онлайн и офлайн версии, – это Орфо. Скачать или воспользоваться онлайн проверкой можно здесь: https://online. orfo. ru/.

Слова, которые написаны с ошибкой, подчеркнуты красным. Как в текстовом редакторе Word, если установлен нужный языковый пакет и включена автоматическая проверка правописания. При нажатии на подчеркнутое слово программа предлагает его исправить:

Орфо-онлайн проверяет не только грамматику, но и пунктуацию. Следит за лексикой и логикой текста. Конечно, программа не совершенна, так как русский язык очень сложен. Она не может заменить квалифицированного редактора, но большинство ошибок, особенно по орфографии, исправит.

В офлайн версии программы Орфо дополнительно есть расстановка переносов в тексте, автокоррекция и вставка буквы «ё», где про нее забыли.

Орфограф

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

В случае с проверкой орфографии на сайте результат похожий – неизвестные словарю слова просто выделены жёлтым.

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

PerevodSpell

На сайте для онлайн-переводов PerevodSpell сервис предоставляет пользователям возможность проверить сначала свой текст на русском языке на ошибки:

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

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

Text. ru

Text. ru более известен в качестве онлайн-сервиса для проверки уникальности текста. Однако после ее запуска обычно одновременно происходит проверка орфографии. Если вам не нужно проверять на уникальность, можно выполнить только проверку орфографии. Дополнительно пользователям может быть интересен словарь синонимов и SEO-анализ текста:

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

Адвего

На бирже контента Адвего есть хорошая бесплатная онлайн-программа проверки текста. Ее большой плюс – мультиязычность. 20 языковых словарей уже присутствуют в программе. Проверка быстрая, есть предложение правильного варианта написания:

Минус Адвего в том, что программа проверяет только правописание. Проверить пунктуацию, семантику, стилистику и типографику здесь нельзя.

Орфограммка

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

Заявлено, что программа помогает проверить орфографию, пунктуацию, типографику, стилистику и семантику. Но на практике иногда случается, что Орфограммка не замечает некоторых ошибок. Это не мешает программе быть одним из лучших инструментов для проверки текстов.

С 2016 года Орфограммка перестала быть полностью бесплатным сервисом. Теперь проверки свыше 500 символов стали платными.

LanguageTool

Онлайн-сервис проверки LanguageTool ищет грамматические, стилистические и пунктуационные ошибки:

Программа предлагает правильные варианты. В ней есть возможность проверить 30 языков.

Большой плюс LanguageTool – есть расширение для самых популярных браузеров, которое позволяет работать без перехода на сайт. После его скачивания и установки достаточно выделить текст и щелкнуть по значку программы:

Спеллер от Яндекса

Яндекс. Спеллер помогает проверить на ошибки сайты или текст на русском, английском и украинском языке:

Интерфейс понятный и удобный. Варианты для исправления есть. Визуально сервис очень похож на проверку орфографии в Word. Если у вас проблемы с пунктуацией, Спеллер не поможет их исправить.

Для проверки веб-документов необходимо будет заняться кодом сайта. Не всем подойдет такой вариант.

5-ege. ru

Сервис 5-ege. ru был создан для подготовки в ЕГЭ, но его вполне можно использовать для любых текстов в режиме онлайн.

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

Резюме

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