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

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
Следующая правка →
Новая страница: «== Основы информационного поиска == Осенний курс по выбору для студентов 4 курсов ПМИ ФКН…»
 
Нет описания правки
Строка 5: Строка 5:
'''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis].
'''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis].


Чат курсы TDB
Чат курса 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 ранжирование


* '''Лекция 1, 2 сен 2024'''. Организация курса; Формальные методы и теория типов; Язык NatBool, его денотационная семантика и здравость системы типов относительно неё. [https://disk.yandex.ru/d/WhHJyFeb9mDdkA/02.09%20%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F.mp4 Запись].
* '''Семинар 1, 2 сен 2024'''. Операционные семантики; Эквивалентности семантик; Preservation и Progress теоремы; Корректность системы типов относительно операционной семантики. [https://disk.yandex.ru/d/WhHJyFeb9mDdkA/02.09%20%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80.mp4 Запись].
* '''Лекция 2, 9 сен 2024'''. Система типов NatBool+Let. Подстановка. Соглашение об именах. Preservation и progress теоремы. [https://disk.yandex.ru/d/WhHJyFeb9mDdkA/09.09%20%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F.mp4 Запись].
* '''Семинар 2, 9 сен 2024'''. Семантика с кучей. Эквивалентность семантик с подстановкой и с кучей. Корректность системы типов NatBool+Let. [https://disk.yandex.ru/d/WhHJyFeb9mDdkA/09.09%20%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80.mp4 Запись].
* '''Лекция 3, 16 сен 2024'''. Нетипизированное лямбда-исчисление. Стратегии редукции. Теорема Чёрча-Россера. [ Запись].
* '''Семинар 3, 16 сен 2024'''. Кодирование Чёрча для типов данных: логические значения, пары, натуральные числа, списки. Комбинатор неподвижной точки. [ Запись].
* '''Лекция 4, 23 сен 2024'''. TBA. [ Запись].
* '''Семинар 4, 23 сен 2024'''. TBA. [ Запись].
* '''Лекция 5, 30 сен 2024'''. TBA. [ Запись].
* '''Семинар 5, 30 сен 2024'''. TBA. [ Запись].
* '''Лекция 6, 7 окт 2024'''. TBA. [ Запись].
* '''Семинар 6, 7 окт 2024'''. TBA. [ Запись].
* '''Лекция 7, 14 окт 2024'''. TBA. [ Запись].
* '''Семинар 7, 14 окт 2024'''. TBA. [ Запись].
* '''Лекция 8, 21 окт 2024'''. TBA. [ Запись].
* '''Семинар 8, 21 окт 2024'''. TBA. [ Запись].


== Домашние задания ==
'''Задание 9'''


* ТДЗ-1 (теоретическое). Система типов IntBool+Let. [https://drive.google.com/file/d/1e5iTyjbkPKIABjm4tQHwdzMoW1OVYoma/view?usp=drive_link Условие]. [https://drive.google.com/file/d/1gkqzoSl_h1E2pDWnNn3kDfkN76AeWf8n/view?usp=drive_link Исходник]. Дедлайн: '''26 сентября 2024 в 23:59'''.
''Языки: С++, Python''
* ТДЗ-2 (теоретическое). Тьюринг-полнота нетипизированного лямбда-исчисления. [https://drive.google.com/file/d/13SsC9fjrJwqGT4d5wqcL7zMdwbbaW43_/view?usp=drive_link Условие]. [https://drive.google.com/file/d/1mlBWX8HIrGEsP40NCK1Q9mbqhw9LvLIr/view?usp=drive_link Исходник]. Дедлайн: '''30 сентября 2024 в 23:59'''.
* ТДЗ-3 (теоретическое). TBA. [ Условие]. [ Исходник]. Дедлайн: '''TBA'''.
* ПДЗ-1 (практическое). TBA. [ Условие]. Дедлайн: '''TBA'''.
* ПДЗ-2 (практическое). TBA. [ Условие]. Дедлайн: '''TBA'''.
* БТДЗ (бонусное теоретическое). TBA. [ Условие]. [ Исходник]. Дедлайн: '''TBA'''.
* ПДЗ-3 (практическое). TBA. [ Условие]. Дедлайн: '''TBA'''.
* ПДЗ-4 (практическое). TBA. [ Условие]. Дедлайн: '''TBA'''.
* БПДЗ (бонусное практическое). TBA. [ Условие]. Дедлайн: '''TBA'''.
* ТДЗ-4 (теоретическое). TBA. [ Условие]. [ Исходник]. Дедлайн: '''TBA'''.


Условие теоретических домашних заданий скомпилировано с помощью pdfLaTeX.
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
# используя Faiss для поиска
# понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)


== Литература ==
== Литература ==


TBD
TBD

Версия от 08: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.

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


Задание 5

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

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


Задание 6

Языки: С, С++, Go, Python

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

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


Задание 7

Языки: С, С++, Go, Python

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


Задание 8

Языки: С, С++, Go, Python

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

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


Задание 9

Языки: С++, Python

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

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

Литература

TBD

Источник — https://wiki.cs.hse.ru/index.php?title=Информационный_поиск&oldid=86720