Univerzita Karlova v Praze Matematicko-fyzikální fakulta
DIPLOMOVÁ PRÁCE
Bc. Filip Pekárek
Extrakce fakt· z Webu Katedra softwarového inºenýrství
Vedoucí diplomové práce:
Studijní program:
RNDr. Leo Galambo², Ph.D.
Informatika, Softwarové systémy, Systémové architektury
2010
Na tomto míst¥ bych cht¥l pod¥kovat svému vedoucímu diplomové práce panu RNDr. Leo Galambo²ovi, Ph.D. za podn¥tné p°ipomínky a vedení.
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 1.8.2010
Filip Pekárek
2
Obsah
1 Úvod
6
1.1
Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2
Cíle
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Související práce
7
3 Pouºité technologie
8
3.1
3.2
3.3
3.4
3.5
Parser stránek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.1
Roz²í°ení do Mozilla Firefox . . . . . . . . . . . . . . . . . . . . . .
8
3.1.2
isté Java °e²ení
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.1.3
SWT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
DOM struktura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2.1
Gecko
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.2
XULRunner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.3
XPCOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.2.4
JavaXPCOM
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Vizuální atributy 3.3.1
Výb¥r
3.3.2
CSS a implementace
. . . . . . . . . . . . . . . . . . . . . . . . . .
14
Neuronové sít¥ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.4.1
SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.4.2
LVQ
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.4.3
Weka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
Ostatní . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4 Návrh °e²ení 4.1
4.2
4.3
4.4
18
Vizuální blok
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.1.1
De nice dle VIPS . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.1.2
Implementace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Úprava blok· dle lokálního kontextu
. . . . . . . . . . . . . . . . . . . . .
21
4.2.1
Pozorování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4.2.2
Návrhy algoritm· . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2.3
Implementovaný algoritmus
. . . . . . . . . . . . . . . . . . . . . .
25
4.2.4
Kontrola kontextu
. . . . . . . . . . . . . . . . . . . . . . . . . . .
27
Klasi kace získaných dat . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.3.1
Testované kategorie . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.3.2
De nice atribut·
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.3.3
Implementace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Problémy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
32
5 VIPS
34
5.1
Extrakce vizuálního bloku
. . . . . . . . . . . . . . . . . . . . . . . . . . .
36
5.2
Vizuální separátory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
5.2.1
Detekce separátor· . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
5.2.2
Nastavení vah separátor· . . . . . . . . . . . . . . . . . . . . . . . .
40
5.3
Konstrukce vizuálního stromu
. . . . . . . . . . . . . . . . . . . . . . . . .
6 Výsledky
41
43
6.1
Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
6.2
Klasi kace stránek
44
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 Záv¥r
47
7.1
Spln¥ní cíl·
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
7.2
Dal²í práce
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
8 P°ílohy
49
8.1
Ukázky kon gurací
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
8.2
Tabulky výsledk· . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
8.3
P°iloºený digitální materiál
54
. . . . . . . . . . . . . . . . . . . . . . . . . .
9 Literatura
55
4
Název práce: Extrakce fakt· z Webu Autor: Filip Pekárek Katedra (ústav): Katedra softwarového inºenýrství Vedoucí diplomové práce: RNDr. Leo Galambo², Ph.D. e-mail vedoucího: Leo.Galambos@m.cuni.cz Abstrakt: V p°edloºené práci navrhujeme a testujeme nový postup extrakce fakt· z webu. P°edloºená metoda bere v úvahu, v£etn¥ DOM stromu webové stránky, také její vizuální podobu. Základem a první £ástí je extrakce sémantických £ástí stránky pomocí algoritmu VIPS. Dal²ím krokem je ov¥°ení a p°ípadná úprava získaných dat na základ¥ lokálního kontextu. Finální £ástí je pomocí získaných a p°ípadn¥ upravených fakt· klasi kovat analyzované webové stránky do p°edem de novaných kategorií. Ur£ování t°íd probíhá prost°ednictvím mnoºiny posuzovatel· implementovaných v kon guraci de novatelnými instancemi neuronových sítí.
Klí£ová slova: web, extrakce, fakta, vizuální, DOM, VIPS Title: Web Information Extraction Author: Filip Pekárek Department: Department of Software Engineering Supervisor: RNDr. Leo Galambo², Ph.D. Supervisor's e-mail address: Leo.Galambos@m.cuni.cz Abstract:
In the present work we suggest and test new process of web information ex-
traction. Proposed method consider DOM tree of the web page including it's visual cues. Basic and the rst part is semantic parts extraction of a page using VIPS algorithm. Next step is validation and eventual modi cation of gained information based on the local context. Final part is classi cation of analyzing page into prede ned classes using got facts. Set of critics implemented by con gurable instances of neural networks determine the classes.
Keywords: web, extraction, facts, visual, DOM, VIPS
5
1
Úvod
1.1 Motivace Sou£asný Internet obsahuje nep°eberné, denn¥ rostoucí mnoºství stránek. Podle svých obsah· se dají °adit do mnoha r·zných kategorií, které se navzájem více £i mén¥ p°ekrývají. Pat°í sem nap°íklad informativní weby, internetové obchody, servery s r·znými druhy inzerce, diskuzní fóra, portály poskytující r·zné sluºby a mnoho dal²ích. Jednou z hojn¥ pouºívaných sluºeb Internetu je vyhledávání. Kaºdému se jiº ur£it¥ stalo, ºe po zadání klí£ových slov do vyhledáva£e musel proklikat n¥kolik nalezených odkaz· nebo zm¥nit zadaná slova a hledání opakovat, neº na²el skute£n¥ to, co hledal. Je to zp·sobeno práv¥ zmi¬ovaným obrovským mnoºstvím stránek, které internetoví roboti prohledávají, analyzují a indexují ve svých databázích. Vezm¥me si nap°íklad klí£ová slova ko²atý strom. Pokud tato slova zadá programátor nebo zahrádká°, budou s velkou pravd¥podobností kaºdý z nich hledat zcela odli²né informace. Oba v²ak dostanou stejné výsledky a pokud nebudou mít zrovna ²t¥stí, nebo nezp°esní své dotazy, stráví n¥kolik chvil hledáním toho pro n¥ správného odkazu. Moºnost ur£it si své role, nebo lépe °e£eno oblast svého zájmu p°ed vlastním hledáním by zp·sobilo zp°esn¥ní výsledk·. Tím pádem se uºivateli zkrátí vlastní doba hledání správného výsledku. Aby takový mechanismus mohl fungovat, pot°eboval by ke své práci existenci ur£itého indexu p°es kategorie stránek, ve kterých se vyhledává.
1.2 Cíle Cílem této práce je pokusit se navrhnout, naimplementovat a otestovat zp·sob, který by co moºná nejvíce automaticky, bez pot°eby zásahu uºivatele, za°adil konkrétní webovou stránku do kategorie. Hledaný algoritmus by m¥l krom¥ prosté DOM struktury vyuºívat také prezenta£ní podobu dokumentu a m¥l by pracovat v n¥kolika krocích. T¥mi jsou získání a zpracování DOM struktury analyzované stránky, validace získaných dat v rámci místního kontextu, p°edloºení získaných informací sad¥ tématicky r·zných extraktor· a následné za°azení stránky do jedné z rozpoznávaných kategorií. Implementace by m¥la být v jazyce Java zaji²´ující nezávislost na platform¥ a snadné p°ípadné následné vyuºití programu jinými aplikacemi.
6
2
Související práce
V¥t²ina systém· na získávání informací z Webu povaºuje internetové stránky za nejmen²í a dále ned¥litelnou jednotku, která ale ne vºdy, reprezentuje jeden sémantický celek. V¥t²inou obsahuje r·zné £ásti, které se nevztahují k hlavnímu tématu stránky. Nap°íklad nabídka, dekorativní prvky nebo reklamní panely. Webové stránky £asto obsahují více témat, které spolu nesouvisí. Struktury zaloºené na sémantickém obsahu stránek vyuºívá mnoho aplikací. Nap°íklad p°ístupy pouºívající databázové techniky, které vyuºívají rozd¥lení webových dokument· na r·zné informa£ní £ásti. [1] B¥hem posledních let se mnoho pozornosti soust°edilo také na analýzu odkaz·. Jejím základním p°edpokladem je, ºe pokud je odkaz mezi dv¥ma stránkami, existuje mezi celými stránkami n¥jaký vztah. Ve v¥t²in¥ p°ípad· v²ak odkaz ze stránky A do stránky B indikuje, ºe pouze m·ºe existovat n¥jaká závislost mezi ur£itou £ástí stránky A a ur£itou £ástí stránky B. Nicmén¥ samotný DOM strom stránky není posta£ující k sémantickému d¥lení stránky. Díky své exibilit¥ mnoho stránek nespl¬uje W3C speci kace, coº m·ºe zp·sobit chyby v DOM strom¥. Nap°íklad to, ºe dva prvky DOM stromu mají spole£ného p°edch·dce nemusí znamenat, ºe k sob¥ mají sémanticky blíº, neº k jiným prvk·m stromu. [4] Existuje n¥kolik p°ístup·, jak získat obsahovou strukturu stránky. Mnoho prací bere v úvahu parametry HTML tag·. Mezi ty d·leºité pat°í nap°íklad
(odstavec),
(list) nebo (tabulka). [23] Jiné algoritmy zaloºené na odkazech uvnit° stánek pouºívají heuristiku pro rozpoznání jednotlivých záznam· uvnit° stránek. [17] Dal²ím p°ístupem je FOM (Function-based Object Model), kde kaºdý dál ned¥litelný element v DOM stromu je nazýván objektem a m·ºe být sou£ástí sloºených objekt·. Funk£ní typ lze de novat ke kaºdému objektu a slouºí ke generování hierarchické struktury dokumentu. [10] Lidské vnímání internetových stránek je £asto jako sloºení n¥kolika r·zných sémantických objekt· a ne jako jednoho celku. N¥které výzkumy ukázaly, ºe uºivatelé £asto o£ekávají ur£ité £ásti stránek dle své funk£nosti (nap°íklad nabídka, reklamní plocha) na speci ckých místech. [13] Prostorové a vizuální podn¥ty pomáhají uºivateli podv¥dom¥ rozd¥lit stránky do n¥kolika sémantických £ástí. V²echny vý²e zmín¥né metody neberou v úvahu vizuální strukturu. Proto je v této práci pouºit a naimplementován algoritmus VIPS (Vision-based Page Segmentation), který práv¥ prostorové a vizuální aspekty dokumentu vyuºívá. Podrobn¥ji je algoritmus popsán v samostatné kapitole 5 na stran¥ 34. Dále je v této práci pouºita my²lenka lokálního kontextu jednotlivých £ástí stránek. Kone£nou fází je klasi kace webových stránek pomocí neuronových sítí. V²echny £ásti výsledného programu jsou popsány odd¥len¥. Poslední dv¥ kapitoly práce se zabývají dosaºenými výsledky a celkovým zhodnocením.
7
3
Pouºité technologie
V této kapitole jsou uvedeny existující nástroje, metody a struktury vyuºívané programem DataExtraxtor.
3.1 Parser stránek St¥ºejním úkolem první £ásti celého procesu analyzování a klasi kace konkrétní webové stránky je poºadovanou stránku zobrazit a získat její d·leºité vlastnosti. Bylo tedy pot°eba najít a vybrat technologii, nástroj, který by tento úkol plnil v dostate£né mí°e a poskytoval pot°ebné rozhraní. V úvahu bylo také pot°eba brát poºadavek, ºe implementace celého výsledného programu m¥la být v jazyce Java.
3.1.1
Roz²í°ení do Mozilla Firefox
Prvním pokusem bylo vydat se sm¥rem napsání celé aplikace ve form¥ pluginu do Firefoxu. Po prozkoumání moºností se ukázalo, ºe Firefox poskytuje dobré a ²iroké rozhraní, které odpovídá na²im poºadavk·m a pot°ebám. Men²í p°ekáºkou byla p·vodní neznalost technologií XUL [21], která se pro programování dopl¬k· do Firefoxu pouºívá. XUL (XML User Interface Language) je XML jazyk od Mozilly pro vývoj funk£n¥ bohatých na platform¥ nezávislých aplikací. Technologie mimo jiné poskytuje snadnou jazykovou lokalizaci program· a celkov¥ je velmi podobná dynamickému HTML.
xml version=" 1 . 0 " ?>
t y p e=" t e x t / c s s " ?>
DOCTYPE w i n d o w [ %d t d 1 ;
]> <w i n d o w x m l n s=" h t t p : / /www . m o z i l l a . o r g / k e y m a s t e r / gatekeeper / there . i s . only . xul " x m l n s : h t m l=" h t t p : / /www . w3 . o r g / 1 9 9 9 / x h t m l " i d=" d a t a E x t r a c t o r W i n d o w " w i d t h=" 6 4 0 " h e i g h t=" 4 8 0 " p e r s i s t =" s c r e e n X
screenY
width
height
t i t l e ="& d a t a E x t r a c t o r . t i t l e ; "
8
sizemode "
s i z e m o d e=" n o r m a l ">
i d=" t b x E x t r a c t o r T o o l b o x ">
<m e n u b a r
i d=" m b r E x t r a c t o r M a i n " />
i d=" t b E x t r a c t o r P r i m a r y " />
i d=" b x D a t a E x t r a c t o r M a i n "
f l e x =" 1 " />
Výpis 1: Ukázka XUL kódu Cílem bylo vytvo°it Java aplikaci a zapouzd°it jí pomocí XUL do Firefoxu, který by poskytoval pot°ebné rozhraní informací analyzovaných stránek. P°estoºe tato technologie byla nová, její pouºití se ukázalo jednoduché a vývoj v ní relativn¥ rychlý. Nedostatkem tohoto °e²ení v²ak bylo propojení a £astý p°evod mezi strukturami Java kódu a Javascriptu, a proto se od tohoto °e²ení upustilo.
3.1.2
isté Java °e²ení
Odstran¥ním p°edchozího problému bylo nalezení n¥jaké vhodné implementace HTML parseru, £i p°ímo webového prohlíºe£e v jazyce Java. B¥hem hledání bylo nalezeno n¥kolik °e²ení, která po otestování, více £i mén¥, spl¬ovala na²e poºadavky. T¥mito jsou:
• HTML Parser Jedná se o knihovnu v jazyce Java slouºící k lineárnímu i nesekven£nímu analyzování HTML. Primární uºití je transformace nebo extrakce s moºností pouºití ltr· a jednoduchou integrací do JavaBeans. Auto°i ho popisují jako rychlý, robustní a dob°e otestovaný balík.
• Jericho HTML parser Java knihovna umoº¬ující analýzu a manipulaci £ástí HTML dokumentu v£etn¥ zna£ek serveru a výpisu nerozpoznaných, nebo nevalidních £ástí HTML. Sou£asn¥ poskytuje funkce pro vysoko úrov¬ové transformace.
• Cobra Open source Cobra HTML Toolkit obsahuje HTML parser, který m·ºe být pouºit nezávisle na renderovacím jád°e Cobra. Implementuje W3C HTML DOM Level 2, analyzuje HTML stránky a umoº¬uje modi kaci DOM stromu.
9
• JTidy Java verze projektu HTML Tidy umoº¬uje kontrolu syntaxe a zobrazení HTML. Dá se pouºít jako nástroj pro kontrolu a úpravu HTML obsahujících chyby. Dále poskytuje rozhraní pro p°ístup k DOM stromu zpracovávaného dokumentu.
• CyberNeko HTML Parser Jednoduchý HTML analyzátor, který umoº¬uje zpracovat a získat informace HTML dokumentu pouºitím standardního XML rozhraní. Umí na£íst HTML soubory a v p°ípad¥ pot°eby opravit mnoho b¥ºných chyb, které auto°i stránek d¥lají.
• HotSAX Rychlý, drobný, nevalidující SAX2 analyzátor pro HTML/XML/XHTML. M·ºe být vyuºit jako jednoduchý webový prohlíºe£.
Kaºdý z vý²e uvedených projekt· bohuºel nemohl být pouºit, protoºe vykazoval n¥který z nedostatk·:
•
Chybná £i úpln¥ chyb¥jící moºnost zobrazení zpracovávané stránky.
•
Nedostate£né rozhraní DOM stromu.
•
Chyb¥jící £i nedostate£né rozhraní vizuálních vlastností stránky.
Ideálním a vhodným kandidátem se nakonec ukázal nástroj SWT popsaný v dal²í kapitole.
3.1.3
SWT
The Standard Widget Toolkit [16] je open source nástroj v jazyce Java, který poskytuje výkonné, p°enosné rozhraní a úzkou integraci s gra ckým uºivatelským rozhraním nativního opera£ního sytému. Mnoho nízko úrov¬ových programových úkol· gra ckého rozhraní je obsluhováno vy²²ími vrstvami platformy Eclipse, jejíº je SWT sou£ástí. SWT de nuje jednotné API poskytované na v²ech podporovaných platformách. Vlastní implementace se snaºí pouºívat nativní nástroje kaºdé platformy jak jen to je moºné, £ímº umoº¬uje okamºit¥ reagovat na zm¥ny gra ckého rozhraní aktuáln¥ pouºívaného opera£ního systému. V praxi se jedná o skupinu základních gra ckých prvk·, mezi kterými si programátor m·ºe vybírat a r·zn¥ je poskládat. Pat°í sem nap°íklad:
•
r·zné typy tla£ítek (²ipka, klasické, p°epínací, ...)
•
plátno (p°ímé kreslení na obrazovku)
•
menu (snadné vytvá°ení klasických programových nabídek)
•
tabulka (zobrazuje seznam text· i obrázk·)
10
•
text (jedno i více °ádkový, stylizovaný)
•
a pro nás nejd·leºit¥j²í - prohlíºe£ webových stránek
Práv¥ díky existenci prohlíºe£e, který spl¬uje na²e poºadavky, se komponenty SWT nakonec staly základem výsledného softwaru DataExtractor. Instance t°ídy Browser implementují webový prohlíºe£. Mimo jiné umoº¬ují uºivateli zobrazit a navigovat se uvnit° HTML dokument·. Hlavní výhody a rozhodující argumenty v²ak byly tyto:
•
isté Java °e²ení.
•
Pomocí XULRunner ( 3.2.2 na následující stran¥ ) umoº¬uje pouºití Mozillla zobrazovacího jádra.
•
Umoº¬uje p°ístup k JavaXPCOM ( 3.2.4 na stran¥ 13 ) .
import import import //
o r g . m o z i l l a . i n t e r f a c e s . nsIDOMDocument ; org . m o z i l l a . i n t e r f a c e s . nsIWebBrowser ;
vytvo°í
Browser
//
org . e c l i p s e . swt . b r o w s e r . Browser ;
instanci
browser
p°istoupí
new
Browser ( s h e l l ,
SWT . MOZILLA ) ;
k JavaXPCOM n s I W e b B r o w s e r
nsIWebBrowser
//
=
prohlíºe£e
wb = ( n s I W e b B r o w s e r )
b r o w s e r . getWebBrowser ( ) ;
z í s k á DOM dokumentu
nsIDOMDocument
d o c u m e n t = wb . getContentDOMWindow ( ) . g e t D o c u m e n t ( ) ;
Výpis 2: Ukázka SWT a JavaXPCOM
3.2 DOM struktura DOM (Document Object Model) je na platform¥ a jazyku nezávislá objektová reprezentace XML, nebo HTML dokumentu. Je to rozhraní zprost°edkující p°ístup, nebo modi kaci obsahu, struktury, stylu dokumentu, £i jeho vlastností. Dne²ní de nice následovala p·vodn¥ nejednotné rozhraní, jeº m¥l kaºdý webový prohlíºe£ vlastní a speci cké. [7] Tato vzájemná nekompatibilita p°im¥la W3C k vytvo°ení jednotného standardu. [18] DOM umoº¬uje p°ístup k dokumentu jako ke stromu a je vhodný pro opakovaný a nesekven£ní p°ístup. Proto musí implementace pouºívat vnit°ní pam¥´ pro uloºení minimáln¥ aktuáln¥ zpracovávaného dokumentu. Webový prohlíºe£ nemusí nutn¥ vyuºívat DOM pro zobrazení stránek, nicmén¥ scripty Javascriptu ho vyºadují, aby mohly procházet a m¥nit struktury stránek dynamicky. R·zné prohlíºe£e pouºívají r·zná renderovací jádra poskytující práv¥ DOM strukturu stránky. Jedno z konkrétních zobrazovacích jader vyuºívaným na²í aplikací a s ním souvisejících technologie jsou popsány v následujících podkapitolách.
11
3.2.1
Gecko
Gecko je název renderovacího jádra vyvinutého projektem Mozilla, které implementuje W3C DOM standardy. [8] Jeho funkce jsou vyuºívány ke £tení webového obsahu, jako jsou HTML, CSS, XUL £i Javascript a následnému vykreslení na obrazovku. Je pouºíváno mnoha aplikacemi v£etn¥ internetových prohlíºe£·, nap°íklad Thunderbird, Firefox £i SeaMonkey.
package
org . m o z i l l a . i n t e r f a c e s ;
public i n t e r f a c e
nsIDOMDocument
nsIDOMDocumentType
extends
getImplementation ( ) ;
nsIDOMElement
getDocumentElement ( ) ;
nsIDOMElement
createElement ( String
nsIDOMDocumentFragment
target ,
String
nsIDOMEntityReference
nsIDOMNode
data ) ; name ) ;
createEntityReference ( String
getElementsByTagName ( S t r i n g
i m p o r t N o d e ( nsIDOMNode
nsIDOMElement
createElementNS ( S t r i n g
createAttributeNS ( String String
nsIDOMNodeList
deep ) ;
qualifiedName ) ; namespaceURI , qualifiedName ) ;
getElementsByTagNameNS ( S t r i n g
getElementById ( S t r i n g
boolean
namespaceURI ,
String nsIDOMElement
name ) ;
tagname ) ;
importedNode ,
String nsIDOMAttr
data ) ;
createProcessingInstruction (
createAttribute ( String
nsIDOMNodeList
data ) ;
createCDATASection ( S t r i n g
nsIDOMProcessingInstruction
nsIDOMAttr
data ) ;
createComment ( S t r i n g
nsIDOMCDATASection
String
tagName ) ;
createDocumentFragment ( ) ;
createTextNode ( S t r i n g
nsIDOMComment
{
getDoctype ( ) ;
nsIDOMDOMImplementation
nsIDOMText
nsIDOMNode
namespaceURI , localName ) ;
elementId ) ;
}
Výpis 3: Mozilla nsIDOMDocument rozhraní
3.2.2
XULRunner
XULRunner je b¥hové prost°edí Mozilla, které m·ºe být pouºito pro zavád¥ní XUL a XPCOM aplikací mezi n¥º pat°í Firefox £i Thunderbird. [22] Poskytuje mechanismus pro instalaci, aktualizaci a odinstalaci aplikací tohoto druhu. XULRunner téº zprost°edkovává libxul, coº je °e²ení, které umoº¬uje vyuºití technologií Mozilla jinými projekty. Program DataExtractor pouºívá knihovnu xulrunner-sdk-1.9.3, která zprost°edkovává vý²e zmín¥né Gecko integrovanému webovému prohlíºe£i.
12
3.2.3
XPCOM
Jedná se o multiplatformní komponentový objektový model od Mozilly s vlastním de novaným rozhraním. Poskytuje komponenty a t°ídy jádra pomocí nichº je p°ístupný nap°íklad DOM strom renderované stránky generovaný jádrem Gecko. [20]
3.2.4
JavaXPCOM
Zprost°edkovává komunikaci mezi Java a XPCOM, díky n¥muº m·ºe Java aplikace p°istupovat k XPCOM objekt·m a XPCOM ke kaºdé Java t°íd¥ implementující XPCOM rozhraní. [11] Tento nástroj je standardní sou£ástí vý²e zmín¥ného XULRunneru.
3.3 Vizuální atributy Jedním z hlavních poºadavk· práce bylo p°i extrahování dat vyuºít prezenta£ní podoby dokumentu. Bylo tedy pot°eba vybrat vhodné atributy dokumentu a nalézt nástroj, který by nám jejich hodnoty poskytl.
3.3.1
Výb¥r
Hledané atributy m¥ly nahradit zrakový vjem uºivatele, který by ru£n¥ ur£oval shodhosti, rozdíly mezi více r·znými i uvnit° jedné webové stránky. Mezi vybrané a programem pouºívané vizuální vlastnosti stránek £i jejich £ástí pat°í:
• Velikost D·leºitá je velikost jednotlivých testovaných men²ích £ástí stránky, respektive její pom¥r v·£i celkové velikosti stránky. Udává po£et obrazových bod· uvnit° plochy jeº ur£itá £ást stránky zabírá.
• Poloha Kaºdá díl£í £ást stránky m·ºe být ur£ena £ty°mi hranami pravoúhlého £ty°úhelníku. Jednotkou jsou odpovídající sou°adnice obrazových bod· ur£ující tyto hranice.
• Barva pozadí Je detekována barva pozadí jednotlivých prvk· DOM strom· analyzovaných webových stránek. Hodnoty jsou bu¤ konkrétní barvy £i klí£ové slovo transparent ur£ující pr·hlednou barvu prvku.
• Font textu Obdobn¥ jako barva pozadí je detekována velikost fontu v obrazových bodech textových prvk· DOM stromu.
13
3.3.2
CSS a implementace
Cascading Style Sheets (CSS) je kolekce metod pro gra ckou úpravu webových stránek. [6] Kaºdý text má formu, £ímº je my²leno nap°íklad barva a velikost písma, pozadí, zarovnání atd., kde CSS je nov¥j²í zp·sob de nování t¥chto vlastnosní. Je trochu sloºit¥j²í neº p·vodní r·zné zp·soby vzniklé b¥hem vývoje jazyka HTML, ale o to uºite£n¥j²í. Díky CSS je moºné gra cké atributy HTML prvk· p°i tvorb¥ stránek nejen de novat, ale pokud to webový prohlíºe£ umoº¬uje, také hodnoty t¥chto vlastností získávat. P°íkladem je námi pouºité Gecko a konkrétn¥ XPCOM, který obsahuje rozhraní s CSS renderované stránky a jednotlivých prvk· DOM stromu.
import
org . m o z i l l a . i n t e r f a c e s . ∗ ;
// DOM HTML dokumentu nsIDOMDocument
document ;
nsIDOMDocumentView
documentView =
( nsIDOMDocumentView ) d o c u m e n t . q u e r y I n t e r f a c e ( nsIDOMDocumentView . NS_IDOMDOCUMENTVIEW_IID ) ; nsIDOMViewCSS
cssView =
( nsIDOMViewCSS ) d o c u m e n t V i e w . g e t D e f a u l t V i e w ( ) . q u e r y I n t e r f a c e ( nsIDOMViewCSS . NS_IDOMVIEWCSS_IID ) ;
// DOM e l e m e n t nsIDOMElement
// CSS
elem ;
styl
nsIDOMCSSStyleDeclaration
computedStyle ;
// CSS h o d n o t y nsIDOMCSS2Properties
cssProps ;
c o m p u t e d S t y l e = c s s V i e w . g e t C o m p u t e d S t y l e ( elem , cssProps
= ( nsIDOMCSS2Properties )
"" ) ;
computedStyle . q u e r y I n t e r f a c e (
n s I D O M C S S 2 P r o p e r t i e s . NS_IDOMCSS2PROPERTIES_IID ) ;
//
získá
barvu
pozadí
cssProps . getBackgroundColor ()
Výpis 4: Ukázka XPCOM a CSS
3.4 Neuronové sít¥ Neuronová sí´ je jedním z výpo£etních model· pouºívaných v um¥lé inteligenci. Jejím vzorem je chování odpovídajících biologických struktur. Skládá se z um¥lých (nebo také formálních) neuron·, jejichº obrazem je biologický neuron. Neurony jsou vzájemn¥ propojeny a navzájem si p°edávají signály a transformují je pomocí ur£itých p°enosových funkcí. Neuron má libovolný po£et vstup·, ale pouze jeden výstup.
14
Jedná se o ²irokou oblast pouºívanou nejen v informatice. Protoºe v sou£asné dob¥ je k dispozici mnoho i on-line materiál· s touto problematikou, jsou v této kapitole uvedeny pouze základní informace o konkrétních technologií, které jsou v této práci pouºity.
3.4.1
SOM
Self -Organizing Maps (Samoorganizující se mapy) £ast¥ji známé po svém stvo°iteli jako Kohonenovy mapy pat°í mezi základní a nejpopulárn¥j²í neuronové sít¥. P°edstavují skupinu sítí s u£ením bez u£itele, které ke svému nastavování nepot°ebují ideální vzory. K u£ení sítí sta£í jen velká skupina reálných signál·, z nichº n¥které mají ur£itou spole£nou vlastnost nebo naopak zna£né odli²nosti a nemusí k nim být p°i°azeny ºádné ideální u£ící informace. Ty v jiném typu sítí tzv. u£ení s u£itelem udávají cílový stav, do kterého se má sí´ svým u£ením dostat. Jejich získání bývá práv¥ nejv¥t²ím problémem. Kohonenovy mapy, resp. samoorganizující se mapy, jsou silným a kvalitním nástrojem pro identi kaci neznámých vlastností a parametr· skrytých v digitalizovaných vzorcích libovolného signálu. V n¥kterých aplikacích mohou pracovat jako alternativa k jiným algoritm·m, v n¥kterých aplikacích jsou jiº nenahraditelné.
3.4.2
LVQ
Learning Vector Quantization je ozna£ení pro typ neuronové sít¥. Jedná se o modi kaci Kohonenovy sít¥, která je schopna pracovat s pomocí u£itele. Ve skute£nosti jde o skupinu podobných algoritm· LVQ1, LVQ2, LVQ3 a jejich modi kace ur£ených pro de nování t°íd uvnit° prostoru vstupních dat. Tento druh sít¥ p°esn¥ vyhovuje poºadavk·m poslední fáze celého procesu fungování programu DataExtractor popsaného v kapitole 4.3 na stran¥ 28. Protoºe se jednotlivé algoritmy li²í nastavením parametr·m a n¥kdy i výsledky, m·ºe si uºivatel programu v kon guraci de novat kterou z t¥chto t°íd pouºije v£etn¥ hodnot jejich inicializa£ních parametr·. Význam jednotlivých parametr· je uveden v p°iloºené uºivatelské dokumentaci programu DataExtractor.
3.4.3
Weka
Weka je software pro získávání znalostí napsaný v jazyce Java. [19] Dá se spustit jako samostatná aplikace s gra ckým rozhraním, nebo jako sou£ást jiného programu, coº byl ná² p°ípad integrace. Jedná se o nástroj pro práci s r·znými neuronovými sít¥mi ideální pro na²e pouºití. Jedinou drobnou komplikací byly vý²e zmín¥né algoritmy, které nejsou standardní sou£ástí programu. e²ením bylo pouºití dal²í knihovny ve form¥ zásuvného modulu do programu Weka, které tyto algoritmy implementuje a je velmi jednodu²e pouºitelná.
15
<weka> < !−−
Command
line
−−>
weka . c l a s s i f i e r s . n e u r a l . l v q . L v q 3
−I
10000
−L
3
−R
0.1
−S
6
−G
true
−M
3
−C
−W
0.2
100
−E
0.2
< !−−
Filter
−−>
command
< f i l t e r >weka . f i l t e r s . u n s u p e r v i s e d . a t t r i b u t e . N o r m a l i z e
−S
1.0
−T
0.0
−u n s e t −c l a s s − t e m p o r a r i l y
< !−−
File
with
training
data
for
neural
network .
−−>
< t r a i n i n g F i l e > c o n f / weka / e s h o p . a r f f
Výpis 5: Ukázka kon gurace critixs.xml
Integrace programu Weka je následující. V kon gura£ním souboru critics.xml je moºné de novat r·zný po£et posuzovatel·. Na p°edchozím výpise je vid¥t, ºe kaºdý z posuzovatel· má mimo jiné de nováno:
• Pouºitý algoritmus
zadaný jménem t°ídy, která tento algoritmus implementuje
následovaný seznamem parametr·.
• Filtr
na vstupní data, pokud je pot°eba op¥t pomocí názvu t°ídy, která ho imple-
mentuje a seznamem parametr·.
• Soubor
s trénovacími daty konkrétní neuronové sít¥ ve formátu programu Weka.
Po nastudování dokumentace a ukázkových p°íklad· se integrace do softwaru DataExtractor ukázala snadnou a rychlou záleºitostí.
import //
weka . c l a s s i f i e r s . C l a s s i f i e r ;
et¥zec
String
commandLine z
konfigurace
config ;
String [ ]
values
String [ ]
options
=
config . s p l i t ("
=
new
String [ values . length
System . a r r a y c o p y ( v a l u e s ,
1,
options ,
values . length
//
instance
Classifier
konkrétní classifier
");
−
neuronové
−
1];
0,
1);
sít¥
=
C l a s s i f i e r . forName ( v a l u e s [ 0 ] ,
options );
}
Výpis 6: Ukázka integrace programu Weka
16
3.5 Ostatní Následuje vý£et dal²ích zatím nezmín¥ných technologií a knihoven vyuºívaných programem DataExtractor, které stojí za zmínku a jejich prvotní pouºití není zcela triviální. U kaºdé z nich je uveden stru£ný popis a p°ípadn¥ odkaz na ukázku uºití. Verze knihoven pouºívané tímto programem je moºné zjistit na p°íloºeném DVD.
BDB JE
Bdb-je je open source databáze od spole£nosti Oracle implementovaná £ist¥
v jazyce Java. [2] Podporuje transakce, je velmi jednodu²e pouºitelná ostatními aplikacemi a svou architekturou podporuje vysoký výkon a soub¥ºnost £tení i zapisování dat. Nabízí n¥kolik druh· rozhraní a p°ístup· k dat·m. Program DataExtractor vyuºívá prosté ukládání dvojic klí£-hodnota. Dle autor· je bdb-je ideálním nástrojem pro aplikace poºadující uloºení mimo hranice rela£ní databáze. Pouºití tohoto úloºi²t¥ se opravdu ukázalo jako velmi jednoduché a efektivní. Software DataExtractor pouºívá databázi pro ukládání výsledných vizuálních struktur analyzovaných stránek, protoºe jejich výpo£et je £asov¥ i pam¥´ové náro£ný a zárove¬ jsou opakovan¥ pouºívány v dal²ích £ástech programu. Klí£e i hodnoty jsou ukládány ve form¥ pole byt·, tudíº v²echny pot°ebné vnit°ní struktury programu mají implementovány vlastní serializa£ní i deserializa£ní metody. Data jsou uloºena ve dvou tabulkách, protoºe v n¥kterých p°ípadech se nejprve p°istupuje k základním údaj·m o uloºené stránce a aº pozd¥ji, v p°ípad¥ pot°eby, k vlastním dat·m.
• Základní informace zované stránky,
ve tvaru [url ]: [index,
rebuild, time ] kde url je adresa analy-
index je klí£ v tabulce s vlastními daty, rebuild je p°íznak, zda data
odpovídají jiº p°estav¥nému vizuálnímu stromu,
• Vlastní data
time je £as uloºení záznamu.
ve tvaru [index] : [data], kde index je pole osmi byt· a data je pole
byt· r·zné délky obsahující serializovaný vizuální strom. Serialozovány jsou vºdy základní atributy prvk· stromu, aby se daly op¥t deserializovat, celý strom pouºívat a zárove¬ uloºených dat bylo co nejmén¥.
LOG4J
Jedná se o open source projekt mnoha autor· pod zá²titou Apache Software
Foundation. [14] Umoº¬uje p°idání více úrov¬ového logování do program· a jejich následnému informativnímu výpisu uºivateli, £i vlastnímu debugování. Logovat lze textové °et¥zce i instance za b¥hu vzniklých výjimek. Pouºití je op¥t velmi jednoduché a skládá se ze dvou £ástí. Jejich ukázky jsou uvedeny na stran¥ 49.
Apache Commons
Op¥t projekt pod zá²titou Apache Software Foundation, který
se zam¥°uje na v²echny aspekty znovu pouºitelných komponent r·zných kategorií a oblastí, v²echny v jazyce Java. [5] V programu DataExtraktor je nap°íklad pouºita komponenta pro zpracování parametr· p°edaných programu z p°íkazové °ádky. Ukázka pouºití je na stran¥ 50.
17
4
Návrh °e²ení
4.1 Vizuální blok Vizuální blok pat°í mezi základní prvky algoritmu VIPS a programu DataExtractor. Blok, protoºe se jedná o abstrakci skute£ného pravoúhlého £ty°úhelníku a vizuální, protoºe odpovídá sémantické £ásti stránky z pohledu lidského oka. Ob¥ de nice si odpovídají a jsou popsány v následujících dvou £ástech. Vlastní detekce vizuálních blok· je popsána v kapitole 5.
4.1.1
De nice dle VIPS
Jedním ze vstupních dat algoritmu je DOM strom analyzované webové stránky. List tohoto stromu, který nem·ºe být dále d¥len je povaºován za základní objekt. Jeden vizuální blok tvo°ící dle de nice elementární prvky výsledné vizuální struktury celé stránky se skládá z jednoho £i více t¥chto základních objekt·. Z toho plyne d·leºité pozorování, ºe prvky výsledné vizuální struktury stránky nutn¥ neodpovídají prvk·m DOM stromu. Kaºdý vizuální blok má de novanou £íselnou hodnotu
Degree of Coherence (DoC)
ur£ující jeho míru souvislosti. Tato hodnota má následující vlastnosti:
•
ím v¥t²í je hodnota, tím vy²²í míra koherence.
•
Ve výsledné stromové struktu°e vizuálních blok· hodnota potomka není nikdy men²í neº hodnota jeho p°edka.
V algoritmu je také de nována konstanta
Permitted Degree of Coherence (PDoC),
která slouºí k ur£ení celkové granularity výsledné vizuální struktury. B¥hem výpo£tu algoritmu je s ní porovnávána hodnota
DoC nov¥ vznikajících vizuálních blok· a pokud
hodnota bloku je vy²²í nebo rovna této mezní hodnot¥, není blok dále d¥len a stane se listem. R·zným nastavením hodnoty
PDoC dosáhneme r·zné granularity výsledné
detekované struktury stránky. ím men²í je tato hodnota, tím hrub²í struktura bude. V na²í implementaci algoritmu nabývá atribut
DoC hodnot od 1 do 10. Protoºe chceme
detekovat dostate£né malé vnit°ní £ásti stránek, námi zvolená hodnota konstanty
PDoC
je 9.
4.1.2
Implementace
Algoritmické de nici odpovídá v programu DataExtractor t°ída
VisualBlock. Je nejob-
sáhlej²í a nejvíce pouºívanou t°ídou po celý b¥h programu od detekce blok· aº po nální klasi kaci jednotlivých stránek. Protoºe sdílí n¥které vlastnosti s jinými vnit°ním strukturani, je t°ída p°ímým potomkem t°ídy
Item a nep°ímým potomkem t°ídy Box. 18
VisualBlock
•
Základní vnit°ní t°ída
public c l a s s /∗ ∗
levá
Box
/∗ ∗ p r a v á
hranice
horní
hranice
spodní
private i n t
/∗ ∗
£ty°úhelníku
∗/
£ty°úhelníku
∗/
hranice
∗/
£ty°úhelníku
bottom ;
velikost
£ty°úhelníku
∗/
size ;
vertikální
private i n t
/∗ ∗
∗/
pixlech
top ;
private i n t
/∗ ∗
v
right ;
private i n t
/∗ ∗
£ty°úhelníku
left ;
private i n t
/∗ ∗
{
hranice
private i n t
Box reprezentuje pravoúhlý £ty°úhelník.
sou°adnice
st°edu
£ty°úhelníku
∗/
centerTop ;
horizontální
private i n t
sou°adnice
st°edu
£ty°úhelníku
∗/
centerLeft ;
}
Výpis 7: Vnit°ní t°ída Box
•
Dal²í t°ída v hierarchii obsahuje n¥které atributy spole£né s jinou vnit°ní strukturou.
public c l a s s
Item
/∗ ∗ D e g r e e
of
protected i n t
/∗ ∗
interní
vizuální
protected
/∗ ∗
doc =
prvku
type
/∗ ∗ Tento
atribut
VisualBlock
/∗ ∗ jméno
∗/
/∗ ∗
text
protected
String
pro
String
∗/
prvkem
VisualBlock
block
name =
vnit°ní
p°ed
je
odkaz
∗/
stromu .
protected
∗/
beforeSeparators ;
t°ídy ve
za prvkem
afterSeparators ;
separátory
Separator [ ]
protected
∗/
( DoC )
∗/
separátory
p°edch·dce
C o m p a r a b l e {
− 1;
=
protected na
implements
0;
Separator [ ]
vizuální
Box
Coherence
typ
protected i n t
/∗ ∗
extends
=
null ;
null ;
testovací
ú£ely
valueTestString
=
∗/
null ;
}
Výpis 8: Vnit°ní t°ída Item
19
•
VisualBlock.
Nejroz²í°en¥j²í t°ída
public c l a s s
extends
VisualBlock
/∗ ∗ c o m p a r á t o r
vizuálních
Item
blok·
s t a t i c f i n a l VBSizeComparator = new V B S i z e C o m p a r a t o r ( ) ;
/∗ ∗
p°ímí
private
/∗ ∗
potomci
zda
private boolean
/∗ ∗
p°ímí
private
byli
private
potomci
/ ∗ ∗ pom¥r
jeº
zda
se
∗
ºádnému HTML t a g u .
více
ku
blok·
∗/
virtual
virtuální
potomk·
/∗ ∗ h l o u b k a
prvku
private
blok· ,
private
/∗ ∗
Box
kontrole
private boolean
byl
/∗ ∗
statistika
private
/∗ ∗
String
prvek
rebuild
kontroly
lokálního
pozice
private i n t
/∗ ∗
=
sousedy
null ;
sousedé
kontextu
false ;
∗/ ∗/
null ;
potomk·
∗/
prvek
odstran¥n
kontextu
false ;
null ;
b¥hem
∗/
∗/
NNType ;
bloku
na
stránce
pagePosition
vzdálenost
private i n t
potenciální
reprezentuje
removed =
i n t e r n í NN t y p
potenciálními
I n t e g e r > nameStats =
byl
∗/
ko°ene
zpracován
p°ímých
zda
private i n t
/∗ ∗
jeº
p°íznak ,
private boolean /∗ ∗
=
nodeName =
Map<S t r i n g ,
st°edu
pouze
0;
null ;
lokálního
jmen
který
neodpovídá
supposedSiblings
tvo°ící
/ ∗ ∗ j m é n o HTML p r v k u
private
=
jsou
supposedBox =
zda
∗/
1;
které
oblasti
p°íznak , p°i
=
S e t
/∗ ∗ r o z m ¥ r y
a
blok ,
s t r o m u sm¥rem od
rootLevel
stránky
∗/
childrenValidated
ve
celé
true ;
=
private i n t
/∗ ∗ m n o º i n y
∗/
reprezentuje
velikosti
o
men²ích
p°idaných
private i n t
blok
− 1;
jedná
obsahuje
/∗ ∗ p o £ e t
tento
=
∗
private boolean
∗/
velikosti
childrenBySize ;
bloku
sizeRatio
/∗ ∗ P ° í z n a k ,
false ;
=
node ;
velikosti
private i n t
∗ ∗/
∗/
set°íd¥ni
dle
L i s t
NodeInfo
velikostí
children ;
se°azeni
/ ∗ ∗ p r v e k DOM s t r o m u
jejich
sizeComparator
childrenSorted
potomci
dle
∗/
bloku
L i s t
p°íznak ,
{
=
bloku
centerDistance
∗/ − 1; od =
st°edu
− 1; 20
stránky
∗/
∗/
∗/
/ ∗ ∗ NN k l a s i f i k o v a n á
private double
private double [ ] tvar
/∗ ∗ seznam
k l a s i f i k a c e NN
NNClassDist =
shape =
∗/
null ;
blok·
− 1;
podobné
L i s t
/∗ ∗ seznam
private
− 1;
∗/
private i n t
private
∗/
NNClassType =
/∗ ∗ p r a v d ¥ p o d o b n o s t
/∗ ∗
t°ída
blok·
s
velikosti
NNSimilarSizeBlocks
podobnými
L i s t
∗/
p ° í m ý m i potomky
NNSimilarKidsBlocks
=
∗/ =
null ; null ;
}
Výpis 9: Vnit°ní t°ída VisualBlock
4.2 Úprava blok· dle lokálního kontextu Výsledkem poslední £ásti VIPS algoritmu popsané na stran¥ 41 jsou vizuální bloky tvo°ící sémantickou hierarchickou strukturu stránky. Takto detekované £ásti stránky ov²em nejsou pro na²e pot°eby dosta£ující, protoºe neberou v úvahu lokální kontext jednotlivých element·.
Obrázek 1: Vizuální bloky (a) p·vodní detekované algoritmem VIPS (b) upravené dle lokálního kontextu.
21
Lokálním kontextem se rozumí nap°íklad to, ºe název konkrétního produktu zboºí v katalogu bude také obsaºen v prolinkovaném dokumentu obsahující detailní popis konkrétního produktu. Obdobn¥ je to s cenou £i ilustrativním obrázkem. Na základ¥ tohoto pozorování je pot°eba detekované bloky zkontrolovat a p°ípadn¥ podle pot°eb upravit, jak je znázorn¥no na obrázku £íslo 1. Klí£ovou roli v ov¥°ování t¥chto závislostí hrají práv¥ odkazy na stránce. Podmínky, návrhy algoritm· a detaily kone£ného °e²ení jsou popsány v následujících kapitolách.
4.2.1
Pozorování
Jak jiº bylo zmín¥no vý²e, k hledání závislostí mezi jednotlivými detekovanými bloky slouºí linky na stránce. B¥hem extrakce vizuálních blok· jsou v²echny odkazy detekovány a vkládány do jedné mnoºiny. Pro na²e ú£ely nejsou v²ak v¥t²inou pot°eba v²echny linky. Jednotlivé prvky mnoºiny detekovaných link· jsou p°ed svým zpracováním nejprve kontrolovány, zda spl¬ují následující vlastnosti:
•
Odkaz musí být v rámci stejné domény jako je doména zpracovávané stránky. e n¥které linky sm¥°ují mimo ur£itou doménu v²ak v n¥kterých p°ípadech odhalí aº jejich na£tení v integrovaném prohlíºe£i.
•
N¥které typy nebo hodnoty link· de novatelné v kon guraci jsou povaºovány za neplatné. Nap°íklad odkaz tvaru mailto:, nebo odkazy v rámci stejného html dokumentu (de nované znakem #).
Po ov¥°ení kaºdého linku je stránka nejprve zobrazena v prohlíºe£i. Poté je zpracována stejným zp·sobem jako stránka p·vodní, tudíº je také p°edloºena algoritmu VIPS a je zkonstruován strom jejích vizuálních blok·. Nyní je pot°eba oba stromy ur£itým zp·sobem porovnat a vyhledat závislosti.
22
Obrázek 2: Detekované bloky (a) p·vodní stránky (b) stránky odkazované linkem.
Vezm¥me op¥t stejný p°íklad, kdy p·vodní stránka je seznam produkt· a aktuáln¥ zpracovávaná je stránka s detailním popisem produktu odkazovaná z p·vodní stránky. Viz. obrázek £íslo 2. Z pozorování b¥hem implementace vyplývá, ºe n¥které £ásti stránky z·stávají £asto nem¥nné. Typicky to bývají r·zné druhy nabídek £i reklam. Tyto £ásti stránek jsou pro nás nezajímavé. Proto zde vzniká úkol ony rozdílné £ásti obou strom· vizuálních blok· reprezentujících dané stránky detekovat a dále je zpracovat. Tento problém se ukázal jako zásadní v celé £ásti ov¥°ování lokálního kontextu blok·, a proto následuje nastín¥ní p·vodních návrh· °e²ení spole£n¥ s nálním, fungujícím a implementovaným. V²echny detekované stromy mohou mít za listy vizuální bloky odpovídající pouze n¥kterému z t¥chto HTML tag·:
TEXT • •
obsahující vlastní text.
mající bu¤ text, nebo obrázek jako svého potomka a obsahující hodnoty
atribut· href a hodnoty p°ípadných potomk·.
•
![]()
obsahující hodnoty atribut· src a alt.
23
Ostatní prvky stromu bu¤ reprezentují n¥jaký HTML tag, nebo jsou virtuální vizuální bloky a spojují n¥kolik men²ích prvk· v celek. Problém ur£ení vzájemn¥ r·zných £ástí dvou stránek komplikuje skute£nost, ºe vizuáln¥ shodné £ásti mohou být v obou stromech pouze p°ehozené nebo posunuté. I tento p°ípad je pot°eba správn¥ odhalit. V²echny níºe uvedené návrhy postupují stejným zp·sobem a to tak, ºe od jednoho stromu umazávají shodné spole£né prvky, a tudíº po celém pr·chodu z·stanou pouze prvky odli²né. S nimi se pak dále pracuje.
4.2.2
Návrhy algoritm·
1. Prvním nápadem bylo porovnávat oba stromy od ko°ene s tím, ºe první strom se prochází postupn¥ a u druhého se ve stejné úrovni hledají odpovídající prvky.
•
Pokud je nalezena shodnost list· (HTML tag, velikost, obsah), prvek je odebrán.
•
Pokud je nalezena shoda vnit°ních prvk· (HTML tag, velikost), pokra£uje kontrola v obou prvcích rekurzivn¥.
•
Pokud shoda není nalezena, pokra£uje hledání v úrovni o jednu vy²²í a niº²í.
Pokud jsou nalezeny shodné, op¥t probíhá kontrola rekurzivn¥ u obou.
Pokud shoda není ani te¤ nalezena, jsou hledány prvky co nejvíce podobné (velikost, po£et potomk·, podobnost potomk·).
∗
Pokud je shoda nalezena, pokra£uje se rekurzivn¥.
∗
Pokud shoda nalezena není, je prvek ozna£en jako r·zný a proces detekce pokra£uje v dal²ích prvcích.
Problémem tohoto °e²ení je, ºe pokud by shodné prvky £i £ásti obou strom· byly v hladinách od sebe r·zných o více jak jednu, nebyly by detekovány. O²et°ení této situace by jiº dost v¥tvenou implementaci je²t¥ více zkomplikovalo, a proto bylo hledáno jiné °e²ení.
2. Dal²ím návrhem se zamý²lelo postupovat podobn¥, se zm¥nou sm¥ru procházení a za£ít v obou stromech s postupem od list· ke ko°en·m.
•
Pokud najdu v²echny shodné listy, odpovídající prvek je odebrán.
•
Pokud jsou prvku odebrány v²echny potomci, je také odebrán.
Jinak je prvek nechán ve výsledném rozdílovém strom¥.
Tento postup je p°ímo£a°ej²í a pr·hledn¥j²í. Má v²ak také jednu vadu na kráse a to tu, ºe je pot°eba detekovat v¥t²í shodné kusy, neº samostatné listy. Pokud se totiº n¥jaký list nachází v obou stránkách, na úpln¥ jiném míst¥ a s jinými sousedy, je detekován
24
chybn¥ jako shodný. Nap°íklad p·vodní stránka obsahuje tabulku produkt· s uvedenou cenou. Stránka s detailním popisem produktu obsahuje stejnou cenu, ale v úpln¥ jiném virtuálním bloku neº stránka p·vodní.
3. Posledním neúsp¥²ným nápadem byla jemná úprava p°edchozího algoritmu. Místo p°ímého mazání se shodné detekované prvky nejprve ozna£ily a aº kdyº byly ozna£eny v²ichni p°ímí potomci, byly odstran¥ny a prvek byl ozna£en k odstran¥ní. I toto °e²ení má v²ak své nedostatky a to konkrétn¥ p°ípad, kdy do jednoho stejného, v¥t²ího bloku na obou stránkách p°ibude jeden men²í r·zný blok. V tomto p°ípad¥ nebudou detekovány ani tyto shodné pod£ásti.
4.2.3
Implementovaný algoritmus
Obrázek 3: Detekované bloky stránky (a) p·vodní (b) odkazované (c) jejich rozdíl.
25
Poslední správn¥ fungující a také implementovaný algoritmus je následující. Algoritmus prochází stromy sm¥rem od list· ke ko°eni. Pozorování ukázalo, ºe mezi listem p·vodního stromu a jeho odpovídajícím listem stromu druhého mohou nastat následující vztahy:
•
Odpovídající prvek v·bec neexistuje a prvek se stane sou£ástí výsledného rozdílového stromu.
•
Odpovídající prvek je na shodném míst¥ jako ve stromu p·vodním. Detekce tohoto stavu je jednoduchá a v tomto p°ípad¥ je prvek z rozdílového stromu odstran¥n.
•
Poslední p°ípad je, ºe shodný prvek existuje, ale je v·£i p·vodnímu více £í mén¥ posunut. Zde je d·leºitá vlastnost, kterou mají zpracovávané stromy. Výsledné stromy VIPS algoritmu jsou vºdy upravovány tak, aby ºádný prvek nem¥l pouze jednoho potomka. Tím je zaru£eno ºe kaºdý prvek má alespo¬ jednoho sourozence a tato vlastnost je vyuºita p°i hledání a ov¥°ování shodných prvk·. Výjimku tvo°í odkaz jinam neº na webovou stránku, nap°íklad na obrázek, kde výsledný strom obsahuje pouze ko°en a jednoho potomka, vizuální blok odpovídající HTML tagu ![]()
. Pomocí soused· shodných prvk· nacházejících se v jiných £ástech strom· mohou být rozpoznány následující p°ípady. Vºdy jde o vztah shodného listu v novém stromu v·£i hledanému listu ve stromu p·vodním: 1. Prvek má v²echny sousedy shodné. 2. Prvek má v²echny p·vodní sousedy a n¥které nové. 3. Prvek nemá v²echny p·vodní sousedy, ale nemá ºádné nové. 4. Prvek nemá v²echny p·vodní sousedy a má n¥které nové. 5. Prvek nemá ºádného p·vodního souseda a má n¥které nové.
P°ípad 1 aº 4 odpovídá posunu nebo p°ípadné malé zm¥n¥ uvnit° bloku obsahujícího hledaný shodný prvek. Pokud byl celý blok pouze posunut, znamená to nalezení shodného listu a je smazán z rozdílového stromu. Nap°íklad v p·vodní stránce je hledaný list obsaºen v bloku p¥ti nejvíce prodávaných produkt·. Na nové stránce je tento seznam také obsaºen, ale p°ibude p°ed n¥j vizuální blok obsahující seznam p¥ti nejdiskutovan¥j²ích produkt·. D·leºitý je pro nás pouze p°ípad £íslo 5, který zna£í, ºe shodný list sice existuje, ale nachází se v jiném kontextu. Tento list je zapo£ítán do rozdílu. P°íkladem je op¥t stránka se seznamem produkt· obsahující cenu a stránka s detailním popisem konkrétního produktu, kde v obou je obsaºen stejný list obsahující HTML
TEXT
s ce-
nou, ale vºdy s jinými sousedy a také velmi £asto na jiném míst¥ stránky.
Kontrola shodnosti sousedních vizuálních blok· prvk· je zaloºena na následujících atributech:
26
•
U list· - velikost a obsah HTML tag·, jeº reprezentují.
•
U ostatních - jméno HTML tagu, jeº reprezentují (v p°ípad¥ virtuálního bloku je toto jméno rovno V), hodnota
DoC, protoºe p°idání nebo odebrání potomka toto
£íslo neovlivní. To samé bohuºel neplatí o velikosti bloku, a proto v tomto p°ípad¥ pouºita být nem·ºe.
4.2.4
Kontrola kontextu
Po úsp¥²ném výpo£tu rozdílu strom· p°íjde na °adu vlastní ov¥°ení místního kontextu.
private void if
executeRebuild ( VisualBlock
mainPage ,
VisualBlock
linkPage )
( isSameDomain ( domain , VisualBlock
diff
=
l i n k ))
{
intersect ( VisualBlock
mainPage ,
VisualBlock
/∗ ∗ T e s t
if
ve
zda
je
výsledném
hodnota
odkazu
rozdílovém
{
linkPage );
obsaºena
stromu
∗/
( d i f f . contains ( linkPage . searchData )) c h e c k A n d R e b u i l d T r e e ( mainPage ,
{
linkPage ,
diff );
} } }
Výpis 10: Pseudokód algoritmu kontrolování lokálního kontextu Odkaz na stránce má tvar textu nebo obrázku. P°ítomnost stejného obsahu ve výsledném rozdílovém stromu indikuje existenci lokálního kontextu. Jeho sou£ástí ov²em mohou být i ostatní sousední prvky v p·vodním stromu, které nejsou odkazy na stejné místo. Algoritmus kontroly proto postupuje následovn¥:
•
Získá okolní listy aktuáln¥ zpracovávaného odkazu v p·vodní stránce. Testy bylo okolí de nováno jako podstrom prvku v p·vodním stromu, který leºí v polovin¥ cesty od aktuálního odkazu ke ko°eni. Do testovací mnoºiny jsou zahrnuty v²echny listy, jeº je²t¥ nebyly ºádným zp·sobem p°euspo°ádány a zárove¬ bu¤ nejsou odkazy, nebo jsou linky sm¥°ující na stejné místo jako aktuáln¥ zpracovávaný odkaz.
•
V²echny prvky detekované mnoºiny jsou postupn¥ procházeny a je testována jejich existence v aktuálním rozdílovém stromu.
Pokud prvek není nalezen, nepat°í do místního kontextu a tím jeho kontrola kon£í.
Pokud prvek nalezen je, testuje se dále vzájemná poloha ploch, které na stránce zabírají. Z pozorování vyplynulo, ºe prvky pat°ící do stejného místního kontextu se na stránce nacházejí hlavn¥ vedle sebe £i pod sebou.
27
∗
Pokud se plochy neprotínají, prvek do kontextu nepat°í a jeho kontrola je ukon£ena.
∗
Pokud plochy spole£ný pr·nik mají, je dále otestována jejich vzájemná vzdálenost. Kdyº nejv¥t²í vzájemná vzdálenost je dostate£n¥ malá, pat°í prvky do spole£ného kontextu. V p°ípad¥, ºe detekovaný prvek není jiº sousedem analyzovaného linku, je p·vodní strom p°euspo°ádán tak, aby se jím stal a zárove¬ je detekovaný prvek odebrán ze v²ech mnoºin potenciálních soused·, ve kterých se do té doby vyskytoval. V opa£ném p°ípad¥ je prvek pouze p°idán do mnoºiny potenciálních soused· aktuáln¥ zpracovávaného odkazu.
•
V poslední fázi jsou zkontrolovány v²echny neprázdné mnoºiny potenciálních soused· v²ech analyzovaných odkaz·, nacházejících se na p·vodní stránce. B¥hem p°edchozího zpracování mohly do kontextu zpracovávaných link· p°ibýt nové bloky, £ímº se zm¥nil rozm¥r plochy kontextu. Zbylé prvky potenciálních soused· jsou se°azeny podle své vzdálenosti od plochy lokálního kontextu a pokud nyní jiº spl¬ují podmínky, jsou do n¥j p°idány (stanou se sousedy odkazu v p·vodní stránce). Tím je celý proces kontroly místního kontextu u konce a výsledkem je p°euspo°ádaný p·vodní strom vizuálních blok· stránky.
4.3 Klasi kace získaných dat Poslední £ástí celého procesu uvnit° programu DataExtraktor je snaha o ur£ení kategorie analyzované webové stránky. Pro pot°eby a rozsah této práce byly vybrány dv¥ existující kategorie, na kterých byl také navrºený algoritmus testován. Z kaºdé kategorii byly vybrány vzorky stránek, na jejímº základ¥ byly analyzovány spole£né i pro kaºdou kategorii speci cké vlastnosti. Bylo zanalyzováno kolem ²edesáti r·zných stránek z p°ibliºn¥ deseti r·zných £eských domén pro kaºdou kategorii. V procesu klasi kace konkrétních webových stránek hrají d·leºitou roli detekované vizuální bloky stromu, který je výsledkem p°edchozích dvou £ástí algoritmu. Nejvy²²í informa£ní hodnotu mají ty vizuální bloky, které nejsou listy a zárove¬ jejich v²echny potomci listy jsou. Díky p°euspo°ádání v²echny potomci t¥chto prvk· pat°í do stejného lokálního kontextu a díky vyvaºování celého stromu jsou tyto bloky co moºná nejv¥t²í. Konkrétní kategorie, testované atributy vizuálních blok· a detaily implementace jsou uvedeny v následujících podkapitolách.
4.3.1
Testované kategorie
U kaºdé kategorie byly na základ¥ pozorování de novány t°i typy detekovaných vizuálních blok· a rozpoznávány r·zné prvky, které se vyskytují na v¥t²in¥ stránkách dané kategorie. Konkrétní typ testovaných vizuálních blok· a existence speci ckých prvk· na stránce
28
slouºí k ur£ení výsledné kategorie celé stránky. P°i výb¥ru kategorií stránek bylo zohledn¥no o£ekávané velké mnoºstí zástupc·. Typy vizuálních blok· detekovaných uvnit° stránek byly de novány tak, aby jejich celkový po£et nebyl p°íli² velký a aby byly vzájemn¥ dost odli²né.
• eshop Do této kategorie pat°í v²echny internetové obchody s r·zným zam¥°ením. De novány byly t°i typy detekovaných vizuálních blok·:
Krátká informace o produktu/nabídce.
Detailní informace o produktu/nabídce.
R·zné menu, formulá°e a reklamy na stránce.
Analyzovány byly stránky z domén czechcomputer.cz, alza.cz, barbone.cz, ceskatelevize.cz, krasa.cz, nakupnicentrum.cz, kasa.cz, kontaktni-cocky-levne.cz, aukro.cz, iautodily.cz, eshop.autokelly.cz a annonce.cz.
• informativní weby Sem °adíme stránky nahrazující denní tisk £i £asopisy, které v ur£itém pravidelném intervalu p°iná²í nové informace. De novány byly op¥t t°i typy detekovaných vizuálních blok·:
Krátká informace o £lánku.
Detailní popis £lánku.
Nabídky, formulá°e a reklamy na stránce.
Analyzovány byly stránky z domén idnes.cz, astro.cz, novinky.cz, blisty.cz, root.cz, lidovky.cz, ihned.cz, aktualne.centrum.cz, denik.cz a re ex.cz.
4.3.2
De nice atribut·
Jak jiº bylo zmín¥no, k ur£ování kategorie stránky slouºí jednotlivé vizuální bloky v ní de nované. Bylo proto pot°eba de novat takové vlastnosti t¥chto blok·, na jejímº základ¥ budou mezi sebou porovnávány a zárove¬ budou dostate£n¥ re ektovat jejich vizuální vlastnosti. De novány byli následující atributy.
• jméno
- odpovídá názvu HTML tagu, který daný blok reprezentuje, nebo má hod-
notu V, pokud se jedná o blok virtuální.
• DoC • top
- £íselná hodnota udávající souvislost bloku v rozmezí 1 aº 10.
- horní vertikální sou°adnice bloku.
• height
- vý²ka bloku v obrazových bodech.
29
• left
- levá horizontální sou°adnice bloku.
• width
- ²í°ka bloku v obrazových bodech.
• position - £íslo ur£ující polohu bloku na stránce. Plocha stránky je rozd¥lena na dev¥t stejných £ástí (t°i °ádky, t°i sloupce) a hodnota udává polohu st°edu bloku v jedné z t¥chto devíti £ástí.
• distance • size
- vzdálenost st°edu bloku od st°edu stránky v pixelech.
- po£et obrazových bod·, které zabírá plocha bloku.
• sizeRatio • children • shape
- pom¥r velikosti bloku ku velikosti celé stránky v procentech.
- po£et potomk· daného bloku ve stromu vizuálních blok·.
- tvar bloku (horizontální/vertikální obdélník, £tverec).
• type - typ bloku, který se odvíjí od druh· jeho potomk· tvo°ící listy a které mohou být jedním z t¥chto druh·: odkaz, obrázek nebo £istý text. Na základ¥ r·zného po£tu potomk· a jejich r·zných druh· je de nováno t°icet p¥t r·zných typ· blok·.
• similarSize - po£et vizuálních blok· pouºitých ke klasi kaci celé stránky, kte°í mají maximáln¥ o deset procent r·znou velikost neº daný blok.
• similarKidsCount
- po£et vizuálních blok· pouºitých ke klasi kaci celé stránky
mající po£et potomk· maximáln¥ o dvacet procent r·zný neº daný blok.
4.3.3
Implementace
V¥t²ina parametr· bloku je aktualizována b¥hem jejich vytvá°ení i následném p°ípadném upravování. U blok· ozna£ených pro klasi kaci stránky jsou dopo£ítány hodnoty zbylých vý²e zmín¥ných atribut·. Sou£ástí kon gurace kaºdého z posuzovatel· je cesta k souboru s trénovacími daty konkrétní pouºité neuronové sít¥. Tato data byla získána ru£ním ur£ením t°íd v²ech blok· konkrétní kategorie. Data jsou uloºena v textovém souboru speciálního vlastního formátu s názvem ar pouºité knihovny Weka. @RELATION
eshop
@ATTRIBUTE name
{ DIV , FORM, L I , OL , P , SPAN , TBODY, TD, TH , TR , UL , V}
@ATTRIBUTE
doc
numeric
@ATTRIBUTE
top
numeric
@ATTRIBUTE
height
@ATTRIBUTE
left
@ATTRIBUTE
width
@ATTRIBUTE
position
numeric
@ATTRIBUTE
distance
numeric
numeric
numeric numeric
30
@ATTRIBUTE
size
numeric
@ATTRIBUTE
sizeRatio
@ATTRIBUTE
children
@ATTRIBUTE
shape
@ATTRIBUTE
type
@ATTRIBUTE
similarSize
@ATTRIBUTE
similarKidsCount
@ATTRIBUTE
class
numeric numeric
numeric numeric numeric numeric
{1 ,2 ,3}
@DATA DIV , 5 , 1 3 0 , 1 3 , 4 7 , 8 3 3 , 1 , 1 1 7 5 , 1 0 8 2 9 , 0 , 8 , 1 , 3 , 2 , 2 , 3 LI , 7 , 7 5 7 , 2 4 , 7 6 1 , 1 5 4 , 2 , 6 6 3 , 3 6 9 6 , 0 , 2 , 1 , 3 5 , 8 , 1 9 , 1 ...
Výpis 11: Ukázka eshop.ar První °ádek ur£uje jméno relace, dal²í °ádky za£ínající @ATTRIBUTE de nují v p°edchozí £ásti vypsané atributy kaºdého vizuálního bloku v£etn¥ posledního ur£ujícího t°ídu bloku. Po °ádku @DATA následují jednotlivé záznamy. P°i spu²t¥ní programu DataExtraktor jsou vytvo°eny v²echny nade nované instance posuzovatel· (kon gura£ní soubor critics.xml). Odpovídajícím neuronovým sítím jsou p°edloºena p°iloºená trénovací data p°ípadn¥ spole£n¥ s de novaným ltrem a sít¥ jsou nau£eny a p°ipraveny ke klasi kaci. Vlastní klasi kace jednotlivé stránky probíhá následovn¥:
•
Po extrakci a úprav¥ stromu dle lokálního kontextu jsou vybrány vhodné bloky pro klasi kaci.
•
U v²ech vybraných blok· jsou aktualizovány jejich atributy.
•
V²echny bloky jsou vloºeny do vnit°ní datové struktury knihovny Weka jako kdyby byly na£teny ze souboru typu ar .
•
Tato data jsou p°edána v²em instancím neuronových sítí, kde kaºdá z nich ur£í pravd¥podobnosti rozd¥lení svých t°íd pro jednotlivé bloky. Pravd¥podobnosti vít¥zných t°íd jsou zaznamenány.
•
T°ída odpovídající neuronové síti s nejv¥t²í celkovou pravd¥podobností v²ech klasi kovaných blok· je ozna£ena za vít¥ze.
•
Pokud by existovaly dv¥ shodné vít¥zné t°ídy, rozhodne procento po£tu nalezených shodných prvk·.
•
Vít¥zná t°ída ur£uje t°ídu analyzované stránky.
31
•
Výsledky jsou zobrazeny v záloºce
Classify results a uloºeny do textového souboru
s p°íponou dec (DataExtractor Classifycation).
4.4 Problémy B¥hem návrhu i samotné implementace bylo nutné °e²it n¥kolik mén¥ £i více závaºných problém· a rozhodnutí. Ty nejd·leºit¥j²í, které nebyly zmín¥ny v p°edchozích £ástech práce, jsou uvedeny níºe.
• HTML Jak jiº bylo zmín¥no v práci, díky rozmanitosti HTML existují stránky, které nespl¬ují W3C standardy. Prvky stránek, které nespl¬ovaly tato doporu£ení, byly sice detekovány, ale nebylo jich mnoho a £asto se jednalo o drobné £ásti, a proto nezp·sobovaly ºádné velké problémy. Nap°íklad se jednalo o stránku, kde za koncovým tagem
