Univerzita Karlova v Praze Matematicko-fyzikální fakulta

DIPLOMOVÁ PRÁCE

René Mihula

Indexace HTML dokumentů Katedra softwarového inženýrství Vedoucí diplomové práce: RNDr. Michal Kopecký, Ph.D. Studijní program: Informatika

Na tomto místě bych rád poděkoval vedoucímu své diplomové práce RNDr. Michalovi Kopeckému, Ph.D. za odborné rady a podněty, které významným způsobem přispěly k vytvoření a dokončení této práce. Dále bych chtěl poděkovat RNDr. Leovi Galambošovi, Ph.D. za odborné konzultace a zpřístupnění systému Egothor.

Prohlašuji, že jsem svou diplomovou práci napsal samostatně a výhradně s použitím citovaných pramenů. Souhlasím se zapůjčováním práce. V Praze dne 20. dubna 2005 René Mihula

Obsah 1 Úvod 1.1 Cíl práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Členění textu . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Teorie 2.1 Jazyk HTML . . . . . . . . . . . . . . . . 2.1.1 Sledované HTML značky . . . . . . 2.1.2 Ohraničení dokumentu . . . . . . . 2.1.3 Záhlaví dokumentu . . . . . . . . . 2.1.4 Tělo dokumentu . . . . . . . . . . . 2.1.5 Základní formátování . . . . . . . . 2.1.6 Strukturování textu . . . . . . . . . 2.1.7 Hypertextové odkazy . . . . . . . . 2.1.8 Seznamy . . . . . . . . . . . . . . . 2.1.9 Tabulky . . . . . . . . . . . . . . . 2.1.10 Formuláře . . . . . . . . . . . . . . 2.2 Dokumentografické informační systémy . . 2.3 Architektura DIS . . . . . . . . . . . . . . 2.3.1 Indexace . . . . . . . . . . . . . . . 2.3.2 Řešení vyhledávacího problému . . 2.4 Modely DIS . . . . . . . . . . . . . . . . . 2.5 Boolský model . . . . . . . . . . . . . . . . 2.5.1 Reprezentace dokumentu a dotazu 2.5.2 Proximitní operátory . . . . . . . . 2.5.3 Zástupné znaky . . . . . . . . . . . 2.5.4 Kritika modelu . . . . . . . . . . . 2.6 Vektorový model . . . . . . . . . . . . . . 2.6.1 Reprezentace dokumentu . . . . . . 2.6.2 Reprezentace dotazu . . . . . . . . 2.6.3 Koeficient podobnosti . . . . . . . 2.6.4 Negace . . . . . . . . . . . . . . . . 2.6.5 Řízení velikosti výstupu . . . . . . 2.6.6 Zpětná vazba . . . . . . . . . . . . 2.6.7 Indexace . . . . . . . . . . . . . . . 2.7 Určování vah . . . . . . . . . . . . . . . . 2.7.1 Inverzní frekvence termu . . . . . . 2.7.2 Poměr signál-šum . . . . . . . . . . 2.7.3 Další rozdělení . . . . . . . . . . .

i

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 2 3 3 3 6 6 10 12 12 14 15 16 18 19 20 21 22 23 24 24 25 25 25 26 26 27 27 28 28 28 29 29 30 30 31

3 Přehled existujících přístupů 3.1 Strukturální analýza . . . . . . . . . 3.1.1 Základní strukturální analýza 3.1.2 Rozšířená strukturální analýza 3.2 Analýza odkazů . . . . . . . . . . . . 3.2.1 Definice grafů . . . . . . . . . 3.2.2 Ohodnocení dokumentů . . . 3.2.3 Algoritmus PageRank . . . . 3.2.4 Algoritmus HITS . . . . . . . 3.2.5 Systém ARC . . . . . . . . . 3.2.6 Kategorizace dokumentů . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

4 Návrh algoritmu 4.1 Schéma indexace . . . . . . . . . . . . . . 4.1.1 Fáze přípravy dokumentu . . . . . 4.1.2 Fáze výpočtu a sjednocení vah . . . 4.2 Algoritmus indexace . . . . . . . . . . . . 4.2.1 Definice množin . . . . . . . . . . . 4.2.2 Dokument jako graf . . . . . . . . . 4.2.3 Výpočet vah – naivní přístup . . . 4.2.4 Výpočet vah – adaptivní přístup . 4.2.5 Normalizace ohodnocení . . . . . . 4.2.6 Sloučení ohodnocení . . . . . . . . 4.2.7 Analýza vizualizace . . . . . . . . . 4.2.8 Kompletní algoritmus indexace . . 4.2.9 Zhodnocení navržené indexace . . . 4.3 Schéma dotazování . . . . . . . . . . . . . 4.4 Algoritmus dotazování . . . . . . . . . . . 4.4.1 Reprezentace dotazu . . . . . . . . 4.4.2 Vyhovující dokumenty . . . . . . . 4.4.3 Výsledek dotazu . . . . . . . . . . 4.4.4 Kompletní algoritmus dotazování . 4.5 Distribuce indexu . . . . . . . . . . . . . . 4.5.1 Clustery . . . . . . . . . . . . . . . 4.5.2 Distribuované vyhledávací systémy 4.5.3 Návrh modelu . . . . . . . . . . . . 4.5.4 Dotazování v navrhovaném systému

ii

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

32 32 32 33 36 36 36 37 37 38 39

. . . . . . . . . . . . . . . . . . . . . . . .

41 41 41 43 44 44 45 45 46 50 52 55 65 69 70 71 71 72 72 73 75 75 75 76 78

5 Ukázková implementace 5.1 Použité nástroje . . . . 5.2 Architektura systému . 5.3 Konfigurace systému . 5.4 Popis ovládání . . . . . 5.5 Testy . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

81 81 81 82 83 83

6 Závěr

85

Literatura

86

A Stoplist

88

B Obsah CD-ROM

89

iii

Seznam obrázků 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Příklad HTML dokumentu . . . . . . . . . . . . . . . . . Indexace dokumentu . . . . . . . . . . . . . . . . . . . . Normalizace vektorů dokumentů . . . . . . . . . . . . . . Textově shodné dokumenty s různými styly . . . . . . . . Schéma indexace . . . . . . . . . . . . . . . . . . . . . . Příklad parametrizace pro adaptivní přístup . . . . . . . Příklad parametrizace pro adaptivní přístup doplněný o vinná pravidla . . . . . . . . . . . . . . . . . . . . . . . . Příklad parametrizace pro nestandardní ohodnocení . . . Příklad parametrizace pro statické ohodnocení . . . . . . Sledované parametry písma . . . . . . . . . . . . . . . . Příklad parametrizace implicitní vizualizace . . . . . . . Příklad parametrizace explicitní vizualizace . . . . . . . . Schéma dotazování . . . . . . . . . . . . . . . . . . . . . Příklad clusterů . . . . . . . . . . . . . . . . . . . . . . . Schéma modelu distribuce . . . . . . . . . . . . . . . . . Schéma architektury systému Egothor . . . . . . . . . . .

iv

. . . . . . . . . . . . po. . . . . . . . . . . . . . . . . . . .

. . . . . .

4 21 28 35 42 47

. . . . . . . . . .

48 48 50 56 59 59 70 76 79 82

Seznam tabulek 1 2 3 4 5 6 7

Značky frázových prvků (idiomy) . . . . Značky pro změnu písma . . . . . . . . . Operátory tezauru . . . . . . . . . . . . Logické operátory . . . . . . . . . . . . . Proximitní operátory . . . . . . . . . . . Výskyty sledovaných termů ve vybraných Stoplist pro češtinu (DESAM) . . . . . .

v

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . dokumentech . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

12 13 23 24 25 84 88

Seznam algoritmů 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Výpočet skóre (HITS) . . . . . . . . . . . . . . . Výpočet vah pro naivní přístup . . . . . . . . . . Výpočet vah pro adaptivní přístup . . . . . . . . Normalizace ohodnocení pro adaptivní přístup . . Sloučení ohodnocení pro adaptivní přístup . . . . Výpočet funkce style . . . . . . . . . . . . . . . . Výpočet funkce apply . . . . . . . . . . . . . . . . Výpočet vizualizace . . . . . . . . . . . . . . . . . Normalizace ohodnocení pro analýzu vizualizace . Sloučení ohodnocení pro analýzu vizualizace . . . Kompletní algoritmus indexace . . . . . . . . . . Výpočet množiny dokumentů vyhovujících dotazu Proces řízení výstupu . . . . . . . . . . . . . . . . Kompletní algoritmus dotazování . . . . . . . . .

vi

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

38 45 49 51 53 60 60 62 64 65 66 72 73 74

Název práce: Indexování HTML dokumentů Autor: René Mihula Katedra: Katedra softwarového inženýrství Vedoucí diplomové práce: RNDr. Michal Kopecký, Ph.D. e-mail vedoucího: [email protected] Abstrakt: V současné době patří jazyk HTML mezi nejpoužívanější jazyky pro elektronické uchovávání dat. S tímto faktem ovšem vyvstává i nezbytný požadavek na efektivní vyhledávání informací v HTML dokumentech uložených. Touto oblastí se zabývají tzv. dokumentografické informační systémy. Tato práce se zabývá návrhem algoritmu indexace a vyhledávání v rozsáhlé databázi HTML dokumentů s využitím formátovacích značek. Na základě jejich významu je totiž možné určit váhy jednotlivých termů v dokumentu přesněji. Myšlenka algoritmu je založena na předpokladu, že autor textu důležité informace odliší právě pomocí HTML značek. Navržené řešení navíc podporuje distribuci indexu na více počítačů. Součástí práce je také ukázková implementace navrženého algoritmu. Klíčová slova: indexace, HTML, vektorový model, strukturální analýza Title: Indexing of HTML documents Author: René Mihula Department: Department of software engineering Supervisor: RNDr. Michal Kopecký, Ph.D. Supervisor’s e-mail address: [email protected] Abstract: Recently HTML is one of the most exploited languages for electronic data storage. However, this tendency brings an essential demand for effective retrieval of information stored in HTML documents. Systems that deal with this area are called information retrieval systems. This thesis proposes an algorithm of indexation and retrieval of information stored in a large database of HTML documents, which is based on exploitation of formatting tags. On the basis of their meaning and significance the weights of terms in a document can be determined more precisely. The idea is based on a presumption that the author of a document differentiates important information using HTML tags. Furthermore, the proposed technique enables distribution of the index to several machines. The thesis also includes sample implementation of the proposed algorithm. Keywords: indexation, HTML, vector space model, structural analysis

1

Úvod

Jeden z typických rysů současnosti je prudký rozvoj informačních technologií. Převážná většina dostupných informací je uchovávána a přístupná v elektronické podobě, například prostřednictvím sítě Internet jako dokumenty ve formátu HTML. Celosvětová síť Internet je dnes tudíž s převahou největším zdrojem informací a obsahuje několik miliard webových stránek. Při stále se zvětšujícím počtu dostupných (textových) informací ovšem roste i potřeba jejich efektivní organizace. V oblasti vyhledávání informací (information retrieval, IR) se systémy pro údržbu a vyhledávání textů nazývají dokumentografické informační systémy (DIS ) – podrobněji viz. [23]. Zpočátku bylo vyhledávání omezeno pouze na tzv. katalogy a jejich vyhledávače. V katalozích jsou odkazy na dokumenty shromažďovány a řazeny do jednotlivých kategorií dle svého obsahu. Protože však vkládání do katalogu probíhá nejčastěji ručně (a tedy pomalu), zatímco obsah Internetu se mění a narůstá velmi rychle, je udržení aktuálnosti a úplnosti takového katalogu v podstatě nemožné. Proto je dnes kladen mnohem větší důraz na vyhledávací nástroje označované jako tzv. fulltextové vyhledávače (tj. vyhledávače v úplných textech), které jsou schopné automaticky zařazovat a uchovávat informace o větším počtu dokumentů. Jelikož navíc vzhledem k časové náročnosti nelze při vyhledávání v textu pracovat s celými dokumenty, vytváří se pro potřeby vyhledávání tzv. index – pomocná struktura reprezentující dokumenty. Vyhledávač tedy obsahuje pouze odkazy na dokumenty a pomocí indexu dokáže vybrat odpovídající záznamy mnohem rychleji. Protože jsou dokumenty převážně zařazovány a indexovány prostřednictvím automatů, vyvstává otázka jak data v dokumentu kategorizovat. Jak již bylo řečeno, nejrozšířenějším formátem dokumentů v síti Internet je HTML, který definuje jakým způsobem má být dokument zobrazen uživateli. Právě významu jeho formátovacích značek by bylo možné při indexaci využít pro určení vah jednotlivých termů a získat tak přesnější informace o dokumentu jako celku pro následné vyhledávání.

1.1

Cíl práce

Cílem této práce je navrhnout a implementovat nástroje pro indexaci a vyhledávání v rozsáhlé databázi HTML dokumentů s využitím významu formátovacích značek. Výsledné řešení s ohledem na množství dat bude navíc podporovat distribuci indexu na více počítačů.

1

1.2

Členění textu

Tato práce se skládá z několika kapitol. V následující (druhé) kapitole je stručně popsána teorie, ze které práce vychází. Existující přístupy indexace využívající struktury HTML dokumentů jsou popsány v kapitole třetí. Ve čtvrté kapitole je popis navrženého algoritmu indexace a v páté jeho experimentální implementace. V poslední kapitole jsou shrnuty výsledky práce a nastíněna další možná rozšíření.

2

2

Teorie

V této kapitole je uveden přehled teorie potřebné k pochopení problematiky HTML, DIS a ostatních oblastí, kterých se tato diplomová práce týká nebo jejichž formáty a výsledky využívá. Kromě přehledu architektury DIS jsou zde popsány také základní modely DIS a metody ohodnocování termů.

2.1

Jazyk HTML

Jazyk HTML (Hypertext Markup Language – jazyk pro značkování hypertextu) slouží k prezentaci hypertextových dokumentů v síti Internet (podrobný popis standardu je uveden na [25] nebo v [4, 17]). Jedná se o neproprietární formát, který je jednou z aplikací jazyka SGML (Standard Generalized Markup Language – standard pro obecný značkovací jazyk). Jazyk HTML tedy definuje množinu značek pro strukturování textu, vkládání hypertextových odkazů apod. Každá značka se skládá ze tří částí – uvozující části (s případnými atributy), těla a ukončující části – a má následující zápis: tělo značky

Některé značky jsou zapisovány bez ukončovací části, jako např. <META>,
,

---

apod. Tyto značky se také označují jako nepárové či prázdné. Pro potřeby indexace nás budou zajímat zejména značky definující prezentační vrstvu HTML dokumentu, tj. ty, které určují jak bude vysázen text v těle značky (např.

, , . . . ), a značky odkazující se na HTML dokumenty či zdroje jiných datových formátů (, . . . ). Příklad základní struktury HTML dokumentu je uveden na obrázku 1. 2.1.1

Sledované HTML značky

Jak již bylo řečeno standard HTML předepisuje širokou škálu značek. Zde jsou uvedeny pouze ty, které definují základní strukturu dokumentu nebo mají přímý vliv na prezentační vrstvu dokumentu.1 Základní strukturu HTML dokumentu lze rozdělit do tři částí: 1. Řádek s informací o verzi HTML standardu použitém v dokumentu. 2. Hlavička dokumentu – ohraničená značkou . 1

Celá diplomová práce pracuje se standardem HTML ve verzi 4.01, který je v současné době nejnovější specifikací HTML (celý standard je k dispozici na [25]).

3

<meta http-equiv="content-type" content="text/html; charset=windows-1250">

René Mihula - Indexování HTML dokumentů
Cílem práce je navrhnout a implementovat nástroje pro indexaci a vyhledávání v rozsáhlé databázi HTML dokumentů s využitím informací formátovacích značek. S ohledem na množství dat by výsledné řešení mělo podporovat distribuci indexu na více počítačů.

Obrázek 1: Příklad HTML dokumentu 3. Tělo dokumentu – vlastní obsah dokumentu tvořený značkou nebo . Podrobnější popis značek definujících základní strukturu dokumentu je uveden v následujících sekcích. Základní datové typy Před vlastním popisem značek je třeba uvést některé typy používané ve standardu HTML, především pak ty, které jsou spojeny s navrhovaným indexováním: Znakem může být libovolný prvek zvolené znakové sady nebo některá z předdefinovaných konstant (např. &, ©,   apod.). Textový řetězec představuje text v „čitelné forměÿ, tj. běžný text (použitý např. v atributech title). CDATA je sekvence znaků ze zadané znakové sady. Představuje „běžný textÿ v dokumentech (tj. pro indexaci nejdůležitější část dokumentu).

4

Uniform Resource Identifiers (URI) je řetězec znaků identifikující abstraktní nebo fyzický zdroj dat (např. URL, relativní odkaz, cestu k souboru na disku apod.). Odkaz pomocí URI je použit např. v atributu href značky . Typ obsahu udává formát souboru pomocí MIME2 typů (např. text/html, text/css, image/png apod.) – více viz. [11]. Typ odkazu definuje význam odkazovaného dokumentu vzhledem k aktuálnímu a naopak. Nabývá hodnot Next, Prev, Index apod. Barva je reprezentována buď hexadecimálním číslem (např. #FCD786) nebo předdefinovanou konstantou (např. Yellow). Obecné atributy Většina značek obsahuje čtyři hlavní atributy id, title, class a style. Existuje však několik výjimek, které tyto atributy nemají. Mnohé značky mají navíc atributy pro určení jazyka (lang a dir) a atributy pro události3 (ve tvaru On«NázevUdálosti» jako např. OnClick, OnKeyPress, OnMouseOver apod.). Přítomnost (resp. nepřítomnost) obecných atributů je v dalším textu u jednotlivých značek zdůrazněna. Význam výše zmíněných atributů je následující: id – jednoznačný identifikátor prvku v rámci celého dokumentu title – krátký popis prvku class – možnost obecného značkování v HTML; instance značek je možné rozdělit do tříd a pro tyto třídy definovat jednotlivé styly (např. dva hypertextové odkazy mohou mít jiný vzhled) style – aplikace kaskádového stylu přímo v zápisu značky lang – jazyk, v němž je dokument napsán; skládá se z primárního a sekundárního (nepovinného) kódu oddělených pomlčkou (např. en, en-US, cs); primární kód jazyka udává norma ISO 639, sekundární odpovídá buď kódu země stanoveným normou ISO 3166 (např. Česká Republika má kód CZ) nebo kódu z RFC 3066 (např. dialekty a experimentální jazyky) 2

MIME – Multipurpose Internet Mail Extensions Tyto atributy nemají přímý vliv na prezentační vrstvu dokumentu, a proto nebudou podrobněji popisovány. 3

5

dir – určuje jakým směrem má být text reprezentován – zleva doprava (ltr) či naopak (rtl). V dalších %core% %language% %events% 2.1.2

definicích jsou použity následující zkratky: na místě atributů id, title, class a style na místě atributů lang, dir na místě atributů událostí

Ohraničení dokumentu

Celý HTML dokument ohraničuje párová značka . Ostatní HTML značky se zapisují do těla této značky. ... dokument ...

Tato značka nemá žádné speciální atributy. 2.1.3

Záhlaví dokumentu

Záhlaví dokumentu vymezuje párová značka . Obsahuje souhrn informací o dokumentu (meta informace, styly, skripty atd.), tj. prvky <TITLE>, , <META>, , <STYLE>, <SCRIPT> a