Skip to content

Latest commit

 

History

History
84 lines (55 loc) · 5.8 KB

README.md

File metadata and controls

84 lines (55 loc) · 5.8 KB

Лабораторная работа 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