2. Парсер текста

Цель

Реализовать парсер, который будет использоваться для нормализации поисковых запросов и содержимого документов. Покрыть тестами.

Инструменты

Для реализации рекомендуется использовать средства стандартной библиотеки C++:

Если вы реализуете алгоритм вручную, то это решение должно быть аргументированно.

При проверке работы учитываются:

  1. Корректность алгоритма и качество тестов.

  2. Идиоматичное использование C++.

  3. Оптимальность (выбор структур данных, отсутствие избыточных аллокаций).

Алгоритм работы парсера

Вход:

  1. Строка для разбора.

  2. Параметры парсера:

    • Множество стоп-слов.

    • Минимальная и максимальная длина n-граммы.

Выход: разобранный запрос, состоящий из списка n-грам и позиций n-gram в тексте. Позиция определяется как индекс токена, не считая индексов стоп-слов.

Примерная последовательность преобразований входной строки:

  1. Удалить знаки пунктуации. Для проверки можно использовать функцию std::ispunct.

  2. Привести символы к нижнему регистру (std::tolower).

  3. Разделить строку на слова по пробельным символам (std::isspace).

  4. Удалить из получившегося списка слов стоп-слова.

  5. Для каждого слова сгенерировать список n-грамм длиной от min_ngram_length до max_ngram_length.

Стоп-слова — это слова, не влияющие на релевантность. Для первой итерации можете воспользоваться этим списком:

a
an
and
are
as
at
be
but
by
for
if
in
into
is
it
no
not
of
on
or
s
such
t
that
the
their
then
there
these
they
this
to
was
will
with

Пример

Вход:

text: "Dr. Jekyll and Mr. Hyde"
stop_words: ["and", "dr", "mr"]
ngram_min_length: 3
ngram_max_length: 6

Выход:

jek 0 jeky 0 jekyl 0 jekyll 0 hyd 1 hyde 1

Конфиг

Система поиска может содержать множество входных параметров. Передавать все через аргументы командной строки может быть слишком накладно, поэтому имеет смысл предусмотреть конфигурационный файл в машиночитаемом формате: xml, json или yaml. Для парсинга конфига вы можете использовать любую стороннюю библиотеку, например:

  1. XML: pugixml

  2. JSON: nlohmann::json, rapidjson

  3. YAML: yaml-cpp

Возможный вариант xml-конфига:

<?xml version="1.0" encoding="utf-8"?>
<fts>
   <parser ngram_min_length="3" ngram_max_length="6">
      <stop_words>
         <word>a</word>
         <word>an</word>
         …
      </stop_words>
   </parser>
</fts>

Путь к конфигурационному файлу удобно передавать через именованный аргумент командной строки, плюс предусмотреть ему значение по умолчанию:

--config <path> (default=config.xml)

Дополнительно

Для разных языков и наборов данных оптимальные параметры парсера могут отличаться. Уже на этом этапе имеет смысл предусмотреть формат конфигурационного файла для всей поисковой системы.