interestIngc/inverted_index

Инвертированный индекс

Идея

https://en.wikipedia.org/wiki/Inverted_index

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

На похожем принципе основаны глоссарии в книгах.

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

Исходные данные

Набор текстовых файлов в кодировке UTF-8. Каждый файл - документ. Словом считается последовательность символов, ограниченная пробельными символами с обеих сторон. Символы, отличные от букв, цифр и пробельных символов, расположенные по краям слова, должны удаляться. Слова в файле нумеруются с нуля и позиция слова - это его номер. Если слово встречается в файле несколько раз, то у него будет несколько позиций в этом файле (нумерация слов не учитывает повторения, т.е. каждое повторное вхождение какого-либо слова нумеруется, как новое слово).

Для упрощения будем считать, что в файлах встречается лишь подмножество UTF-8, совпадающее с 7-битной кодировкой ASCII. Таким образом, для классификации символов можно использовать функции стандартной библиотеки std::isspace, std::ispunct и т.п.

Пример: "A goal of a search engine implementation is to optimize the speed of the query."

A	goal	of	a	search	engine	implementation	is	to	optimize	the	speed	of	the	query
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

"EST assembly was an early strategy, dating from the mid-1990s to the mid-2000s,"

EST	assembly	was	an	early	strategy	dating	from	the	mid-1990s	to	the	mid-2000s
0	1	2	3	4	5	6	7	8	9	10	11	12

Поисковый запрос

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

Если фрагмент поискового запроса или весь запрос заключён в кавычки, то слова в кавычках должны искаться как точная фраза, т.е. встречаться в документе именно в таком порядке, друг за другом и полностью (т.е. фраза в кавычках должна полностью присутствовать в документе).

В запросе символы интерпретируются так же, как и в документе, за исключением прямых кавычек ", которые служат для обозначения "фраз".

Фраза задаёт лишь последовательность слов в представлении документа, как цепочки слов - например, символы пунктуации внутри фразы обрабатываются так же, как и в других случаях.

Пример: Поиск фразы '"early strategy dating"' в документах из предыдущего примера будет давать второй документ.

Постановка задачи

Для простоты будем работать с индексом в памяти, без сохранения на диск.

Вам предлагается реализовать такой интерфейс:

class Searcher
{
public:
    using Filename = std::string; // or std::filesystem::path

    // index modification
    void add_document(const Filename & filename);

    void remove_document(const Filename & filename);

    // queries
    class DocIterator
    {
    public:
        using value_type = const Filename;
        ...
    };

    class BadQuery : public std::exception
    {
        ...
    };

    std::pair<DocIterator, DocIterator> search(const std::string & query);
};

• Допускается для имён файлов вместо std::string использовать std::filesystem::path.

Модификация индекса

Возможны две операции, меняющие индекс:

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

Поиск

• Searcher::search принимает строку поискового запроса, а возвращает пару итераторов, задающих диапазон найденных документов (по их именам). Метод вернёт значение, если запрос был корректен.
• Поисковый запрос должен разбиваться на слова по тем же правилам, что и файл с текстом документа, за исключением обработки кавычек - символ " должен обрабатываться и интерпретироваться, как открывающая или закрывающая кавычка.
• В запросе могут быть ошибки - например, отсутствие слов или непарные кавычки, в этом случае результатом поиска будет выброс исключения BadQuery с сообщением об ошибке, начинающееся с "Search query syntax error:".