Алгоритмы. Опечаточное — интересны ли результаты?

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

В итоге среднее время проверки одного слова по словарю из 108 070 слов занимает от 0.02 до 0.3 секунды для MySQL и от 0.01 до 1.8 секунды для MSSQL на рядовом компьютере 2GHz Athlon TL-60 Mobile.

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

Кстати, оказалось что MSSQL в среднем в 2-3 раза производительнее причём похоже исключительно благодаря индексам. Времени сейчас не так уж много чтобы проверять с остальными СУБД, но думаю что и там результаты будут не хуже. Конечно, всё можно оптимизировать ещё где-то на 50% если заменить СУБД на загрузку словаря в память, построение дерева, оптимизация на C и т.д. и т.п., но это уже не так интересно и в готовые системы где SQL активно используется так просто не вставишь.

Да, конечно, производительность алгоритма — это куда лучше чем O(mn). Фактически он состоит из двух частей — фильтра и сравнивателя. Фильтр отсеивает все варианты сравнение с которыми точно превышает L1, а сравниватель уже проверяет полученную выборку со словом по алгоритму Левенштейна. Сейчас фильтр, в среднем, возвращает от 1 до 200 результатов в выборке и даже если словарь увеличить в разы, то сильно на производительности это не скажется поскольку доля времени на сравнение данных в выборке несопоставимо со временем фильтрации, в свою очередь этими временами можно управлять упрощая фильтр и уменьшая время сравнения. Плюс ещё масса оптимизационных трюков как общетехнических, которые в обыденных задачах просто ни к чему — ибо они полезны уже только при соответствующих нагрузках, так и алгоритмических поскольку ряд шагов алгоритма можно существенно упростить.

Поскольку результаты оказались хоть и не идеальными, но лучше чем хотелось — исходный код, увы, показать не могу, а вот если кому-либо интересны детали бенчмарков отметьтесь — перешлю по email.

Если кто-нибудь также может подсказать где можно взять словарь из хотя бы 5-10 миллионов слов — буду благодарен. Делать словарь самому никакого азарта нет.

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

About This Author

  • http://saterenko.ru Andrey

    Демон на C даст гораздо большую производительность чем база данных, тут и говорить нечего.

    По словарям, я изпользую aspell-овский словарь, там чуть больше 100К основ слов которые дают где-то 1.3М словоформ. Если надо, могу дать скрипт на php, который на основе словарей aspell гененирует все словоформы…

  • http://ivan.begtin.name ivbeg

    2Andrey
    Скрипт бы весьма пригодился, а что он использует — mystem, aspell или что-то своё?

  • http://saterenko.ru Andrey

    Скрипт использует aspell преобразованный в utf8. Вот тут выложил архив http://saterenko.ru/files/dictionary.zip

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

    Плюс там словари aspell преобразованные в utf8.

  • http://ivan.begtin.name ivbeg

    Спасибо, очень помогло.

  • http://saterenko.ru Andrey

    your welcome 😉

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