спеллчекер что это такое

Спеллчекер что это такое

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

Spell Checker избавит Вас от подобных неудобств! Он тщательно проверит весь вводимый Вами текст и немедленно уведомит об обнаруженных орфографических ошибках. Spell Checker совместим с любым программным обеспечением и настраивается в соответствии с конкретными требованиями пользователя. Подробнее.

Настоятельно рекомендуется для постоянного использования!

Вышел новый Spell Checker Ver. 2.1.0.115

О изменениях:

Вышел новый Spell Checker Ver. 2.1.0.112

О изменениях:

Вышел новый релиз Spell Checker Ver. 2.0.0.103

О изменениях:

Вышел новый релиз Spell Checker Ver. 2.0.0.102

Источник

Делаем спеллчекер на фонетических алгоритмах своими руками

Запустив в продакшене супер-мега-навороченную систему нечёткого поиска с поддержкой морфологии, которая показывала на тестовый кейсах блестящие результаты, разработчик сталкивается с суровой реальностью. Пользователи, избалованные автокоррекцией Яндекса и Гугла, делают ошибки и опечатки. И вместо аккуратной страницы с результатами поиска получают грустный смайлик — машина не поняла запроса.

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

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

Орфографические ошибки и опечатки

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

Откуда берутся орфографические ошибки

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

здесь ни знают албанскава изыка и бискровнае убийства дает действа па ниволи бис пиривода так как албанский изык с руским идет ат ывоннава… пачиму ни смучяйтись помнити шта вот изык албанскай…

…за нажи дируцца врываюца разнимают аркестрам

N.B. Обратите внимание! Особенно сложно распознать короткие слова — количество вариантов начинает расти с большой скоростью. Эта особенность и при машинном спеллчекинге присутствует.

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

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

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

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

Фонетический принцип

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

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

Чем-то напоминает фонетические разборы, которые делают школьники младших классов. Только теперь эта техника находит вполне себе практическое применение.

Собственно идея не новая — похожие алгоритмы, только для английского языка, были предложены ещё в начале XX века и продолжают развиваться и совершенствоваться. См. Soundex, Metaphone.

Детали реализации

С высоты птичьего полёта алгоритм выглядит так:

Правила компиляции фонетической метки

N.B. Здесь и ниже, фонетические метки на любой стадии обработки будут заключаться в угловые скобки. Ошибочное написание слов будет предваряться звёздочкой и выделяться курсивом. Это позволяет снизить негативный эффект, оказываемый работой с ошибочными написаниями слов.

1. Слитно, раздельно, через дефис

Большой класс орфографических ошибок — написание раздельно/слитно/через дефис. Поэтому при компиляции фонетической метки все символы, кроме русских букв, удаляются. Этот пункт применим к словарным записям, представляющих собой устойчивые группы из нескольких слов (потому что; в течение; за границу).

по-разному →
потому что →
в течение →
за границу →

2. Двойные согласные

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

Имеет смысл повторить склеивание на последнем этапе, склеивая не буквы, а звукометки, чтобы учесть ошибки типа:

*иЗСкуЗСтво
француЗСкий (самое популярное неправильное написание *французкий).

3. Мягкий знак, твёрдый знак

Мягкий и твёрдый знаки удаляем из слова. Часто эти буквы либо забывают поставить в нужное место, либо наоборот — ставят куда не следует (*японський).

4. Упрощение групп согласных

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

А также менее продуктивные:
здц → сц: под уздцы
лнц → нц: солнце
ндц → нц: голландцы
нтг → нг: рентген
рдц → рц: сердце
рдч → рч: сердчишко

5. Характерные сочетания букв

Характерные двухбуквенные сочетания со статистически заметными случаями совершения ошибок:
сч, зч, жч, сш, сщ, тч → ш (*сЩастье, *закаЩик, *муЩина, *сумаШедший, *АЩистка)
стг → сг (*бюЗгалтер)
хг → г (*буГалтер, *двуГодичный, *трёГлавый)
тс, дц → ц (*деЦтво, *богаЦтво, *спорЦмен)

6. Гласные буквы

Гласные заменяем по принципу:
a, о, ё → а
ю, у → у
я, ы, и, е, э → и

С буквами Ё и Я существует неоднозначность, к какому их относить классу при компиляции метки.

Фонетически буква Ё может передавать два звука ЙОТ-О. И если посмотреть по статистике пользовательских ошибок, то пара Ё — О является наиболее вероятной. Но на практике, если ваш словарь не ёфицирован или пользователи не используют Ё при вводе, то лучше сводить Ё к И-классу (ы, и, е, э).

Буква Я, по аналогии, может передавать два звука ЙОТ-А. Но по статистике люди чаще, совершая ошибку, пишут Е или И вместо Я (*премая, *кипеток, *выпримлять). Так что отнесение Я к И-классу (ы, и, е, э) однозначно будет более выгодным.

N.B. Если быть совсем въедливым, то после шипящих и Ц более вероятной будет как раз ошибка А — Я. (Наоборот быть не может — в русской орфографии после этого класса согласных Я никогда не пишется.) Можно встроить это правило в алгоритм.

Какие буквы предшествуют обозначенным на тепловой карте парам эталон-ошибка.

7. Оглушение согласных

Согласные оглушаем:
б → п
з → с
д → т
в → ф
г → к

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

8. Шипящие и Ц

Отдельная история с шипящими и Ц, не зря им уделяется так много внимания при изучении правописания:
ш, щ, ч, ж, ц → ш

Применимость и сравнение с другими алгоритмами

Главное преимущество предложенного алгоритма — его можно использовать везде, где есть быстрый поиск по индексу. Т.е. с любой, даже самой древней СУБД. Второе немаловажное преимущество — пишется и внедряется такой алгоритм за пару часов (с запасом).

Его серьёзный недостаток — это неумение работать с опечатками, пропусками и лишними буквами.

N.B. Если сравнивать с распространённым тестом на расстояние Левенштейна, то фонетический алгоритм даёт выигрыш при наличии нескольких орфографических ошибок. В то же время алгоритм Л. позволяет отлавливать опечатки. Комбинируя сильные стороны обоих подходов, можно придти к взвешенному алгоритму Левенштейна.

Пути для улучшения

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

Вторая возможность для улучшения алгоритма — делать дополнительные метки, где один из символов заменяется джокер-символом (например звёздочкой). Это даст возможность работать в том числе с опечатками или специфическими ошибками, но количество меток вырастет на порядок.

Обоснование работы алгоритма

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

Если хотите филигранные правила — смотрите в сторону машинного обучения.

Тепловая карта читается по строкам. Например для буквы а наиболее вероятная ошибка — о. Все остальные ошибки существенно менее вероятны.

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

Оценка результатов

Оценка результатов сильно зависит от того, как мерить.

На тестовом датасете L1.5 (грубо: расстояние Левенштейна в паре слово-ошибка не больше единицы), включающем также опечатки, алгоритм даёт точность в 25%. Но это на словах любой длины. Если взять минимальную длину 5, то точность будет уже 34%. Для семи (средняя длина слова в русском языке) — 41%.

Звёзд с неба не хватает, но для простого алгоритма это более чем достойный результат. Если добавить грубый стемминг с отсечением окончаний, можно вытянуть ещё 2-3%.

На тестовом датасете L1.5+PHON (предыдущий датасет + пары слово-ошибка эквивалентные по фонетической метке), алгоритм даёт прирост точности в целых 5%. С точки зрения статистики подмешивать результат работы алгоритма в тестовый набор — смертный грех, но эта цифра говорит о том, что доля мульти-орф-ошибок, т.е. где пользователь ошибается в нескольких местах одновременно, не такая уж и маленькая. А это — конёк фонетического алгоритма.

Если приведённое качество вас не устроит — придётся вложиться в более умные алгоритмы, но их уже так просто на базе СУБДшных индексов не построить.

Датасет

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

Источник

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

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

Задача исправления опечаток, на первый взгляд, кажется довольно несложной. Но если отталкиваться от разнообразия ошибок, реализация решения может оказаться трудной. В целом, исправление опечаток разделяется на контекстно-независимое и контекстно-зависимое (где учитывается словарное окружение). В первом случае ошибки исправляются для каждого слова в отдельности, во втором – с учетом контекста (например, для фразы «она пошле домой» в контекстно-независимом случае исправление происходит для каждого слова в отдельности, где мы можем получить «она пошел домой», а во втором случае правильное исправление выдаст «она пошла домой»).

В поисковых запросах русскоязычного пользователя можно выделить четыре основные группы ошибок только для контекстно-независимого исправления [1]:
1) ошибки в самих словах (пмрвет → привет), к этой категории относятся всевозможные пропуски, вставки и перестановки букв – 63,7%,
2) слитно-раздельное написание слов – 16,9%,
3) искаженная раскладка (ghbdtn → привет) – 9,7 %,
4) транслитерация (privet → привет) – 1,3%,
5) смешанные ошибки – 8,3%.

Пользователи совершают опечатки приблизительно в 10-15% случаях. При этом 83,6% запросов имеют одну ошибку, 11,7% –две, 4,8% – более трёх. Контекст важен в 26% случаев.

Эта статистика была составлена на основе случайной выборки из дневного лога Яндекса в далеком 2013 году на основе 10000 запросов. В открытом доступе есть гораздо более ранняя презентация от Яндекса за 2008 год, где показано похожее распределение статистики [2]. Отсюда можно сделать вывод, что распределение разновидностей ошибок для поисковых запросов, в среднем, с течением времени не изменяется.

В общем виде механизм исправления опечаток основывается на двух моделях: модель ошибок и языковая модель. Причем для контекстно-независимого исправления используется только модель ошибок, а в контекстно-зависимом – сразу две. В качестве модели ошибок обычно выступает либо редакционное расстояние (расстояние Левенштейна, Дамерау-Левенштейна, также сюда могут добавляться различные весовые коэффициенты, методы на подобие Soundex и т. д. – в таком случае расстояние называется взвешенным), либо модель Бриля-Мура, которая работает на вероятностях переходов одной строки в другую. Бриль и Мур позиционируют свою модель как более совершенную, однако на одном из последних соревнований SpellRuEval подход Дамерау-Левенштейна показал результат лучше [3], несмотря на тот факт, что расстояние Дамерау-Левенштейна (уточнение – невзвешенное) не использует априори информацию об опечаточной статистике. Это наблюдение особо показательно в том случае, если для разных реализаций автокорректоров в библиотеке DeepPavlov использовались одинаковые обучающие тексты.

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

Также контекстно-зависимое исправление для корректировки опечаток в запросах очень требовательно по ресурсам. Например, в одном из выступлений Яндекса список пар для исправления опечаток (биграмм) слов отличался в 10 раз по сравнению с количеством слов (униграмм), что тогда говорить про триграммы? Очевидно, что это существенно зависит от вариативности запросов. Немного странно выглядит, когда автокорректор занимает половину памяти от предлагаемого продукта компании, целевое назначение которого не ориентировано на решение проблемы правописания. Так что вопрос внедрения контекстно-зависимого исправления в поисковых системах программных продуктов может быть весьма спорным.

На первый взгляд, складывается впечатление, что существует много готовых решений под любой язык программирования, которые можно использовать без особого погружения в подробности работы алгоритмов, в том числе – в коммерческих системах. Но на практике продолжается разработка своих решений. Например, сравнительно недавно в Joom было сделано собственное решение по исправлению опечаток с использованием языковых моделей для поисковых запросов [4]. Действительно ли ситуация непроста с доступностью готовых решений? С этой целью был сделан, по возможности, широкий обзор существующих решений. Перед тем как приступить к обзору, определимся с тем, как проверяется качество работы автокорректора.

Проверка качества работы

Вопрос проверки качества работы автокорректора весьма неоднозначен. Один из простых подходов проверки — через точность (Precision) и полноту (Recall). В соответствии со стандартом ISO, точность и полнота дополняются правильностью (на англ. «corectness»).

Полнота (Recall) рассчитывается следующим образом: список из правильных слов подается автокорректору (Total_list_true), и, количество слов, которое автокорректор считает правильными (Spellchecker_true), разделенное на общее количество правильных слов (Total_list_true), будет считаться полнотой.

Для определения точности (Precision) на вход автокорректора подается список из неправильных слов (Total_list_false), и, количество слов, которое автокорректор считает неправильным (Spell_checker_false), разделенное на общее количество неправильных слов (Total_list_false), определяют как точность.

Насколько вообще эти метрики информативны и как могут быть полезны, каждый определяет самостоятельно. Ведь, фактически, суть данной проверки сводится к тому, что проверяется вхождение слова в обучающий словарь. Более наглядной метрикой можно считать correctness, согласно которой автокорректор для каждого слова из тестового множества неправильных слов формирует список кандидатов-замен, на которые можно исправить это неправильное слово (следует иметь в виду, что здесь могут оказаться слова, которые не содержатся в обучающем словаре). Допустим, размер такого списка кандидатов-замен равен 5. Исходя из того, что размер списка равен 5, будет сформировано 6 групп, в одну из которых мы будем помещать наше каждое исходное неправильное слово по следующему принципу: в 1-ую группу — если в списке кандидатов-замен предполагаемое нами правильное слово стоит 1-ым, во 2-ую если стоит 2-ым и т. д., а в последнюю группу — если предполагаемого правильного слова в списке кандидатов-замен не оказалось. Разумеется, чем больше слов попало в 1-ую группу и чем меньше в 6-ую, тем лучше работает автокорректор.

Рассмотренного выше подхода придерживались авторы в статье [5], в которой сравнивались контекстно-независимые автокорректоры с уклоном на стандарт ISO. Там же приведены ссылки на другие способы оценки качества.

С одной стороны, такой подход не базируется на опечаточной статистике, в основу которого может быть положена модель ошибок Бриля-Мура [6], либо модель ошибок взвешенного расстояния Дамерау-Левенштейна.

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

Далее была проведена серия экспериментов для всего списка слов обучающего словаря (слова обучающего словаря исправлялись на неправильные в соответствии с вероятностью возникновения той или иной опечатки). В среднем, автокорректор исправляет слова верно в 75% случаев. Вне всякого сомнения, это количество будет сокращаться при пополнении обучающего словаря близкими по редакционному расстоянию словами, большом многообразии словоформ. Эта проблема может решаться за счет дополнения языковыми моделями, но здесь следует учитывать, что количество требуемых ресурсов ощутимо возрастет.

Готовые решения

Рассмотрение готовых решений проводилось с уклоном на собственное использование, и приоритет отдавался автокорректорам, которые удовлетворяют трем критериям:
1) язык реализации,
2) тип лицензии,
3) обновляемость.

В продуктовой разработке язык Java считается одним из самых популярных, поэтому приоритет при поиске библиотек отдавался ему. Из лицензий актуальны: MIT, Public, Apache, BSD. Обновляемость — не более 2-х лет с последнего обновления. В ходе поиска фиксировалась дополнительная информация, например, о поддерживаемой платформе, требуемые дополнительные программы, особенности применения, возможные затруднения при первом использовании и т. д. Ссылки с основными и полезными ресурсами на источники приведены в конце статьи. В целом, если не ограничиваться вышеупомянутыми критериями, количество существующих решений велико. Давайте кратко рассмотрим основные, а более подробно уделим внимание лишь некоторым.

Исторически одним из самых старых автокорректоров является Ispell (International Spell), написан в 1971 на ассемблере, позднее перенесен на C и в качестве модели ошибок использует редакционное расстояние Дамерау-Левенштейна. Для него даже есть словарь на русском языке. В последующем ему на замену пришли два автокорректора HunSpell (ранее MySpell) и Aspell. Оба реализованы на на C++ и распространяются под GPL лицензиями. На HunSpell также распространяется GPL/MPL и его используют для исправления опечаток в OpenOffice, LibreOffice, Google Chrome и других инструментах.

Для Интернета и браузеров есть целое множество решений на JS (сюда можно отнести: nodehun-sentences, nspell, node-markdown-spellcheck, Proofreader, Spellcheck-API — группа решений, базирующаяся на автокорректоре Hunspell; grunt-spell — под NodeJS; yaspeller-ci — обертка для автокорректора Яндекс.Спеллер, распространяется под MIT; rousseau — Lightweight proofreader in JS — используется для проверки правописания).

Широкой популярностью пользуется автокорректор Питера Норвига, программный код на Python которого находится в публичном доступе в статье «How to Write a Spelling Corrector» [7]. На основе этого простого решения были построены автокорректоры на других языках, например: Norvig-spell-check, scala-norvig-spell-check (на Scala), toy-spelling-corrector — Golang Spellcheck (на GO), pyspellchecker (на Python). Разумеется, здесь никакой речи не идет о языковых моделях и контекстно-зависимом исправлении.

Для текстовых редакторов, в частности для VIM сделаны vim-dialect, vim-ditto — распространяются под публичной лицензией; для Notepad++ разработан DspellCheck на C++, лицензия GPL; для Emacs сделан инструмент автоматического определения языка при печати, называется guess-language, распространяется под публичной лицензией.

Есть отдельные сервисы от поисковых гигантов: Яндекс.Спеллер — от Яндекса, про обертку к нему было сказано выше, google-api-spelling-java (соответственно, от Google).

Бесплатные библиотеки для Java: languagetool (лицензируется под LGPL), интегрируется с библиотекой текстового поиска Lucene и допускает использование языковых моделей, для работы необходима 8 версия Java; Jazzy (аналог Aspell) распространяется под лицензией LGPLv2 и не обновлялась с 2005 года, а в 2013 была перенесена на GitHub. По подобию этого автокорректора сделано отдельное решение [8]; Jortho (Java Orthography) распространяется под GPL и разрешает бесплатное использование исключительно в некоммерческих целях, в коммерческих — за дополнительную плату; Jaspell (лицензируется под BSD и не обновлялся с 2005 года); Open Source Java Suggester — не обновлялся с 2013 года, распространяется SoftCorporation LLC и разрешает коммерческое применение; LuceneSpellChecker — автокорректор библиотеки Lucene, написана на Java и распространяется под лицензией Apache.

На протяжении длительного времени вопросом исправления опечаток занимался Wolf Garbe, им были предложены алгоритмы SymSpell (под MIT лицензией) и LinSpell (под LGPL) с реализациями на C# [9], которые используют расстояние Дамерау-Левенштейна для модели ошибок. Особенность их реализации в том, что на этапе формирования возможных ошибок для входного слова, используются только удаления, вместо всевозможных удалений, вставок, замен и перестановок. По сравнению с реализацией автокорректора Питера Норвига оба алгоритма за счет этого работают быстрее, при этом прирост в скорости существенно увеличивается, если расстояние по Дамерау-Левенштейну становится больше двух. Также за счет того, что используются только удаления, сокращается время формирования словаря. Отличие между двумя алгоритмами в том, что LinSpell более экономичен по памяти и медленнее по скорости поиска, SymSpell — наоборот. В более поздней версии SymSpell исправляет ошибки слитно-раздельного написания. Языковые модели не используются.

К числу наиболее свежих и перспективных для пользования автокорректоров, работающих с языковыми моделями и исправляющих контекстно-зависимые опечатки относятся Яндекс.Спеллер, JamSpell [10], DeepPavlov [11]. Последние 2 распространяются свободно: JamSpell (MIT), DeepPavlov (под Apache).

Яндекс.Спеллер использует алгоритм CatBoost, работает с несколькими языками и исправляет всевозможные разновидности ошибок даже с учетом контекста. Единственное из найденных решение, которое исправляет ошибки неверной раскладки и транслитерацию. Решение обладает универсальностью, что делает его популярным. Его недостатком является то, что это удаленный сервис, а про ограничения и условия пользования можно прочитать здесь [12]. Сервис работает с ограниченным количеством языков, нельзя самостоятельно добавлять слова и управлять процессом исправления. В соответствии с ресурсом [3] по результатам соревнований RuSpellEval этот автокорректор показал самое высокое качество исправлений. JamSpell — самый быстрый из известных автокорректор (C++ реализация), здесь есть готовые биндинги под другие языки. Исправляет ошибки только в самих словах и работает с конкретным языком. Использовать решение на уровне униграмм и биграмм нельзя. Для получения приемлемого качества требуется большой обучающий текст.
Есть неплохие наработки у DeepPavlov, однако интеграция этих решений и последующая поддержка в собственном продукте может вызвать затруднения, т. к. при работе с ними требуется подключение виртуального окружения и использование более ранней версии Python 3.6. DeepPavlov предоставляет на выбор три готовых реализации автокорректоров, в двух из которых применены модели ошибок Бриля-Мура и в двух языковые модели. Исправляет только ошибки орфографии, а вариант с моделью ошибок на основе расстояния Дамерау-Левенштейна может исправлять ошибки слитного написания.

Упомяну ещё про один из современных подходов к исправлению опечаток, который основан на применении векторных представлений слов (Word Embeddings). Достоинством его является то, что на нем можно построить автокорректор для исправления слов с учетом контекста. Более подробно про этот подход можно прочитать здесь [13]. Но чтобы его использовать для исправления опечаток поисковых запросов вам потребуется накопить большой лог запросов. Кроме того, сама модель может оказаться довольно емкой по потребляемой памяти, что отразится на сложности интеграцию в продукт.

Выбор Naumen

Из готовых решений для Java был выбран автокорректор от Lucene (распространяется под лицензией от Apache). Позволяет исправлять опечатки в словах. Процесс обучения быстрый: например, формирование специальной структуры данных словаря – индекса для 3 млн. строк составило 30 секунд на процессоре Intel Core i5-8500 3.00GHz, 32 Gb RAM, Lucene 8.0.0. В более ранних версиях время может быть больше в 2 раза. Размер обучающего словаря – 3 млн. строк (

73 Mb txt-файл), структура индекса

235 Mb. Для модели ошибок можно выбирать расстояние Джаро-Винклера, Левенштейна, Дамерау-Левенштейна, N-Gram, если нужно, то можно добавить свое. При необходимости есть возможность подключения языковой модели [14]. Модели известны с 2001 года, но их сравнение с известными современными решениями в открытом доступе не было обнаружено. Следующим этапом будет проверка их работы.

Полученное решение на основе Lucene исправляет только ошибки в самих словах. К любому подобному решению несложно добавить исправление искаженной раскладки клавиатуры путем соответствующей таблицы перевода, тем самым сократить возможность нерелевантной выдачи до 10% (в соответствии с опечаточной статистикой). Кроме того, несложно добавить раздельное написание слитых 2-х слов и транслитерацию.

В качестве основных недостатков решения можно выделить необходимость знания Java, отсутствие подробных кейсов использования и подробной документации, что отражается на снижении скорости разработки решения для Data-Science специалистов. Кроме того, не исправляются опечатки с расстоянием по Дамерау-Левенштейну более 2-х. Опять же, если отталкиваться от опечаточной статистики, более 2-х ошибок в слове возникает реже, чем в 5% случаев. Обоснована ли необходимость усложнения алгоритма, в частности, увеличение потребляемой памяти? Тут уже зависит от кейса заказчика. Если есть дополнительные ресурсы, то почему бы их не использовать?

Основные ресурсы по доступным автокорректорам:

Источник