Obsah Dal¹í Pøedchozí

5.2.3 Vstupní filtry

Filtry jsou souèástí vyhledávacího serveru. Jejich úkolem je pøevod dat (dokumentù i dotazù) do jednotného formátu. Jedná se o pøevod na termy, se kterými potom pracuje databázové jádro vyhledávacího serveru. Termem nazýváme slovo získané z dokumentu a ohodnocené váhou. Váha termu je hodnota urèující èetnost výskytu a význam termu v dokumentu. Vìt¹í váhu mají zvýraznìná nebo opakující se slova.

Dokumenty, které zadá u¾ivatel k indexaci, jsou rùzných typù, ale i v rùzných typech kódování. Také termy lze upravit èi nevhodné odstranit. Proto je pøevod dat na termy rozdìlen na nìkolik èástí. Ka¾dou specifickou èást provádí jeden filtr. Napøíklad filtr "Code" dokument pøekóduje zatímco filtr "CutHTML" získá slova z HTML dokumentu. Ka¾dý filtr má tedy svùj úkol a teprve zøetìzením v¹ech filtrù dostaneme termy v po¾adované formì.

5.2.3.1 Co je to filtr

Zpracování dokumentu (i dotazu) je rozdìleno na nìkolik èástí. Ka¾dý filtr obstarává pouze urèitou èást. O existenci ostatních filtrù nemá ¾ádné informace a je na nich zcela nezávislý. Ka¾dý filtr je realizován krátkým programem, který plní urèitou èinnost pøi zpracovávání dokumentu nebo dotazu. Jedná se o program, který na vstupu dostane data, ty zpracuje a po¹le na výstup. Vhodným zøetìzením (spu¹tìním) více filtrù pak dostaneme potøebný výsledek pro databázové jádro vyhledávacího serveru. Ka¾dý filtr mù¾e mít vlastní konfiguraci, která je ulo¾ena v pøíslu¹ném souboru. Filtr si tento soubor naète a podle konfigurace zpracuje data, která obdr¾í na vstupu. Napøíklad filtr získávající jednotlivá slova z dokumentu si naète tabulku, kde zjistí, které znaky se mohou ve slovech vyskytovat (ostatní znaky jsou pova¾ovány za oddìlovaèe). Získaná slova posílá na výstup. Dal¹í filtry tak mohou pracovat ji¾ se slovy (lematizace, stoplist,...).

Ke ka¾dému dokumentu pøíslu¹í hlavièka dokumentu. Hlavièka obsahuje základní informace o dokumentu. Podle nastavení polo¾ek v hlavièce se rozhoduje o tom, které filtry se spustí. Hlavièka také mù¾e slou¾it pro pøedávání informací dal¹ím filtrùm. Pøi volání filtru je tedy potøeba zadat datový vstup, datový výstup a také hlavièku. Napøíklad filtr pro pøekódování si v hlavièce zjistí druh kódování, naète si pøíslu¹nou kódovací tabulku a dokument pøekóduje. Nìkteré polo¾ky v hlavièce nastaví na zaèátku aplikaèní server, dal¹í pak mù¾e vyplnit libovolný filtr. Nastavení mù¾e ovlinit i u¾ivatel zadáním pøíslu¹ných hodnot (napøíklad lze specifikovat v jakém jazyce u¾ivatel dotaz zadává, èi jaký dokument posílá k indexaci,...).

Polo¾ky obsa¾ené v hlavièce:

První tøi polo¾ky obsahují doplòující informace o dokumentu a jsou s termy ulo¾eny v databázi. Dal¹í polo¾ky jsou potøebné pro správnou èinnost filtrù. Polo¾ka charset urèuje druh kódování. Se systémem Agent jsou dodávány následující tabulky: iso-8859-2 (pou¾ívané na systémech Unix - støední Evropa), win-1250 (kódování pro Windows - støední Evropa) a MacCE (kódování na poèítaèích Macintosh - støední Evropa). Typ dokumentu (type) urèuje o jaký textový dokument se jedná. Napøíklad HTML, T602, Word nebo pouze èistý TEXT. Dokument mù¾e být vícejazyèný. Jazyk dokumentu (language) je tedy øetìzec obsahující zkratky jazykù, které se v dokumentu vyskytují. Doporuèuji tøípísmené mezinárodní zkratky (napø. "ENG CZE FRA SVK RUS GER SPA ..."). Dal¹ími polo¾kami v hlavièce jsou volné polo¾ky (free1, free2 a free3). Tyto polo¾ky filtry nevyu¾ívají, ale mohou je pou¾ít novì vzniklé filtry. Buï pro pøedávání informací mezi jednotlivými filtry nebo pro nastavaní dal¹ích informací o dokumentu (napøíklad velikost dokumentu, poèet slov, ...). Pøedposlední polo¾kou je parametr path. Ten mù¾e být nastaven vyhledávacím serverem nebo pomocí pøíkazu SET v konfiguraèním souboru pro FilterManager (viz. dále). Polo¾ka obsahuje adresáøovou cestu k adresáøi urèenému pro filtry. Filtry tuto polo¾ku pou¾ívají pøi hledání konfiguraèních souborù a tabulek. Poslední polo¾ka (error) je pro zapisování chyb. Pokud nìjaký filtr zaznamená chybu pøi své èinnosti, tak ji zapí¹e do této polo¾ky.

5.2.3.2 Zøetìzení filtrù.

Jak bylo øeèeno, pro zpracování dokumentu se pou¾ívá nìkolik filtrù v urèitém poøadí. Kdy a jaký filtr bude zavolán urèuje správce filtrù - FilterManager. FilterManager podle zadané konfigurace volá filtry jeden po druhém. Konfigurace (tj. poøadí v jakém se filtry volají) je v konfiguraèním souboru. Cesta k tomuto souboru je jedním ze tøí parametrù, které FilterManager dostane pøi volání. Poøadí volání jednotlivých filtrù je následující:

  1. Urèení typu dokumentu
  2. Urèení typu kódování
  3. Pøekódovaní dokumentu
  4. Rozdìlení na termy
  5. Urèení jazyka
  6. Lematizace
  7. Zpracovaní víceslovných termù
  8. Vyøazení slov podle Stoplistu
  9. Spoèítání výskytù jednotlivých slov

Nìkteré filtry mohou být vynechány, nìkteré mohou být spu¹tìny i vícekrát. Napøíklad je-li znám typ kódování není tøeba volat filtr pro urèení typu kódování. Filtr pro sluèování termù mù¾eme zavolat vícekrát, aby se po ka¾dém volání zmen¹il objem dat. Na stejné úrovni se mù¾e objevit nìkolik filtrù, volá se v¾dy jen ten správný. Napøíklad u filtrù pro získávání slov (termù) se pou¾ije filtr podle typu dokumentu (HTML, TEXT). V jiném pøípadì se pou¾ije i více filtrù. Napøíklad pro dvojjazyèný dokument se zavolají dva stoplisty (filtry vyhazující "nevhodná" slova). Pokud o dokumentu nic nevíme, spustí se témìø v¹echny filtry. Pokud je dokument vícejazyèný spustí se i v¹echny Stoplisty a Lematizátory (v podstatì se spustí úplnì v¹echny filtry). Bì¾ný HTML dokument má velikost do 10KB a pøefiltrování trvá øádovì desítky milisekund (100-200 ms). Pokud se spustí v¹echny filtry, tak pøefiltrování trvá maximálnì 500 ms. Chceme-li pøefiltrovat vìt¹í dokument, tak èasová nároènost roste, nebo» proudy dat (class strstream) zpomalují èinnost filtrù. Vìt¹í dokumenty (o velikosti pøibli¾nì 100KB) se pøefiltrují do nìkolika vteøin. Filtrace pøi pøidávání dokumentu do databáze tolik nepodléhá rychlostním nárokùm, ale vyhodnocení dotazu musí být co nejrychlej¹í. To filtry splòují, nebo» krátký dotaz je pøefiltrován okam¾itì. Je¹tì jeden faktor ovlivòuje rychlost filtrù. První spu¹tìní filtrù je pomalej¹í, nebo» se musí naèíst DLL knihovny. Ka¾dé dal¹í volání je ji¾ mnohem rychlej¹í.

Urèení filtrù, které se pou¾ijí pro filtraci, a následné urèení jejich poøadí, s sebou pøiná¹í urèité problémy.

Konfiguraèní soubor vhodný pro velké dokumenty nemusí být vhodný pro velmi krátký dokument èi dotaz. Je mo¾né vytvoøit nìkolik konfiguraèních souborù a zále¾í na konfiguraci FilterManageru, který si zvolí. Postup vytváøení a editace konfiguraèního souboru je uveden v Pøíruèce administrátora (kapitola 9.4).

5.2.3.3 Formát dat

Fomát dat je pevný a musí ho dodr¾ovat v¹echny filtry. Syntaxe vychází z jazyka SGML. Jedná se o vkládání takzvaných "tagù" mezi data textového dokumentu. Termy získané z dokumentu se oznaèují tagem <T>. Na zaèátku se nevyskytují ¾ádné tagy <T>. Nìkteré filtry získávají z dokumentu jednotlivé termy (vkládají tag <T>) a ty jsou následnì vyu¾ity dal¹ímy filtry. Jedná se o filtry, které pracují s termy (lematizace, stoplist). Tyto filtry mezi daty hledají tagy <T> a ty dále zpracovávají. Data, která si filtry pøedávají, mají nasledující formát: 

<DATA>
<T WEIGHT=2>krabice</T>
<T WEIGHT=1>internet</T>
<T>and</T>
<T WEIGHT=12>house</T>
</DATA>

- Jediný povinný "tag" je <DATA>, ostatní tagy jsou nepovinné.
- V souèasné dobì filtry znají pouze dva tagy: <DATA> a <T>.
- Je mo¾né zavést dal¹í tagy i parametry, ale na¹e filtry je budou ignorovat (napø. pro oznaèení víceslovných termù).
- Filtry zpracovávají pouze data uzavøená tagem <DATA>.

Parametry tagù:

Slovo ignorovat chápu, tak ¾e se neznámé tagy èi parametry budou pouze pøedávány na výstup (ale neztratí se). I pøidáním parametru u tagu <T> se nic nezmìní.

Proè jednotný formát dat ?
V¹echny filtry mají stejné chování. Naèítají data ze vstupu a zapisují na výstup. Data jsou v textové podobì a datová struktura je proto pro v¹echny filtry stejná. Filtry tedy nepotøebují vìdìt o existenci ostatních filtrù. Neví ani, v jakém poøadí budou spu¹tìny. Filtr hledá v datech to, co umí zpracovat, ostatní ignoruje. Pokud  chce u¾ivatel pøidat nový filtr, jednodu¹e podle tagù dokument pøefiltruje. Napøíklad pokud spustíme jako první filtr StopENG, tak ten ¾ádné termy nenajde a pouze data pøedá na výstup v nezmìnìné podobì (ale datùm vlastì rozumìl).

Pøidání nového filtru.
U¾ivatel si mù¾e vytvoøit vlastní filtr a v konfiguraèním souboru specifikovat, kdy se má zavolat. Filtr nesmí ru¹it ¾ádné tagy a ani jemu nesrozumitelná data by nemìl mazat. Jedním z filtrù, který pøipadá v úvahu, je napøíklad filtr pro zpracování víceslovných termù. Dal¹ím je napøíklad filtr, který se bude sna¾it v dokumentu hledat autora nebo datum vzniku, èi poslední aktualizace.

5.2.3.4 Popis jednotlivých filtrù.

Filtr TryHTML

Filtr zji¹»uje, zda se jedná o HTML dokument. Filtr pouze ète data a hledá tag <HTML>. Pokud je tag nalezen, tak se nastaví v hlavièce typ dokumentu na "HTML", jinak se hlavièka dokumentu nezmìní. Data se pøedávají na výstup nezmìnìna. Tento filtr nemá ¾ádný konfiguraèní soubor. Pokud se v HTML dokumentu hledaný tag nevyskytuje, tak získávání termù z dokumentu by mìl provádìt filtr pro èistý text (CutTEXT). Ten samozøejmì slova z dokumentu získá, ale k nim pøipojí i slova pøedstavující HTML tagy. Dnes se v¹ak ji¾ chybné HTML dokumenty na Internetu prakticky nevyskytují.

Filtr Charset

Filtr zji¹»uje kódování dokumentu (tj. o jakou znakovou sadu se jedná).

Filtr si naète v¹echny kódovací tabulky. Ka¾dé kódování má své vlastní poèítadlo znakù. V konfiguraèním souboru si filtr zjistí, které znaky jsou "dobré" a které "¹patné" (viz. konfiguraèní soubor). Potom ji¾ filtr ète data (znak po znaku). Ka¾dý znak pøekóduje podle v¹ech tabulek a zjistí, jestli se znak pøekóduje na "dobrý". Pokud ano, tak se zvý¹í hodnota poèítadla pøíslu¹ného kódování. Mezi kódování patøí i "win-1250". V tomto pøípadì se znak nepøekódovává, ale pouze se testuje, zda patøí mezi "dobré". Nakonec se vybere kódování, které získá nejvíce "dobrých" znakù (v pøípadì rovnosti více kódování má pøednost kódování "win-1250"). Pokud bude konfiguraèní soubor obsahovat velké mno¾ství dobrých znakù, mù¾e se stát, ¾e filtr správnì nerozpozná kódování a èasto bude upøednostòovat kódování "win-1250" (nebo» dokument bude dobrý podle jakékoli kódovací tabulky). Proto¾e filtr ka¾dý znak porovnává se v¹emi tabulkami, není vhodné mít v adresáøi velké mno¾ství tabulek, nebo» by zpomalovaly èinnost filtru. Kódování lze zjistit i z HTML dokumentu (z META tagu), ale to nemusí být správné, nebo» dokument se vìt¹inou pøekódovává buï na stranì serveru nebo na stranì klienta. Toto øe¹ení  tedy v systému Agent není zahrnuto.

Filtr Code

Filtr pøekóduje dokument ze zadaného kódování do "win-1250". V hlavièce je nastaveno kódovaní dokumentu. Filtr si podle jména kódování najde pøislu¹nou tabulku na disku. Jméno kódování v hlavièce musí pøesnì odpovídat jménu souboru na disku (bez koncovky ".tab"). Potom podle tabulky pøekóduje celý dokument.

Filtr CutHTML

Filtr z HTML dokumentu získá termy (odstraní HTML tagy). Velká písmena se pøevedou na malá (pokud chce u¾ivatel velká písmena zachovat tak staèí v konfiguraèním souboru pøepsat kódy pøíslu¹ných znakù na hodnotu "Y"). Teèka slou¾í jako oddìlovaè. To znamená, ¾e datum 24.12.1998 se rozpadne na tøi èísla. To mù¾e nìkdo pova¾ovat za nevýhodu, ale pokud hledáme dokument obsahující text "December 1998", tak dokument obsahující datum 24.12.1998 bude mezi nalezenými dokumenty a to je spravné. To samé platí pro URL adresy. Výsledkem dotazu "mff.cuni.cz" budou v¹echny dokumenty, obsahující libovolnou URL adresu z domény mff. Pokud se v dokumentu vyskytne tag <TITLE>, tak z nìj získá název dokumentu a nastaví ho do hlavièky.

Nejprve si filtr naète pøíslu¹né konfiguraèní soubory. Soubor "usechar.cfg" obsahuje informace o tom, které znaky slou¾í jako oddìlovaèe. Soubor "easytags.cfg" obsahuje váhy jednotlivých tagù a soubor "entita.cfg" obsahuje pøepis HTML entit (napø &iacute; znamená "í").

Filtr ète dokument - znaky patøící do textu (objeví se po zobrazení HTML prohlí¾eèem) si uchovává v bufferu. Kdy¾ pøijde znak, který slou¾í jako oddìlovaè, tak ze znakù v bufferu vytvoøí nový term a po¹le ho na výstup. Váhu termu urèí aktualní váha, která se mìní v závislosti na HTML tazích. Pokud pøijde na vstupu tag HTML jazyka, tak se filtr podívá do svého seznamu. Pokud pøíslu¹ný tag najde, upraví aktualní váhu. Pokud má tag nastaveno zalomení (viz. Pøíruèka administrátora), vyprázdní se buffer (term se po¹le na výstup). Neznámé tagy se zahazují. U¾ivatel si ale mù¾e pøidat i vlastní metodu na zpracování slo¾itìj¹ího HTML tagu. Musí ji v¹ak naprogramovat a potom znovu zkompilovat DLL knihovnu. Takto byla vytvoøena metoda na zpracování tagu <IMG> (HTML tag pro vlo¾ení obrázku). Metoda v tagu najde alternativní text (zobrazuje se místo obrázku) a ten zaøadí mezi termy. Jestli¾e filtr narazí na HTML entitu, tak ji hledá v seznamu. Pokud ji najde, pøidá do bufferu znak, který entita vyjadøuje. Jinak se nejedná o HTML entitu a v¹echny pøeètené znaky se pøidají do bufferu.

Filtr CutTEXT

Filtr z textového dokumentu získá termy.

Nejprve si filtr naète konfiguraèní soubor, aby vìdìl, které znaky slou¾í jako oddìlovaèe (soubor "usechar.cfg"). Podrobnosti naleznete u filtru CutHTML. Filtr ète dokument a znaky nepatøící mezi oddìlovaèe si uchovává v bufferu. Kdy¾ pøijde znak, který slou¾í jako oddìlovaè, tak ze znakù v bufferu vytvoøí nový term a po¹le na výstup. Buffer se vyprázdní a ètení pokraèuje a¾ do konce.

Filtr TryCZE

Filtr zji¹»uje, zda se jedná o dokument v èe¹tinì. Filtr si naète z konfiguraèního souboru èeská slova. Potom ète ze vstupu termy (tag <T>) a porovnává je se slovy v konfiguraèním souboru. Jakmile najde term shodný s nìjakým slovem, tak se ji¾ pouze pøefiltrují data na výstup a do hlavièky se pøidá èeský jazyk - hodnota je "CZE". Filtr tedy hledá zadaná slova v dokumentu a pøi prvním úspìchu èinnost ukonèí.

Filtr TryENG

Filtr zji¹»uje, zda se jedná o dokument v angliètinì. Filtr má stejné chování jako filtr TryCZE. Pouze v pøípadì úspìchu se do hlavièky pøidá anglický jazyk - hodnota je "ENG".

Filtr LemCZE

Filtr lematizuje termy (odstraní koncovky u èeských slov). Filtr ète jednotlivé termy (tag <T>) a ty lematizuje. Tento filtr nepou¾ívá ¾ádný konfiguraèní soubor.

Pøi vyhledávání slova v textu vìt¹inou nepotøebujeme rozli¹ovat jeho jednotlivé tvary (pády, osoby), ale zajímá nás pouze výskyt slova v textu. K nalezení základního tvaru slova se v DIS pou¾ívá filtr zvaný lematizátor. Pou¾ití tohoto filtru pøiná¹í podstatné zmen¹ení objemu indexovaných slov.

Nalezení základního tvaru slova v èe¹tinì je pomìrnì nesnadná úloha. Potí¾e souvisí s bohatostí jazyka, která se projevuje pøedev¹ím velkým mno¾stvím koncovek a následnou neschopností rozli¹it, zda shluk písmen je koncovka, nebo souèást kmene (napø. koncovka -em : objem, objemem). Dal¹ím problémem je napø. zmìna kmenové souhlásky, tvarová nejednoznaènost (napø. hrách mù¾e být tvarem slova hrách nebo hry), atd. Vytvoøení dokonalého lematizátoru by proto samo o sobì zøejmì staèilo na samostatný projekt. Na¹ím cílem tedy bylo vytvoøit lematizátor, který by i pøes svou jistou nedokonalost pøiná¹el alespoò dílèí výsledky.

Lematizaci je zpravidla mo¾né provádìt dvìma základními pøístupy:

Slovník je sice pomìrnì pøesný, ale nezpracuje neznámá slova, proto by vy¾adoval urèitou údr¾bu. Gramatika (soubor pravidel reprezentovaný koneèným automatem) doká¾e správnì lematizovat skoro v¹echna slova, vèetnì novotvarù, ale obvykle je neúplná a tím i nepøesná.

V na¹í implementaci je lematizátor realizován gramatikou doplnìnou o nìkteré výjimky. Pøi lematizaci se slovo prochází od konce a hledá se nejdel¹í mo¾ná koncovka podstatného nebo pøídavného jména, která se následnì odtrhne. Hlavní výhodou této metody je rychlost, nebo» lematizátor nepotøebuje ¾ádná pomocná data a pracuje v lineárním èase. Pøi testování bylo zji¹tìno, ¾e v¹echny pùvodní tvary jednoho slova v jednotném i mno¾ném èísle se lematizací redukují na jeden, dva, pøípadnì tøi tvary (více tvarù vzniká hlavnì v dùsledku zmìny kmenové souhlásky). Nevýhody této metody spoèívají pøedev¹ím v tom, ¾e lematizací se dvì rùzná slova mohou pøevést na stejný tvar a dále ¾e lematizátor prakticky nefunguje pro slovesa (podle tìch se ale v èe¹tinì pøíli¹ nevyhledává).

Filtr LemENG

Filtr lematizuje termy (odstraní koncovky u anglických slov).

Filtr ète jednotlivé termy (tag <T>) a ty lematizuje. Proto¾e vyhledávání se provádí nejèastìji podle podstatných jmen, filtr pouze odstraòuje koncovku -s, pomocí které se tvoøí mno¾né èíslo (odstranit vhodným zpùsobem koncovky u sloves je velmi obtí¾né). Ve vìt¹inì pøípadù se odøízne koncovka -s. Pouze u slov konèících na -uses, -shes -sses, -ches se oøízne koncovka -es. Koncovky -xes a -zes jsou sporné. Ve vìt¹inì pøípadù je spravné odøíznout pouze -s. Podrobnìj¹í rozbor je pøímo ve zdrojovém programu (LemENG.cpp). Tento filtr nepou¾ívá ¾ádný konfiguraèní soubor.

Filtr Stoplist

Filtr odstraòuje "nevhodná slova". Filtr ète jednotlivé termy (tag <T>) a zji¹»uje zda nejsou obsa¾eny ve "Stoplistu" (seznam nevhodných slov). Nevhodná slova jsou velmi frekventovaná nebo slova bez "významu" (napøíklad pøedlo¾ky, spojky, sloveso být, ...). Termy obsa¾ené ve Stoplistu nejsou zapsány na výstup. Tento filtr nepou¾ívá ¾ádný konfiguraèní soubor.

Filtr Count

V ka¾dém dokumentu se nìkterá slova vyskytují vícekrát. Opakující se slovo je tøeba slouèit do jednoho výsledného termu. Také po lematizaci vznikají shodné termy (napø. pod hradem, u hradu) a i tyto termy je potøeba slouèit. Filtr Count tedy spojí stejné termy a slouèí jejich váhu. Filtr hledá tagy <T>, které obsahují stejná slova. Výsledkem je jediný term, který obsahuje v¹echny pùvodní parametry a jediný parametr WEIGHT, který je souètem pùvodních hodnot. V¹e je patrné z následujícího pøíkladu. 

<T PARAM1=value WEIGHT=3 PARAM2=value>radio</T>
<T WEIGHT=2 PARAM3=value>radio</T>

pøevede se na: 

<T WEIGHT=5 PARAM1=value PARAM2=value PARAM3=value>radio</T>

Souèasný návrh obsahuje pouze parametr WEIGHT, ale pokud si v budoucnu nìkdo pøidá dal¹í parametr, pak tento filtr nové parametry zachová a objeví se ve výsledném tagu <T>. V¹echny ostatní tagy jsou propou¹tìny na výstup (tedy i novì pøidané). Tento filtr nepou¾ívá ¾ádný konfiguraèní soubor.

1999-03-04 Radek Weisfeit