Soutěž dětí a mládeže v programování – 18. ročník
Krajské kolo 2003/2004
Napište program, který umožní uživateli prohledávání sady webových stránek. Sada stránek je určena adresou URL první stránky a maximálním počtem odkazů, pomocí kterých se z ní jde dostat na další stránky v sadě. Tyto údaje (počáteční URL a maximální hloubku odkazů) si může uživatel v programu volit.
Program bude nabízet následující funkce:
Vygenerování seznamu stránek obsažených v sadě – do textového souboru se zvoleným názvem se zapíší adresy URL všech stránek v sadě. Každé URL na samostatnou řádku.
Vygenerování seznamu slov a stránek, kde se slova vyskytují – do souboru se zvoleným názvem se uloží stránka v jazyce HTML, která bude obsahovat seřazený seznam všech slov vyskytujících se na stránkách v sadě. U každého slova budou hypertextové odkazy na všechny stránky, kde se slovo vyskytlo.
Prohledávání sady stránek – po zadání slova program vrátí seznam stránek, které toto slovo obsahují. Výsledek dotazu půjde uložit do souboru v podobě stránky HTML.
Seřazení výsledků dotazu podle relevance – výsledky dotazu by měly být seřazeny podle důležitosti. Navrhněte vlastní metodu pro určení pořadí stránek ve výsledku.
První stránka pro stahování a další odkazy obsažené ve stránkách jsou zapsány v podobě adres URL. Program by měl podporovat práci se stránkami, jež jsou dostupné pomocí následujících druhů adres (tzv. URL schémat):
Stránky dostupné pomocí protokolu HTTP. Příklad URL:
http://www.stv.cz/soutez/sdmp-v.html
Stránky dostupné pomocí protokolu FTP. Příklad URL:
ftp://pub.example.com/download/doc/faq.htm
Stránky uložené na lokálním disku. Příklad URL:
file:///c:/data/stranky/index.html
Toto URL odpovídá souboru index.html, který je uložen v adresáři data\stranky na disku c:.
Program nemusí podporovat všechny tři způsoby přístupu k dokumentům, ale čím více jich bude podporovat, tím více bodů dostanete.
Stahování vždy začíná na zadané adrese. Na ní bude umístěna stránka v jazyce HTML. Z této stránky vyberete všechny odkazy na další soubory (stránky), které mají příponu .htm nebo .html (nezáleží přitom na velikosti písmen). Stáhnete stránky, které jsou dostupné na vybraných odkazech. Celý proces nalezení odkazů a stažení odkazovaných stránek se pak pro stažené stránky opakuje tak dlouho, dokud existují nějaké nezpracované stránky a dokud vzdálenost stahovaných stránek od první stránky nepřesáhne zadaný maximální počet odkazů.
Jako odkazy ve stránce chápejte jen URL uvedená v atributu href elementu a.
Příklad 1. Ukázka různých zápisů odkazu
<a href="stranka.html">odkaz</a> <A HREF='stranka.html'>odkaz</A> <A href="stranka.html">odkaz</A> <a HREF="stranka.html">odkaz</A> <a Href=stranka.html>odkaz</a> <a title="Odkaz někam jinam" href="stranka.html">odkaz</a>
Nezapomeňte, že odkaz ve stránce může být zapsán i jako relativní URL, které je potřeba před zpracováním převést na absolutní URL tím, že se složí se základním URL stránky.
Příklad 2. Skládání relativních URL
Předpokládejme, že stránka dostupná na adrese http://www.stv.cz/soutez/sdmp-v.html obsahuje následující odkazy:
<a href="kontakt.html">Kontakty</a> <a href="../index.html">Hlavní stránka</a> <a href="kraje/zadani.html">Zadání krajských kol</a> <a href="http://www.example.com/katalog/dokumenty.html">Seznam dokumentů</a>
Po složení ze základním URL stránky tak dostaneme následující absolutní URL identifikující dokumenty k dalšímu stažení:
http://www.stv.cz/soutez/kontakt.html http://www.stv.cz/index.html http://www.stv.cz/soutez/kraje/zadani.html http://www.example.com/katalog/dokumenty.html
Změnu základního URL stránky pomocí elementu base nemusíte ve vašem programu ošetřovat.
URL adresa může na konci obsahovat znak ‚#‘ následovaný návěstím. Takový odkaz ukazuje na konkrétní místo stránky. Pro účely vaší aplikace znak ‚#‘ a vše za ním v URL ignorujte.
Na každé stránce je pro potřeby dalšího vyhledávání nutné vybrat všechna slova. Za slovo se považuje souvislý úsek textu, který obsahuje pouze malá nebo velká písmena anglické abecedy (A-Z) a číslice (0-9). Slova se hledají pouze v textovém obsahu elementů a v atributech alt a title.
Příklad 3. Textový obsah elementu
Textový obsah elementu je tvořen znaky mezi počátečním a koncovým tagem. Například následující kód:
<p>Vyhledávání není úplně jednoduchá úloha.</p>
Obsahuje počáteční tag <p>, koncový tag </p> a mezi nimi je textový obsah elementu – „Vyhledávání není úplně jednoduchá úloha.“.
Příklad 4. Atributy alt a title
Atributy se zapisují jako součást počátečního tagu. Např.:
<img src="foto.jpg" alt="Fotografie Jana Nováka"> <h1 title="Úvodní část textu">Úvod</h1>
V jazyce HTML se pro zápis znaků mohou používat odkazy na znakové entity. Například pevnou mezeru jde zapsat jako , znak ‚A‘ jako A apod. Pro účely vaší aplikace můžete tento zápis znaků ignorovat. Odkaz na entitu vždy začíná znakem ‚&‘ a končí znakem ‚;‘.
Příklad 5. Jak se pozná slovo
V následujícím HTML kódu
<p>Karel IV. (*1316) se nejspise narodil v <a href="praha.html" title="Historie stare Prahy">prazskem podhradi</a>.</p>
budou nalezena následující slova:
Karel | nejspise | stare |
IV | narodil | Prahy |
1316 | v | prazskem |
se | Historie | podhradi |
Počáteční a koncové tagy elementu přitom slovo nepřerušují, jak ukazuje následující příklad.
Jako dotaz lze zadat jedno slovo. Výsledkem dotazu jsou všechny stránky sady, které toto slovo obsahují. Při hledání se přitom ignoruje velikost písmen.
Na svém počítači máte nahraná ukázková data a jednoduchý testovací HTTP a FTP server, na kterém můžete testovat vaši aplikaci. Testovací server se spouští příkazem WWWftpServer.exe. Dokumenty uložené v podadresáři ftproot jsou dostupné na adrese ftp://localhost/, resp. ftp://127.0.0.1/. Dokumenty uložené v podadresáři wwwroot jsou dostupné na adrese http://localhost/, resp. http://127.0.0.1/.
Při hodnocení se v maximální možné míře držte pokynů, jen tak lze zajistit srovnatelnost výsledků mezi kraji.
funkčnost | 1 bod | jde zadat adresu, kde má začít stahování |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #1 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #2 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #3 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #4 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #5 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #6 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #7 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #8 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #9 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #10 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #11 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #12 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #13 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #14 | |
1 bod | správně vygenerovaný textový soubor s adresami stažených stránek pro ukázková data #15 | |
1 bod | při ukládání souboru lze zvolit jeho název | |
3 body | vygenerovaný seznam slov v HTML pro ukázková data #1 | |
1 bod | seznam slov lze uložit do souboru a při ukládání je možné zvolit název souboru | |
1 body | seznam slov obsahuje odkazy na HTML stránky, kde se slova vyskytují | |
2 body | seznam je setříděný | |
3 body | v seznamu se nevyskytují duplicitní data | |
1 bod | jde zadat dotaz | |
1 bod | dotaz jde editovat | |
1 bod | historie dříve zadaných dotazů | |
2 body | zobrazení alespoň nějakého výsledku dotazu | |
3 body | výsledek jde uložit do souboru jako HTML stránka | |
3 body | výsledek dotazu obsahuje názvy stránek (obsah elementu title) | |
2 body | přímo z programu lze vyvolat prohlížení nalezené stránky (např. spuštěním prohlížeče, zabudováním komponenty prohlížeče do aplikace) | |
2 body | Slovo „titulni“ je v kolekci #5 nalezeno na stránkách kosek.cz/xml/db/dsssl.html, kosek.cz/xml/db/index.html, kosek.cz/xml/db/xsl.html | |
2 body | Slovo „bibliograficky“ je v kolekci #5 nalezeno na stránce kosek.cz/clanky/index.html (vyskytuje se pouze v atributu) | |
2 body | Slovo „anglictina“ je v kolekci #5 nalezeno na stránkách kosek.cz/clanky/swn-xml/ar01s02.html, kosek.cz/clanky/xmleditory/xmetal.html a kosek.cz/php/faq.html | |
2 body | Slovo „answer“ je v kolekci #5 nalezeno na stránce kosek.cz/xml/db/ukazky.html (nesmí být nalezena stránka kosek.cz/php/faq.html, kde je slovo pouze v atributu, který není určen k prohledávání) | |
3 body | Slovo „jadetexu“ je v kolekci #5 nalezeno na stránkách kosek.cz/xml/db/vystupy.html a kosek.cz/clanky/tex-xml/jadetex.html (testuje, zda je ignorována velikost písmen) | |
2 body | Slovo „vstupgama“ je v kolekci #5 nalezeno na stránce kosek.cz/clanky/cw/png.html (elementy nepřerušují slovo) | |
2 body | Slovo „14h2“ je v kolekci #5 nalezeno na stránce kosek.cz/clanky/egavga/chap04.html (elementy nepřerušují slovo a slovo se může skládat z číslic) | |
4 body | výsledky jsou seřazeny podle důležitosti (relevance) | |
1 bod | relevance je zobrazena jako ukazatel u každé stránky výsledku | |
efektivita | 5 bodů | pro parsování HTML kódu se používá nějaká existující komponenta (např. MSIE) |
5 bodů | parsování HTML je proudové, celý dokument není najednou načten do paměti např. v podobě DOM stromu nebo dlouhého řetězce | |
5 bodů | při hledání odkazů nejsou do seznamu stránek ke stažení vkládány duplicitní záznamy | |
10 bodů | pro prohledávání stránek je sestaven index (např. invertovaný seznam, B-strom, hashovací tabulka apod.) | |
5 bodů | pro skládání relativních URL se základním URL se používá metoda/funkce použitého programovacího jazyka | |
dokumentace | 4 body | komentáře nebo vysvětlení činnosti programu |
2 body | vysvětlení metody použité pro stanovení relevance dokumentů | |
2 body | přehledný zdrojový text | |
2 body | výstižné názvy proměnných |
Při testování dotazů používejte sadu stránek #5. Pokud není implementována podpora protokolu file, použijte stejnou sadu stránek #10 nebo #15 dostupnou pomocí protokolů HTTP a FTP.
Následující tabulka obsahuje informace o počtu stránek v jednotlivých testovacích sadách.
Tabulka 1. Testovací data
# | Počáteční URL | Maximální hloubka odkazů | Očekávaný výsledek |
---|---|---|---|
#1 | file:///cesta/test/test.htm | 2 | 2 stránky: test.htm a test2.htm |
#2 | file:///cesta/kosek.cz/index.html | 1 | 36 stránek, jejich seznam je v souboru 2.txt |
#3 | file:///cesta/kosek.cz/index.html | 2 | 330 stránek, jejich seznam je v souboru 3.txt |
#4 | file:///cesta/kosek.cz/index.html | 3 | 413 stránek, jejich seznam je v souboru 4.txt |
#5 | file:///cesta/kosek.cz/index.html | 10 | 624 stránek, jejich seznam je v souboru 5.txt |
#6 | http://localhost/test/test.htm | 2 | 2 stránky: test.htm a test2.htm |
#7 | http://127.0.0.1/kosek.cz/index.html | 1 | 36 stránek, jejich seznam je v souboru 7.txt |
#8 | http://localhost/kosek.cz/index.html | 2 | 330 stránek, jejich seznam je v souboru 8.txt |
#9 | http://localhost/kosek.cz/index.html | 3 | 413 stránek, jejich seznam je v souboru 9.txt |
#10 | http://localhost/kosek.cz/index.html | 4 | 624 stránek, jejich seznam je v souboru 10.txt |
#11 | ftp://localhost/test/test.htm | 2 | 2 stránky: test.htm a test2.htm |
#12 | ftp://127.0.0.1/kosek.cz/index.html | 1 | 36 stránek, jejich seznam je v souboru 12.txt |
#13 | ftp://127.0.0.1/kosek.cz/index.html | 2 | 330 stránek, jejich seznam je v souboru 13.txt |
#14 | ftp://localhost/kosek.cz/index.html | 3 | 413 stránek, jejich seznam je v souboru 14.txt |
#15 | ftp://localhost/kosek.cz/index.html | 4 | 624 stránek, jejich seznam je v souboru 15.txt |