Алгоритмы. Другие подходы к опечаткам

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

Под катом ряд сугубо технических соображений.

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

1. Извлечь специализированный признак из слова

2. По признаку получить предрасчитанный кластер слов для проверки по алгоритму Левенштейна —

3. Рассчитать расстояние Левенштейна слова против слов из кластера.

Самое замысловатое во всей этой простой схеме — это подбор признака и для достижения наиболее эффективного распределения его значений в заданной размерности. То есть если, к примеру, у нас 1 000 000 слов и берём признак размерностью в 16 бит (2 байта), то идеальный случай когда каждому его значению соответствует не более 16 слов.

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

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

Конечно, есть и свои существенные недостатки — время подбора признака/признаков. Например, если такой признак как размер слова практически лежит на поверхности и позволяет сократить выборки до 1-40% от отбщего числа слов, но равномерности распределения значений там нет и близко. В то же время есть ряд признаков которыми я не так давно занимался и даже кое-что писал про анализ букв в алфавите и не только, по которым можно достичь распределения в пределах от 1 до 150 при размерности признака в 32 бита, но для 5 000 000 это по предварительным оценкам займёт неделю только на построение индекса на стационарном компьютере — нужен кластер и много времени на расчёты.

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

А вот остальные подходы что удалось почитать с одной стороны интересны с другой стороны удивляют скромностью приводимых в исследованиях словарей.

Например, у Martin Lazarov «Finite-State Methods for Spelling Correction» описывается несколько подходов по построению FSA на по анализу Edit Distance. Я, правда, не понимаю откуда там микросекунды в результатах.

А заодно и Fast approximate search in large dictionaries что куда как более правильный подход в отличии от метода фильтрации по отношению расстояний Левенштейна которые я ранее упоминал в одной из своих записей с рассуждениями о вариантах решения этой задачи.

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

About This Author

Яндекс.Метрика