В этом проекте мы напишем простейший поисковый движок. Для этого нужно реализовать:
— Класс SearchEngine для поискового движка.
— Класс данных SearchResult для элемента списка результатов поиска.
— Вспомогательную функцию split_to_words() для разбиения строки на слова.
Класс SearchEngine должен уметь две вещи: индексировать документы и искать по ним. За это отвечают соответственно инициализатор класса и метод search():
— __init__(self: SearchEngine, documents: list[str]) -> None — инициализатор, принимающий список путей к файлам. Выполняет индексирование коллекции текстовых файлов.
— search(self: SearchEngine, query: str) -> list[SearchResult] — метод для поиска документов, соответствующих запросу. В ответ на запрос query он формирует отранжированную по релевантности поисковую выдачу. Она представлена в виде списка объектов SearchResult. Ранжировать (сортировать) выдачу требуется с использованием формулы TF-IDF (об этом чуть ниже).
Для реализации вам пригодятся: классы defaultdict и Counter из модуля collections, функция для расчета логарифма log из модуля math.
Класс данных SearchResult должен содержать два поля:
— name: str — имя документа.
— score: float — релевантность документа относительно запроса.
Для реализации вам пригодится декоратор dataclass из модуля dataclasses.
Вспомогательная функция split_to_words(text: str) -> list[str] пригодится и для индексирования документов, и для поиска. Она приводит строку к нижнему регистру, разбивает ее по пробельным символам и символам пунктуации на отдельные слова.
Символами пунктуации считаем набор: !"#$%&'()*+,-./:;<=>?@[\]^_``{|}~.
Например, строку Search engines. (COMPUTER SCIENCE!) функция разобьет на набор слов search, engines, computer, science.
Для реализации вам пригодятся: константа string.punctuation, статический метод maketrans() и метод класса translate() класса str.
Рассмотрим, как именно требуется реализовать индексирование документов и их ранжирование в поисковой выдаче.
Индексирование — это анализ документов для построения поискового индекса, который используется при поиске.
Инициализатор SearchEngine должен строить обратный индекс (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 (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().