Hlavní navigace

Architektury a modely webových strojů

Karel Pánek

Také vás někdy zajímalo, jaké nástroje používají pro práci s velkými objemy informací v CIA nebo NASA? V dnešním pokračování se podíváme blíže na strukturu webových vyhledávačů a představíme i stroj těmito agenturami používaný. Zároveň s tím popíšeme některé základní modely, na kterých fulltextové stroje pracují.

Webový vyhledávací stroj se od svého běžného bratříčka, kterého používají například v knihovnách, liší kvůli odlišným podmínkám, ve kterých pracuje. Předně je pro něj poměrně obtížné získat data k indexování v krátkém časovém intervalu. S touto problematikou (resp. s určením, co tahat nejdříve) může do jisté míry pomoci již zmíněná technika PageRank, ale ani ta není všemocná. Proto prvotní indexace stojí poměrně dost času, tedy pokud ji neprovádíme nadmíru agresivně. Tím se ale mezi správci webů staneme nevhodně populárními.

Dalším problémem je i to, že dokumenty v době řešení úkolů nemusíme mít přímo přístupné, a proto by techniky měly využívat algoritmů, které nepotřebují k zodpovídání uživatelských dotazů originální texty.

Centralizovaná architektura

Všechny české stroje, i naprostá většina zahraničních, využívají nejjednodušší 2-stupňovou architekturu. Její první stupeň (crawler) dokumenty stahuje a předzpracovává a návazný stupeň (indexer) z těchto dat vyrábí požadovaný index.

Základní problém, kterému toto řešení čelí, je objem dostupných dat přístupných v celosvětové internetové síti. Je jen otázkou technických omezení, kdy už nebude možné všechna data stahovat a vyrábět jeden centralizovaný index. Tomu by měla zabránit právě distribuovaná architektura.

Distribuovaná architektura

Základní myšlenka tohoto typu řešení spočívá v procesu zpracování dat na jednom z uzlů a v následné distribuci výsledku do zbytku systému. Pro implementaci ji využil jeden z prvních představitelů  – stroj Harvest.

Tento stroj v současnosti používá americká CIA a NASA, a byl navíc jako „public domain software“ včleněn do mnoha komerčních produktů (např. Netscape Catalog Server). Pokud si budete chtít zkoušet vlastní instalaci, nebuďte šokováni na dnešní dobu dosti dřevním webovým rozhraním, protože jeho kvalitní srdce bije právě pod touto slupkou. Stejně tak věnujte dostatečnou pozornost procesu reindexovaní. Pokud provedete chybu v jeho nastavení, má démon Harvestu velkou touhu padat právě v reindexačním procesu.

Harvest jako jeden z prvních představil systém Gathererů a Brokerů. Gatherer je zodpovědný za shromáždění a zpracování informací z jednoho (nejčastěji lokálního) nebo více webových serverů. Broker pak získává předzpracovaná data z jednotlivých gathererů nebo i dalších brokerů. Na základě těchto informací následně obnovuje jím spravovaný index, s jehož pomocí pak řeší uživatelské dotazy.

Je-li systém brokerů dobře vyladěn, umožňuje obrovské úspory v indexačním procesu. Je to dáno tím, že daný broker distribuuje své výsledky dalším brokerům, kteří je pak nemusí pracně získavat z gathererů. Kromě toho je Harvest vybaven i replikačními mechanismy. Ty umožňují rychle přemostit a nahradit chybující systémy, příp. zajišťují posílení systému rozkladem zátěže.

Modely

Abychom se mohli postupně odlepit od teoretických úvah a popisů, bude nutné zmínit některé z modelů vyhledávacích strojů. Model je vlastně myšlenkový princip, na kterém stroj běží. Takových principů existuje několik a významně modifikují implementaci takových postupů, jako je sběr zpěrné vazby nebo clusterovaní.

V dnešní době žádný skutečně dobrý vyhledávač nepracuje na základě jediného z modelů, které představíme. Spíše se hledají cesty, jak několik modelů sladit tak, aby se jejich negativa vzájemně potlačila. Výpočty, které budeme postupně představovat, vycházejí ze základních implementací a nejsou vhodné pro velké báze textů, kde ve všech případech dochází k znásobení veškerých negativních aspektů daného modelu.

Pro jednoduchost označme di i-tý dokument; q dotaz složený ze slov q1 až qt; relevanci, nebo-li podobnost, dotazu q a dokumentu di jako simdiq.

Boolský model

Tento model je jeden z nejstarších vůbec a v minulosti býval hojně používán v knihovnických informačních systémech. Na dotaz vrací jako výsledky ty dokumenty, které obsahují slova z dotazu. V základní variantě neumožňuje stanovování relevance a funkce podobnosti je vyčíslována pouze s hodnotami 0 (zásah nenalezen) nebo 1 (zásah).

V pozdějších variantách byl boolský model obohacen o jemnější výpočet relevance, viz. výpočet Q strojem Webfast. V příslušné recenzi jsem ukázal dotazy, které vedou buď k příliš malé nebo naopak příliš rozsáhlé odpovědi na dotaz. To je také hlavní nevýhoda tohoto modelu, který bývá pro své výsledky označován jako model pro získávání dat, nikoliv informací.

Vektorový model

Vektorový model umožňuje jemnější výpočet relevance. Myšlenka je opět velice jednoduchá. Každý text či dotaz (prostě jakákoliv skupina slov) je reprezentován bodem v n-rozměrném souřadnicovém systému. Tento bod představuje i vektor (začínající v počátku souřadnic), a tak dostal model i svůj název.

Konstrukce bodů je taková, že čím blíže jsou k sobě, tím více reprezentují podobný (dokonce téměř totožný) text. Dále ale budeme hovořit o vektorech, nikoliv bodech. Možná si pamatujete, že skalární součin dvou vektorů vychází největší, pokud mají tyto vektory stejný směr. Jako nulový vychází, pokud mají vektory směr opačný. Tohoto jevu bývá s úspěchem využito pro vlastní kalkulaci podobnosti.

Jak se stanovují vektory? Předpokládejme, že v textech máme n rozdílných slov. Toto n také určuje onu n-rozměrnost našeho vektorového systému. Každý vektor pak na souřadnici – odpovídající danému slovu – obsahuje jeho četnost (ať již v jednotlivém dokumentu, nebo třeba dotazu).

Podobnost stanovíme jako skalární součin dvou vektorů – ty budeme pro přehlednost označovat jako v(). V případě podobnosti dotazu a dokumentu pak tato formule vypadá takto:

simv(dj),v(q) = sum( i=1..n; wi,j wi,q )

kde v(dj) = (w1,j,..wn,j) a v(q) = (w1,q,..wn,q). Hodnoty wi,j udávají počet slova ti v j-tém dokumentu. Podobně wi,q udává počet slova ti v dotazu q.

V pokročilých implementacích již wi,j nepředstavuje četnost, ale naopak důležitost, která má většinou výchozí kalkulaci v četnosti.

Dále nebývá vhodné nechat růst vektory (jejich délku) nade všechny meze. Proto je výhodné normalizovat používané vektory na jednotkovou délku.

Tím je pak do značné míry zajištěno, že původně dva krátké vektory (protože obsahovaly jen malý počet slov), jdoucí týmž směrem, nebudou při výpočtu podobnosti pomocí skalárního součinu přebity dvěma velice dlouhými vektory, které již ale nejdou tak úplně týmž směrem. Tak dostáváme základní formuli:

simv(dj)v(q) = sum( i=1..n; wi,j wi,q ) / ( length( v(dj) ) length( v( q ) ) )

Nakonec ještě zmíním způsob, kterým lze efektivněji kalkulovat wi,j. Četnosti slov, které jsme původně používali jako wi,j, označme nyní freqi,j (frekvence i-tého slova v j-tém dokumentu). Pak jako normalizovanou frekvenci použijeme:

tfi,j = freqi,j / max( all l; freql,j )

Ještě spočteme inverzní frekvenci dokumentu pro i-té slovo, idfi. Pozn.: vysvětlení této kalkulace je obdobné jako při výpočtu ief (viz. metavyhledávače).

idfi = log( N/ni)

kde ni je počet dokumentů obsahujících i-té slovo a N je počet všech dokumentů.

Pak můžeme určit wi,j takto (jedná se o skutečně jednu z nejlepších formulí):

wi,j = tfi,j . idfi

Pokud uvidíte stroj s vyhodnocováním tf.idf, jedná se o stroj právě s variací této formule. Její další zkvalitnění přineseme ve zvláštní kapitole.

Pro výpočet w-hodnot pro dotaz q se ale s ohledem na malý počet slov v dotazu používá většinou jiná kalkulace. Asi nejpoužívanější je formule od Saltona a Buckleye:

wi,j = (0.5 + 0.5 tfi,q ) idfi

Dodatek

Mezi základní modely patří ještě pravděpodobnostní model, fuzzy model, neuronový, latentní sémantický a spousta modifikací Beyesovských sítí. Ty zatím pomineme pro jejich celkovou složitost a v neposlední řadě i obtížnost zápisu a popisu v HTML. V dalším díle se proto budeme zabývat hlavně praktickými vylepšeními základních formulí a eliminaci některých nevýhod obou představených modelů.

Našli jste v článku chybu?

7. 2. 2002 22:07

k.p. (neregistrovaný)
Ne, ke zmateni pojmu nedoslo. Skutecne se pouziva skalarni soucin. Sim pak znamena similarity (podobnost).

7. 2. 2002 13:37

J.K. (neregistrovaný)
Jaké meze kritiky myslíte? To jste vymyslel četnosti slov sám, vektorový model také - Vy jste přece měl citovat první. A to jste neudělal proč?
Lematizaci sem pletu proto, že pojem "četnost slova v dokumentu" je pro ohebné jazyky potřeba správně nadefinovat. Hned máte možnost mi odepsat, na jakou definici se odvoláváte Vy.
Pokud na žádnou, tak mi promiňte, že myslím a mluvím (vlastně píši).

Vitalia.cz: Pravda o přibírání na zimu

Pravda o přibírání na zimu

Podnikatel.cz: V restauraci bez cigaret? Sněmovna kývla

V restauraci bez cigaret? Sněmovna kývla

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Vitalia.cz: Analýza letáků: Na co lákají do prodejen?

Analýza letáků: Na co lákají do prodejen?

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

Root.cz: Mirai má nový cíl 5 milionů routerů

Mirai má nový cíl 5 milionů routerů

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

DigiZone.cz: Perspektivy TV v roce 1939 podle časopisu Life

Perspektivy TV v roce 1939 podle časopisu Life

120na80.cz: Stoná vaše dítě často? Upravte mu jídelníček

Stoná vaše dítě často? Upravte mu jídelníček

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: Nahradí sluch, ale zvuk je zcela jiný

Nahradí sluch, ale zvuk je zcela jiný

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Root.cz: Kamery Sony se dají ovládnout na dálku

Kamery Sony se dají ovládnout na dálku