Введение
Вы помните слово из заметки, но забыли её каталог. Полезный поиск должен находить все подходящие заметки, различать одинаковые имена файлов и показывать реальные строки, которые можно открыть в оригинале.
Постройте эту связь с помощью map и set в C++. Загрузка, разбор слов, обработка запросов и вывод строк уже подготовлены; вы реализуете индекс и проверите его на изменяемых учебных заметках. Нужны основы работы в терминале, строки, векторы, функции, файловые потоки и исключения C++. Контейнеры map и set объясняются здесь. 50 минут — оценка автора.
Свяжите слово со всеми подходящими заметками
На этом шаге вы запустите готовый пример, затем построите индекс слов и документов для своего исполняемого файла. Во всём курсе используйте вкладку Terminal. Она открывает оболочку UTF-8; выбирайте именно эту вкладку, а не терминал внутри WebIDE. Рабочий каталог сохраняется в течение открытого соединения. Если откроете другое соединение, повторите указанный cd.
cd меняет рабочий каталог. Начните с подготовленного проекта:
cd /home/labex/project/note-search
notes/reference содержит защищённые оригиналы; notes/practice — копию, доступную для записи. find рекурсивно перечисляет пути; -type f ограничивает список обычными файлами. Порядок списка не важен.
find notes -type f
Существуют и notes/reference/archive/notes.txt, и notes/reference/field/notes.txt. Последний компонент, то есть базовое имя файла, одинаков, но полные пути обозначают разные документы. ./ запускает исполняемый файл из текущего каталога. Готовый sample принимает каталог заметок и запрос:
./sample notes cat
Он возвращает три группы документов, включая эти две:
File: reference/archive/notes.txt
1: CAT, cat!
3: cat blue together
File: reference/field/notes.txt
1: cat; red
Третья группа — practice/旅行 notes.txt. Каждый идентификатор отсчитывается от переданного корня notes, поэтому префикс notes/ опущен. Документ появляется один раз, даже если слово повторяется. Числа — реальные номера исходных строк, начиная с 1. Показаны только подходящие строки; пропуск номера не означает удаление строки. cat выводит текстовый файл для сравнения:
cat notes/reference/archive/notes.txt
Строка 2, Blue ledger — 東京, существует, но не содержит cat. Исходные пути UTF-8 и текст строк сохраняются.
Наше небольшое правило слов строго определено: токен — максимальная непрерывная последовательность букв ASCII A-Z или a-z, причём заглавные буквы ASCII переводятся в нижний регистр. Цифры, подчёркивания, знаки пунктуации, пробельные символы и каждый байт вне ASCII разделяют токены. CAT-blue_42 превращается в cat и blue; cat отличается от catalog; 猫cat狗 содержит cat; café даёт caf, а не cafe. Сохранение Unicode-текста не равно пониманию слов всех языков. Многоязычную сегментацию мы не реализуем.
Прочитайте подготовленный интерфейс и начальный код:
cat search.hpp
cat engine.cpp
Document хранит id, полный относительный путь, и lines, вектор строк оригинального текста. Подготовленный загрузчик рекурсивно читает обычные файлы .txt и сортирует их идентификаторы. Заметки — текст UTF-8 с окончаниями строк LF. Допустимы пробелы и Unicode в путях; табуляции и переводы строк в путях, символические ссылки, NUL-данные и произвольные двоичные файлы вне формата. Нечитаемый ввод приводит к ошибке, а не к частичному результату.
Index — псевдоним std::map<std::string, std::set<std::string>>. Map связывает каждый отдельный ключ-слово со значением: здесь это множество идентификаторов документов. Set хранит каждый идентификатор один раз. Поэтому три появления cat в документе дают одну связь. Такой обратный поиск от слов к документам называется инвертированным индексом.
Начальный код возвращает пустой индекс. provided.inc содержит уже работающую функцию запроса этой части. #include вставляет файл при компиляции. Сохраните search.hpp, provided.inc, support.cpp, main.cpp, sample и все пути и содержимое notes/reference/. Редактируйте engine.cpp; разрешены вспомогательные функции и эквивалентные алгоритмы. Менять, добавлять и удалять данные можно только в notes/practice/. Сохранение его начального состава файлов не является условием оценки.
bash запускает подготовленный скрипт самопроверки. index выбирает изучаемое здесь поведение. Первый запуск намеренно завершается с FAIL exact whole-word postings retain complete document identities и ненулевым кодом. Это означает незавершённый индекс, а не неисправное окружение:
bash /opt/labex-note-search/check.sh index
Обойдите каждый документ, строку и разобранное слово. Цикл for по диапазону посещает каждый элемент; const auto& даёт ссылку только для чтения вместо копии. index[word] обращается к множеству идентификаторов документов для этого слова, создавая пустое множество для нового ключа. .insert(doc.id) добавляет полный идентификатор и игнорирует повторные связи. Держите map вне всех циклов, чтобы накапливать связи всех документов.
Следующая команда заменяет только engine.cpp. Here-document передаёт несколько строк в cat; > записывает их в указанный файл, заменяя содержимое. Разделитель в кавычках 'CPP' предотвращает раскрытие текста C++ оболочкой. Завершите команду строкой, содержащей только CPP. Оставьте обе директивы включения, чтобы сохранить объявления и готовую реализацию запроса.
cat > engine.cpp <<'CPP'
#include "search.hpp"
#include "provided.inc"
Index buildIndex(const std::vector<Document>& documents) {
Index index;
for (const auto& doc : documents) {
for (const auto& line : doc.lines) {
for (const auto& word : words(line)) {
index[word].insert(doc.id);
}
}
}
return index;
}
CPP
words(line) — подготовленный анализатор ASCII. Не извлекайте только базовое имя, не останавливайтесь на первом совпадении и не храните число появлений вместо множества документов.
Скомпилируйте результат. g++ — компилятор; -std=c++17 выбирает версию языка, -Wall -Wextra включает полезные предупреждения, а -o findnotes задаёт имя исполняемого файла. Три входных .cpp — ваш поисковый код, подготовленные загрузчик и анализатор, а также командный интерфейс. Включаемые файлы читаются автоматически.
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
Успешная сборка обычно ничего не выводит. При ошибке прочитайте первое имя файла и номер строки, исправьте engine.cpp или повторите его полную замену, затем скомпилируйте снова. После неудачной сборки может остаться старый исполняемый файл. Правка исходника сама по себе его не обновляет. Самопроверка выполняет ваши функции в исходном представленном виде на изолированных данных и запускает существующий findnotes; она не пересобирает его за вас.
./findnotes notes cat
Ожидаются все три идентификатора и те же исходные строки, что в примере. Допустим другой воспроизводимый порядок документов; внутри каждого номера строк должны возрастать, и каждая строка появляется один раз. Шаг оценивает индекс и запросы из одного слова. Объединение разных поисковых слов пока подготовлено и станет вашей задачей в следующей работе.
Перестройте индекс по текущим учебным заметкам
На этом шаге вы измените, добавите и удалите учебные данные, сохранив оригиналы. Оставайтесь в Terminal, в /home/labex/project/note-search. Каждый запуск загружает текущие файлы и строит новый индекс в памяти. Нет сохранённого файла индекса, демона обновления или дополнительной команды перестроения.
Сначала сравните границы целых слов:
./findnotes notes catalog
Ожидаются reference/catalog.txt и practice/旅行 notes.txt со строками, содержащими catalog. Это не дополнительные совпадения для cat. Неизвестное слово тоже является нормальным поиском:
./findnotes notes absent
Он выводит No matching documents. и успешно завершается. Это отличается от некорректно сформированного ввода, который готовый интерфейс отвергает. Следующая работа рассматривает это различие.
Учебная копия уже доступна для записи; эталонные оригиналы — только для чтения. Одинарные кавычки сохраняют путь с пробелами одним аргументом и оставляют символы Unicode. printf пишет текст; \n создаёт перевод строки. > полностью заменяет указанный учебный файл. Замените его содержимое, убрав cat из этой копии:
printf 'owl green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes cat
Теперь подходят только две эталонные заметки. Учебный файл существует, но его текущее содержимое больше не подходит. Добавьте другую разрешённую учебную заметку:
printf 'CAT beside the window\nA new observation\n' > 'notes/practice/new notes.txt'
./findnotes notes cat
Снова подходят три документа, включая строку 1 в practice/new notes.txt. Вы не перекомпилировали код: изменение данных требует лишь повторного запуска. Изменение исходника C++ требует компиляции.
rm удаляет файл. Его единственный аргумент в кавычках здесь — новая учебная заметка, а не оригинал и не весь каталог:
rm 'notes/practice/new notes.txt'
./findnotes notes cat
Этот идентификатор исчезает, два эталонных результата остаются. Никогда не удаляйте оригиналы и не меняйте анализатор ради нужного ответа. При опечатке в пути прочитайте No such file or directory, выведите пути через find notes -type f и используйте точный. Если выбрали оригинал только для чтения, оставьте его нетронутым и используйте учебный файл. Обычные ошибки пути не требуют сброса окружения.
Запустите самопроверку снова. Она читает текущие файлы и создаёт временные тестовые данные для других входов. Их изменение, добавление и удаление никогда не меняют ваши учебные заметки. Изолированные пробы неверного ввода могут печатать ожидаемые ошибки рядом с PASS; успешный запуск заканчивается CLI CHECKS PASSED.
bash /opt/labex-note-search/check.sh index
Проверка кнопкой тоже должна пройти. Повторные проверки не переписывают код, не заменяют программу и не сбрасывают заметки. Если проверка не прошла после правки исходника, пересоберите настоящий findnotes и повторите. Одних временных тестов функций недостаточно, чтобы подтвердить актуальность исполняемого файла.
Резюме
Вы построили инвертированный индекс со множествами полных идентификаторов документов в качестве значений. Повторы слов не дублируют документы, одинаковые базовые имена остаются разными, а реальные номера строк ведут к оригиналу. Повторный запуск прозрачно перестраивает индекс после разрешённых изменений, добавлений и удалений учебных данных. Далее реализуйте пересечение, требующее нескольких слов в одном документе.
