Техническое. Опечаточное. Продолжение и окончание

В качестве итогов.

После включения основного фильтра проверка одного слова занимает не больше 1 секунды, из которой 0,3-0,4 — это отработка SQL запроса.

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

Пока же выборка из 100 000 слов сокращается до 100-3500 сравнений. При том что 80% находятся в границах 1000 — 2000 сравнений.

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

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

При переписывании алгоритма расчёта расстояния на C, можно ещё выиграть на процедуре сравнения.

Результаты куда как лучше чем спец. индексы про которые я писал ранее. По меньшей мере на порядок.

Да, в качестве уточнения, измерения производились исходя из не менее двух ошибок в слове, то есть при дистанции левенштейна 2 или менее. Если сократить учёт до 1 ошибки, производительность будет куда выше.

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

P.S. Вопрос, востребован ли веб-сервис исправления опечаток в сети? Например, принимающий слово, или множество слов и возвращающий варианты исправления в формате JSON или XML.

About This Author

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