README.md

Подсказки к запросам

Поиск следующего слова

Сделаем предподсчет: для каждого слова посчитаем номера предложений, в которых это слово встречается(то есть построим обратный индекс)

Сам поиск слова будет построен в 2 этапа:

1. Для начала нам надо выбрать из датасета предложений наиболее релевантные. Получим список индексов предложений rel, которые релевантны к текущему запросу. Для этого возьмем из запроса топ-X слова с максимальным tf-idf(на самом деле поскольку запросы обычно короткие, то нам подойдет и просто idf, но это уже мелочи) и Y последних слов. Так мы получим X + Y слов, которые важны для запроса. Переберем все подмножества этих X + Y слов и пересечем обратные индексы слов из этого подмножества, получив массив индексов предложений, в которых содержится каждое из этих слов. Будем добавлять все элементы этого массива в список rel. Будем так делать пока размер массива rel не превосходит M

2. Переберем все слова из предложений, которые лежат в rel. Для каждого перебираемого слова найдем количество фраз с этим словом и словом из X + Y. Выберем топ-5 слов, у которых это количество максимально

Асимптотика: Пересечение обратных индексов занимает O(n) времени, то есть первая часть занимает O(n * 2 ^ (X + Y)) времени и O(M) памяти. Будем брать небольшие X + Y и должно работать нормально =). Вторая часть будет занимать O(M * s) времени, где s - средняя длина предложения

##Исправление ошибок и дополнение слова

Сначала научимся детектировать опечатки. Добавим все слова в бор. Если в боре нету данного слова или его префикса, то будем считать, что в слове опечатка.

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

Переведем каждое слово из датасета в вектора размера alph_size. Сделать это просто - для каждого слова просто посчитаем количество букв в нем(пример: "abca" - [2, 1, 1]). Переберем все подмножества 2 ^ alph_size и для каждого слова запишем вектор, который получится если оставить только индексы, принадлежащие перебираемому подмножеству(то есть сделаем в некотором смысле обратный индекс).

Поиск 10-50 более-менее релевантных строк будет состоять из нескольких итераций. Заметим, что при опечатке вектор слова меняется в 3-4 позициях максимум. То есть, если выбрать случайное подмножество индексов 2 ^ alph_size, то очень вероятно, что в нем не будет позиции, в котором вектор поменялся. На каждой итерации выберем 2 случайных подмножества и пересечем обратные индексы(заметим, что их размеры также не очень большие). Все слова, принадлежащие к пересечению, добавим к итоговому ответу.

Итак, мы научились находить ~50 слов, из них скорее всего есть то слово, которое имел в виду пользователь. Чтобы найти его, переберем каждое слово и посчитаем расстояние Левенштейна для каждого слова. Однако, поскольку большая часть опечаток происходит как замена на букву, которая находится рядом на клавиатуре, то целесообразно считать штраф при замене символа как кратчайшее расстояние между клавишами.

Хорошо, слово научились исправлять, научимся его дополнять. Для этого в датасете будем хранить не только слово, но и все его префиксы. Тогда, если мы хотим заменить опечатку на префикс какого-то слова, то будем просто предлагать это слово, а не его префикс.