https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BAИнформационный поиск - История изменений2026-06-06T16:00:44ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://www.wikicshse.ru/index.php?title=%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA&diff=2261&oldid=previmported>M8hew: Migrated current public revision from wiki.cs.hse.ru2024-11-08T20:15:39Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>== Основы информационного поиска ==<br />
<br />
Осенний курс по выбору для студентов 4 курсов ПМИ ФКН ВШЭ.<br />
<br />
Занятия проводятся онлайн по вторникам в 18:10 в [https://us06web.zoom.us/j/9624371278?pwd=WEN6a2hvaU9pR0xpalY2T3JHV0QwUT09 zoom]<br />
<br />
'''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis].<br />
<br />
'''Записи пар''': TBD<br />
<br />
'''Текущая ведомость''': TBD<br />
<br />
== Формула оценки == <br />
<br />
Оценка за курс состоит из оценки за задачи и зачета.<br />
<br />
Чтобы быть допущенным к зачету балл за задачи должен быть минимум 2.0<br />
<br />
3.0 за задачи — удовлетворительная отметка(4 балла) автоматом, можно получить "хорошо" на зачёте <br><br />
5.0 — хорошо (6 баллов) автоматом, можно получить "отлично" (8 баллов) <br><br />
8.0 — отлично (8 баллов) автоматом, можно получить максимум <br><br />
<br />
== Домашние задания ==<br />
<br />
Домашние задания можно желательно сдавать на C/C++, Python, Go <br><br />
Допустимо на Java, C#<br />
<br />
'''Задание 1'''<br />
<br />
Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. <br />
Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.<br />
<br />
''Deadline: 18 октября''<br />
<br />
<br />
'''Задание 2'''<br />
<br />
Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps.<br />
# Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов<br />
# Для слов применить стеммирование / лемматизацию / очистку от стоп-слов<br />
# Реализовать индекс как LSM-подобное дерево<br />
<br />
''Deadline: 25 октября''<br />
<br />
'''Задание 3'''<br />
<br />
Взяв за основу индекс из задания 2:<br />
# Реализовать поиск по префиксу<br />
# Реализовать поиск по wildcard с помощью k-gram<br />
<br />
''Deadline: 10 ноября''<br />
<br />
'''Задание 4'''<br />
<br />
Взяв за основу индекс из задания 2:<br />
# Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат<br />
# Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,<br />
#* валидных в диапазоне дат<br />
#* появившихся в диапазоне дат <br />
<br />
''Deadline: 17 ноября''<br />
<br />
'''Задание 5'''<br />
<br />
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.<br />
<br />
''Deadline: 24 ноября''<br />
<br />
'''Задание 6'''<br />
<br />
Реализуйте FM-index для поиска по подстроке и тесты к нему. <br />
<br />
''Deadline: 1 декабря''<br />
<br />
'''Задание 7'''<br />
<br />
Построить индекс, что позволит давать ранжированные результаты<br />
# по TF-IDF<br />
# согласно модели векторного пространства<br />
# реализовать эффективное Inexact top K ранжирование<br />
<br />
''Deadline: 8 декабря''<br />
<br />
'''Задание 8'''<br />
<br />
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов<br />
# используя Faiss для поиска<br />
# понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)<br />
<br />
''Deadline: 15 декабря''<br />
<br />
'''Задание 9'''<br />
<br />
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.<br />
<br />
''Deadline: 22 декабря''<br />
<br />
== Литература ==<br />
<br />
* Petrov, A. (2019). Database Internals: A deep dive into how distributed data systems work.<br />
* Luo, C., & Carey, M. J. (2020). LSM-based storage techniques: a survey.<br />
* Schütze, H., Manning, C. D., & Raghavan, P. (2008). Introduction to information retrieval.<br />
* Lemire, D., Ssi‐Yan‐Kai, G., & Kaser, O. (2016). Consistently faster and smaller compressed bitmaps with roaring.<br />
* Grabowski, S., Raniszewski, M., & Deorowicz, S. (2017). FM-index for Dummies.<br />
* Navarro, G., & Mäkinen, V. (2007). Compressed full-text indexes.</div>imported>M8hew