CS
Задачник Базовый курс EN

Задача

Лучшие абзацы

ранжирование поиск куча поисковики в проде

Сделайте поиск по абзацам — того же устройства, что у поисковых библиотек. Абзацы уже разбиты на слова: строчные латинские буквы, без знаков препинания. Запрос — одно, два или три слова. Каждому абзацу D запрос даёт оценку BM25:

$$\text{score}(D) = \sum_{w} \text{idf}(w) \cdot \frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1 \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)},$$

$$\text{idf}(w) = \ln\left(1 + \frac{N - \text{df} + 0{,}5}{\text{df} + 0{,}5}\right),$$

где сумма — по словам запроса, которые есть в D; tf — сколько раз w встречается в D, |D| — число слов в D, avgdl — среднее число слов в абзаце, N — число абзацев, df — в скольких абзацах есть w; k1 = 1,2, b = 0,75. Для каждого запроса выведите k абзацев с наибольшей оценкой. Абзацы, где нет ни одного слова запроса, в ответ не попадают. Среди тестов — абзацы «Войны и мира» в переводе Луизы и Эйлмера Мод.

Вход

В первой строке — N и k (1 ≤ N ≤ 4·104, 1 ≤ k ≤ 10). Дальше N строк — абзацы: слова через пробел, в каждом хотя бы одно слово, длиной до 20 букв; всего слов во всех абзацах не больше 3·105.

Затем число запросов q (1 ≤ q ≤ 3·104) и q строк: число слов запроса c (1 ≤ c ≤ 3) и сами слова, различные. Если для каждого слова каждого запроса взять, в скольких абзацах оно встречается, сумма этих чисел не больше 2·106.

Выход

Для каждого запроса — строка с номерами абзацев (с единицы) по убыванию оценки, не больше k номеров. В тестах первые k оценок запроса и следующая за ними отличаются друг от друга больше чем на 10−6, поэтому порядок однозначен. Если ни в одном абзаце нет ни одного слова запроса, выведите 0.

Второй пример — шесть коротких абзацев романа подряд.

Примеры

Пример 1

Вход
6 2
natasha went to the ball
the ball was the first ball in her life
pierre did not dance
natasha and pierre talked about the war
the old prince did not go to the ball at all
war and peace
4
2 natasha ball
1 the
2 war pierre
1 hunt
Выход
1 4
2 5
4 6
0

Пример 2

Вход
6 3
i don t understand mamma what is his attitude to pierre asked the son
the will will show that my dear our fate also depends on it
but why do you expect that he will leave us anything
ah my dear he is so rich and we are so poor
well that is hardly a sufficient reason mamma
oh heaven how ill he is exclaimed the mother
3
1 pierre
2 my dear
3 what is it
Выход
1
4 2
1 2 5

Ограничения

Время · Python
6000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

В последнем тесте 40 000 абзацев и 30 000 запросов. Сколько абзацев на самом деле может получить хоть какую-то оценку по запросу из двух редких слов?

2Идея

Оценка складывается только из слов запроса, которые есть в абзаце. Абзац без них получает ноль, и смотреть на него незачем. Значит, нужен инвертированный индекс: для каждого слова — список пар «абзац, сколько раз». Его строят один раз, проходом по всем абзацам, и заодно запоминают длину каждого абзаца. Запрос проходит только списки своих слов и копит оценки в словаре «абзац → сумма» — это порядок «термин за термином». Остаётся выбрать k лучших из тронутых абзацев.

3Разбор

Знаменатель BM25 зависит от абзаца, но не от запроса: k1 · (1 − b + b · |D| / avgdl) удобно посчитать заранее для каждого абзаца. idf считается по длине списка слова — это и есть df. k лучших — heapq.nlargest в Python или сортировка тронутых в Go: тронутых обычно немного. Работа на запрос пропорциональна сумме длин списков его слов. Перебор всех абзацев для каждого запроса даёт тот же ответ, но в последнем тесте это больше миллиарда проверок.

Формула idf в условии — с единицей под логарифмом, как в Lucene. В исходной формуле Робертсона и Спарк Джонс единицы нет, и у слова, которое встречается больше чем в половине абзацев, idf отрицательный: «the» в четвёртом тесте есть в 2046 абзацах из 3000, и абзац с «the» терял бы очки. Это не мелочь: с такой формулой разошлись бы 1072 ответа из 4000 в четвёртом тесте и даже 320 из 20 000 в третьем, где частых слов нет, — там меняются соотношения весов.

3+Решение
4Сложность

Индекс — O(всего слов). Запрос — O(S + T log k), где S — сумма длин списков его слов, T ≤ S — число тронутых абзацев.

5Типичные ошибки
  • Перебор абзацев на каждый запрос. Формула верна, ответ тоже, но работа — O(N) на запрос вместо длины списков.
  • idf без единицы. Частые слова получают отрицательный вес, и порядок меняется.
  • Длина абзаца — число разных слов. |D| — все слова с повторами, как и avgdl.
  • Абзацы с нулевой оценкой. Если подходящих абзацев меньше k, выводится столько, сколько есть, без добивки нулями.

Алгоритмы задачи

SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи
Каталог алгоритмов