Информационный поиск — различия между версиями

Версия 23:45, 4 ноября 2024

Основы информационного поиска

Осенний курс по выбору для студентов 4 курсов ПМИ ФКН ВШЭ.

Лектор: Алексей Неганов aka @bokareis.

Чат курса: TBD

Ссылка на подключение к паре: TBD

Записи пар: TBD

Текущая ведомость: TBD

Формула оценки

Оценка за курс состоит из оценки за задачи и зачета.

Чтобы быть допущенным к зачету балл за задачи должен быть минимум 2.0

3.0 за задачи — удовлетворительная отметка(4 балла) автоматом, можете получить "хорошо" на зачёте
5.0 — хорошо (6 баллов) автоматом, можете получить "отлично" (8 баллов)
8.0 — отлично (8 баллов) автоматом, можете получить максимум

Домашние задания

Домашние задания можно желательно сдавать на C/C++, Python, Go
Допустимо на Java, C#

Задание 1

Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.

Deadline: 18 октября

Задание 2

Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps.

1. Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов
2. Для слов применить стеммирование / лемматизацию / очистку от стоп-слов
3. Реализовать индекс как LSM-подобное дерево

Deadline: 25 октября

Задание 3

Взяв за основу индекс из задания 4:

1. Реализовать поиск по префиксу
2. Реализовать поиск по wildcard с помощью k-gram

Deadline: 10 ноября

Задание 4

Взяв за основу индекс из задания 4:

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

Deadline: 17 ноября

Задание 5

Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.

Deadline: 24 ноября

Задание 6

Реализуйте FM-index для поиска по подстроке и тесты к нему.

Deadline: 1 декабря

Задание 7

Построить индекс, что позволит давать ранжированные результаты

1. по TF-IDF
2. согласно модели векторного пространства
3. реализовать эффективное Inexact top K ранжирование

Deadline: 8 декабря

Задание 8

Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов

1. используя Faiss для поиска
2. понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)

Deadline: 15 декабря

Задание 9

Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.

Deadline: 22 декабря

Литература

TBD