Zadání soutěžní úlohy

Kategorie žáci a mládež

Soutěž dětí a mládeže v programování – 18. ročník

Krajské kolo 2003/2004

16. a 17. dubna 2004

Za úlohu můžete získat maximálně 100 bodů, z nichž 60 je vyhrazeno na ohodnocení funkčnosti programu a jeho shody se zadáním, 30 bodů na efektivitu a deset bodů na dokumentaci a přehlednost zdrojového kódu.

Na řešení úlohy máte 4 hodiny čistého času.

Před zahájením soutěže vám pořadatel oznámí, kde najdete testovací soubory pro úlohu.

Vyhledávání ve webových stránkách

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.

Stahování stránek

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):

http

Stránky dostupné pomocí protokolu HTTP. Příklad URL:

http://www.stv.cz/soutez/sdmp-v.html
ftp

Stránky dostupné pomocí protokolu FTP. Příklad URL:

ftp://pub.example.com/download/doc/faq.htm
file

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.

Výběr slov k prohledávání

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 &nbsp;, znak ‚A‘ jako &#65; 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&nbsp;<a href="praha.html"
title="Historie stare Prahy">prazskem podhradi</a>.</p> 

budou nalezena následující slova:

Karelnejspisestare
IVnarodilPrahy
1316vprazskem
seHistoriepodhradi

Počáteční a koncové tagy elementu přitom slovo nepřerušují, jak ukazuje následující příklad.

Příklad 6. Tagy nepřerušují slovo

V následujícím HTML kódu

C<sub>2</sub>H<sub>5</sub>OH

bude nalezeno jedno slovo C2H5OH.

Vyhodnocování dotazu

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/.