Техническое. Бенчмарки по опечаткам

Наконец-то я прогнал несколько полноценных тестов по оптимизированному алгоритму и словарю в 1 361 764 слов (1.3 миллиона слов) — спасибо Андрею Сатеренко за словари с скрипт по генерации словоформ. Далее результаты бенчмарков и комментарии.

Как работает алгоритм: алгоритм работает по принципу расчёта edit distance (расстояния Левенштейна) с предварительной фильтрацией словаря под слово. Время его работы складывается из времени получения отфильтрованной выборки из БД и время на рассчёт расстояния Левенштейна для каждого из её элементов.

Как проводился бенчмарк.

1. Словарь в 1 361 764 был загружен в БД, данные реорганизованы для оптимальной работы алгоритма, проставлены нужные для его работы индексы.

2. По другому словарю в 100 000 слов, лишь частично пересекающемуся с первым, была создана выборка слов с однократно внесённой опечаткой. Поскольку не все слова есть в обоих словарях, то у части слов в результате не находится слов близких — так и должно быть.

3. Для каждого слова из выборки с опечатками прогонялся алгоритм который замерял время получения выборки из БД и время рассчёта edit distance.

4. В файл результатов вносились: оригинальное слово, слово с опечаткой, длина слова, время на выполнение SQL запроса, время на сравнение, сколько всего слов было получено из БД, сколько слов подошли под заданное edit distance и результаты через запятую.

В файле результатов, а его можно скачать здесь, spellcheck_mssql_11c.xls бенчмарки только для слов  от 11 символов. Для слов меньшего размера результаты лучше, если будет интересно приведу и их тоже.

Комментарии с результатам:

• Результаты даже лучше чем я ожидал, хотя и не без сюрпризов.Изначально тесты я проводил как с MySQL, так и с MSSQL. При этом, оказалось что для MySQL время построения фильтрующей выборки линейно к размеру словаря и, если для словаря в 100 000 слов, время SQL запроса было 0,2 секунды, то для 1 300 000 слов — это 25 секунд, что неприемлимо много. В итоге результаты для MySQL я не привожу — они очень плохи, но для MS SQL 2005 Express Edition результаты оказались ожидаемо быстрыми. Осталось теперь только подобрать кроссплатформенную БД способную решать эту же задачу столько же быстро — PostgreSQL  или Oracle.

• Среднее время работы алгоритма в пределах 0.1-0.3 секунды на слово. Во многих случаях гораздо быстрее и реже чуть медленнее.
• Выборка по нескольким словам (5-6 словам) происходила по 2-3 секунды, но это, похоже, недоработка стенда поскольку последующая их перепроверка показывала средние времена. Для идеального теста, конечно, нужен выделенный сервер занятый решением только этой задачи.
• Плюсом алгоритма оказывается простая маштабируемость как в рамках одного сервера так и горизонтально со многими серверами.
• Минусом алгоритма является зависимость от движка СУБД. Этот минус можно перекрыть реализовав его индексы на C или другом языке с возможностью быстрой работы со структурами данных, но большой вопрос нужно ли это вообще. Другой минус в том что для подготовки алгоритма требуется время на построение индексов.
• Этот алгоритм является заменой полного скана с проверкой всех слов в словаре на расстояние Левенштейна от рассматриваемого. В реальной работе словари могут быть значительно уменьшены, в десятки раз соответственно изменится и скорость поиска.
• Для каждого L и для каждого словаря требуется однократная подготовительная работа и построение специальной схемы адаптированной под выборку. Этот процесс может занимать до нескольких дней, но, единожды его проделав повторять его необходимости нет.

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