1. úkol: Fulltextové vyhledávání - deadline 2.12.2018 23:59

Základní idea: Ze souboru načteme databázi článků a z druhého souboru či standardního vstupu seznam dotazů. Pro každý dotaz zobrazíme na standardním výstupu seznam článků, ve kterých se nacházejí všechna slova z dotazu, včetně úryvku článku obsahující první hledané slovo.

Vstup

• Program očekává 1-2 argumenty: fulltext soubor_clanky [soubor_dotazy]
• Textový soubor soubor_clanky obsahuje seznam článků, které se mají na začátku programu načíst. Data každého článku jsou zapsána na 3 po sobě jdoucích řádcích. Osamocený prázdný řádek značí, že seznam článků je u konce. Ukázku souboru si můžete stáhnout zde. V programu můžete předpokládat, že pokud tento vstupní soubor existuje a je možné z něj číst, je ve správném formátu (tedy např., že soubor obsahuje 3k + 1 odřádkování). Nemusíte se tedy starat o EOF, konec souboru lze poznat z prázdného řádku. Jednotlivé 3 řádky každého článku obsahují následující údaje:
  1. Identifikátor článku: Posloupnost velkých písmen a čísel o celkové délce maximálně 10. Každý článek má unikátní identifikátor a články jsou dle tohoto identifikátoru vzestupně seřazeny.
  2. Název článku: Text dlouhý maximálně 60 znaků, obsahovat může pouze znaky z dolní ASCII znakové sady (0-127) kromě CR a LF.
  3. Text článku: Text neomezené délky, obsahovat může pouze znaky z dolní ASCII znakové sady (0-127) kromě CR a LF.
• Pokud je zadaný argument soubor_dotazy, dotazy se načítají z daného souboru, v opačném případě ze standardního vstupu (konzole). Každý dotaz je na samostatném řádku, prázdný řádek opět značí ukončení vstupu. Nemusíte tedy ošetřovat EOF. Každý dotaz může opět obsahovat pouze znaky z dolní ASCII znakové sady (0-127) kromě CR a LF. Ukázku vstupu si můžete stáhnout zde.

Zpracování

• Definice: Slovo je nejdelší (tj. zleva a zprava ohraničená znaky, co toto nesplňují) posloupnost malých a velkých písmen. Např. v textu Lorem Ipsum dolor42sit amet, consecteurer! Alibiscit elit se nacházejí slova Lorem, Ipsum, dolor, sit, amet, consecteurer, Alibiscit a elit. Vzhledem k omezení znakové sady se v žádném slově nemohou vyskytovat písmena s diakritikou.
• Všechny články je potřeba načíst a uložit do nějaké datové struktury (kontejneru).
• Kromě databáze článků je nutné vytvořit i invertovaný index, tedy mapování mezi slovy a dokumenty, ve kterých se vyskytují. Pro každé slovo (které je alespoň v textu jednoho článku) se zde bude nacházet seznam článků, ve kterých se vyskytuje, vzestupně seřazený dle identifikátoru článku. Kromě odkazu na článek (ten můžete vyjádřit různě: identifikátorem, pozicí v seznamu, referencí,... v žádném případě sem však celý článek nekopírujte) musí každá položka obsahovat i pozici prvního výskytu tohoto slova v tomto článku. Naším cílem je umožnit vyhledávání nezávislé na velikosti písmen, každé slovo tedy musí být před uložením do indexu přeměněno do "kanonické" podoby (t.j. např. všechna písmena malá).
• Každý dotaz se vyhodnocuje následujícím způsobem:
  1. Vyčtou se z něj všechna slova. Pokud dotaz neobsahuje žádné slovo (např. 1,2,3,...42!), vracíme prázdný výsledek.
  2. Z invertovaného indexu načteme seznamy odkazů na články obsahující slova z dotazu. Pokud se nějaké slovo z dotazu v indexu nenachází, znamená to, že se nenachází v žádném článku, vracíme tedy prázdný výsledek.
  3. Získali jsme množinu seřazených seznamů a chceme zjistit jejich průnik. Maximální bodové ohodnocení této podúlohy (2 body, viz níže) bude za řešení, které projde každý seznam pouze jednou. Nabízí se synchronizované procházení všech seznamů najednou - ve chvíli, kdy ve všech seznamech dojdeme ke stejné hodnotě, předáme příslušný článek na výstup a posuneme se dál. Efektivita ostatních řešení bude posuzována individuálně.

Výstup

• Pokud jakýkoliv ze zadaných vstupních souborů nelze načíst, ukončete program bez výstupu.
• Ukázku výstupu najdete zde. Vypisujeme výsledky všech dotazů, za seznamem výsledků každého dotazu následuje volná řádka. Pokud dotaz vrátil prázdný výsledek, vypíšeme řádek "No results" (bez uvozovek). V opačném případě vypisujeme každý výsledek následovně (výsledky řaďte vzestupně dle identifikátoru článku):
  1. řádek výsledku má podobu [identifikator] nazev.
  2. řádek výsledku obsahuje úryvek textu, který začíná místem 1. výskytu 1. slova zadaného v dotazu, má délku 75 znaků (méně, pokud by to přesáhlo konec článku) a je zakončen...

Hodnocení

• Řešení odevzdávejte do ReCodExu, který automaticky vyhodnocuje následující kritéria (počet pokusů o odevzdání není omezen):
  • 8 bodů - Funkcionalita: Program musí fungovat správně na ukázkovém vstupu i na několika dalších neveřejných vstupech.
  • 2 body - Stabilita: Program musí ošetřit špatný počet argumentů, neexistující soubory a nesmí spadnout na obskurních dotazech (jako např. zmíněný 1,2,3,...42!). Naopak formáty obou dvou vstupů ověřovat nemusí, může předpokládat, že řádkování je u nich správně (konce řádků testovacích souborů v ReCodExu jsou ve správném Linuxovém formátu LF, čili znak CR by se při čtení řádků neměl navíc objevovat).
• Po uplynutí deadline bude provedeno ruční hodnocení zbývajících kritétií u řešení, která projdou úspěšně alespoň veřejně dostupným testem. Kritéria:
  • 2 body - Efektivita průniku seřazených seznamů: popsáno výše.
  • 3 body - Štábní kultura: Není potřeba tolik řešit zapouzdření tříd (může se hodit mít pomocné třídy s public datovými položkami), ale kód by měl být přehledný a funkcionalita alespoň rámcově rozdělená. Vlastní vyhledávací "engine", tedy databáze a dotazování nad ní, by měl být umístěn v samostatné třídě/třídách s vhodně navrženým rozhraním. Příliš dlouhé metody a funkce je lepší rozdělit na samostatné celky. Dále je lepší nekopírovat stejnou logiku na více míst, ale zabalit ji do funkce/třídy a tu z těchto míst používat (pokud to tam dává smysl).
• 1. veřejný test základní funkcionality v ReCodExu (sám o sobě za 3 body):
  • Články
  • Dotazy
  • Výstup
• Za každý započatý týden zpoždění je penále -5 bodů.