Introduction
Se souvenir de deux mots doit restreindre la recherche aux notes contenant les deux. Ils peuvent se trouver sur des lignes différentes, et deux notes portant le même nom doivent rester distinctes.
Ce laboratoire indépendant fournit un index correct des mots vers les documents. Vous implémenterez l'intersection des requêtes, reconstruirez l'exécutable CLI réel, distinguerez un résultat vide normal d'une entrée invalide et chercherez après avoir modifié les notes d'exercice. Il s'appuie sur les tables associatives, ensembles, jetons ASCII et opérations de terminal et fichiers du laboratoire précédent. Les 55 minutes sont une estimation de l'auteur.
Ne garder que les documents communs à tous les mots
Dans cette étape, implémentez AND au niveau du document : une note ne correspond que si elle contient chaque mot demandé, même sur des lignes différentes. Ce laboratoire démarre indépendamment. Un index correct est déjà fourni ; il ne dépend pas de l'environnement précédent. Utilisez l'onglet Terminal, pas un terminal dans WebIDE. Il ouvre un shell UTF-8 sans modifier vos fichiers. cd change le répertoire de ce shell ; répétez-le pour une autre connexion.
cd /home/labex/project/note-search
L'exemple complet reçoit un répertoire et une requête. Les apostrophes conservent les deux mots dans un seul argument du shell. Le programme analyse cet argument avec la même règle ASCII que les notes :
./sample notes 'cat blue'
Vous devez obtenir practice/旅行 notes.txt et reference/archive/notes.txt. Le groupe de la note archivée contient :
File: reference/archive/notes.txt
1: CAT, cat!
2: Blue ledger — 東京
3: cat blue together
Chaque ligne contenant l'un ou l'autre mot demandé apparaît une fois, avec son vrai numéro à partir de 1. La décision AND s'applique au document entier, pas à une ligne. Une note avec cat uniquement sur la ligne 1 et blue uniquement sur la ligne 2 doit tout de même correspondre. Les répétitions ou deux termes sur une ligne ne répètent pas cette ligne. Les extraits conservent les octets Unicode d'origine.
cat affiche un fichier. Lisez l'interface et l'implémentation préparée de l'index :
cat search.hpp
cat provided.inc
Index associe un mot à un ensemble d'identifiants relatifs complets de documents. L'ensemble des documents d'un mot est aussi appelé son ensemble de références documentaires. provided.inc fournit le bon buildIndex dans cette unité. engine.cpp contient le findAll incomplet :
cat engine.cpp
Conservez search.hpp, provided.inc, support.cpp, main.cpp, sample et tous les chemins et contenus de notes/reference/. Modifiez engine.cpp ; les auxiliaires et algorithmes équivalents sont permis. Seules les données de notes/practice/ sont modifiables, sans obligation de garder leurs fichiers initiaux. Le chargeur préparé lit récursivement les fichiers .txt ordinaires UTF-8 avec LF. Les espaces et l'Unicode sont admis dans les chemins ; tabulations ou retours à la ligne dans les chemins, liens symboliques, octets NUL et binaires arbitraires sont hors format. Une erreur de lecture ne produit aucun résultat partiel.
L'analyseur préparé words() produit des séquences maximales de lettres ASCII et convertit A-Z en a-z. Chiffres, traits de soulignement, ponctuation, espaces et chaque octet non ASCII délimitent les jetons. cat n'est pas catalog ; CAT-blue_42 donne cat et blue ; 猫cat狗 donne cat ; café donne caf, et non cafe. Cela ne prétend pas réaliser une segmentation multilingue. findAll reçoit les termes ASCII minuscules déjà normalisés de cet analyseur, éventuellement répétés. Si la liste de termes est vide, il doit renvoyer un vecteur vide sans danger. La CLI rejette séparément une requête brute sans mot ASCII avec le code 2 et aucun résultat sur stdout ; un mot inconnu ou une requête valide sans correspondance donne normalement 0 et No matching documents.
bash lance l'autovérification ; query sélectionne tout le comportement de requête. Le code de départ échoue volontairement, généralement à FAIL all documents, not only the first. Un code non nul signifie ici qu'il reste du travail :
bash /opt/labex-note-search/check.sh query
Pour une requête AND, commencez par une copie de l'ensemble de références du premier mot. Examinez ensuite, un par un, les ensembles des autres termes et supprimez un candidat dès qu'il manque dans un seul de ces ensembles. C'est l'intersection d'ensembles. Si un terme est inconnu, aucun document ne peut les contenir tous. N'ajoutez jamais toutes les références les unes aux autres : ce serait OR, acceptant des notes qui ne contiennent qu'un des mots demandés.
Vérifiez terms.empty() avant que terms.front() n'accède au premier élément. index.find(word) recherche une clé sans l'insérer ; index.end() signifie qu'elle n'existe pas. Ne déréférencez pas cette entrée absente. Pour une entrée trouvée, first->second ou posting->second utilise -> pour y accéder par l'itérateur ; second est sa valeur, l'ensemble d'identifiants. Copiez cet ensemble dans found pour que la requête ne modifie pas l'index.
La boucle utilise un itérateur, une position dans l'ensemble. found.begin() est la première position ; found.end() marque celle après le dernier élément. *it est l'identifiant courant. .count(*it) vaut 0 si cet identifiant est absent d'un autre ensemble de références. L'effacement invalide l'ancienne position ; erase(it) renvoie donc l'itérateur valide suivant. Sinon, ++it avance normalement. N'incrémentez pas deux fois après l'effacement.
Remplacez engine.cpp par cette implémentation. Comme précédemment, le here-document écrit un fichier complet ; > le remplace et le délimiteur entre apostrophes 'CPP' empêche le développement par le shell. CPP doit terminer la commande seul sur une ligne. Les inclusions conservent l'interface et l'index correct préparé.
cat > engine.cpp <<'CPP'
#include "search.hpp"
#include "provided.inc"
std::vector<std::string> findAll(const Index& index,
const std::vector<std::string>& terms) {
if (terms.empty()) return {};
auto first = index.find(terms.front());
if (first == index.end()) return {};
std::set<std::string> found = first->second;
for (const auto& term : terms) {
auto posting = index.find(term);
if (posting == index.end()) return {};
for (auto it = found.begin(); it != found.end();) {
if (posting->second.count(*it) == 0) it = found.erase(it);
else ++it;
}
}
return std::vector<std::string>(found.begin(), found.end());
}
CPP
Le constructeur final copie la plage restante de l'ensemble dans un vecteur. Un ensemble contient des identifiants uniques, donc chaque document est renvoyé une fois. Revérifier le premier terme dans la boucle est sans effet : l'intersection d'un ensemble avec lui-même ne le change pas. Les termes répétés sont sans effet pour la même raison. Une intersection vide renvoie naturellement un vecteur vide. Un autre ordre reproductible des groupes, y compris des chemins décroissants, est autorisé ; les numéros de ligne de chaque groupe doivent toujours croître.
Compilez le code courant. g++ compile les trois fichiers .cpp ; -std=c++17 choisit C++17, -Wall -Wextra active les avertissements et -o nomme l'exécutable. Les fichiers inclus sont compilés automatiquement via engine.cpp :
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
Une réussite n'affiche normalement rien. En cas d'échec, lisez le premier diagnostic de fichier et ligne, corrigez engine.cpp ou répétez son remplacement, puis reconstruisez. Un échec peut laisser un ancien binaire ; la vérification teste les fonctions et le véritable findnotes existant sans le reconstruire. Un exécutable manquant ou périmé n'est pas une livraison terminée.
./findnotes notes 'cat blue'
Comparez les groupes complets et les lignes probantes avec l'exemple. L'affichage préparé utilise les identifiants renvoyés pour sélectionner les vraies lignes originales ; modifier les notes originales ou afficher un message de réussite fixe n'implémente pas une recherche.
Distinguer un résultat vide d'une requête invalide
Dans cette étape, testez les mots répétés, les limites des jetons, les erreurs et la reconstruction depuis les fichiers courants. Restez dans Terminal, dans le projet. La fonction terminée ne doit pas modifier son entrée const Index& ni dupliquer les documents lorsqu'un mot se répète :
./findnotes notes 'cat cat blue'
Les groupes et lignes sont identiques à ceux de cat blue. Ajoutez maintenant un terme inconnu :
./findnotes notes 'cat absent'
Attendez-vous à No matching documents.. Un document contenant seulement cat ne suffit pas. La requête est valide mais sans réponse, elle se termine donc par 0. Juste après une commande, la variable du shell $? contient son code de sortie ; les guillemets doubles la développent en un argument. printf l'affiche et \n termine la ligne :
printf 'Exit status: %s\n' "$?"
La sortie est Exit status: 0. Testez la conversion de casse et les séparateurs :
./findnotes notes 'CAT-blue_42'
Cela signifie la même chose que cat blue. Ni les chiffres ni les traits de soulignement ne font partie des jetons. Une recherche de mot entier ne cherche pas des sous-chaînes :
./findnotes notes catalog
Seuls reference/catalog.txt et la note d'exercice contenant catalog correspondent. Cela ne signifie pas cat.
Une chaîne vide s'écrit avec deux apostrophes adjacentes, ''. C'est un argument du shell fourni mais vide. La commande suivante est un échec volontaire, affichant Query needs at least one ASCII word sur stderr et aucun résultat sur stdout :
./findnotes notes ''
Lisez immédiatement son code :
printf 'Exit status: %s\n' "$?"
Il affiche 2. Une requête composée uniquement de chiffres, séparateurs et caractères non ASCII est invalide pour la même raison :
./findnotes notes '42_東京'
C'est aussi un échec volontaire de code 2. Il ne signifie pas que le stockage Unicode est cassé : la requête ne contient simplement aucun mot ASCII pris en charge. Reprenez avec une requête contenant un mot, sans modifier l'original ni l'analyseur.
Une erreur de nom de répertoire est un autre problème. Cette commande indique volontairement un répertoire inexistant :
./findnotes missing-notes cat
Elle affiche Cannot read notes directory et se termine par 2 sans résultats partiels. Utilisez find notes -type f pour consulter les chemins réels si nécessaire, puis reprenez avec la bonne racine :
./findnotes notes cat
Les résultats normaux reviennent. La même règle de lecture complète ou d’erreur s'applique si un fichier source est illisible. En revanche, un répertoire de notes vide mais lisible est valide et ne donne aucune correspondance.
Modifiez maintenant la copie d'exercice préparée et accessible en écriture. Les apostrophes préservent le nom avec espaces et Unicode. printf écrit du texte, \n produit des fins de ligne LF et > remplace ce fichier. Les originaux sous reference restent intacts :
printf 'cat green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes 'cat blue'
Seule la note archivée reste : la note d'exercice ne contient plus blue. Chaque invocation relit les fichiers actuels et crée un nouvel index en mémoire. Il n'y a ni cache sauvegardé ni commande d'actualisation supplémentaire. Les données modifiées demandent une nouvelle exécution ; le C++ modifié demande une recompilation.
Ajoutez une note dont les mots demandés sont sur des lignes distinctes :
printf 'BLUE here\ncat elsewhere 東京\n' > 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
practice/new notes.txt correspond maintenant et affiche les lignes 1 et 2, avec le résultat archivé. C'est une preuve directe de AND au niveau du document, sur plusieurs lignes. rm ne supprime que le fichier d'exercice indiqué :
rm 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
Le groupe supplémentaire disparaît. Si un chemin est mal saisi, énumérez les fichiers et utilisez le bon ; ne réinitialisez pas la VM. Si vous visez un original protégé, laissez-le intact et utilisez un fichier d'exercice. Toutes les modifications légitimes de pratique restent autorisées par l'évaluation.
Lancez l'autovérification. Elle lit votre projet et utilise des données temporaires pour d'autres entrées ; elle ne répare jamais votre binaire, ne modifie pas les notes réelles et ne réinitialise pas le progrès. Les sondes d'entrées invalides peuvent afficher leurs erreurs attendues près de PASS ; la réussite finit par CLI CHECKS PASSED :
bash /opt/labex-note-search/check.sh query
Si les tests du code réussissent mais que l'exécutable réel échoue, recompilez findnotes à partir du code courant et réessayez. Répéter les vérifications doit laisser intacts votre moteur, exécutable, fichiers préparés, originaux et contenu d'exercice actuel.
Résumé
Vous avez implémenté AND comme intersection d'identifiants de documents, y compris pour des termes sur des lignes distinctes. Les termes répétés sont sans effet, les mots inconnus donnent un résultat vide normal et les requêtes mal formées ou entrées illisibles échouent explicitement. Votre exécutable existant lit les données actuelles et affiche chaque ligne originale pertinente une fois. Le défi associe ce comportement à la construction de l'index sur une autre collection.
