Сжатый список вхождений
Поисковый индекс хранит для каждого слова список его вхождений — номера слов текста, где оно стоит. Номера идут по возрастанию, поэтому хранят не их, а промежутки между соседними: первый промежуток — сам первый номер. Каждый промежуток записан кодом Элиаса δ, и коды склеены в одну строку битов без разделителей.
Код δ числа x ≥ 1 строится так. Пусть у x в двоичной записи N цифр. Сначала пишется N кодом Элиаса γ: столько нулей, сколько у N двоичных цифр после первой, затем само N в двоичной записи. Затем — двоичная запись x без первой цифры (она всегда 1). Например, δ(1) = 1, δ(3) = 0101, δ(5) = 01101, δ(21) = 001010101.
Раскодируйте список и ответьте на запросы: сколько вхождений слова среди первых p слов текста. Три теста — настоящие списки вхождений слов «Наташа», «война» и «и» в «Войне и мире».
Вход
В первой строке число вхождений k и число запросов q (1 ≤ k ≤ 2·105, 1 ≤ q ≤ 2·105). Во второй — строка из нулей и единиц: коды k промежутков подряд. Номера вхождений не больше 1012. В третьей — q чисел p (1 ≤ p ≤ 1012).
Выход
q строк: для каждого p — сколько вхождений имеют номер не больше p.
Примеры
Пример 1
4 6 0101101101001010101 1 3 8 9 29 100
0 1 2 3 3 4
Пример 2
1 2 0001010111101000 999 1000
0 1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Разделителей между кодами нет. Как понять, где кончается код одного промежутка? Посмотрите, что стоит в начале каждого кода и сколько оно говорит о его длине.
2Подсказка 2
Начальные нули — это первая фаза экспоненциального поиска: каждый ноль удваивает границу, первая единица её закрывает. Сколько цифр нужно прочитать после этой единицы?
3Идея
Код префиксный: ни одно кодовое слово не начало другого, поэтому строка читается слева направо однозначно. Считаем нули до первой единицы — пусть их z; следующие z + 1 цифр, начиная с этой единицы, — длина промежутка N; следующие N − 1 цифр с приписанной впереди единицей — сам промежуток. Номера вхождений — накопленные суммы промежутков, а ответ на запрос — двоичный поиск в отсортированном списке номеров.
4Разбор
На Python удобно искать первую единицу методом str.index("1", at) — он пробегает нули на C, — а цифры превращать в число через int(…, 2). Каждый бит строки читается один раз. Номера накапливаются в списке по возрастанию, и bisect_right(positions, p) отвечает, сколько их не больше p.
Ради чего такие хлопоты. Список вхождений слова «Наташа» — 827 номеров — в коде δ занимает 9198 битов, около 11 на номер, а 32-битными числами — 26 464. Список слова «и» — 21 079 номеров по 8 битов вместо 32: промежутки у частых слов короткие, и код подстраивается под них сам. В настоящих индексах так же сжимают промежутки — кодами Элиаса, Голомба или байтовыми, — а при поиске разжимают на лету.
4+Решение
5Сложность
O(L + q log k), где L — длина строки битов: раскодировка — один проход, каждый запрос — двоичный поиск.
6Типичные ошибки
- Читать промежутки кодом γ. Код γ — это только первая часть δ, длина промежутка. Если прочитать по нему сам промежуток, строка рассыпается с первого кода. Это
wrong.py. - Забыть первую единицу. Хвост кода δ — цифры промежутка без старшей единицы; её нужно приписать обратно.
- Номер вместо промежутка. Коды хранят разности соседних номеров, первая разность — сам первый номер. Ответ нужен про номера, то есть про накопленные суммы.
- 32-битные числа. Номера доходят до 1012; в Go нужен
int64.
Алгоритмы задачи
2⌊log₂ i⌋ + 1 вопрос до позиции i
1 задача
SYS
Структура данных
Инвертированный индекс и BM25
Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов.
O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m))
2 задачи