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

By On 12.09.2008 · 5 Comments

Вдогонку к предыдущему тексту, исправляю упущение отсутствия цифр.

Так вот задачка с использованием расстояния Левенштейна решается очень быстро фильтрами и созданием специальных индексов объём которых может достигать и превосходить объём выборки слов.

Например мои короткие тесты на базе в 100 000 русских слов из словаря Зализняка и расстояния Левенштейна равное 2 показали что при использовании базовых фильтров — поиск происходит не более 15 секунд, а при использовании специализированных индексов не более 1 секунды.

Всё это без какой-либо технологической оптимизации вроде реализации на C/C++/Asm, оптимизации загрузки в оперативную память, использования графических процессоров, оптимизации SQL выборок (сейчас SQL запросы вообще не используются) и так далее.

Я чувствую зря назвал эту задачу интересной, в отличии от аналогичных сравнений слов с базами регулярных выражений она слишком проста.

Поделиться в соц. сетях

Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники
Нравится
 
If you enjoyed this article, please consider sharing it!
Reddit Facebook Twitter Delicious
  • tasman

    А можно подробней про специальные индексы? Имеется в виду все возможные варианты «ошибочных» слов из базы? Или что-то более хитрое?

    PS Где лучше оставлять комментарии? В этом блоге или жж зеркале?

  • http://ivan.begtin.name ivbeg

    Специальные индексы — это анализ выборки слов в массиве и предварительный расчёт ряда метрик в результате которых значительно конечное число расчетов расстояния Левенштейна значительно снижается.

    Комментарии можно оставлять что тут что там, разьве что в ЖЖ я отвечаю чуть быстрее.

  • mp_1812

    А что использует яндекс, когда предполагает опечатку в моем запросе?
    Потому что и в запросах к Еноту люди часто опечатываться могут, и еще больше опечаток я встречал в текстах, размещаемых заказчиками. Учитывая, что охота идет за 0,001 — - 0,0001 полезных извещений среди кучи мусора, учет возможных опечаток может стать сильным козырем, если этот учет можно применить.

  • http://ivan.begtin.name ivbeg

    2mp_1812: Яндекс использует свои технологии, скорее всего N-Gram’ный метод и базы накопленных пользовательских запросов без опечаток.
    Проблема автоматического и полуавтоматического исправления в том что это «дорого» с точки зрения ресурсов. Насколько я слышал в Яндексе обработкой опечаткой занимается не один сервер и даже если завершить все тесты по описанному мною выше подходу, всё равно потребуется не меньше одного сервера чтобы всё работало с приемлимой скоростью.

  • DmitryS

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

    Удалось добиться быстрой работы — поиск в словаре из 200 тыс. слов идет менее 5 мс.