Einführung
Du erinnerst dich an ein Wort aus einer Notiz, aber nicht mehr an ihr Verzeichnis. Eine nützliche Suche muss alle passenden Notizen finden, gleichnamige Dateien unterscheiden und echte Zeilen anzeigen, die du im Original nachlesen kannst.
Baue diese Beziehung mit Maps und Mengen in C++ auf. Laden, Wortzerlegung, Abfragen und Zeilenanzeige sind vorbereitet; du implementierst den Index und testest ihn mit veränderlichen Übungsnotizen. Vorausgesetzt werden grundlegende Terminalnavigation, C++-Strings, Vektoren, Funktionen, Dateistreams und Ausnahmen. Maps und Mengen werden hier erklärt. Die 50 Minuten sind eine Schätzung des Autors.
Ein Wort mit jeder passenden Notiz verknüpfen
In diesem Schritt nutzt du ein funktionierendes Beispiel und baust danach den Wort-Dokument-Index für dein eigenes Programm. Verwende im gesamten Kurs den Tab Terminal. Er öffnet eine UTF-8-Shell; nutze diesen benannten Tab statt eines Terminals innerhalb von WebIDE. Das Arbeitsverzeichnis bleibt während dieser offenen Verbindung bestehen. Öffnest du eine andere Verbindung, wiederhole das angegebene cd.
cd wechselt das Arbeitsverzeichnis. Beginne im vorbereiteten Projekt:
cd /home/labex/project/note-search
notes/reference enthält geschützte Originale; notes/practice enthält eine beschreibbare Kopie. find listet Pfade rekursiv auf; -type f beschränkt die Liste auf reguläre Dateien. Ihre Reihenfolge ist unwichtig.
find notes -type f
Sowohl notes/reference/archive/notes.txt als auch notes/reference/field/notes.txt existieren. Der letzte Namensbestandteil, also der Basisname, ist identisch, doch die vollständigen Pfade kennzeichnen verschiedene Dokumente. ./ startet eine ausführbare Datei im aktuellen Verzeichnis. Das vollständige sample erhält ein Notizverzeichnis und eine Abfrage:
./sample notes cat
Es liefert drei Dokumentgruppen, darunter diese beiden:
File: reference/archive/notes.txt
1: CAT, cat!
3: cat blue together
File: reference/field/notes.txt
1: cat; red
Die dritte Gruppe ist practice/旅行 notes.txt. Jede Kennung ist relativ zum angegebenen Stammverzeichnis notes und lässt deshalb notes/ weg. Jedes Dokument erscheint genau einmal, auch wenn das Wort mehrfach vorkommt. Die Zahlen sind echte, bei 1 beginnende Originalzeilennummern. Nur relevante Zeilen werden gezeigt; eine fehlende Nummer bedeutet nicht, dass die Zeile gelöscht wurde. cat zeigt eine Textdatei zum Vergleich an:
cat notes/reference/archive/notes.txt
Zeile 2, Blue ledger — 東京, ist vorhanden, enthält aber kein cat. Die ursprünglichen UTF-8-Pfade und Zeilentexte bleiben erhalten.
Unsere begrenzte Wortregel ist genau definiert: Ein Token ist eine maximale zusammenhängende Folge von ASCII-Buchstaben A-Z oder a-z; ASCII-Großbuchstaben werden in Kleinbuchstaben umgewandelt. Ziffern, Unterstriche, Satzzeichen, Leerraum und jedes Nicht-ASCII-Byte trennen Tokens. CAT-blue_42 wird zu cat und blue; cat unterscheidet sich von catalog; 猫cat狗 enthält cat; café ergibt caf, nicht cafe. Unicode-Text zu erhalten heißt nicht, Wörter aller Sprachen zu verstehen. Wir implementieren keine mehrsprachige Wortsegmentierung.
Lies die vorbereitete Schnittstelle und deinen Ausgangscode:
cat search.hpp
cat engine.cpp
Document enthält id, den vollständigen relativen Pfad, und lines, einen Vektor ursprünglicher Zeilenstrings. Der vorbereitete Lader liest reguläre .txt-Dateien rekursiv und sortiert ihre Kennungen. Notizen sind UTF-8-Text mit LF-Zeilenenden. Leerzeichen und Unicode in Pfaden werden unterstützt; Tabulatoren oder Zeilenumbrüche in Pfaden, symbolische Links, NUL-Daten und beliebige Binärdateien liegen außerhalb des Formats. Unlesbare Eingaben erzeugen einen Fehler statt Teilergebnisse.
Index ist ein Alias für std::map<std::string, std::set<std::string>>. Eine Map ordnet jedem unterschiedlichen Wortschlüssel einen Wert zu: hier eine Menge von Dokumentkennungen. Eine Menge behält jede Kennung nur einmal. Drei Vorkommen von cat in einem Dokument ergeben deshalb eine Beziehung. Diese umgekehrte Suche von Wörtern zu Dokumenten heißt invertierter Index.
Dein Ausgangscode liefert einen leeren Index. provided.inc enthält die bereits funktionierende Abfragefunktion dieser Einheit. #include fügt beim Kompilieren eine Datei ein. Erhalte search.hpp, provided.inc, support.cpp, main.cpp, sample sowie jeden Pfad und Inhalt unter notes/reference/. Bearbeite engine.cpp; Hilfsfunktionen und gleichwertige Algorithmen sind erlaubt. Nur unter notes/practice/ darfst du Daten ändern, hinzufügen oder löschen. Dessen ursprünglicher Dateibestand ist keine Bewertungsvorgabe.
bash führt das vorbereitete Selbstprüfskript aus. index wählt das hier gelehrte Verhalten. Dieser erste Aufruf scheitert absichtlich mit FAIL exact whole-word postings retain complete document identities und einem Rückgabecode ungleich null. Das bedeutet, dass dein Index unvollständig ist, nicht dass die Umgebung defekt ist:
bash /opt/labex-note-search/check.sh index
Besuche jedes Dokument, jede Zeile und jedes zerlegte Wort. Ein bereichsbasiertes for durchläuft alle Elemente; const auto& liefert eine schreibgeschützte Referenz statt einer Kopie. index[word] greift auf die zum Wort gehörige Menge von Dokumentkennungen zu und erzeugt bei einem neuen Schlüssel eine leere Menge. .insert(doc.id) fügt die vollständige Kennung ein und ignoriert doppelte Beziehungen. Halte die Map außerhalb aller Schleifen, damit die Beziehungen aller Dokumente gesammelt werden.
Der nächste Befehl ersetzt nur engine.cpp. Ein Here-Dokument übergibt mehrere Zeilen an cat; > schreibt sie in die genannte Datei und ersetzt deren Inhalt. Der zitierte Begrenzer 'CPP' verhindert Shell-Erweiterungen im C++-Text. Schließe mit CPP allein auf einer Zeile ab. Behalte beide Include-Anweisungen, damit Deklarationen und vorbereitete Abfrageimplementierung verfügbar bleiben.
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) ist der vorbereitete ASCII-Parser. Extrahiere nicht nur den Basisnamen, höre nicht beim ersten Treffer auf und speichere keine Häufigkeit anstelle der Dokumentmenge.
Kompiliere dein abzulieferndes Programm. g++ ist der Compiler; -std=c++17 wählt die Sprachversion, -Wall -Wextra aktiviert hilfreiche Warnungen und -o findnotes benennt die Ausgabedatei. Die drei .cpp-Eingaben sind dein Suchkern, der vorbereitete Lader und Parser sowie die Befehlsschnittstelle. Eingebundene Dateien werden automatisch gelesen.
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
Ein erfolgreicher Build gibt normalerweise nichts aus. Lies bei einem Fehler den ersten Dateinamen und die Zeilennummer, korrigiere engine.cpp oder wiederhole dessen vollständigen Ersatz und kompiliere erneut. Ein fehlgeschlagener Build kann eine alte ausführbare Datei zurücklassen. Nur den Quelltext zu ändern aktualisiert sie nicht. Die Selbstprüfung testet sowohl deine Funktionen in der unverändert abgegebenen Fassung mit isolierten Testdaten als auch dein vorhandenes findnotes; sie baut diese ausführbare Datei nicht für dich neu.
./findnotes notes cat
Erwarte alle drei Dokumentkennungen und dieselben Originalzeilen wie im Beispiel. Eine andere reproduzierbare Dokumentreihenfolge ist zulässig; innerhalb jedes Dokuments müssen die Zeilennummern steigen und jede Zeile nur einmal erscheinen. Dieser Schritt bewertet den Index und Einwortabfragen. Das Kombinieren verschiedener Suchwörter ist hier vorbereitet und wird im nächsten Lab deine Aufgabe.
Aus den aktuellen Übungsnotizen neu aufbauen
In diesem Schritt änderst, ergänzt und löschst du Übungsdaten und erhältst dabei die Originale. Bleibe in Terminal unter /home/labex/project/note-search. Jeder Aufruf lädt die aktuellen Dateien und erstellt einen neuen Index im Arbeitsspeicher. Es gibt keine gespeicherte Indexdatei, keinen Aktualisierungsdienst und keinen zusätzlichen Neuaufbau-Befehl.
Vergleiche zuerst die Grenzen ganzer Wörter:
./findnotes notes catalog
Erwarte reference/catalog.txt und practice/旅行 notes.txt mit Zeilen, die catalog enthalten. Das sind keine zusätzlichen cat-Treffer. Auch ein unbekanntes Wort ist eine normale Suche:
./findnotes notes absent
Sie zeigt No matching documents. an und endet erfolgreich. Das unterscheidet sich von einer fehlerhaft geformten Eingabe, die die vorbereitete Schnittstelle ablehnt. Das nächste Lab erklärt diesen Unterschied.
Die Übungskopie ist bereits beschreibbar; Referenzoriginale sind schreibgeschützt. Einfache Anführungszeichen halten einen Pfad mit Leerzeichen als ein Argument zusammen und erhalten Unicode-Zeichen. printf schreibt Text; \n erzeugt einen Zeilenumbruch. > ersetzt die gesamte genannte Übungsdatei. Ersetze ihren Inhalt, sodass diese Kopie kein cat mehr enthält:
printf 'owl green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes cat
Jetzt passen nur die beiden Referenznotizen. Die Übungsdatei existiert weiterhin; ihr aktueller Inhalt passt nicht mehr. Füge eine weitere erlaubte Übungsnotiz hinzu:
printf 'CAT beside the window\nA new observation\n' > 'notes/practice/new notes.txt'
./findnotes notes cat
Wieder passen drei Dokumente, darunter practice/new notes.txt mit Zeile 1. Du hast nicht neu kompiliert: Datenänderungen benötigen nur einen erneuten Programmaufruf. Änderungen am C++-Quelltext erfordern eine Kompilierung.
rm löscht eine Datei. Sein einziges zitiertes Argument ist hier die neue Übungsnotiz, kein Original und kein gesamtes Verzeichnis:
rm 'notes/practice/new notes.txt'
./findnotes notes cat
Diese Kennung verschwindet; die zwei Referenztreffer bleiben bestehen. Lösche niemals Originale und ändere den Parser nicht, um Ergebnisse zu erzwingen. Bei einem falsch geschriebenen Pfad lies No such file or directory, liste mit find notes -type f die Pfade auf und verwende den richtigen. Zielst du auf ein schreibgeschütztes Original, lasse es unverändert und nutze eine Übungsdatei. Normale Pfadfehler erfordern kein Zurücksetzen der Umgebung.
Führe die Selbstprüfung erneut aus. Sie liest deine aktuellen Dateien und erstellt danach wegwerfbare Testdaten für weitere Eingaben. Deren Änderungen, Ergänzungen und Löschungen verändern deine Übungsdaten niemals. Isolierte Tests ungültiger Eingaben können erwartete Fehler neben PASS-Zeilen ausgeben; ein erfolgreicher Lauf endet mit CLI CHECKS PASSED.
bash /opt/labex-note-search/check.sh index
Auch die Prüfung über die Schaltfläche sollte erfolgreich sein. Wiederholte Prüfungen schreiben deinen Code nicht um, ersetzen nicht das Programm und setzen keine Übungsnotizen zurück. Scheitert sie nach einer Quelltextänderung, baue das tatsächliche findnotes neu und versuche es erneut. Temporäre Funktionstests allein beweisen nicht, dass deine ausführbare Datei aktuell ist.
Zusammenfassung
Du hast einen invertierten Index mit Mengen vollständiger Dokumentkennungen als Werten gebaut. Wiederholte Wörter duplizieren keine Dokumente, gleiche Basisnamen bleiben getrennt und echte Zeilennummern führen zum Originaltext. Ein erneuter Aufruf baut den Index transparent aus erlaubten Änderungen, Ergänzungen und Löschungen der Übungsdaten neu auf. Als Nächstes implementierst du die Schnittmenge, die mehrere Wörter im selben Dokument verlangt.
