Информационный поиск — различия между версиями
Материал из Wiki - Факультет компьютерных наук
M8hew (обсуждение | вклад) (Новая страница: «== Основы информационного поиска == Осенний курс по выбору для студентов 4 курсов ПМИ ФКН…») |
M8hew (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
'''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis]. | '''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis]. | ||
| − | Чат | + | Чат курса TBD |
| + | |||
| + | Записи пар TBD | ||
== Формула оценки == | == Формула оценки == | ||
| Строка 11: | Строка 13: | ||
TBD | TBD | ||
| − | == | + | == Домашние задания == |
| − | + | '''Задание 1''' | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ''Языки: C, C++, Go'' | |
| + | |||
| + | Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. | ||
| + | Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона. | ||
| + | |||
| + | |||
| + | '''Задание 2''' | ||
| + | |||
| + | ''Языки: C, C++, Go'' | ||
| + | |||
| + | Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k. | ||
| + | |||
| + | |||
| + | '''Задание 3''' | ||
| + | |||
| + | ''Языки: Go, Python'' | ||
| + | |||
| + | Реализуйте FM-index для поиска по подстроке и тесты к нему. | ||
| + | |||
| + | |||
| + | '''Задание 4''' | ||
| + | |||
| + | Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps. | ||
| + | # Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов | ||
| + | # Для слов применить стеммирование / лемматизацию / очистку от стоп-слов | ||
| + | # Реализовать индекс как LSM-подобное дерево | ||
| + | |||
| + | |||
| + | '''Задание 5''' | ||
| + | |||
| + | Взяв за основу индекс из задания 4: | ||
| + | # Реализовать поиск по префиксу | ||
| + | # Реализовать поиск по wildcard с помощью k-gram | ||
| + | |||
| + | |||
| + | '''Задание 6''' | ||
| + | |||
| + | ''Языки: С, С++, Go, Python'' | ||
| + | |||
| + | Взяв за основу индекс из задания 4: | ||
| + | # Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат | ||
| + | # Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов, | ||
| + | #* валидных в диапазоне дат | ||
| + | #* появившихся в диапазоне дат | ||
| + | |||
| + | |||
| + | '''Задание 7''' | ||
| + | |||
| + | ''Языки: С, С++, Go, Python'' | ||
| + | |||
| + | Построить позиционный индекс, что позволит выполнять фразовый поиск по документам. | ||
| + | |||
| + | |||
| + | '''Задание 8''' | ||
| + | |||
| + | ''Языки: С, С++, Go, Python'' | ||
| + | |||
| + | Построить индекс, что позволит давать ранжированные результаты | ||
| + | # по TF-IDF | ||
| + | # согласно модели векторного пространства | ||
| + | # реализовать эффективное Inexact top K ранжирование | ||
| + | |||
| + | |||
| + | '''Задание 9''' | ||
| − | + | ''Языки: С++, Python'' | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов | |
| + | # используя Faiss для поиска | ||
| + | # понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc) | ||
== Литература == | == Литература == | ||
TBD | TBD | ||
Версия 11:12, 25 сентября 2024
Основы информационного поиска
Осенний курс по выбору для студентов 4 курсов ПМИ ФКН ВШЭ.
Лектор: Алексей Неганов aka @bokareis.
Чат курса TBD
Записи пар TBD
Формула оценки
TBD
Домашние задания
Задание 1
Языки: C, C++, Go
Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.
Задание 2
Языки: C, C++, Go
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.
Задание 3
Языки: Go, Python
Реализуйте FM-index для поиска по подстроке и тесты к нему.
Задание 4
Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps.
- Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов
- Для слов применить стеммирование / лемматизацию / очистку от стоп-слов
- Реализовать индекс как LSM-подобное дерево
Задание 5
Взяв за основу индекс из задания 4:
- Реализовать поиск по префиксу
- Реализовать поиск по wildcard с помощью k-gram
Задание 6
Языки: С, С++, Go, Python
Взяв за основу индекс из задания 4:
- Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
- Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
- валидных в диапазоне дат
- появившихся в диапазоне дат
Задание 7
Языки: С, С++, Go, Python
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
Задание 8
Языки: С, С++, Go, Python
Построить индекс, что позволит давать ранжированные результаты
- по TF-IDF
- согласно модели векторного пространства
- реализовать эффективное Inexact top K ранжирование
Задание 9
Языки: С++, Python
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
- используя Faiss для поиска
- понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)
Литература
TBD
