1. úkol: Fulltextové vyhledávání - deadline 20.11.2017 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) by měla 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 by tedy mělo 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. Za efektivní řešení se považuje takové, které má časovou složitost O(n), kde n je součet délek nalezených seznamů. 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. Méně efektivní řešení jsou také přípustná, ale nebude za ně plný počet bodů, viz část Hodnocení.

Výstup

• 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. V opačném případě vypisujeme každý výsledek následovně:
  1. řádek výsledku má podobu [identifikator] nazev.
  2. řádek výsledku by měl obsahovat ú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í

• Na odevzdání máte jen jeden pokus, není tedy možné úkol vylepšovat na základě připomínek.
• Části zadání výše, které nejsou psané kurzívou, je nutné naprogramovat, abyste z úkolu nějaké body dostali. Tato základní funkčnost bude testována těmito daty:
  • Články
  • Dotazy
  • Očekávaný výstup: rozlišující malá a velká písmena / nerozlišující malá a velká písmena
• Bodování je následně rozdělené na několik kategorií:
  • Funkcionalita: za základní verzi, kde se při vyhledávání rozlišuje velikost písmen a nejsou vypisovány úryvky textu, jsou 4 body. Za nerozlišování velikosti písmen je další 1 bod a za výpis úryvků textu další 2 body.
  • Stabilita: Maximálně 3 body. 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ě.
  • Efektivita: Zatím neznáme v C++ příliš mnoho prostředků k zajištění efektivity (zabránění zbytečnému kopírování apod.), omezíme se tedy pouze na hodnocení jedné konkrétní věci - zjišťování průniku několika seznamů odkazů na články během vyhodnocování dotazů. Za algoritmus, který pracuje v lineárním čase vůči součtu jejich délek, dostanete 2 body, za méně efektivní algoritmus 1 nebo žádný bod.
  • Štábní kultura: Maximálně 3 body. 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).
• Za každý započatý týden zpoždění je penále -5 bodů.
• Při odevzdání úkolu vždy popište, zda jste naimplementovali verzi s rozlišováním velikosti písmen nebo bez. Dále stručně popište, jak je logika rozdělená mezi jednotlivé kusy kódu. Pokud jste udělali nějaké zajímavé optimalizace (efektivity, přehlednosti apod.), napište to také. Pokud uznám, že jsou dostatečně významné a užitečné, mohu vám za ně odpustit některé jiné prohřešky.

Poznámky

• Pokud budete vyvíjet na Linuxu, upravte si konce řádků přiložených testovacích souborů na znak LF (ve Windows je standardně CR LF). Pokud to neuděláte, můžete mít problém se správným načítáním řádek. O naprogramování v Linuxu mi napište i do komentáře, udejte i konkrétní distribuci, pod kterou jste to kompilovali, kompilátor (většinou GCC) a jeho verzi.