Недавно мне понадобилась библиотека для исправления опечаток.
Большинство открытых программ проверки правописания (например, hunspell) не учитывают контекст, и без него сложно добиться хорошей точности.
За основу я взял программу проверки орфографии Питера Норвига, прикрепил к ней языковую модель (на основе N-грамм), ускорил ее (при помощи подхода SymSpell), поборол большое потребление памяти (с помощью фильтра Блума и идеального хеша) и затем поместил все это в библиотека на C++ с привязками swig для других языков.
Метрики качества
Прежде чем писать саму программу проверки орфографии, необходимо было придумать способ измерения ее качества.Для этих целей Норвиг использовал готовый сборник опечаток, в котором наряду с правильным вариантом указан список слов с ошибками.
Но в нашем случае этот метод не подходит из-за отсутствия в нем контекста.
Вместо этого первым шагом было написать простой генератор опечаток.
Генератор опечаток принимает слово на входе и выдает на выходе слово с определенным количеством ошибок.
Ошибки могут быть следующих типов: замена одной буквы на другую, вставка новой буквы, удаление существующей, а также перестановка двух букв.
Вероятности каждого типа ошибок настраиваются отдельно; Также корректируются общая вероятность сделать опечатку (в зависимости от длины слова) и вероятность сделать повторную опечатку.
Пока все параметры выбраны интуитивно, вероятность ошибки примерно 1 на 10 слов, вероятность ошибки самого простого типа (замена одной буквы на другую) в 7 раз выше, чем других типов ошибок.
У этой модели много недостатков — она не основана на реальной статистике опечаток, не учитывает раскладку клавиатуры, не склеивает и не разделяет слова.
Однако для начальной версии этого достаточно.
И в будущих версиях библиотеки модель будет улучшена.
Теперь, имея генератор опечаток, вы можете пропустить через него любой текст и получить похожий текст с ошибками.
В качестве показателя качества проверки орфографии можно использовать процент ошибок, оставшихся в тексте после его прохождения через эту проверку орфографии.
Помимо этой метрики использовались следующие:
- процент исправленных слов (в отличие от метрики с процентом ошибок – рассчитывается только по словам с ошибками, а не по всему тексту)
- процент битых слов (это когда ошибки в слове не было, но проверка правописания решила, что она есть и исправила ее)
- процент слов, для которых был предложен правильный вариант в списке из N кандидатов (программы проверки орфографии обычно предлагают несколько вариантов исправления)
Проверка орфографии Питера Норвига
Питер Норвиг описал простую версию проверки орфографии.Для каждого слова генерируются все возможные варианты изменений (удаления+вставки+замены+перестановки), рекурсивно с глубиной <= 2. The resulting words are checked for presence in the dictionary (hash table), and the one that occurs most often is selected from among the many suitable options. You can read more about this spell checker in оригинальная статья .
Основными недостатками данной проверки правописания являются долгое время работы (особенно на длинных словах) и отсутствие учета контекста.
Давайте начнем с исправления последнего — мы добавим языковую модель и вместо просто частоты слов будем использовать оценку, возвращаемую языковой моделью.
Языковая модель на основе N-грамм
| N-грамма — это последовательность из n элементов.
Например, последовательность звуков, слогов, слов или букв.
|
Сегодня в основном используются два подхода: Модели на основе N-грамм и на основе нейронных сетей .
Для первой версии библиотеки была выбрана модель N-граммы, поскольку она проще.
Однако в будущем планируется опробовать модель нейронной сети.
Модель N-граммы работает следующим образом.
Мы просматриваем текст, используемый для обучения модели, с окном размером N слов и подсчитываем, сколько раз встречается каждая комбинация (n-грамма).
При запросе модели мы аналогично проходим через окно по предложению и вычисляем произведение вероятностей всех n-грамм.
Вероятность встретить n-грамму мы оцениваем по количеству таких n-грамм в обучающем тексте.
Вероятность P(w 1 ,.
, ш м ) удовлетворить предложение (ш 1 ,.
, ш м ) m слов примерно равно произведению всех n-грамм размера n, составляющих это предложение: 
Вероятность каждой n-граммы определяется количеством раз, когда эта n-грамма встречалась по отношению к количеству раз, когда та же самая n-грамма встречалась, но без последнего слова: 
На практике такая модель в чистом виде не используется, поскольку имеет следующую проблему.
Если какая-то n-грамма не была найдена в обучающем тексте, все предложение сразу получит нулевую вероятность.
Чтобы решить эту проблему, используйте один из вариантов сглаживания.
В простой форме это добавление единицы к частоте появления всех n-грамм; в более сложной форме он использует n-граммы низшего порядка при отсутствии n-граммы более высокого порядка.
Самый популярный метод сглаживания Сглаживание Кнезера – Нея .
Однако для каждого н-грамма требуется хранить дополнительную информацию, а выигрыш по сравнению с более простым сглаживанием оказался невелик (по крайней мере, в экспериментах с небольшими моделями, до 50 миллионов н-граммов).
Для простоты в качестве сглаживания будем считать вероятность каждой н-граммы произведением н-грамм всех порядков, например для триграмм: 
Теперь, имея языковую модель, мы выберем среди кандидатов на исправление опечаток того, для которого языковая модель с учетом контекста даст лучшую оценку.
Кроме того, мы добавим небольшой штраф к оценке за изменение исходного слова, чтобы избежать большого количества ложных срабатываний.
Изменение этого штрафа позволяет регулировать процент ложных срабатываний: например, в текстовом редакторе можно оставить процент ложных срабатываний выше, а для автоматической коррекции текста — ниже.
СимСпелл
Следующая проблема проверки правописания Норвига — низкая скорость работы для случаев, когда кандидаты не найдены.Итак, на слове из 15 букв алгоритм работает около секунды; такой производительности вряд ли будет достаточно для практического использования.
Одним из вариантов повышения производительности является Алгоритм SymSpell , который, по словам авторов, работает в миллион раз быстрее.
SymSpell работает по следующему принципу: для каждого слова из словаря в отдельный индекс добавляются удаления, а точнее все слова, полученные из оригинала путем удаления одной или нескольких букв (обычно 1 и 2), со ссылкой на оригинал.
слово.
При поиске кандидатов на слово производятся подобные удаления и проверяется их наличие в индексе.
Этот алгоритм корректно обрабатывает все случаи ошибок – замены букв, перестановки, добавления и удаления.
Для примера рассмотрим замену (в примере мы будем учитывать только расстояние 1).
Пусть в исходном словаре есть слово « тест «.
И мы набрали слово « соблазнить " Индекс будет содержать все удаления слова " тест ", а именно: принимать пищу , тест , тет , тес .
За слово « соблазнить удаления будут следующими: эмт , ТМТ , тет , эмт .
Удаление » тет ” содержится в индексе, что означает, что в слове есть опечатка “ соблазнить » соответствует слову « тест ”.
Идеальный хеш
Следующая проблема — потребление памяти.Модель, обученная на тексте из двух миллионов предложений (миллион из Википедии + миллион из новостных текстов), занимала 7 ГБ ОЗУ.
Около половины этого объема использовалась моделью языка (n-граммы с частотой встречаемости), а другая половина — индексом для SymSpell. При таком потреблении памяти использование приложений стало не очень практичным.
Уменьшать размер словаря не хотелось, так как качество стало заметно падать.
Как оказалось, это не новая проблема.
В научных статьях предлагаются разные способы решения проблемы потребления памяти языковой моделью.
Один из интересных подходов (описан в статье Эффективные минимальные идеальные модели языка хеширования ) - использовать идеальный хеш (вернее, алгоритм CHD ) для хранения информации о n-граммах.
Идеальный хэш — это хэш, который не вызывает коллизий фиксированного набора данных.
Если коллизий нет, хранить ключи нет необходимости, так как нет необходимости их сравнивать.
В результате вы можете хранить в памяти массив, равный количеству n-грамм, в котором нужно хранить частоту их появления.
Это дает очень сильную экономию памяти, так как сами n-граммы занимают гораздо больше места, чем частота их появления.
Но есть одна проблема.
При использовании модели она получит n-граммы, которые никогда не встречались в обучающем тексте.
Как следствие, идеальный хэш вернет хеш какой-либо другой существующей n-граммы.
Чтобы решить эту проблему, авторы статьи предлагают для каждой н-граммы дополнительно хранить еще один хеш, по которому можно сравнивать, совпадают ли н-граммы или нет. Если хеш другой, такой n-граммы не существует и частоту появления следует считать равной нулю.
Например, у нас есть три н-граммы: n1, n2, n3, которые встречались 10, 15 и 3 раза, а также н-грамма n4, которой не было в исходном тексте:
| n1 | n2 | n3 | n4 | |
| Идеальный хеш | 1 | 0 | 2 | 1 |
| Второй хэш | 42 | 13 | 24 | 18 |
| Частота | 10 | 15 | 3 | 0 |
Мы используем значение Perfect-Hash в качестве индекса массива:
| 15, 13 | 10, 42 | 3, 24 |
Оно совпадает, а это значит, что частота n-граммы равна 10. Теперь рассмотрим n-грамму n4. Его совершенный хэш также равен 1, но его второй хеш равен 18. Это отличается от хеша, который имеет индекс 1, что означает, что частота появления равна 0. На практике в качестве хеша использовался CityHash размером 16 бит. Конечно, хэш не устраняет ложные срабатывания полностью, но снижает их частоту до такого уровня, что на конечные показатели качества это не влияет. Сама частота появления также кодировалась более компактно, от 32-битных чисел до 16-битных, с использованием нелинейного алгоритма.
Маленькие числа соответствовали 1 к 1, большие — 1 к 2, 1 к 4 и т. д. Квантование снова не повлияло на конечные показатели.
Скорее всего, можно еще сильнее упаковать и хэш, и частоту появления — но это произойдет в будущих версиях.
В текущей версии модель уменьшилась до 260 МБ - более чем в 10 раз, без какого-либо падения качества.
Фильтр Блума
Помимо языковой модели там был еще индекс от алгоритма SymSpell, который тоже занимал много места.Пришлось подумать над этим еще немного, так как готовых решений для этого не было.
В научных статьях о компактном представлении языковой модели часто использовалось фильтр Блума .
Казалось, что он мог бы помочь и с этой задачей.
Непосредственно применить фильтр Блума не удалось — для каждого слова из индекса с удалениями нужны были ссылки на исходное слово, а фильтр Блума не позволяет хранить значения, только проверяя факт существования.
С другой стороны, если фильтр Блума скажет, что такое удаление есть в индексе, мы можем восстановить для него исходное слово, выполнив вставки и проверив их в индексе.
Окончательная адаптация алгоритма SymSpell оказалась следующей: Мы будем хранить все удаления слов из исходного словаря в фильтре Блума.
При поиске кандидатов мы сначала сделаем удаления из исходного слова на необходимую глубину (аналогично SymSpell).
Но, в отличие от SymSpell, следующим шагом при каждом удалении является вставка и проверка полученного слова в исходном словаре.
И мы будем использовать индекс с делециями, хранящийся в фильтре Блума, чтобы пропускать вставки для тех делеций, которых в нем нет. В этом случае мы не боимся ложных срабатываний — просто проделаем немного дополнительной работы.
Производительность получившегося решения практически не замедлилась, а используемый объем памяти сократился весьма существенно — до 140 МБ (примерно в 25 раз).
В результате общий размер памяти был уменьшен с 7 ГБ до 400 МБ.
Полученные результаты
В таблице ниже показаны результаты для английского текста.Для обучения использовались 300 тыс.
предложений из Википедии и 300 тыс.
предложений из новостных текстов (тексты взяты Здесь ).
Исходная выборка была разделена на 2 части, 95% использовалось для обучения, 5% — для оценки.
Полученные результаты:
| Ошибки | Топ-7 ошибок | Фиксированная ставка | Топ-7 фиксированных ставок | Сломанный | Скорость (слов в секунду) | |
| JamSpell | 3.25% | 1.27% | 79.53% | 84.10% | 0.64% | 1833 |
| Норвиг | 7.62% | 5.00% | 46.58% | 66.51% | 0.69% | 395 |
| Ханспелл | 13.10% | 10.33% | 47.52% | 68.56% | 7.14% | 163 |
| Дурачок | 13.14% | 13.14% | 0.00% | 0.00% | 0.00% | - |
Манекен — корректор, который ничего не делает; он предоставлен для того, чтобы было понятно, какой процент ошибок содержится в исходном тексте.
Норвиг — проверка орфографии Питера Норвига.
Ханспелл — одна из самых популярных программ проверки орфографии с открытым исходным кодом.
Для чистоты эксперимента также была проведена проверка на художественном тексте.
Метрика к тексту «Приключения Шерлока Холмса»:
| Ошибки | Топ-7 ошибок | Фиксированная ставка | Топ-7 фиксированных ставок | Сломанный | Скорость (слов в секунду) | |
| JamSpell | 3.56% | 1.27% | 72.03% | 79.73% | 0.50% | 1764 |
| Норвиг | 7.60% | 5.30% | 35.43% | 56.06% | 0.45% | 647 |
| Ханспелл | 9.36% | 6.44% | 39.61% | 65.77% | 2.95% | 284 |
| Дурачок | 11.16% | 11.16% | 0.00% | 0.00% | 0.00% | - |
В следующей таблице показаны метрики для разных языков и для разного размера обучающих наборов:
| Ошибки | Топ-7 ошибок | Фиксированная ставка | Топ-7 фиксированных ставок | Сломанный | Скорость | Память | |
| Английский (300 тысяч википедии + 300 тысяч новостей) | 3.25% | 1.27% | 79.53% | 84.10% | 0.64% | 1833 | 86,2 МБ |
| Русский (300 тысяч википедии + 300 тысяч новостей) | 4.69% | 1.57% | 76.77% | 82.13% | 1.07% | 1482 | 138,7 МБ |
| Русский (1 миллион википедии + 1 миллион новостей) | 3.76% | 1.22% | 80.56% | 85.47% | 0.71% | 1375 | 341,4 МБ |
| Немецкий (300 тысяч википедии + 300 тысяч новостей) | 5.50% | 2.02% | 70.76% | 75.33% | 1.08% | 1559 | 189,2 МБ |
| Французский (300 тысяч википедии + 300 тысяч новостей) | 3.32% | 1.26% | 76.56% | 81.25% | 0.76% | 1543 | 83,9 МБ |
Полученные результаты
В результате получается качественная и быстрая проверка орфографии, превосходящая аналогичные открытые решения.Примеры использования — текстовые редакторы, мессенджеры, предварительная обработка грязного текста в задачах машинного обучения и т. д. Источники доступен на github , по лицензии MIT. Библиотека написана на C++, привязки для других языков доступны через swig. Пример использования в Python:
Дальнейшие улучшения включают улучшение качества языковой модели, снижение потребления памяти, добавление возможности обработки слияния и разделения слов, а также поддержку функций разных языков.import jamspell corrector = jamspell.TSpellCorrector() corrector.LoadLangModel('model_en.bin') corrector.FixFragment('I am the begt spell cherken!') # u'I am the best spell checker!' corrector.GetCandidates(['i', 'am', 'the', 'begt', 'spell', 'cherken'], 3) # (u'best', u'beat', u'belt', u'bet', u'bent', .) corrector.GetCandidates(['i', 'am', 'the', 'begt', 'spell', 'cherken'], 5) # (u'checker', u'chicken', u'checked', u'wherein', u'coherent', .
)</td>
Если кто-то захочет поучаствовать в улучшении библиотеки, буду рад вашим пул-реквестам.
Ссылки
- Исходники JamSpell: github.com/bakwc/JamSpell
- Как написать корректор орфографии, Питер Норвиг : norvig.com/spell-correct.html
- Ханспелл: github.com/hunspell/hunspell
- Моделирование языка с помощью N-грамм, Дэниел Джурафски и Джеймс Х.
Мартин
: web.stanford.edu/~jurafsky/slp3/4.pdf - Понимание сетей LSTM Кристофер Ола : colah.github.io/posts/2015-08-Understanding-LSTMs/
- МОДЕЛИРОВАНИЕ ЯЗЫКА N-GRAM С ИСПОЛЬЗОВАНИЕМ РЕКУРЕНТНОЙ ОЦЕНКИ НЕЙРОННОЙ СЕТИ, Технический отчет Google, Чиприан Чельба, Мохаммад Норузи, Сами Бенджио : static.googleusercontent.com/media/research.google.com/ru//pubs/archive/46183.pdf
- Эмпирическое исследование методов сглаживания для языкового моделирования.
Стэнли Ф.
Чен и Джошуа Гудман : u.cs.biu.ac.il/~yogo/courses/mt2013/papers/chen-goodman-99.pdf
- Алгоритм исправления орфографии в 1000 раз быстрее, Вольф Гарбе : blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/
- Эффективные минимальные идеальные модели языка хеширования, Дэвид Гатри, Марк Хеппл, Вэй Лю : www.lrec-conf.org/proceedings/lrec2010/pdf/860_Paper.pdf
- Идеальная хэш-функция Википедия : en.wikipedia.org/wiki/Perfect_hash_function
- Хешировать, перемещать и сжимать.
Джамаль Белаццуги1, Фабиано К.
Ботельо, Мартин Дитцфельбингер : cmph.sourceforge.net/papers/esa09.pdf
- фильтр Блума, хабрахабр : habrahabr.ru/post/112069/
- Коллекция Лейпцигской корпорации: wortschatz.uni-leipzig.de/en/download/
-
В Мошенничество Нельзя Верить
19 Oct, 24 -
Яндекс: Конкурентам – С Новым Годом!
19 Oct, 24
