Запросы с ошибками

[alexanderpanchenko]

Мотивация

Многие запросы пользователей будут содержать ошибки из-за опечаток или из-за того что пользователь не знает как правильно написать (иностранное) слово. Желательно чтобы система могла отвечать и на такие неправильно сформулированные запросы. Для этого следует автоматически исправлять незначительные ошибки и предлагать на выбор наиболее близкие запросы в случае сильных ошибок. Это позволит системе отвечать на значительно большее количество запросов чем количество слов в лексиконе.

Реализация

Реализация простого метода исправления ошибок основана на расстоянии Левенштейна [1] между запросом (ответ на который не найден) и всеми словами в базе. Находяться слова которые имеют расстояние Левенштейна 1, 2 или 3 с запросом. Пользователю предлагается список из 2-5 слов с минимальным расстоянием.

Сложность реализации заключается в быстром вычислении расстояния между произвольной строкой и лексиконом из ~500.000 слов в базе. Я вижу несколько возможных реализаций. Предлагаю обсудить каждый из вариантов:

Вариант 1-- суффиксное дерево

Можно использовать суффиксное дерево как описано здесь http://stevehanov.ca/blog/index.php?id=114 или его улучшенный вариант как описано здесь http://stevehanov.ca/blog/index.php?id=115. Данный метод позволяет достаточно быстро найти слова с расстоянием Левенштейна 1. Ниже -- данные для словаря из 736480 слов (1,2,3,4 -- расстояние):

wordss
1: 0.0441308 s
2: 0.432341 s
3: 1.67618 s
4: 3.8026 s
wordssss
1: 0.0559099 s
2: 0.527886 s
3: 2.05063 s
4: 4.63594 s
vehiclee
1: 0.0500319 s
2: 0.523845 s
3: 2.10965 s
4: 4.70797 s
vehikle
1: 0.046864 s
2: 0.462254 s
3: 1.8697 s
4: 4.26858 s
crums
1: 0.039803 s
2: 0.37783 s
3: 1.48961 s
4: 3.38001 s
stuff
1: 0.0442381 s
2: 0.381701 s
3: 1.45479 s
4: 3.24301 s
romaa
1: 0.045455 s
2: 0.420157 s
3: 1.65054 s
4: 3.65738 s
oma
1: 0.0351961 s
2: 0.301008 s
3: 1.18484 s
4: 2.69824 s
kola
1: 0.0490651 s
2: 0.349479 s
3: 1.39279 s
4: 3.14407 s

Недостаток данного подхода

• долгое время нахождения для расстояний от 2х и более (2 все еще приемлемо)
• большое количество оперативной памяти (1.5-2.5 Гб)
• необходимость в отдельном процессе и в синхронизации
• длительное время загрузки словаря

Вариант 2 -- поиск в монго

Идеальный вариант заключался бы приблизительном поиске напрямую в коллекции words в монго. Попробуй посмотреть можно ли так сделать? Может быть с помощью каких нибудь специальных расширений для fuzzy string matсhing?

Вариант 3 -- поиск в монго перебором

Этот вариант заключается в следующем.

• Для входного запроса генерируется множество строк с заданным расстоянием левенштейна. Например, для строки windowss будут сгенерированы варианты вроде
  • aindowss
  • bindowss
  • windows
  • windowsss
  • ....
• Для операций удаления, вставки и перестановки
• Только для расстояния 1
• Далее мы проверяем содержит ли база каждую из данных строк в базе обычным запросом
• Если совпадение найдено -- возвращаем его пользователю

Посмотри сколько времени занимает в среднем сделать 10, 100, 1000 подобных обращений к коллекции words в монго. Будет ли это время сопоставимо с вариантом 1?

[1] http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0

[PomanoB]

Реализовал вариант №1, но ещё не интегрировал в поиск, пока такие результаты:

init trie: 3714ms

Вверху результаты поиска в массиве, внизу: search слово:маскисмальное_расстояние: время

[ { word: 'torrentrelay', cost: 0 } ] search torrentrelay:1: 14ms

[ { word: 'torrentrelay', cost: 1 } ] search torretrelay:1 (torrentrelay): 8ms

[ { word: 'bradstock', cost: 1 }, { word: 'broadstock', cost: 1 }, { word: 'broodstock', cost: 1 } ] search brodstock:1 (bradstock): 7ms

[ { word: 'policeware', cost: 2 } ] search polcewore:2 (policeware): 80ms

[ { word: 'brickman', cost: 2 }, { word: 'brinkman', cost: 2 }, { word: 'briskman', cost: 2 }, { word: 'brimpton', cost: 2 }, { word: 'rimmon', cost: 2 } ] search brimkmon:2 (brinkman): 67ms

[ { word: 'pretas', cost: 3 }, { word: 'prepas', cost: 3 }, { word: 'preface', cost: 3 }, ...... { word: 'erewash', cost: 3 }, { word: 'efas', cost: 3 }, { word: 'xrefs', cost: 3 }, { word: 'oreas', cost: 3 } ] search wrefasf:3: 278ms

Памяти, правда, отжирает около 460 мб( Но это без оптимизации по второй статье.

[PomanoB]

Сделал второй алгоритм, с поиском повторяющихся цепочек, результаты такие: Первый: 172 мб памяти, 3.5с инициализация Второй: 139 мб памяти, 16с инициализация Не знаю, стоит ли оно того...

[alexanderpanchenko]

Не понял все-таки 490Мб для обычного суффиксного дерева или 172Мб? Для какого количества слов? Проверь на словаре из базы (можно еще посмотреть на 100.000, 500.000, 1.000.000, 3.000.000 слов чтобы увидеть динамику). MA-FSA должен давать преимущества именно на больших лексиконах.

Думаю что стоит сохранить обе реализации. Одну из них установить по умолчанию. Если разница в памяти действительно около 50Мб тогда думаю действительно лучше первый алгоритм оставить.

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

[PomanoB]

450 это была общая память на весь процесс. Скорость одинакова, в пределах погрешности 24.10.2012 15:57 пользователь "Alexander Panchenko" < notifications@github.com> написал:

Не понял все-таки 490Мб для обычного суффиксного дерева или 172Мб? Для какого количества слов? Проверь на словаре 100.000, 500.000 и 1.000.000 слов. MA-FSA должен давать преимущества именно на больших лексиконах.

Думаю что стоит сохранить обе реализации. Одну из них установить по умолчанию. Если разница в памяти действительно около 50Мб тогда думаю действительно лучше первый алгоритм оставить.

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

Reply to this email directly or view it on GitHubhttps://github.com/PomanoB/lsse/issues/10#issuecomment-9736629.

[alexanderpanchenko]

Ну так это для дерева из всех 400.000 слов? Если да и расходуется около 450Мб и старт за 3 секунды думаю что нужно остановиться на этом решении на данный момент.

[PomanoB]

Да, это для всех 630281 слов. Эти 450 мб включают в себя в том числе полный массив данных, который пришёл из монго, а само дерево только 172 мб

[alexanderpanchenko]

Ну нормально. Я насколько понял ты портировал код на питоне приведенный в статье на javascript? Или сделал каки-нибудь изменения?

А что кстати насчет монго (варианты 2 и 3)? Она не умеет строить какие-нибудь умные индексы по текстовому полю (может быть с помощью расширений)...

[PomanoB]

Да, портировал код. Из изменений, надо только перевести его на асинхронный поиск, что бы он не блокировал весь процесс на время поиска...

Монго так не умеет(

[alexanderpanchenko]

Я думаю что следует для ошибок стоимостью 1 выдавать результаты непосредственно на исправленный запрос (тот из них на который больше всего результатов). При этом указывать пользователю что результаты ведуться по исправленному запросу. Для запросов же с ошибками 2 и выше просто предлагать список результатов на выбор (в таком же формате как сейчас выдаются предложения на запросы без резултата).

Что ты думаешь?

[PomanoB]

Согласен.

[PomanoB]

Пока что не сделал автоматическое исправление ошибок стоимости 1, так как:

1. Это сопряжено с некоторыми трудностями.
2. Слова со стоимостью два иногда дают больше результатов

[alexanderpanchenko]

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

[PomanoB]

Ага, именно так

[PomanoB]

Запустил исправление - http://trytoimagine.org:3000/#pyhon

[alexanderpanchenko]

Почему то часто находит не все варианты. Например для запроса uniz должен найтись unix, однако этого не происходит. Другие примеры:

• на gogle нет google
• на auro нет auto
• на sux нет sun
• на eeer нет beer

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

[PomanoB]

Так происходит, потому что берутся только несколько первых результатов, а не все

[PomanoB]

Просто загружать количество результатов для всех вариантов - слишком дорого. Хотя можно их при старте загрузить...

[alexanderpanchenko]

А несколько сейчас это сколько? Около 10? Может хотя бы 20-30 первых брать и потом отображать первые 10 для которых больше всего нашлось результатов? Или будет уже слишком медленно?

Хотя можно их при старте загрузить...

Ты пробовал насколько это будет долго? Много ли нужно будет памяти?

[PomanoB]

Попробую 20-30

Ты пробовал насколько это будет долго? Много ли нужно будет памяти?

Ну тут же ещё и для разных моделей надо...

[PomanoB]

Попробовал разные варианты, оставил 60, время запроса на моём компьютере не превышает 700мс, хотя это тоже много(

[alexanderpanchenko]

Я думаю что нужно наверное сортировать все-таки сначала по рассотянию левенштейна а уже затем по количетву хитов: http://trytoimagine.org:3000/#gogle

Попробовал разные варианты, оставил 60, время запроса на моём компьютере не превышает 700мс, хотя это тоже много

Думаю что оставим пока как есть -- в любом случае пока сервер вообще не загружен. Опять же запросы с ошибками не так уж часты. И если такой запрос происходит то думаю лучше выдать более качественный результат чем менее качественный но более быстро.

Прошу тебя тогда оставить 60 по умолчанию. Тогда я разверну на основном сервере. Дерево строится просто по запуску node app.js или надо как-нибудь его отдельно инициализировать?

[PomanoB]

Сейчас первые 60 отбираются по расстоянию, а из них уже 10 штук по количеству. Ок, исправлю Инициализировать никак не надо

[alexanderpanchenko]

OK

[PomanoB]

Готово

[alexanderpanchenko]

Обновил