Техническое. Опечаточное. Пост-окончательное

Замена алгоритма сравнения на оптимизированную (тоже не до упора, но значительно) версию на C скорость перебора увеличилать более чем в 20 раз.

Суммарно, как я сейчас вижу, либо интегрировав оптимизированный алгоритм расчета расстояния Левенштейна в SQL сервер, либо создав свой бинарный индекс для быстрых выборок можно довести исправление до 0,05-0,1 секунды на слово или лучше измерять в потоковых величинах. До 10-20 исправлений опечаток в секунду.

Кстати, набор коротких тестов исправления опечаток в Яндексе показал что проверка по массиву всех слов у них проходит с L=1, а более серьёзные проверки идут по сочетаемости, в случае наличия сочетаемости слов. В случае же 2-х сознательно внесённых опечаток — исправления не происходит.

Может оно и впрямь ненужно учитывать L > 1 и L=1 достаточно с головой. Незнаю, статистики у меня на руках нет.

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

И по прежнему я лично считаю эту задачу очень посредственной по сложности, хотя и полезной по существу.

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

P.S. Кстати, в ru_ir (http://community.livejournal.com/ru_ir/75026.html) itman пишет что хорошие цифры для опечаточного сервиса — 0,02-0,2 секунды. Очень может статься что так и есть. В моих экспериментах основной оверхед создавали именно вспомогательные инструменты — SQL, хранилище словаря, язык разработки которые легко подвергаются дальнейшей оптимизации. Если заменить SQL на свой упрощённый язык, язык на ассемблер и сделать хранилище в своём бинарном формате, то такие цифры легко достижимы. Но, как я и писал раньше, это уже не из серии интересных задач, а рутинных.

About This Author

  • http://elena-kryukova.livejournal.com/ ЕК

    Можно спросить доброго кибер-волшебника, последователя Великих Трурля и Клапауция,
    который знает непонятных слов??? В новой мобели Нокии 5800 есть операционная система Symbian S 60
    — не важно что это, я все равно не пойму.
    А вот хорошо ли оно как явление по мнению столь достопочтенного мэтра?

  • tasman

    А какой использовался словарь? В нём присутствовали словоформы? И если нет, то каким образом решалась проблема сравнения словоформ с базовым словом из словаря?

  • http://ivan.begtin.name ivbeg

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

    Впрочем да, надо конечно на словоформах погонять тексты чтобы в этом окончательно убедиться.

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