Einführung
Zwei erinnerte Wörter sollten die Suche auf Notizen eingrenzen, die beide enthalten. Die Wörter können in verschiedenen Zeilen stehen, und gleichnamige Notizen müssen weiterhin getrennte Dokumente bleiben.
Dieses unabhängige Lab stellt einen korrekten Wort-Dokument-Index bereit. Du implementierst die Abfrageschnittmenge, baust das reale CLI-Programm neu, unterscheidest normale leere Ergebnisse von ungültigen Eingaben und suchst nach Änderungen an Übungsnotizen. Es baut auf Maps, Mengen, ASCII-Tokens sowie Terminal- und Dateioperationen des vorherigen Labs auf. Die 55 Minuten sind eine Schätzung des Autors.
Nur Dokumente behalten, die alle Suchwörter enthalten
In diesem Schritt implementierst du AND auf Dokumentebene: Eine Notiz passt nur, wenn sie jedes Suchwort enthält, auch in unterschiedlichen Zeilen. Dieses Lab startet unabhängig. Der korrekte Index ist bereits vorhanden und hängt nicht von deiner vorherigen Umgebung ab. Verwende den Tab Terminal, kein Terminal innerhalb von WebIDE. Er öffnet eine UTF-8-Shell, ohne Dateien zu verändern. cd wechselt das Verzeichnis dieser Shell; wiederhole es bei einer neuen Verbindung.
cd /home/labex/project/note-search
Das vollständige Beispiel erhält ein Verzeichnis und eine Abfrage. Einfache Anführungszeichen halten zwei Wörter als ein Shell-Argument zusammen. Das Programm zerlegt dieses Argument nach derselben ASCII-Regel wie die Notizen:
./sample notes 'cat blue'
Erwarte practice/旅行 notes.txt und reference/archive/notes.txt. Die Gruppe der archivierten Notiz enthält:
File: reference/archive/notes.txt
1: CAT, cat!
2: Blue ledger — 東京
3: cat blue together
Jede Zeile mit mindestens einem der Suchwörter erscheint einmal mit ihrer echten, bei 1 beginnenden Zeilennummer. Die AND-Entscheidung gilt für das gesamte Dokument, nicht für eine einzelne Zeile. Eine Notiz mit cat nur in Zeile 1 und blue nur in Zeile 2 muss ebenfalls passen. Mehrfache Vorkommen oder zwei Suchwörter in einer Zeile wiederholen diese Zeile nicht. Die Ausschnitte behalten die ursprünglichen Unicode-Bytes.
cat zeigt eine Datei an. Lies die Schnittstelle und die vorbereitete Indeximplementierung:
cat search.hpp
cat provided.inc
Index ist eine Map von einem Wort zu einer Menge vollständiger relativer Dokumentkennungen. Die Dokumentmenge eines Wortes wird auch als Menge seiner Dokumentverweise bezeichnet. provided.inc liefert in dieser Einheit das korrekte buildIndex. engine.cpp enthält das unvollständige findAll:
cat engine.cpp
Erhalte search.hpp, provided.inc, support.cpp, main.cpp, sample und alle Pfade und Inhalte unter notes/reference/. Bearbeite engine.cpp; Hilfsfunktionen und gleichwertige Algorithmen sind erlaubt. Nur Daten unter notes/practice/ sind veränderbar; der ursprüngliche Dateibestand ist nicht vorgeschrieben. Der vorbereitete Lader liest reguläre .txt-Dateien mit UTF-8 und LF-Zeilenenden rekursiv. Leerzeichen und Unicode-Pfade sind zulässig; Tabulatoren oder Zeilenumbrüche in Pfaden, symbolische Links, NUL-Bytes und beliebige Binärdateien liegen außerhalb des Formats. Lesefehler liefern einen Fehler ohne Teilergebnisse.
Der vorbereitete Parser words() erzeugt maximale ASCII-Buchstabenfolgen und wandelt A-Z in a-z um. Ziffern, Unterstriche, Satzzeichen, Leerraum und jedes Nicht-ASCII-Byte begrenzen Tokens. cat ist nicht catalog; CAT-blue_42 ergibt cat und blue; 猫cat狗 ergibt cat; café ergibt caf, nicht cafe. Das beansprucht keine mehrsprachige Wortsegmentierung. findAll erhält bereits normalisierte ASCII-Suchwörter in Kleinbuchstaben des Parsers, eventuell mehrfach. Für eine leere Wortliste muss es sicher einen leeren Vektor liefern. Die CLI lehnt eine rohe Abfrage ohne ASCII-Wort separat mit Status 2 und ohne Ergebnisausgabe auf stdout ab; ein unbekanntes Wort oder eine gültige Abfrage ohne Treffer endet normal mit 0 und No matching documents.
bash startet die Selbstprüfung; query wählt das vollständige Abfrageverhalten. Der Ausgangscode scheitert absichtlich, normalerweise bei FAIL all documents, not only the first. Ein Status ungleich null bedeutet hier, dass noch Arbeit offen ist:
bash /opt/labex-note-search/check.sh query
Beginne für eine AND-Abfrage mit einer Kopie der Dokumentmenge des ersten Wortes. Prüfe danach die Mengen der weiteren Suchwörter nacheinander. Entferne einen Kandidaten, sobald er in einer einzigen dieser Mengen fehlt. Das ist die Schnittmenge. Ist ein Suchwort unbekannt, kann kein Dokument alle Wörter enthalten. Vereinige niemals alle Dokumentverweise durch bloßes Hinzufügen: Das wäre OR und würde Notizen akzeptieren, die nur eines der verlangten Wörter enthalten.
Prüfe terms.empty(), bevor terms.front() das erste Element liest. index.find(word) sucht einen Map-Schlüssel, ohne ihn einzufügen; index.end() bedeutet, dass er fehlt. Dereferenziere diesen fehlenden Eintrag nicht. Bei einem gefundenen Eintrag greift first->second oder posting->second mit -> über den Iterator auf ihn zu; second ist sein Wert, die Kennungsmenge. Kopiere sie nach found, damit die Abfrage den Index nicht verändert.
Die Schleife nutzt einen Iterator, eine Position in der Menge. found.begin() ist die erste Position; found.end() markiert die Position nach dem letzten Element. *it ist die aktuelle Kennung. .count(*it) ist 0, wenn diese Kennung in einer anderen Dokumentmenge fehlt. Löschen macht die alte Position ungültig; deshalb liefert erase(it) den nächsten gültigen Iterator. Andernfalls rückt ++it normal weiter. Erhöhe nach dem Löschen nicht noch ein zweites Mal.
Ersetze engine.cpp durch diese Implementierung. Wie im vorherigen Lab schreibt das Here-Dokument eine vollständige Datei; > ersetzt sie und der zitierte Begrenzer 'CPP' verhindert Shell-Erweiterungen. CPP muss den Befehl allein auf einer Zeile beenden. Die Include-Anweisungen erhalten die Schnittstelle und den vorbereiteten korrekten Index.
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
Der abschließende Konstruktor kopiert den verbliebenen Mengenbereich in einen Vektor. Mengen enthalten eindeutige Kennungen, daher wird jedes Dokument einmal geliefert. Das erste Wort in der Schleife nochmals zu prüfen schadet nicht: Die Schnittmenge einer Menge mit sich selbst verändert sie nicht. Wiederholte Suchwörter sind aus demselben Grund harmlos. Eine leere Schnittmenge liefert von selbst einen leeren Vektor. Andere reproduzierbare Gruppenreihenfolgen, auch absteigende Pfade, sind erlaubt; die Zeilennummern innerhalb jeder Gruppe müssen weiterhin steigen.
Kompiliere den aktuellen Quelltext. g++ kompiliert die drei .cpp-Dateien; -std=c++17 wählt C++17, -Wall -Wextra aktiviert Warnungen und -o benennt die ausführbare Datei. Eingebundene Dateien werden automatisch über engine.cpp mitkompiliert:
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
Erfolg erzeugt normalerweise keine Ausgabe. Lies bei einem Fehler die erste Datei-/Zeilendiagnose, korrigiere engine.cpp oder wiederhole dessen Ersatz und baue erneut. Eine fehlgeschlagene Kompilierung kann eine alte Binärdatei zurücklassen; die Prüfung testet Funktionen und dein tatsächlich vorhandenes findnotes, ohne es neu zu bauen. Eine fehlende oder veraltete ausführbare Datei ist keine fertige Abgabe.
./findnotes notes 'cat blue'
Vergleiche vollständige Gruppen und Zeilenbelege mit dem Beispiel. Die vorbereitete Anzeige verwendet deine zurückgegebenen Kennungen, um echte Originalzeilen auszuwählen; Originalnotizen zu verändern oder festen Erfolgstext auszugeben implementiert keine Suche.
Leere Ergebnisse von ungültigen Abfragen unterscheiden
In diesem Schritt testest du wiederholte Wörter, Token-Grenzen, Fehler und den Neuaufbau aus aktuellen Dateien. Bleibe in Terminal im Projektverzeichnis. Die fertige Funktion darf ihre Eingabe const Index& nicht ändern und bei wiederholten Wörtern keine Dokumente duplizieren:
./findnotes notes 'cat cat blue'
Dokumentgruppen und Zeilen entsprechen cat blue. Füge jetzt ein unbekanntes Wort hinzu:
./findnotes notes 'cat absent'
Erwarte No matching documents.. Ein Dokument, das nur cat enthält, genügt nicht. Diese Abfrage ist gültig, hat aber keine Antwort und endet deshalb mit 0. Direkt nach einem Befehl enthält die Shell-Variable $? dessen Rückgabecode; doppelte Anführungszeichen expandieren ihn als ein Argument. printf zeigt ihn an und \n beendet die Ausgabezeile:
printf 'Exit status: %s\n' "$?"
Die Ausgabe lautet Exit status: 0. Teste Groß-/Kleinschreibung und Trennzeichen:
./findnotes notes 'CAT-blue_42'
Das hat dieselbe Bedeutung wie cat blue. Ziffern und Unterstriche gehören nicht zu Tokens. Eine Ganzwortsuche verwendet keine Teilzeichenfolgensuche:
./findnotes notes catalog
Nur reference/catalog.txt und die Übungsnotiz mit catalog passen. Es bedeutet nicht cat.
Eine leere Zeichenfolge schreibst du mit zwei direkt aufeinanderfolgenden einfachen Anführungszeichen, ''. Das ist ein vorhandenes, aber leeres Shell-Argument. Der folgende Befehl ist ein absichtlicher Fehler, der Query needs at least one ASCII word auf stderr und keine Ergebnisse auf stdout ausgibt:
./findnotes notes ''
Lies seinen Status sofort:
printf 'Exit status: %s\n' "$?"
Er zeigt 2. Eine Abfrage nur aus Ziffern, Trennzeichen und Nicht-ASCII-Zeichen ist aus demselben Grund ungültig:
./findnotes notes '42_東京'
Auch dies ist ein beabsichtigter Fehler mit Status 2. Das bedeutet nicht, dass Unicode-Speicherung defekt ist: Die Abfrage enthält einfach kein unterstütztes ASCII-Wort. Verwende zur Wiederherstellung eine Wortabfrage, statt Originaltext oder Tokenizer zu ändern.
Ein falsch geschriebener Verzeichnisname ist ein anderer Fehler. Dieser Befehl nennt absichtlich ein nicht vorhandenes Verzeichnis:
./findnotes missing-notes cat
Er zeigt Cannot read notes directory und endet mit 2 ohne Teilergebnisse. Mit find notes -type f kannst du bei Bedarf die echten Pfade ansehen; verwende danach das korrekte Stammverzeichnis:
./findnotes notes cat
Die normalen Ergebnisse erscheinen wieder. Dieselbe Regel „alles lesbar oder Fehler“ gilt, wenn irgendeine Quelldatei unlesbar ist. Ein leeres, aber lesbares Notizverzeichnis ist dagegen gültig und ergibt keine Treffer.
Ändere jetzt die vorbereitete beschreibbare Übungskopie. Einfache Anführungszeichen erhalten einen Namen mit Leerzeichen und Unicode. printf schreibt Text, \n erzeugt LF-Zeilenumbrüche und > ersetzt diese Übungsdatei. Die Originale unter reference bleiben unangetastet:
printf 'cat green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes 'cat blue'
Nur die archivierte Notiz bleibt: Die Übungsnotiz enthält kein blue mehr. Jeder Aufruf liest die aktuellen Dateien erneut und erzeugt einen neuen Index im Speicher. Es gibt keinen gespeicherten Cache und keinen zusätzlichen Aktualisierungsbefehl. Datenänderungen benötigen einen neuen Aufruf; C++-Änderungen erfordern eine neue Kompilierung.
Füge eine Notiz hinzu, deren Suchwörter in getrennten Zeilen stehen:
printf 'BLUE here\ncat elsewhere 東京\n' > 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
practice/new notes.txt passt jetzt und zeigt Zeilen 1 und 2 zusätzlich zum archivierten Treffer. Das belegt direkt dokumentweites AND über Zeilengrenzen hinweg. rm löscht nur die angegebene Übungsdatei:
rm 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
Die zusätzliche Gruppe verschwindet. Bei einem falsch geschriebenen Pfad liste die Dateien auf und nutze den genauen Namen; setze die VM nicht zurück. Zielst du auf ein geschütztes Original, lasse es unverändert und nutze eine Übungsdatei. Die Bewertung erlaubt weiterhin sämtliche legitimen Übungsänderungen.
Führe die Selbstprüfung aus. Sie liest dein aktuelles Projekt und nutzt wegwerfbare Daten für weitere Eingaben; sie repariert nie deine Binärdatei, ändert keine echten Notizen und setzt keinen Fortschritt zurück. Tests ungültiger Eingaben können erwartete Fehler neben PASS zeigen; Erfolg endet mit CLI CHECKS PASSED:
bash /opt/labex-note-search/check.sh query
Bestehen die Quelltexttests, aber nicht die tatsächliche ausführbare Datei, kompiliere findnotes aus dem aktuellen Quelltext und versuche es erneut. Wiederholte Prüfungen müssen Suchkern, Programm, vorbereitete Dateien, Originale und den aktuellen Übungsinhalt unverändert lassen.
Zusammenfassung
Du hast AND als Schnittmenge von Dokumentkennungen implementiert, auch für Wörter in verschiedenen Zeilen. Wiederholte Wörter sind harmlos, unbekannte Wörter ergeben normale leere Ergebnisse und fehlerhafte Abfragen oder unlesbare Eingaben scheitern ausdrücklich. Dein vorhandenes Programm liest nun aktuelle Übungsdaten und zeigt jede relevante Originalzeile einmal. Die Challenge verbindet dieses Abfrageverhalten mit dem Indexaufbau für eine andere Notizsammlung.
