Информационный поиск: различия между версиями
M8hew (обсуждение | вклад) Нет описания правки |
M8hew (обсуждение | вклад) Нет описания правки |
||
| Строка 14: | Строка 14: | ||
== Домашние задания == | == Домашние задания == | ||
Домашние задания можно желательно сдавать на C/C++, Python, Go. <br> | |||
Допустимо на Java, C# | |||
'''Задание 1''' | '''Задание 1''' | ||
Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. | Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. | ||
| Строка 32: | Строка 33: | ||
# Реализовать индекс как LSM-подобное дерево | # Реализовать индекс как LSM-подобное дерево | ||
''Deadline: 25 октября'' | |||
'''Задание 3''' | '''Задание 3''' | ||
| Строка 38: | Строка 40: | ||
# Реализовать поиск по префиксу | # Реализовать поиск по префиксу | ||
# Реализовать поиск по wildcard с помощью k-gram | # Реализовать поиск по wildcard с помощью k-gram | ||
''Deadline: 10 ноября'' | |||
'''Задание 4''' | '''Задание 4''' | ||
| Строка 48: | Строка 52: | ||
#* валидных в диапазоне дат | #* валидных в диапазоне дат | ||
#* появившихся в диапазоне дат | #* появившихся в диапазоне дат | ||
''Deadline: 17 ноября'' | |||
'''Задание 5''' | '''Задание 5''' | ||
| Строка 54: | Строка 60: | ||
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам. | Построить позиционный индекс, что позволит выполнять фразовый поиск по документам. | ||
''Deadline: 24 ноября'' | |||
'''Задание 6''' | '''Задание 6''' | ||
| Строка 60: | Строка 68: | ||
Реализуйте FM-index для поиска по подстроке и тесты к нему. | Реализуйте FM-index для поиска по подстроке и тесты к нему. | ||
''Deadline: 1 декабря'' | |||
'''Задание 7''' | '''Задание 7''' | ||
| Строка 69: | Строка 79: | ||
# согласно модели векторного пространства | # согласно модели векторного пространства | ||
# реализовать эффективное Inexact top K ранжирование | # реализовать эффективное Inexact top K ранжирование | ||
''Deadline: 8 декабря'' | |||
'''Задание 8''' | '''Задание 8''' | ||
| Строка 77: | Строка 89: | ||
# используя Faiss для поиска | # используя Faiss для поиска | ||
# понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc) | # понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc) | ||
''Deadline: 15 декабря'' | |||
'''Задание 9''' | '''Задание 9''' | ||
| Строка 83: | Строка 97: | ||
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k. | Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k. | ||
''Deadline: 22 декабря'' | |||
== Литература == | == Литература == | ||
TBD | TBD | ||
Версия от 20:33, 4 ноября 2024
Основы информационного поиска
Осенний курс по выбору для студентов 4 курсов ПМИ ФКН ВШЭ.
Лектор: Алексей Неганов aka @bokareis.
Чат курса TBD
Записи пар TBD
Формула оценки
TBD
Домашние задания
Домашние задания можно желательно сдавать на C/C++, Python, Go.
Допустимо на Java, C#
Задание 1
Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.
Deadline: 18 октября
Задание 2
Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps.
- Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов
- Для слов применить стеммирование / лемматизацию / очистку от стоп-слов
- Реализовать индекс как LSM-подобное дерево
Deadline: 25 октября
Задание 3
Взяв за основу индекс из задания 4:
- Реализовать поиск по префиксу
- Реализовать поиск по wildcard с помощью k-gram
Deadline: 10 ноября
Задание 4
Языки: С, С++, Go, Python
Взяв за основу индекс из задания 4:
- Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
- Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
- валидных в диапазоне дат
- появившихся в диапазоне дат
Deadline: 17 ноября
Задание 5
Языки: С, С++, Go, Python
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
Deadline: 24 ноября
Задание 6
Языки: Go, Python
Реализуйте FM-index для поиска по подстроке и тесты к нему.
Deadline: 1 декабря
Задание 7
Языки: С, С++, Go, Python
Построить индекс, что позволит давать ранжированные результаты
- по TF-IDF
- согласно модели векторного пространства
- реализовать эффективное Inexact top K ранжирование
Deadline: 8 декабря
Задание 8
Языки: С++, Python
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
- используя Faiss для поиска
- понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)
Deadline: 15 декабря
Задание 9
Языки: C, C++, Go
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.
Deadline: 22 декабря
Литература
TBD