wordspell

README

wordspell

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

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

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

Мне понравилась идея с использованием bloom-фильтра, изложенная вот здесь (2). Хотя реализовывать весь алгорим, описанный в статье по ссылке (2), на мой взгляд, нет смысла - в статье по ссылке (1) достаточно убедительно показано, что в нашем случае не нужно учитывать контекст.

Вот так в результате возникла идея гибридной реализации - мы берем за основу алгоритм SymSpell, но не храним индекс удалений. Все удаления, построенные по основному индексу, мы храним в bloom-фильтре, и если слово не нашлось в базовом индексе, мы строим по нему набор удалений до глубины в 2 символа, отсекаем все, для чего bloom-фильтр отрицателен (а он не дает ложно-отрицательных результатов), строим наборы вставок по 1-2 символам, и ищем то, что получилось, в базовом индексе. Если получаем несколько результатов, отбираем тот, у которого в индексе выше значение частоты встречаемости.

В результате получился спеллер в сотню раз быстрее hunspell, потребляющий 140-160 мегабайт оперативной памяти, и не создающий утечек - wordspell.

Настройка и применение

Структура настроек выглядит вот так:

type Options struct {
	DataDir string
	Langs   []string
}

При этом поле Langs на данный момент избыточно - там по умолчанию используются два языка - ru и en. Это поле предусмотрено на будущее, на данный момент работа корректора опирается на автоматическое распознавание языка по одному слову. А это распознавание реализовано для трех "языков" - русского, английского и "численного".

Существуют библиотеки, которые довольно достоверно позволяют распознавать больше языков, но здесь они пока не используются.

Так что на данный момент достаточно указать значение DataDir. В этой директории должны присутствовать три файла:

ru.dat
en.dat
bloom.dat

В директории rawdata приведен инструмент для построения этих файлов и описание работы с ним. Там же - текстовые примеры из Leipzig Corpora Collection Они достаточно представительны, чтобы как минимум протестировать этот спеллер. Если точность коррекции с этими файлами достаточна, можно их использовать и на проде.

Подключаем, используем:

package main

import (
	"github.com/cannonflesh/wordspell"
	"github.com/cannonflesh/wordspell/options"
	"github.com/sirupsen/logrus"
)

func main() {
	logger := logrus.NewEntry(logrus.New())
	
	opt := &options.Options{
		DataDir: "<path to data dir>",
	}
	
	spell := wordspell.New(opt, logger)
	
	mistake := "слово-с-опечаткой"
	corrected := spell.Correct(mistake)
	
	logger.Infof("%s -> %s", mistake, corrected)
}

corrected будет равно mistake в трех случаях:

• mistake - корректное число, возможно, дробное, возможно, с запятой в качестве десятичного символа.
• mistake есть в индексе и, следовательно, не требует правки
• wordspell не может найти вариант исправления для mistake - например, потому, что не может определить язык, или в силу бедности индексов. Если язык определить удалось, это значит, что в индексе нет ничего, что может быть получено из mistake добавлением/удалением до двух символов включительно, или заменой любых - максимум двух - символов - на любые другие символы алфавита в любой комбинации.

Русский алфавит включает все буквы плюс дефис, английский - еще плюс backtick и одинарную кавычку.

Как wordspell определяет язык?

• если слово содержит только цифры и (возможно) одну точку или запятую, это число. Спеллер ничего не делает с таким словом - просто возвращает "как есть".
• для русского языка в слове имеют право находиться русские буквы и дефис
• для английского языка - английские буквы, дефис и backtick

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

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

Выбор лучшего исправления

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

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

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

Результаты тестирования

В качестве тестовых данных были использованы 380 000 слов с опечатками, накопленных поисковой системой одного из маркетплейсов. Все эти опечатки были исправлены сначала hunspell, потом - wordspell.

Wordspell оказался в 108 раз быстрее, и ему понадобилось в 25 раз меньше памяти (160 Mb против 4+ Gb). При сравнимом качестве исправлений. Но качество работы wordspell можно улучшить:

• Если построить словарь по актуальному лексикону. Например, если речь идет о системе исправления поисковых запросов на маркетплейсе, можно взять названия товаров и категорий из каталога маркетплейса и умножить частоты на количество покупок товара или в категории.
• Если научить wordspell работать со словами, ошибочно написанными слитно (добавить в индекс пары слов, часто встречающихся вместе, и добавить в алфавит пробел).

Documentation

Index

• type Service
  • func New(opt *options.Options, l *logrus.Entry) *Service
  • func (s *Service) Correct(word string) string

Types

type Service

type Service struct {
	// contains filtered or unexported fields
}

func New

func New(opt *options.Options, l *logrus.Entry) *Service

func (*Service) Correct

func (s *Service) Correct(word string) string