Лабораторная работа 11

Simple Search Engine

Задача

За этот год вы написали большой объем кода. В качестве последней лабораторной работы вам предлагается написать проcтой полнотекстовый поиск над файлами с вашими предыдущими заданиями.

Решение подобных задач предполагает подготовку поискового индекса (набора файлов с различными структурами данных) и поиска по полученным файлам.

В данной работе от вас потребуется реализовать один из самых простых вариантов поискового индекса - инвертировнный индекс.

Задача полнотекстового поиска так же подразумевает решение проблемы ранжирования (упорядочения найденных по запросу документов). От вас требуется реализовать функцию ранжироавние BM25, а в качестве фактора для нее TF-IDF.

Таким образом вам необходимо реализовать два приложения - индексатор (подготовка поискового индекса) и поиск (программу осуществляющуюу не посредственно поиск по построенному индексу)

Требования

Требования к индексирующей программе

• Консольное приложение. Структура аргументов командной строки - детали вашей реализации
• Обходить все файлы по определенной директории рекурсивно
• Осуществлять подготовку инвертированного индекса и сопутствующий файлов (если потребуется)
• Формат индекса - ваша задача. Основное требование, его размер должен быть оптимизирован, в предположение что количество файлов может быть очень большим (например весь GitHub). Таким образом в данной части задания основной вашей задачей будет продумывание структур данных
• Приведение слов к нормальной форме не требуется

Требования к поисковой программе

• Консольное приложение, взаимодействие с пользователем через стандартные потоки ввода и вывода
• Осуществлять поиск по построенному индексу
• Ранжировать найденные документы согласно BM25
• Выдавать в качестве результат список файлов с номерами строк где встречается данное слово
• Поддерживать синтаксис запросов с 'AND' и 'OR'
• Некорректный запрос должен приводить к выводу ошибки
• Поиск регистронезависимый

Синтаксис запросов

Должен поддерживать скобки а также операции AND и OR (регистр имеет значение). Таким образом в качестве запроса выступают логические выражения. Разделитель между словами - пробел(ы)

Следующие запросы считаются корректными

• "for"
• "vector OR list"
• "vector AND list"
• "(for)"
• "(vector OR list)"
• "(vector AND list)"
• "(while OR for) and vector"
• "for AND and"

Некорректными запросами считаются

• "for AND"
• "vector list"
• "for AND OR list"
• "vector Or list"

Тесты

Тесты также являются частью задания, поэтому покрытие будет влиять на максимальный балл.

NB

Это ваша последняя работа в рамках данного курса. В ней разрешается использовать все части стандартной библиотеки, но запрещено использование внешних.

Критерии оценивания - Общая архитектура вашего решения - Корректное использование языка и стандартной библиотеки - Оптимальность работы как индексирующей так и поисковой части - Оптимальной придуманных вам структур и форматов хранения

На Хабре есть статья хорошо описывающая инвертировнный индекс и поиск по нему.

Deadline

1. 15.05.24. 0.8
2. 22.05.24. 0.65
3. 29.05.24. 0.5

Максимальное количество баллов - 15