# Практика. Поисковый движок ## Описание проекта В этом проекте мы напишем простейший поисковый движок. Для этого нужно реализовать: — Класс `SearchEngine` для поискового движка. — Класс данных `SearchResult` для элемента списка результатов поиска. — Вспомогательную функцию `split_to_words()` для разбиения строки на слова. ### Класс SearchEngine Класс `SearchEngine` должен уметь две вещи: индексировать документы и искать по ним. За это отвечают соответственно инициализатор класса и метод `search()`: — `__init__(self: SearchEngine, documents: list[str]) -> None` — инициализатор, принимающий список путей к файлам. Выполняет индексирование коллекции текстовых файлов. — `search(self: SearchEngine, query: str) -> list[SearchResult]` — метод для поиска документов, соответствующих запросу. В ответ на запрос `query` он формирует отранжированную по релевантности поисковую выдачу. Она представлена в виде списка объектов `SearchResult`. Ранжировать (сортировать) выдачу требуется с использованием формулы TF-IDF (об этом чуть ниже). **Для реализации вам пригодятся:** классы [defaultdict](https://docs.python.org/3/library/collections.html#collections.defaultdict) и [Counter](https://docs.python.org/3/library/collections.html#collections.Counter) из модуля `collections`, функция для расчета логарифма [log](https://docs.python.org/3/library/math.html#math.log) из модуля `math`. ### Класс данных SearchResult Класс данных `SearchResult` должен содержать два поля: — `name: str` — имя документа. — `score: float` — релевантность документа относительно запроса. **Для реализации вам пригодится** декоратор [dataclass](https://docs.python.org/3/library/dataclasses.html#dataclasses.dataclass) из модуля `dataclasses`. ### Функция split_to_words() Вспомогательная функция `split_to_words(text: str) -> list[str]` пригодится и для индексирования документов, и для поиска. Она приводит строку к нижнему регистру, разбивает ее по пробельным символам и символам пунктуации на отдельные слова. Символами пунктуации считаем набор: `!"#$%&'()*+,-./:;<=>?@[\]^_``{|}~`. Например, строку `Search engines. (COMPUTER SCIENCE!)` функция разобьет на набор слов `search`, `engines`, `computer`, `science`. **Для реализации вам пригодятся:** константа [string.punctuation,](https://docs.python.org/3/library/string.html#string.punctuation) статический метод [maketrans()](https://docs.python.org/3/library/stdtypes.html#str.maketrans) и метод класса [translate()](https://docs.python.org/3/library/stdtypes.html#str.translate) класса `str`. ## Детали реализации Рассмотрим, как именно требуется реализовать индексирование документов и их ранжирование в поисковой выдаче. ### Индексирование Индексирование — это анализ документов для построения поискового индекса, который используется при поиске. Инициализатор `SearchEngine` должен строить [обратный индекс](https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D0%B2%D0%B5%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81) (inverted index, инвертированный индекс). Обратный индекс — это структура данных, в которой *каждому слову* коллекции документов соотнесены все документы, в которых оно встретилось. Проиллюстрируем это примером: коллекцией из трех документов. Текст документа `1`: ``` Beautiful is better than ugly. ``` Текст документа `2`: ``` Explicit is better than implicit. ``` Текст документа `3`: ``` Simple is better than complex. ``` Обратный индекс для этой коллекции выглядит следующим образом: ``` beautiful -> 1 better -> 1, 2, 3 complex -> 3 explicit -> 2 implicit -> 2 is -> 1, 2, 3 than -> 1, 2, 3 simple -> 3 ugly -> 1 ``` Помимо обратного индекса вам потребуется для каждого документа сохранить количество содержащихся в нем слов. Это поможет на этапе поиска. ### Поиск и ранжирование После того как обратный индекс построен, поиск по документам коллекции можно организовать очень эффективно. При поиске проверяется вхождение слов запроса в обратный индекс. Каждому слову соотносится значение TF-IDF. [TF-IDF](https://ru.wikipedia.org/wiki/TF-IDF) (Term Frequency — Inverse Document Frequency) — классическая и очень простая формула определения релевантности документа поисковому запросу. Она раскладывается на произведение двух значений: `TF * IDF`. **TF** (term frequency, частота слова в документе) — отношение количества вхождений слова к общему числу слов документа: ``` TF = word_frequency_in_doc / doc_wordcount ``` Здесь `word_frequency_in_doc` — количество раз, которое данное слово встретилось в конкретном документе; `doc_wordcount` — количество всех слов документа. **IDF** (inverse document frequency, обратная частота документа) — инверсия частоты, с которой данное слово встречается во всех документах коллекции. Вариация формулы, которую предлагается использовать, выглядит так: ``` IDF = log ((doc_count + 1) / (doc_count_with_word + 1)) ``` Здесь `doc_count` — количество документов в коллекции; `doc_count_with_word` — количество документов, в которых встречается данное слово. Прибавление единицы к числителю и знаменателю дроби нужно, чтобы эффективно обрабатывать случаи, когда слово не обнаружено в коллекции. Произведение значений `TF` и `IDF` означает **релевантность** данного документа данному слову запроса. Большое значение `TF-IDF` имеют слова с высокой частотой в пределах конкретного документа и с низкой частотой вхождения в другие документы. Для вычисления релевантности документа всему запросу целиком просуммируйте значения `TF-IDF` для каждого из слов запроса. Сумма и будет являться значением `score` в элементе поисковой выдачи `SearchResult`. ## Работа над проектом и тестирование Работа над проектом должна вестись в файле `search_engine.py`. Вы можете запускать его и проверять индексацию и поиск в различных файлах из директории `docs`. Для этого есть кнопка «Запустить». Текущая директория при запуске — директория с именем `project`, в которой расположены `search_engine.py` и `docs`. Когда проект будет готов к тестированию, нажимайте на кнопку «Отправить на проверку». По ней запустятся юнит-тесты из файлов `test_*.py`. В файлах с тестами можно посмотреть ожидаемое поведение класса `SearchEngine`, класса данных `SearchResult` и функции `split_to_words()`.