Invertovaný index (zkouška C++ 15. 01. 2026)

Zadání nám nenechali, tak to aspoň nějak převyprávím

Invertovaný index je datová struktura sloužící k vyhledávání dokumentů podle výskytu klíčových slov. Odpovídá na otázku: V jakých dokumentech se vyskytuje <query>?

Příklad vstupních souborů:

Earth Venus Mars
Earth
Jupiter
Neptune Mars 

Earth Mercury
Venus Pluto

Neptune Saturn

Odpovídající invertovaný index:

Earth -> { 0, 1 }
Jupiter -> { 0 }
Mars -> { 0 }
Mercury -> { 1 }
Neptune -> { 0, 2 }
Pluto -> { 1 }
Saturn -> { 2 }
Venus -> { 0, 1 }

Budeme implementovat zjednodušenou verzi této struktury. Vstupní soubory se skládají z termů oddělených jednou nebo více mezerami. Term nesmí začínat znakem $ (důvod bude vysvětlen později). Jeden soubor může obsahovat více řádků a řádky mohou mít mezery na konci. Index si bude pamatovat, ve kterých souborech se každý term vyskytuje.

Pro identifikaci souborů zavedeme nový typ Identifier, který bude aliasem na size_t ze standardní knihovny. Identifikátory jsou přidělovány implicitně od 0. První zpracovaný soubor bude mít identifikátor 0, druhý 1 atd. V uvedeném příkladu se term Earth vyskytuje v souborech 0 a 1.

Index

Součástí řešení bude třída Index, která zpřístupní základní funkcionalitu. Bude umět:

  • přidat soubor do indexu, tj. soubor celý zpracovat a uložit si jeho termy, (metoda process)

  • vypsat index do výstupního proudu, (metoda dump)

  • vyhledat seznam souborů obsahujících daný term. (metoda search)

Při chybě při otevírání souboru musí funkce vyhodit výjimku typu std::string s textem
"Failed to open file <file>" (včetně zobáčků, bez uvozovek). Pokud se při zpracování narazí na chybný term (začínající na $), vyhodí se výjimka s textem "Invalid term <term>". Již zpracované termy v indexu zůstávají.

Výpis indexu do proudu (pomocí metody dump) bude probíhat tak, že pro každý term se vypíše jeden řádek ve tvaru:

term -> { 0, 1, 2, ... }

Nejprve se vypíše term, poté šipka -> a za ní seznam identifikátorů souborů v složených závorkách, oddělených čárkou a mezerou. Termy i seznamy identifikátorů souborů musí být seřazené vzestupně.

Pro reprezentaci termů použijeme std::string.

Třída Index musí obsahovat následující členské funkce:

  • void process(const std::string& file)

  • void dump(std::ostream& stream = std::cout) const

  • std::set<Identifier> search(const std::string& term) const

Pozor: V zadání bylo, že vnitřní věci musí zůstat skryté!

Query

Dále bude součástí řešení třída Query, která bude reprezentovat složitější dotazy typu:
Dokumenty, ve kterých se vyskytuje (Earth nebo Neptune), a zároveň ne Saturn.

Infixový zápis je obtížný na parsování, proto zvolíme postfixový zápis. Dotazy se budou skládat z termů, konjunkcí, disjunkcí a negací. Pro logické operace budeme používat následující klíčová slova (v tomto pořadí):
$and, $or, $not

Ostatní tokeny začínající znakem $ jsou zakázány. Vyhodí se výjimka popsaná níže.

Výrazy budou vypadat například takto:

Earth Neptune $or Saturn $not $and

Výsledek by byl:

0, 1

Třída Query načte výraz do stromové reprezentace. Listy budou termy, vnitřní vrcholy budou logické operace. Načítání postfixového výrazu proběhne takto:

  • Vytvoří se zásobník a výraz se zpracovává zleva doprava po jednotlivých tokenech (oddělených mezerou).

  • Pokud je token term, vloží se na zásobník jako nový list.

  • Pokud je token klíčové slovo pro binární operaci, odeberou se ze zásobníku dvě horní položky (nejprve pravý, poté levý operand) a na zásobník se vloží nový vrchol reprezentující zadanou operaci.

  • Pokud je token klíčové slovo pro unární operaci, odebere se ze zásobníku jedna položka a na zásobník se vloží vrchol reprezentující zadanou operaci.

Při zpracování dotazu mohou nastat tyto chyby (opět typu std::string):

  • Pokud na zásobníku není dostatek operandů, vyhodí se výjimka "Missing operands".

  • Pokud se narazí na neznámou operaci, vyhodí se výjimka "Unknown operation <operation>".

  • Po zpracování celého výrazu musí na zásobníku zůstat právě jedna položka - kořen výrazu. Pokud není na zásobníku žádná položka, vyhodí se výjimka "Empty condition". Pokud je na zásobníku více než jedna položka, vyhodí se výjimka "Invalid condition".

Výraz má být do stromové struktury převeden pouze jednou, aby bylo možné stejný dotaz efektivně vyhodnocovat nad různými indexy. Strom výrazu by měl využívat polymorfismus a být schopen se vyhodnotit nad libovolnou instancí třídy Index. Třída Query bude držet pouze odkaz na kořen tohoto stromu.

Třída Query musí obsahovat následující členské funkce:

  • konstruktor Query(const std::string& expression)

  • std::set<Identifier> evaluate(const Index& index) const

    • Pro evaluaci se má využít metod na vrcholech, nemá se implementovat ručně nějaký rekurzivní průchod stromu.

Implementační detaily

Do recodexu odevzdávejte Index.h, který zpřístupní třídy Index a Query. Můžete odevzdávat i další .h a .cpp soubory, ale neodevzdávejte vaší funkci main. Test includne pouze Index.h a bude očekávat, že může využívat celé veřejné rozhraní tříd.

Mimo zadání nám bylo řečeno, že požadují abychom využívali konstrukty moderního C++, aby to nevypadalo jako, že programujeme v C. (Na otázku "Jak moc moderní?" byla odpověď, že aspoň na úrovni C++ 11, a že samozřejmě počítají s pochopením jen v rámci toho co bylo probrané na přednášce.)

Řešení

Jelikož zadání není 100% stejné s tím co bylo zadané, tak přidávám řešení, které prošlo testy v recodexu.

Řešení Šimon Kala

  • Tohle není vzorové řešení, je to prostě to co jsem odevzdal.

  • Hodnocení: 55/60, neefektivní vyhledávání (mám tam contains a pak indexuji), zbytečná položka (zjednodušil jsem si předávání parsing_stacku v Query tím že jsem to dal jako položku)

  • Ke stažení zde