DIPLOMOVÁ PRÁCE. Jan Tattermusch. pomocí stemmingu

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

DIPLOMOVÁ PRÁCE

Jan Tattermusch Vyhledávání v českých strukturovaných datech pomocí stemmingu Ústav formální a aplikované lingvistiky

Vedoucí diplomové práce: RNDr. Jaroslava Hlaváčová, Ph.D. Studijní program: Informatika, Softwarové systémy

2010

2

Děkuji vedoucí této práce Dr. Hlaváčové za cenné rady v průběhu celého vypracování a za připomínky k obsahu práce.

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 30. července 2010

Jan Tattermusch 3

Obsah 1 Úvod 1.1 Motivace . . . . . . . . . . . . . . . 1.2 Požadavky . . . . . . . . . . . . . . 1.3 Integrace fulltextového vyhledávání 1.4 Model fulltextové komponenty . . . 1.5 Související práce . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

2 Zpracování českého jazyka 2.1 Doplňování diakritiky . . . . . . . . . . . . . . . . . 2.1.1 Doplňování zohledňující kontext . . . . . . . 2.1.2 Statistické doplňování využívající n-gramy . 2.1.3 Tokenizace . . . . . . . . . . . . . . . . . . . 2.1.4 Typy tokenů v doplňování diakritiky . . . . 2.1.5 Zástupné hodnoty tokenů . . . . . . . . . . 2.1.6 Detekce konců vět . . . . . . . . . . . . . . 2.1.7 Trénování . . . . . . . . . . . . . . . . . . . 2.1.8 Úspěšnost doplňování diakritiky . . . . . . . 2.1.9 Příklady . . . . . . . . . . . . . . . . . . . . 2.2 Stemming . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Algoritmický stemming . . . . . . . . . . . . 2.2.2 Využití slovníku . . . . . . . . . . . . . . . . 2.2.3 Hybridní stemming . . . . . . . . . . . . . . 2.2.4 Síla stemmerů . . . . . . . . . . . . . . . . . 2.2.5 Porovnávání stemmerů . . . . . . . . . . . . 2.2.6 Kvalita lemmatizace pomocí slovníku aspell 2.3 Stopwords . . . . . . . . . . . . . . . . . . . . . . . 2.4 Tokenizace pro fulltextové indexování . . . . . . . .

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

8 8 8 10 11 12

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

14 14 14 15 17 18 19 19 20 22 23 24 24 25 26 28 29 33 33 34

3 Úložiště a fulltextové vyhledávání 36 3.1 Apache Lucene . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1.1 Lucene index . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1.2 Vyhledávání pomocí Apache Lucene . . . . . . . . . . . 37 4

3.2 3.3

3.4

3.5 3.6

3.7

Reprezentace dat . . . . . . . . . . . . . Dotazování . . . . . . . . . . . . . . . . 3.3.1 Prefilter a kritéria . . . . . . . . . 3.3.2 Postfilter . . . . . . . . . . . . . . 3.3.3 Řadicí pravidla . . . . . . . . . . Vyhodnocování dotazů . . . . . . . . . . 3.4.1 Elementární podmínky . . . . . . 3.4.2 Skládání podmínek . . . . . . . . Ukládání a modifikace dat . . . . . . . . 3.5.1 Viditelnost změn . . . . . . . . . Konfigurace . . . . . . . . . . . . . . . . 3.6.1 Konfigurace analýzy textu . . . . 3.6.2 Konfigurace fulltextového úložiště Využití XML . . . . . . . . . . . . . . .

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

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

4 Vliv stemmingu a doplňování diakritiky na tového vyhledávání 4.1 Měření kvality fulltextového vyhledávání . . 4.1.1 Mean Average Precision . . . . . . . 4.2 Přínos stemmingu a doplňování diakritiky . 5 Výkon a optimalizace 5.1 Optimalizace výkonu . 5.2 Optimalizace paměťové 5.3 Měření výkonu . . . . 5.3.1 Dotazování . . 5.3.2 Import dat . .

. . . . . . náročnosti . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

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

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

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

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

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

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

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

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

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

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

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

38 39 40 42 43 43 44 46 46 47 48 48 49 52

vlastnosti fulltex54 . . . . . . . . . . . 54 . . . . . . . . . . . 56 . . . . . . . . . . . 57

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

61 61 62 65 65 69

6 Závěr 70 6.1 Budoucí vývoj . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Literatura

72

Použitá data

73

A Obsah DVD

74

B Pravidla tokenizeru doplňovače diakritiky

75

C Pravidla tokenizeru pro fulltextové indexování

77

D Seznam použitých stopwords

80

5

E Ukázka konfigurace fulltextové komponenty

6

82

Název práce: Vyhledávání v českých strukturovaných datech pomocí stemmingu Autor: Jan Tattermusch Katedra (ústav): Ústav formální a aplikované lingvistiky Vedoucí diplomové práce: RNDr. Jaroslava Hlaváčová, Ph.D. Abstrakt: Tato práce implementuje a popisuje komponentu pro fulltextové vyhledávání s podporou českého doplňování diakritiky a stemmingu. Doplňovač diakritiky pracuje na statistickém principu a zohledňuje kontext. Práce obsahuje pět stemmerů připravených k okamžitému použití (dva algoritmické a tři hybridní), jejichž vlastnosti jsou diskutovány. Komponenta je vystavěna nad knihovnou Apache Lucene a poskytuje jednoduché rozhraní pro dotazování a přidávání, mazání a změnu indexovaných dokumentů. Ukládané dokumenty se skládají z pojmenovaných polí s definovanými datovými typy. Komponenta umožňuje definovat kromě běžných fulltextových dotazů také netriviální dotazy s doplňujícími omezeními a ovlivnit vlastní způsob výpočtu skóre výsledků dotazu. Výkon komponenty je dostatečný pro středně vytížené aplikace a orientační výkon je dle měření 50 dotazů za vteřinu nad úložištěm obsahujícím 2,7 milionu dokumentů. Přínos doplňování diakritiky a stemmingu pro kvalitu fulltextového vyhledávání byl měřen pomocí MAP a byl vyhodnocen jako významný. Klíčová slova: fulltext. vyhledávání, stemming, doplňování diakritiky, Lucene Title: Searching Czech Structured Data Using Stemming Author: Jan Tattermusch Department: Institute of Formal and Applied Linguistics Supervisor: RNDr. Jaroslava Hlaváčová, Ph.D. Abstract: This work describes and implements a component for fulltext searching with czech diacritics restoration and stemming support. Diacritics restoration is based on statistical principles and is context dependent. This work presents five stemmers ready for immediate use (two algorithmic stemmers and three hybrid stemmers) and discusses their properties. The component is implemented using Apache Lucene library and provides a simple interface for querying and insertions, deletions and updates of documents indexed. Stored documents consist of named fields with predefined data types. Besides regular fulltext queries, the component also supports non-trivial queries with additional constraints and provides a way to customize the way query result score is computed. Component’s performance is sufficient for medium-load applications and is approximately 50 queries per second with a repository that contains 2.7 million documents. Contribution of stemming and diacritics restoration to the quality of fulltext searching was measured using MAP and is significant. Keywords: Fulltext Search, Stemming, Diacritics Restoration, Lucene 7

Kapitola 1 Úvod 1.1

Motivace

Primární motivací vývoje komponenty pro fulltextové vyhledávání podporující doplňování diakritiky a stemming bylo její použití pro vyhledávání inzerátů na serveru sbazar.cz. Sbazar.cz je inzertní a aukční server, který umožňuje svým uživatelům vytvářet inzeráty1 , ve kterých ostatní uživatelé mohou vyhledávat.2 Bez ohledu na toto primární určení bylo ovšem dalším požadavkem navrhnout a vyvinout fulltextovou komponentu tak, aby možnosti jejího použití nebyly omezeny pouze na použití pro sbazar.cz, ale bylo ji možné snadno využít i pro jiné aplikace, které vyžadují fulltextové vyhledávání v nějaké formě.

1.2

Požadavky

Inzeráty serveru sbazar.cz jsou strukturované dokumenty skládájící se z několika atributů. Hlavními atributy jsou název inzerátu a jeho text. Tyto atributy představují část inzerátu, která má být prohledávána fulltextově. Inzeráty jsou navíc podle typu prodávaného zboží rozděleny do věcných kategorií (dále jen kategorií) a podle geografického umístění do regionů. Kategorie, region a další doplňující informace jako cena, stav prodáváného/kupovaného zboží ap. jsou tedy dalšími atributy inzerátu. Podle všech zmíněných atributů je třeba mít možnost vyhledávat. Dále je třeba si uvědomit, že kromě inzerátů existuje mnoho dalších možných druhů dokumentů, ve kterých lze vyhledávat.3 Názvy a typy atributů jsou podle druhu ukládaného dokumentu různé, takže navržený nástroj musí umožnit definovat názvy a typy atributů daného dokumentu 1

Mohou být vytvářeny i aukce, které jsou ale z hlediska datového modelu sbazar.cz pouze určitým typem inzerátu. 2 Webové rozhraní serveru sbazar.cz naleznete na http://www.sbazar.cz/. 3 Dalším takovým dokumentem může být třeba webová stránka.

8

ve své konfiguraci. Nad definovanými atributy musí potom být možné podle jejich typu provádět buď fulltextové vyhledávání, nebo konvenční vyhledávání dle hodnoty daného atributu. Hlavním požadavkem na komponentu podporující fulltextové vyhledávání je dosáhnout co možná nejvyšší kvality vyhledávání. Za kvalitní vyhledávání považujeme vyhledávání, které poskytuje z hlediska uživatele přesné a úplné výsledky. Kvality vyhledávání by mělo být v této práci dosaženo zejména díky podpoře pokročilých metod zpracování textu, kterými jsou doplňování diakritiky a stemming. Autorem textu inzerátů serveru sbazar.cz jsou sami uživatelé tohoto webu, čímž je dána i kvalita těchto textů. Velká část inzerátů neobsahuje diakritiku vůbec nebo je diakritika neúplná. Rovněž dotazy mohou být zadávány uživateli s diakritikou či bez ní. Z pohledu fulltextového vyhledávání ovšem diakritika v textu hraje roli, z čehož plyne i požadavek na její doplňování. Další funkcionalita – stemming – je již dnes považována za nedílnou součást všech kvalitních fulltextových vyhledávačů. Pro český jazyk to platí dvojnásob, neboť česká morfologie je oproti většině jiných jazyků zvláště bohatá. Pro praktický nástroj, jakým je komponenta implementovaná v rámci této práce, je zřejmě podstatný její dostatečný výkon, který musí odpovídat objemu uchovávaných dat a požadované rychlosti odezvy systému. V současné době je počet aktivních inzerátů serveru sbazar.cz zhruba 270 tisíc (viz [data02]). S výhledem do budoucna je třeba, aby komponenta umožňovala efektivní práci s řádově miliony dokumentů (inzerátů). Pro účely testování výkonu byla použita historická data inzerátů serveru sbazar.cz, která čítají 2,7 milionů inzerátů (viz [data01]). Frekvence dotazů na serveru sbazar.cz je průměrně 3 dotazy za vteřinu,4 ovšem požadavek na výkon je 10 dotazů za vteřinu. Proto je třeba, aby průměrná doba zpracování jednoho dotazu nepřevyšovala 100 ms. Fulltextová komponenta bude v praxi používána na platformě Linux. Nad touto platformou byly také prováděny veškeré testy i měření výkonu. Vzhledem k tomu, že fulltextová komponenta je implementovaná v jazyce Java, dá se předpokládat její bezproblémová přenositelnost na jiné platformy (např. Windows), ale tato přenositelnost není součástí požadavků a nebyla testována. Je také třeba počítat s tím, že při provozování fulltextové komponenty na jiné platformě nebudou funkční pomocné skripty napsané ve skriptovacím jazyce Bash. 4

Údaj byl získány na základě logu dotazů serveru sbazar.cz [data03].

9

1.3

Integrace fulltextového vyhledávání

Existují v zásadě dvě možnosti, jak zahrnout funkcionalitu fulltextového vyhledávání do produkčního systému.5 Lze předpokládat, že systém pracující s daty bude tato data uchovávat v databázi nad některým z běžně dostupných databázových strojů (DBMS). První možností zprovoznění fulltextového vyhledávání je využít vestavěnou funkcionalitu fulltextového vyhledávání v daném DBMS. V dnešní době existuje mnoho DBMS, které nabízejí i služby fulltextového vyhledávání. Podpora fulltextového vyhledávání byla zavedena do volně dostupných DBMS PostgreSQL, MySQL a je samozřejmostí v komerčních produktech jako Oracle či MS SQL Server. Společným jmenovatelem fulltextového vyhledávání implementovaného v rámci DBMS je sice dobré propojení fulltextu s ostatní funkcionalitou databáze, ovšem možnosti konfigurace fulltextového vyhledávání bývají nedostačující. Možnost přidat k fulltextovému vyhledávání složitější funkce, jakými jsou doplňování diakritiky, stemming a uživatelské úpravy skóre výsledků dotazu je buď velmi složité, nebo by vyžadovalo rozsáhlejší změny ve složitých zdrojových kódech daného DBMS.6 Tyto úpravy by mohly ohrozit stabilitu celého DBMS,7 a navíc by bylo pravděpodobně třeba je vzhledem k poměrně rychle se měnícím zdrojovým kódům open source databází pravidelně aktualizovat. V této práci je použita druhá možnost řešení, a to externí fulltextová komponenta, která je určena speciálně pro realizaci fulltextového vyhledávání. Toto řešení předpokládá, že z primární databáze v DBMS budou pro potřeby fulltextové komponenty vyexportována všechna potřebná data, která budou dále zpracována fulltextovou komponentou tak, aby nad nimi bylo možné efektivně vyhledávat. Takovéto řešení je sice pracnější než využití podpory pro fulltextové vyhledávání samotného DBMS, na druhé straně ovšem skýtá výrazně lepší možnosti konfigurace a může poskytovat i vyšší výkon. Jednou implementovaná fulltextová komponenta je navíc následně použitelná pro širokou škálu aplikací bez ohledu na to, který DBMS je pro konkrétní aplikaci používán. Další významnou výhodou z hlediska výkonu je možnost spustit stejnou fulltextovou komponentu ve více instancích, čímž můžeme násobit výkon z hlediska vyhledávání. 5

V případě této práce je produkčním systémem jádro aplikace spravující inzeráty na serveru sbazar.cz. 6 Možnosti implementace zmíněné funkcionality v rámci komerčních DBMS jako jsou Oracle a MS SQL Server nebyly v rámci této práce analyzovány. 7 PostgreSQL i MySQL jsou implementovány v jazyce C, což činí úpravy jejich kódu problematičtějšími.

10

1.4

Model fulltextové komponenty

Fulltextová komponenta se skládá z několika logických celků. Ty jsou definovány okruhem činností, které musí fulltextová komponenta pro svou správnou funkci vykonávat. Předně musí být definován celek, který zajišťuje perzistentní ukládání indexovaných dat a umožní v nich efektivně vyhledávat podle zvolených kriterií. Dále je třeba mít k dispozici funkcionalitu související se zpracováním českého textu pro potřeby fulltextového vyhledávání. Tyto celky musejí definovat jak rozhraní pro vzájemnou spolupráci, tak pro interakci s externími aplikacemi, které budou fulltextové komponentě zasílat požadavky na vykonání určitých akcí (dotazování, indexace dat). Fulltextová komponenta funguje jako samostatná softwarová knihovna a sama o sobě nemá žádné uživatelské rozhraní. Komponentové schéma celého systému je znázorněno na následujícím obrázku:

Komponenta zpracování českého textu vykonává všechnu funkcionalitu spojenou se zpracováním přirozeného jazyka. Pro potřeby fulltextového vyhledávání v českém jazyce je klíčový především převod indexovaných slov na jejich 11

kmeny (stemming), doplňování chybějící diakritiky a filtrování českých stopwords. Tokenizace je proces dělení vstupního textu na jednotlivá slova a vyžaduje ji každý fulltextový vyhledávač. Zmíněná funkcionalita je detailně popsána v kapitole 2. Druhou klíčovou komponentou celého systému je, jak již bylo zmíněno, fulltextové úložiště. Tato komponenta má na starosti ukládání a modifikaci dat v úložišti a spouštění dotazů nad indexovanými daty. Dále poskytuje možnost jednotné konfigurace celého systému a rozhraní, které umožňuje uživatelským aplikacím pohodlně používat veškerou dostupnou funkcionalitu. Fulltextové úložiště je postaveno na knihovně Apache Lucene. Apache Lucene je open source knihovna pro tvorbu výkonných fulltextových vyhledávačů. Knihovna Apache Lucene je celá napsaná v Javě a poskytuje velmi dobré možnosti rozšíření nebo změny některé funkcionality. O samotné komponentě fulltextové úložiště pojednává kapitola 3. Podstatným úkolem této práce je vyhodnotit přínos implementované funkcionality doplňování diakritiky a stemmingu pro fulltextové vyhledávání. Metoda použitá pro vyhodnocení kvality fulltextového vyhledávání a její výsledky pro různé konfigurace fulltextové komponenty jsou popsané v kapitole 4. Celá fulltextová komponenta implementovaná v rámci této práce je napsána v jazyce Java, což ji dělá multiplatformní a snadno přenositelnou. Vzhledem k tomu, že Java je často považována za pomalou platformu, bylo optimalizaci výkonu věnováno značné úsilí. Konkrétní informace o výkonu fulltextové komponenty a provedených optimalizacích jsou dostupné v kapitole 5. Jak jsme již zmínili, fulltextová komponenta je softwarovou knihovnou a není tedy samostatně spustitelnou aplikací. Aby bylo možné komponentu jednodušeji vyzkoušet, je na přiloženém DVD k dispozici jednoduchá demonstrační aplikace s grafickým rozhraním, která umožňuje spouštět dotazy nad připraveným úložištěm a prohlížet jejich výsledky.

1.5

Související práce

Některé z dílčích úkolů, které jsou řešeny v rámci této práce, jsou známými a dobře zmapovanými problémy. Při jejich řešení byly tedy použity ověřené přístupy popsané v literatuře, nebo byla dokonce využita přímo existující implementace s potřebnou funkcionalitou. Nejdůležitější zdroje, ze kterých tato práce vychází, jsou shrnuty v následujících odstavcích. V literatuře dobře zpracovanou je problematika doplňování české diakritiky. Doplňování diakritiky použité v rámci této práce užívá postupy popsané v diplomové práci J. Vrány [1]. Žádné zdrojové kódy ze zmíněné diplomové práce nebyly ovšem v této práci použity. Implementace stemmingu je založena především na článcích [4] a [5] 12

(L. Dolamic a J. Savoy), které popisují jednoduché algoritmické stemmery pro češtinu. Tyto stemmery byly v rámci této práce významně vylepšeny a vzniklé stemmery byly porovnány s původními variantami. Fulltextové úložiště podporující vyhledávání a modifikaci (přidávání, úpravu a mazání) indexovaných dokumentů bylo implementováno s využitím volně dostupné knihovny Apache Lucene, která je velmi užitečným nástrojem pro vývoj aplikací podporujících výkonné a kvalitní fulltextové vyhledávání.

13

Kapitola 2 Zpracování českého jazyka 2.1

Doplňování diakritiky

Jednou z klíčových fází zpracování českého textu je doplňování diakritiky (někdy též v literatuře označované jako obnovování diakritiky). Problém doplňování je definován následovně: máme český text, z něhož byla dříve plně či částečně odstraněna diakritická znaménka. Úkolem doplňování diakritiky je správně převést text do původní podoby, obsahující diakritická znaménka. Doplňování diakritiky je dobře známou a prozkoumanou úlohou a pro její realizaci lze použít mnoho různých přístupů. Ty se základně dělí na metody statistické a metody založené na pravidlech. Dále se přístupy dělí podle základní jazykové jednotky, se kterou pracují. Většina přístupů pracuje na úrovni slov, ale jsou známy i metody pracující na úrovni znaků či vět. Pro tuto práci byl zvolen přístup statistický, pracující na úrovni jednotlivých slov. Ten poskytuje dobré výsledky pro praktické využití a je zároveň nejrozšířenější používanou metodou.

2.1.1

Doplňování zohledňující kontext

Zásadním problémem doplňování diakritiky v češtině je jeho nejednoznačnost. V češtině existuje mnoho případů, kdy variant doplnění diakritiky k jednomu slovu je více (např. slovo „rad” může být doplněno na „rad”, „rád”, „řád”, „řad”, „raď” a „řaď”). Správná varianta je potom určena kontextem slova. Formální vyjádření pojmu kontext vypadá takto: Máme-li text T = w1 w2 ...wn skládající se ze slov w1 až wn , potom levým kontextem slova wx rozumíme text w1 w2 ...wx−1 a pravým kontextem text wx+1 wx+2 ...wn . Kontext slova je tvořen jeho levým a pravým kontextem. Pro účely doplňování diakritiky budeme ovšem v této práci brát v úvahu pouze kontext levý, protože doplňování diakritiky se obvykle provádí sekvenčně a v době zpracování slova není ještě známo

14

přiřazení diakritiky k jeho pravému kontextu, čili je problematické ho využít.1 Nyní můžeme definovat koncept doplňování diakritiky, na kterém je založena implementace doplňování diakritiky v této práci: Algoritmus 2.1.1 – Doplňování diakritiky zohledňující levý kontext 1. Načti ze vstupního textu i-té slovo ai . 2. Urči možné varianty doplnění diakritiky slova ai a označ je v1 až vn . 3. Pokud i 6= 0, se zohledněním známého kontextu w1 w2 ...wi−1 urči nejpravděpodobnější variantu vx doplnění diakritiky maximalizací výrazu maxx P (w1 w2 ...wi−1 vx ), kde P (T ) je pravděpodobnost výskytu textu T v českém jazyce. Zvolenou variantu vx označ jako wi . 4. Pokud i = 0, vyber jako wi variantu vx s největší pravděpodobností výskytu v českém jazyce. 5. Přejdi k bodu 1, pokud je na vstupu další slovo. Pokud ne, skonči a jako výstup použij w1 w2 ...wi .

2.1.2

Statistické doplňování využívající n-gramy

Popsaný algoritmus pracující s kontextem předpokládá, že známe pravděpodobnost výskytu všech českých kontextů libovolné délky, což je samozřejmě nereálný požadavek. Pro praktické využití budeme muset délku uvažovaných kontextů omezit. Obvykle se pro statistické doplňování diakritiky uvažuje kontext maximální délky 2 (čili vyhodnocujeme pravděpodobnosti výskytu trojic slov, tzv. trigramů). Důvodem k tomu je exponenciální růst potřebné velikosti trénovacích dat vzhledem k délce uvažovaných kontextů. Doplňovač diakritiky implementovaný v rámci této práce využívá k výběru nejlepší varianty doplnění diakritiky pravděpodobnosti výskytu unigramů (samostatných slov), bigramů (dvojic slov) a trigramů (trojic slov) v trénovacích datech.2 Vzhledem k tomu, že unikátních bigramů (nebo dokonce trigramů) je v trénovacích datech obvykle obrovské množství, bývá tabulka pravděpodobností výskytu bigramů (i trigramů) řídká a často se stává, že v průběhu doplňování diakritiky narazíme na kombinaci slov, se kterou jsme se v trénovacích datech nesetkali. V takovém případě by náš algoritmus selhal, protože by neměl jak rozhodnout o nejvhodnější variantě 1

Existují postupy, které umožňují nepřímo pravý kontext zohlednit. Jedním z takových postupů je třeba metoda udržování určitého počtu nejlepších variant doplnění pro celou větu pomocí Vitterbiho algoritmu, zmíněná v [1, str. 10]. 2 Stejný přístup je použit i v [1].

15

doplnění. Tento problém lze efektivně ošetřit technikou zvanou vyvažování popsanou v [1, str. 9]. Ta spočívá ve vyjádření vhodnosti dané varianty doplnění diakritiky jako váženého součtu pravděpodobnosti unigramu, bigramu a trigramu. Zmíněný vztah pro pro výpočet skóre vypadá takto: S = W0 · Punif orm + W1 · Punigram + W2 · Pbigram + W3 · Ptrigram Výrazy W0 , W1 , W2 a W3 označují po řadě váhu uniformního rozdělení, váhu shody v unigramu, váhu shody v bigramu a váhu shody v trigramu. Výrazy Punigram , Pbigram a Ptrigram označují pravděpodobnost daného unigramu, bigramu a trigramu. Výraz Punif orm je jednoduše obrácená hodnota počtu různých unigramů v trénovacích datech. Přítomnost uniformního rozdělení ve vzorci brání tomu, aby výsledné skóre vyšlo nulové, pokud není ve slovníku nalezen vhodný unigram, bigram ani trigram. Pro námi použitý algoritmus sice přítomnost členu uniformního rozdělení nemá efekt, ale přesto byl tento člen do vzorce zahrnut, aby byla umožněna pozdější vylepšení doplňovače diakritiky.3 Pravděpodobnosti výskytu unigramů, bigramů a trigramů jsou získány ze slovníku n-gramů, vytvořeného z trénovacích dat. Váhy jsou parametrem doplňovače diakritiky a určují, jakou měrou přispěje k celkovému skóre shoda v ngramu dané délky. Obvyklé nastavení přiřazuje oproti váze shody v unigramu mnohem větší váhu shodě bigramu nebo příp. trigramu.4 Nyní můžeme uvést modifikovaný algoritmus doplňování diakritiky, který 3

Např. v [1, str. 23] je popsán algoritmus umožňující určit váhy doplňovače pomocí tzv. vyhlazování. K jeho použití musí být splněny některé předpoklady a nenulovost použitých pravděpodobností je jedním z nich. 4 Například při testování doplňovače diakritiky bylo použito nastavení váhy unigramů na 1.0 a váhy bigramů na 50.0).

16

již představuje verzi algoritmu implementovaného v rámci této práce. Algoritmus 2.1.2 – Doplňování diakritiky pomocí slovníku n-gramů Parametry: váhy doplňovače diakritiky (W0 , W1 , W2 , W3 ) a slovník n-gramů vytvořený z trénovacích dat 1. Načti ze vstupního textu i-té slovo ai . 2. Urči možné varianty doplnění diakritiky slova ai a označ je v1 až vn . 3. Pro každou variantu doplnění vx urči pravděpodobnost příslušného unigramu (vx ), bigramu (wi−1 vx ) a trigramu (wi−2 wi−1 vx ) ze slovníku n-gramů. 4. Podle vztahu S = W0 · Punif orm + W1 · Punigram + W2 · Pbigram + W3 · Ptrigram urči vážené skóre pro každou variantu doplnění. 5. Vyber variantu vx s nejvyšším skóre a označ ji jako wi . 6. Přejdi k bodu 1, pokud je na vstupu další slovo. Pokud ne, skonči a jako výstup použij w1 w2 ...wi .

2.1.3

Tokenizace

V předchozím textu jsme se zmínili o tom, že vstupní text je reprezentován posloupností slov. V praxi je ale vstupem doplňovače diakritiky jednoduše sekvence znaků (např. textový soubor). Tu je třeba na jednotlivá slova nejprve rozdělit a také určit, které sekvence znaků jsou z pohledu doplňovače diakritiky považovány za slovo. Tato část zpracování vstupního textu se nazývá tokenizace. Tokenizaci je možné provádět více různými způsoby. Nejjednodušší způsob je rozpoznávání hranice slova podle výskytu předdefinovaných oddělovacích znaků jako například mezera, tečka a středník. Tato metoda sice na první pohled funguje dobře, ovšem skýtá řadu omezení. Při použití na reálném textu,5 který obsahuje entity jako e-mailové adresy, URL, typová čísla produktů a mnohé jiné se nám nepodaří uspokojivě specifikovat sadu oddělovacích znaků. Za příklad si vezměme třeba tečku na konci věty. Ta má sice být následována mezerou, ovšem často se stane, že tato mezera chybí a slova jsou oddělena pouze tečkou. S tímto případem musíme počítat a považovat tečku za oddělovač slov. Na druhou stranu tečka například v rámci URL nebo e-mailové adresy oddělovačem slov není (za předpokladu, že e-mailovou adresu a URL chápeme jako jedno slovo, což je náš případ). 5

Jako např. na textu inzerátů použitých v této práci jako testovací data.

17

Mnohem vhodnější a obecně použitelnou metodou je tokenizace pomocí pravidel. V této metodě jsou rozpoznávané tokeny definovány sadou pravidel, obvykle pomocí regulárních výrazů. Na základě těchto pravidel je potom nástrojem na generování lexikálních analyzátorů6 vytvořen stavový automat, který prochází vstupní text a identifikuje v něm tokeny odpovídající zadaným pravidlům. Tento přístup umožňuje nadefinovat podobu výsledných tokenů přesně podle potřeby, a navíc může o tokenech bez další režie poskytovat doplňující informace, které by jinak bylo třeba získávat dodatečně. Příkladem takovéto informace může být třeba typ rozpoznaného tokenu. Ze zmíněných důvodů provádí tokenizer doplňovače diakritiky tokenizaci podle pravidel. Pro vygenerování kódu tokenizeru byl použit volně dostupný nástroj JFlex. Pravidla pro jednotlivé tokeny jsou definována pomocí rozšířené syntaxe regulárních výrazů. Definovaná pravidla jsou tato: • slovo z písmen české abecedy (např. žehlička nebo Čedok) • slovo z alfanumerických znaků (např. A100 nebo U2) • číslo celé, desetinné i v české tečkované notaci (např. 100, 3.14 nebo 1.000.000) • název se znakem ampersand (např. C&A nebo AT&T) • e-mailová adresa (např. [email protected]) • URL (např. http://www.sbazar.cz/) • označení typu výrobku (například GTX-25) Dále je definováno výchozí pravidlo, které je aktivováno pro všechny znaky, které neodpovídají žádnému jinému pravidlu. Přesnou definici pravidel ve formátu JFlex najdete v příloze B.

2.1.4

Typy tokenů v doplňování diakritiky

V předchozím textu jsme zmínili, že tokenizer doplňovače diakritiky nám poskytuje informaci o typu detekovaných tokenů. Této informace je možné velmi dobře využít ke zlepšení úspěšnosti doplňování diakritiky, a to hned několika způsoby. 6

Lexikální analyzátor je pojem z teorie překladačů. Kód lexikálních analyzátorů je obvykle generován speciálními nástroji. Jedním z nich je například volně dostupný JFlex.

18

První možností je u tokenů některých typů vypnout doplňování diakritiky. To je případ tokenů e-mail a URL, které z principu nemají obsahovat diakritiku a její doplňování je tedy nežádoucí.7 Dalším nastavením, které zohledňuje typ tokenu, je příznak kontextu. Ten určuje, zdali se může daný token vyskytnout jako kontext doplňování diakritiky v bigramu či trigramu. Jinými slovy tento příznak vystihuje, zdali je token považován doplňovačem diakritiky za slovo či za oddělovač.

2.1.5

Zástupné hodnoty tokenů

Pokud se zaměříme na význam některých druhů tokenů při jejich použití coby kontextu v bigramech a trigramech, všimneme si, že z hlediska doplňování diakritiky často nezáleží na jejich konkrétní textové hodnotě. To lze ilustrovat na příkladu tokenu typu číslo. Uvažujeme-li věty „Prodám 25 traktorů.” a „Prodám 26 traktorů.”, není z hlediska doplňování diakritiky podstatné, zdali je ve větě přítomný token s textovou hodnotou „25” nebo „26”. Předchozí úvahu samozřejmě nelze zobecnit pro všechna čísla. Nicméně pokud bychom tokeny typu číslo pro účely doplňování diakritiky reprezentovali pomocí malého počtu vhodných zástupných hodnot, dosáhneme významného zvýšení šance, že bigramy a trigramy obsahující tyto zástupné hodnoty budou při doplňování diakritiky využity. V [1, str. 23] je popsán systém deseti zástupných hodnot pro čísla. Číslovky 0 až 9 jsou reprezentovány samy sebou a všechna ostatní čísla (včetně desetinných) jsou nahrazena zástupnou hodnotou „10”. Tento systém zástupných hodnot je použit i v této práci. Dalšími tokeny vhodnými pro nahrazení zástupnými hodnotami jsou tokeny typu e-mail, URL a označení typu výrobku. Pro doplňování diakritiky je podstatná skutečnost, že v kontextu zpracovávaného slova se nachází libovolná emailová adresa, a konkrétní podoba této adresy již nebude ve většině případů důležitá. Proto je v bigramech a trigramech přesná podoba e-mailové adresy nahrazena zástupnou hodnotou TOK:EMAIL. Stejně jako v případě čísel se tím výrazně zvýší šance, že daný bigram či trigram se vyskytl v trénovacích datech, a proto ho budeme moci využít při doplňování diakritiky. Podobně jsou výskyty tokenů typu URL a označení typu výrobku nahrazeny zástupnými hodnotami TOK:URL a TOK:MODELNUM

2.1.6

Detekce konců vět

Doplňovač diakritiky pracuje s kontextem jednoho či dvou předcházejících slov. V případě přechodu přes hranici věty by však tento kontext nebyl směrodatný.8 7

Všimněme si, že tento případ se liší od úplného ignorování tokenu. Tokeny s vypnutým doplňováním diakritiky stále mohou figurovat jako součást kontextu doplňování. 8 V [1] se rovněž doplňuje diakritika v jednotlivých větách izolovaně.

19

Potom, co je vstupní text rozdělen do tokenů, se provádí detekce konců vět. Konec věty se rozpozná pomocí přítomnosti interpunkčního znaménka (tečka, otazník, vykřičník), za kterým následuje slovo začínající velkým písmenem. Takto stanovená kritéria sice nepracují zcela bez chyb, ale experimentálně bylo ověřeno, že jiné strategie používající méně přísná kritéria vykazují větší počet chyb v rozpoznání konce věty. Navíc občasné nerozpoznání konce věty úspěšnost doplňování diakritiky ovlivní jen minimálně. Na druhé straně nalezení falešného konce věty9 by mohlo zhoršovat úspěšnost doplňování o něco více, při namátkovém testování se však rovněž nezdálo být problémem. Vzhledem k tomu, že doplňovač diakritiky pracuje s kontextem až dvou předcházejících slov, bylo třeba vyřešit otázku, co je kontextem pro první a druhé slovo ve větě. Naivním řešením by bylo na začatku věty provádět doplňování pouze pomocí unigramu (příp. bigramu pro druhé slovo ve větě), tím bychom ovšem přišli o potenciálně cennou informaci, že dané slovo se nachází na začátku věty (což může být pro doplňování diakritiky podstatné). Lepším řešením je chybějící kontext doplnit dvěma umělými slovy TOK:SENTENCE1 a TOK:SENTENCE2 vloženými na začátek každé věty. Potom budeme i pro první slovo ve větě schopni sestrojit jeho kontext ve formě bigramu a trigramu. Stejné řešení pro ošetření kontextu na začátku vět je použito i v [1].

2.1.7

Trénování

Vzhledem k tomu, že doplňovač diakritiky využívá ke své práci statistických dat o unigramech, bigramech a trigramech, je třeba tato data nejprve získat. Tato data se získávají v procesu trénování. Jako trénovací data slouží velký objem textu se správným přiřazením diakritických znamének. Text je nejprve rozdělen na jednotlivé unigramy, bigramy a trigramy, ke kterým se posléze vypočítají jejich pravděpodobnosti a uloží se do slovníku n-gramů. Jako podklad pro trénování byla k dispozici data inzerátů ze serveru sbazar.cz (viz [data01]). Při prozkoumání dat se ovšem dle očekávání zjistilo, že diakritika v textu je často neúplná nebo chybí zcela. Takováto data tedy nejsou pro trénování použitelná, jelikož doplňovač diakritiky by se de facto učil s chybami. Zásadním problémem trénování se tedy ukázalo vybrat s dostatečnou spolehlivostí velké množství inzerátů, které obsahují úplnou a správnou diakritiku. Toho lze dosáhnout s využitím nástroje pro kontrolu pravopisu aspell.10 Aspell je utilita, která pracuje se slovníkem přípustných slov v daném jazyku a o pravopisné správnosti rozhoduje jednoduše dle toho, zda dané slovo nalezne či 9

Při daných kritériích se falešný konec věty detekuje např. v názvu obce „Č. Krumlov” Aspell je GNU utilita pro kontrolu pravopisu a podporuje kromě mnoha jiných jazyků i češtinu. 10

20

nenalezne ve svém slovníku. Znalost pravopisné správnosti izolovaných slov sice přímo inzeráty s úplnou diakritikou vybrat nepomůže, ale pro jejich vybrání je možné použít následující pozorování: Pozorování 2.1.1 – Vztah pravopisné správnosti inzerátů a úplnosti přiřazení diakritiky Mějme inzerát W = w1 w2 ...wn obsahující smysluplné sdělení s částečným či úplným přiřazením diakritiky a skládájící se ze slov w1 až wn . Dále mějme predikát A(x), který vystihuje skutečnost, že slovo x je pravopisně správné podle slovníku aspell. Predikát C(X) značí, že X je inzerát s úplným přiřazením diakritiky. Potom s určitou pravděpodobností P platí, že ∀i=1..n A(wi ) ⇒ C(W ) přičemž P roste s délkou inzerátu (n). Z pozorování plyne, že pokud použijeme pro vytváření slovníku n-gramů pouze ty inzeráty, které mají dle aspellu všechna slova pravopisně správná, můžeme o nich předpokládat, že mají úplnou diakritiku (vzhledem k rozumné délce většiny inzerátů). Vzhledem k velmi dobré úspěšnosti doplňovače diakritiky, o které se zmíníme níže, se dá říci, že se tento předpoklad potvrdil. V konkrétních číslech byla pro trénování použita množina 2,7 milionu inzerátů (95 milionů slov), s neznámou mírou přiřazení diakritiky. Tyto inzeráty byly analyzovány pomocí nástroje aspell a byly z nich vybrány ty, které neobsahovaly žádnou pravopisnou chybu. Podle uvedeného pozorování by tyto inzeráty měly obsahovat úplnou diakritiku. Tímto způsobem bylo vybráno zhruba 537 tisíc inzerátů, čítajících 12,3 milionu slov. Tyto inzeráty byly použity pro statistickou analýzu výskytu n-gramů. Při zkušebním natrénování dat se zjistilo, že statistická data o trigramech nijak nepřispívají k úspěšnosti doplňování diakritiky, a to ani při nastavení extrémně velké váhy shody v trigramu. Vzhledem k tomu, že získávání statistik o trigramech je časově náročné a výsledný slovník trigramů by byl velmi objemný, bylo ve finální verzi získávání dat o trigramech z trénovacího procesu vypuštěno. Podrobnosti o natrénovaných datech naleznete v následující tabulce: Inzeráty filtrované aspellem počet počet počet počet

inzerátů slov unigramů bigramů

537 12 350 150 1 858

973 939 989 268 21

2.1.8

Úspěšnost doplňování diakritiky

Hlavním srovnávacím měřítkem pro různé doplňovače diakritiky je jejich úspěšnost. Ta odpovídá podílu zastoupení slov, která budou na neznámém textu správně doplněna o diakritiku. Měření probíhá obvykle na textu s úplným a správným přiřazením diakritiky. Z něj se před měřením odstraní všechna diakritika a doplňovačem se tato diakritika opět obnoví. Následně se výsledný text porovná s originálem a vyhodnotí se počet slov, která byla doplňovačem správně ohodnocena. Použitý vztah pro výpočet úspěšnosti je převzat z [1] a je formálně vyjádřen takto: Definice 2.1.1 – Úspěšnost doplňovače diakritiky Úspěšnost P doplňovače diakritiky nad textem je definována jako P =

R T

kde R je počet slov se správně doplněnou11 diakritikou a T je celkový počet slov v testovací množině. Popsaný postup jsme použili pro měření úspěšnosti doplňovače v této práci. Jako testovací množina bylo použito 54 158 inzerátů serveru sbazar.cz (různých od trénovacích inzerátů). Použité váhy doplňovače diakritiky pro unigramy a bigramy a uniformní rozdělení byly empiricky zvoleny jako (po řadě) 1.0, 50.0 a 0.5. Výsledky měření úspěšnosti jsou uvedeny v následující tabulce. Výsledky měření úspěšnosti doplňovače diakritiky počet inzerátů celkový počet slov počet správně ohodnocených slov úspěšnost

54 158 1 328 059 1 290 722 97,19 %

Dosažená úspěšnost 97,19 % se jeví jako velmi dobrá opticky i v porovnání s výsledky v [1, str. 28], které se pohybují v rozmezí 95 až 98 %. Hlavním důvodem pro takto dobré výsledky je nejspíše velká specifičnost jazyka inzerátů (ustálenost slovních spojení apod.). Použití inzerátů jako testovacích dat je ovšem zcela regulérní vzhledem k tomu, že v praxi se bude doplňovač využívat právě pro inzeráty. 11

Jedná se i o slova, jejichž správná podoba žádná diakritická znaménka neobsahuje, a tudíž je nebylo třeba doplňovat.

22

2.1.9

Příklady

Nyní si můžeme předvést ukázky, jak natrénovaný doplňovač diakritiky zpracoval neznámý text. Chyby v doplnění oproti předloze jsou vyznačeny podtržením. 1. Prodám Renault Laguna 1,8 Prodám Renault Laguna 1,8, RT výbava klimatizace, centrál, alarm, rádio, okna v elektrice, tmavá zelená metal barva. 2. majitel. Najeto 140.000 km. Interiér nekuřácký, velmi pěkný vůz, spolehlivý. Nové udělaný komplet výfuk a brzdné lanko. K vozu přidám nějaké náhradní díly. Spotřeba průměr 6,5 litrů. Při rychlém jednání sleva 5000,- Kč. 2. Ubytování na Třeboňsku Nabízím ubytování v chatkách až pro 7 osob, s možností postavení stanu na zahradě. Lokalita se nachází blízko Chlumu u Třeboně. Možnost koupání v blízké pískovně nebo v okolních rybnicich. Okolí vhodné pro cykloturistiku, rybaření, pěší túry či houbaření. 3. Prodám: DB, 1+1, ul. Holešická Prodám družstevní byt. Byt je v hezké klidné lokalitě (Holešická ulice), dům je zateplen s plastovými okny, nová střecha a dva výtahy (jeden nové zrekonstruován), byt je v původním stavu. Rozloha 33m2. K bytu patří sklep. V blízkosti bytu je škola, školka, pošta, MHD, knihovna, Norma, za domem je velké hřiště a byt je také kousek od lesa. U domu je možnost parkování 4. STAVEBNICTVÍ PRO MALÉ STAVITELE - NOVÉ SE ZÁRUKOU Skutečný stavitel je inteligentní stavebnice, poskytne skvělou zábavu pro celou rodinu. Stačí rozdělat maltu a postavit dům snů ze skutečných cihel. Skutečný stavitel podporuje kreativitu a představivost dítěte. Po sestavení lze stavebnici rozebrat a znovu postavit. Skutečný stavitel - stavebnice obsahuje 400 dílů: cihly, malta, střešní krytina, okna, dveře, podkladová plocha, stavební nářadí atd. Stavebníci dodáváme v provedení: farma hrad vila s bazénem.

23

Z ukázek je zřejmé, že praktická použitelnost doplňovače diakritiky je vysoká. V prvním inzerátu byla diakritika doplněna zcela správně. Ve druhé ukázce se vyskytly dva rozdíly oproti předloze, ale první z nich vedl k doplnění na gramaticky i významově identickou větu. Ve třetím inzerátu došlo k jedné chybě doplnění, stejně jako ve čtvrtém.

2.2

Stemming

Stemming je termín z lingvistické morfologie a představuje proces, při kterém je slovům přirozeného jazyka přiřazen jejich kmen. V této práci je stemming použit coby nástroj, který zlepšuje užitné parametry fulltextového vyhledávání. Obvykle očekávaným přínosem stemmingu je, že uživatel může zadávat slovo do dotazu v různých gramatických tvarech nebo ho nahradit slovem se stejným významovým kmenem, přičemž množina nalezených výsledků se tím nezmění. Druhotným přínosem stemmingu je rovněž zmenšení velikosti fulltextového indexu. Funkční jednotce, která stemming vykonává, se říká stemmer. Stemmerů existuje mnoho různých druhů, ale v principu se stemmery dají rozdělit na algoritmické, slovníkové a hybridní (kombinované). Algoritmické stemmery jsou obvykle reprezentovány různými pravidly pro odtrhávání koncovek a přípon (obecně suffixů) slov. Slovníkové stemmery jsou založeny na slovníku, který přiřazuje slovům jejich základní tvar. Hybridní stemmery kombinují dvě nebo více různých metod pro dosažení lepších výsledků. My jsme použili několik různých stemmerů, a to algoritmických i hybridních.

2.2.1

Algoritmický stemming

V rámci této práce byly využity dva algoritmické stemmery převzaté z [4], které pracují na principu odstraňování suffixů. Oba obsahují pravidla pro odstraňování pádových koncovek podstatných a přídavných jmen a liší se v obsáhlosti pravidel pro odstraňování přípon. Podle [4] je podpora odstraňování koncovek pouze pro podstatná a přídavná jména dostatečná, jelikož ostatní ohebné slovní druhy jen vzácně nesou z hlediska fulltextového vyhledávání podstatnou informaci. První z použitých stemmerů je označován jako Czech Light Stemmer (dále jen „lehký stemmer”). Kromě pádových koncovek podstatných a přídavných jmen odstraňuje ještě přivlastňovací přípony (-ov- a -in-) a zahrnuje jednoduchá pravidla pro hláskové změny (palatalizaci). Tento stemmer je vzhledem k malému počtu odstraňovacích pravidel ke slovům poměrně „šetrný” a není příliš náchylný k overstemmingu.12 12

Overstemming je jev, ke kterému dochází, pokud stemmer přiřadí stejný kmen dvěma

24

Druhý stemmer je označován jako Czech Aggressive Stemmer (dále jen „agresivní stemmer”). Tento stemmer obsahuje větší počet pravidel pro odstraňování suffixů. Mimo pádových koncovek podstatných a přídavných jmen odstraňuje ještě přípony přivlastňovací, srovnávací, zdrobňovací, přípony zesilující význam a některé další odvozovací přípony. Díky velkému počtu obsažených pravidel je tento stemmer sice často schopen redukovat slova na jejich kmeny velmi efektivně, ovšem zároveň je vzhledem k tomu poměrně náchylný k overstemmingu. Náchylnost k overstemmingu se projevuje zejména u krátkých slov, jejichž kmen je často tvořen jen dvěma nebo třemi písmeny. Na základě namátkového testování zmíněných algoritmických stemmerů na různých slovech se ukázalo, že jejich chování by bylo možné ještě vylepšit. Zejména u lehkého stemmeru docházelo poměrně často k understemmingu, čili k situaci, kdy ke dvěma souvisejícím slovům nebo tvarům slov stemmer přiřadí light light dva různé kmeny (např. akvaristika −−→ akvaristik, ale akvaristice −−→ akvaristic). Jednoduché přidání nových pravidel pro odtrhávání suffixů se ovšem nezdálo vhodné, neboť k understemmingu docházelo v některých případech i v případě agresivního stemmeru. Ke zmíněným problémům navíc dochází nikoliv z důvodu absence relevantních pravidel pro odtrhávání, ale z principiálních důvodů. Jedním z nich je například skutečnost, že je velmi těžké nastavit pravidla pro odtrhávání suffixů tak, aby byla míra agresivnosti stemmeru pro všechna slova homogenní (např. aggressive aggressive akvaristika −−−−−−→ akvar, ale akvaristická −−−−−−→ akvarist). Dalším problémem jsou poměrně časté alternace v českém tvarosloví (např. pes, genitiv psa; nebo již zmíněný příklad akvaristika, dativ akvaristice). I když by některé z popsaných problémů bylo možné alespoň částečně vyřešit přidáním dalších pravidel pro odtrhávání suffixů, je zřejmé, že větší množství pravidel má za důsledek větší míru nežádoucího overstemmingu.

2.2.2

Využití slovníku

Vhodnou metodou pro vylepšení chování stemmerů se ukázalo využití slovníku. Aby bylo slovník možné využít jako součást stemmeru, musí obsahovat mapování slovo → lemma (základní tvar slova). Takovýto slovník je potom možné použít buď namísto stemmeru (v tomto případě bude prováděna tzv. lemmatizace), nebo na získaná lemmata dále aplikovat některý z algoritmických stemmerů, čímž vznikne stemmer hybridní. Problematickým se může jevit získání vhodného slovníku. Ideálním podkladem by byl morfologický slovník češtiny, který obsahuje tvary českých slov společně s jejich základním tvarem a segmentací slova na jeho morfémy (předpona - kmen - přípona - koncovka). Bohužel takové slovníky nejsou volně významově nesouvisejícím slovům.

25

dostupné. Vhodnou náhradou se ovšem ukázal být český slovník, který je používán volně dostupným nástrojem pro kontrolu pravopisu aspell. Jak již bylo zmíněno, aspell ke kontrole pravopisu používá slovník známých českých slov. Slova obsažená ve slovníku jsou považována za pravopisně správná, zatímco slova, která se nepodaří ve slovníku najít, jsou označena jako chyby. Formát, ve kterém aspell slovník uchovává, není prostý seznam slov, ale skládá se ze dvou částí. První z nich je definice skloňovacích pravidel pro jednotlivá slova.13 Druhá je seznam slov v základním tvaru, přičemž ke každému slovu je uvedeno, která ze skloňovacích pravidel lze pro něj použít. Z těchto údajů lze již vytvořit ke každému slovu v základním tvaru seznam jeho tvarů,14 což je dostatečným podkladem pro vytvoření lemmatizačního slovníku. Další zajímavou vlastností slovníku aspellu je to, že většina jeho skloňovacích pravidel je specifická pro některý z ohebných slovních druhů. Na základě seznamu použitelných skloňovacích pravidel pro dané slovo lze tedy s poměrně dobrou úspěšností rozpoznat jeho slovní druh. Možnost sestrojit na základě dat slovníku aspellu jednoduchý klasifikátor slovních druhů byla využita ke konstrukci jednoho z hybridních stemmerů, o kterém se zmíníme později.

2.2.3

Hybridní stemming

Jak již bylo zmíněno, hybridní stemmery kombinují slovníkový a algoritmický přístup pro získání lepších výsledků stemmingu. S jejich pomocí můžeme získat dobře fungující stemmer kombinací slovníku, který provádí lemmatizaci, a jednoduchého algoritmického stemmeru založeného na odtrhávání suffixů, který je aplikován na lemma získané pomocí slovníku. Algoritmickému stemmeru se také říká sekundární, protože je použit až po aplikaci slovníku. Výhod tohoto řešení oproti plně slovníkovému stemmeru je několik. Jednou z nich je skutečnost, že data pro lemmatizační slovník jsou snadněji získatelná (např. z dat slovníku aspellu) než data speciálního slovníku obsahujícího přímo kmeny slov. Další výhodou je přijatelnější chování v případě, že slovník slovo, kterému chceme přiřadit kmen, neobsahuje. V tomto případě je na slovo na vstupu přímo aplikován algoritmický stemmer, což stále může vést k dobrým výsledkům, narozdíl od případu, kdy bychom použili čistě slovníkový přístup. Naopak ve srovnání se samotným algoritmickým stemmerem se hybridní řešení snáze vypořádá s alternacemi ve tvarech slov. Obecný algoritmus fungování hybrid13 14

Definice skloňovacích pravidel pro aspell se označuje jako affix file. Toto je možné provést pomocí funkce aspellu expand.

26

ních stemmerů použitých v této práci vypadá následovně: Algoritmus 2.2.1 – Hybridní stemming (obecně) Parametry: slovo w (jehož kmen hledáme), lemmatizační slovník, sekundární algoritmický stemmer 1. V lemmatizačním slovníku nalezni množinu možných lemmat slova w. Pokud je možných lemmat více, použij heuristiku pro výběr nejvhodnějšího z nich. Vybrané lemma označ l. 2. Pokud slovo w bylo ve slovníku nalezeno, aplikuj na l sekundární stemmer a vrať výsledný kmen. 3. Pokud slovo w nebylo ve slovníku nalezeno, aplikuj na w sekundární stemmer a vrať výsledný kmen. Vzhledem k tomu, že nalezených lemmat slova v prvním bodu algoritmu může být více, a určení správného lemmatu je takřka nemožné, je třeba zvolit některé z lemmat heuristicky. Jednoduchou a poměrně dobře fungující heuristikou použitou v této práci je výběr nejkratšího z lemmat. V této práci byly použity celkem tři různé hybridní stemmery. Ve všech byl jako lemmatizační slovník použit český slovník nástroje aspell. Liší se tedy pouze použitým sekundárním stemmerem, aplikovaným na slovníková lemmata. Výslednými hybridními stemmery jsou: Hybrid Light Stemmer, Hybrid Aggressive Stemmer a Hybrid Part-of-Speech Aided Stemmer. Prvním ze stemmerů je Hybrid Light Stemmer (dále také „hybridní lehký stemmer”). Jak již jeho název napovídá, jeho sekundární stemmer je algoritmický lehký stemmer. Tento stemmer se zdá být nejvhodnější pro praktické využití (indexace inzerátů), protože jím prováděný stemming je dostatečný a díky menšímu počtu suffixů odstraňovaných algoritmickým stemmerem jen velmi zřídka dochází k overstemmingu. Dalším v pořadí je Hybrid Aggressive Stemmer (dále také „hybridní agresivní stemmer”). Jeho sekundárním stemmerem je algoritmický agresivní stemmer, určující také jeho vlastnosti. Stejně jako použitý algoritmický stemmer projevuje mírnou tendenci k overstemmingu. Pro účely indexování inzerátů se jeví na základě porovnání stemmerů jako možná až zbytečně agresivní. Posledním z použitých stemmerů je Hybrid Part-of-Speech Aided Stemmer. Ten, narozdíl od všech dříve zmíněných stemmerů, využívá toho, že z dat slovníku aspellu lze také vytvořit jednoduchý klasifikátor slovních druhů. Informace o slovním druhu je potom využita k výběru vhodného sekundárního stemmeru, který bude na lemma získané ze slovníku aplikován. Ideou tohoto postupu je předpoklad, že algoritmický stemmer může pracovat mnohem efektivněji, pokud zpracovává slovo v základním tvaru a navíc má informaci o slovním 27

druhu daného slova. Algoritmus fungování hybridního stemmeru využívajícího informaci o slovním druhu vypadá takto: Algoritmus 2.2.2 – Hybridní stemming s klasifikátorem pro slovní druh Parametry: slovo w (jehož kmen hledáme), lemmatizační slovník, klasifikátor slovního druhu 1. V lemmatizačním slovníku nalezni množinu možných lemmat slova w. Pokud je možných lemmat více, použij heuristiku pro výběr nejvhodnějšího z nich. Vybrané lemma označ l. 2. Pomocí klasifikátoru odhadni slovní druh slova w. 3. Pokud je slovo w podst. jm., aplikuj na lemma l algoritmický stemmer pro podst. jm. v zákl. tvaru a vrať výsledný kmen. 4. Pokud je slovo w příd. jm., aplikuj na lemma l algoritmický stemmer pro příd. jm. v zákl. tvaru a vrať výsledný kmen. 5. Pokud je slovní druh slova w jiný nebo se ho nepodařilo určit, aplikuj na l Czech Aggressive Stemmer a vrať výsledný kmen. 6. Pokud se nepodařilo slovo w nalézt ve slovníku, aplikuj na w Czech Aggressive Stemmer a vrať výsledný kmen. Zmíněné algoritmické stemmery pro přídavná a podstatná jména v základním tvaru byly vytvořeny v rámci této práce. Použitá pravidla pro odtrhávání koncovek byla inspirována odpovídajícími pravidly agresivního stemmeru a některá nová pravidla byla přidána. Výhoda těchto stemmerů spočívá v tom, že odtrhávají pouze suffixy vyskytující se u podstatných (resp. přídavných) jmen v základním tvaru, čímž se minimalizuje riziko nesprávného stemmingu i při poměrně velkém množství pravidel.

2.2.4

Síla stemmerů

Vytvořit stemmer, který pracuje ideálně ve všech podmínkách, není v praxi možné. Jednak je požadovaná míra agresivity stemmeru subjektivní a může se lišit aplikaci od aplikace a uživatel od uživatele. Dále jsou míra výskytu overstemmingu a understemmingu související hodnoty, a většina přístupů (zejména ty algoritmické) nám neumožní zlepšit hodnotu jedné z nich bez toho, aniž by se tím nezhoršila hodnota té druhé. Proto je podstané mít v konkrétní situaci možných stemmerů k dispozici více a umět jejich užitné vlastnosti porovnávat. Hlavním parametrem charakterizujícím stemmer je jeho síla. Vystihuje, jak moc je stemmer agresivní při převádění tvaru slova na jeho kmen. Slabý stemmer vykazuje obvykle nízké riziko overstemmingu, na druhé straně takovýto 28

stemmer nemusí přiřadit dvěma souvisejícím slovům stejný kmen. Měr pro sílu stemmerů existuje celá řada. Ty nejpoužívanější jsou zmíněny v [6]. Zcela nejnázornější mírou síly stemmeru je tzv. index compression factor, který dává představu o poměru počtu výsledných kmenů vůči počtu výchozích slov, na které byl stemmer aplikován. Formální definice vypadá takto: Definice 2.2.1 – Index Compression Factor Index compression factor (ICF) stemmeru S nad množinou slov W = {w1 , w2 , ..., wn } je ICF =

|W | − |ST EM (W )| |W |

kde ST EM (W ) je množina všech kmenů vygenerovaných stemmerem ST EM na slovech z množiny W . Z definice je zřejmé, že čím větší je ICF, tím silnější daný stemmer je. Silou stemmeru rozumíme jeho tendenci přiřazovat stejný kmen větším množinám souvisejících slov. Pro srovnání byla pro všechny stemmery použité v této práci hodnota ICF spočítána. Výpočet byl proveden nad množinou všech slov z dat inzerátů. Výsledky jsou uvedeny v následující tabulce: Stemmer Czech Light Czech Aggressive Hybrid Light Hybrid Aggressive Hybrid Part-of-Speech Aided Lemmatizace slovníkem aspell

2.2.5

Počet slov

135 235

Počet kmenů 57 43 48 35 38 59

008 994 261 968 561 033

ICF 57.85 % 67.47 % 64.31 % 73.41 % 71.49 % 56.35 %

Porovnávání stemmerů

Porovnávání síly stemmerů pouze pomocí některé z měr síly je sice dobré orientačně, ovšem pro jejich důkladné porovnání nedostačující. Vzhledem k velké subjektivitě vhodnosti stemmeru pro daný účel je zřejmě nutné některé aspekty funkce stemmerů posuzovat manuálně. Proto by bylo vhodné mít k dispozici nástroj, který nám umožní stemmery porovnávat na úrovni jednotlivých slov tak, abychom byli schopni jednoduše vyhodnotit rozdíly v chování stemmerů (například případy, kdy jeden ze stemmerů pracuje agresivněji než druhý či naopak). 29

Je třeba podotknout, že porovnání stemmerů nízkoúrovňovně, tedy na bázi toho, jaké kmeny přiřazují jednotlivým slovům, není jednoduchá úloha. Naivní přístup by byl porovnávat množiny slov, které po aplikaci obou stemmerů vyprodukují stejný kmen. Tento přístup je ovšem špatný, protože dva různé stemmery mohou (a velmi často i budou) produkovat vzájemně různé kmeny. Dále je třeba si uvědomit, že pro fulltextové vyhledávání není rozhodující konkrétní podoba kmenu (čili zda kmen slova „auta” je „auto”, „aut” nebo i „automobil”), ale podoba množiny slov, která generují stejný kmen jako dané slovo. Taková slova budou totiž zaměnitelná z hlediska fulltextového vyhledávání. Množina slov, jíž daný stemmer přiřadí stejný kmen, se označuje termínem conflation class. Český termín „třída shluknutí” se nepoužívá, a proto budeme conflation class dále nazývat s-třída či jen třída. Právě těchto tříd je možné velmi dobře využít pro srovnání dvou stemmerů na konkrétní množině slov. Pokud je s-třída jednoho stemmeru sjednocením s-tříd jiného stemmeru, potom lze prohlásit, že druhý ze stemmerů je na dané množině slov silnější (redukuje slovo agresivněji). Podobně lze hovořit o shodnosti chování stemmerů na dané množině slov, pokud je dělení na s-třídy u obou stemmerů identické. Pro lepší srozumitelnost si uveďme příklad srovnání lehkého a agresivního stemmeru na reálných slovech vyskytujících se v inzerátech:

30

nadřazená s-třída

kbel kbely kbelích kbelík kbelíkem kbelíku kbelíky kbelíků kbelíček kbelíčku kbelíčků

s-třída lehkého stemmeru [kbelík] kbelík kbelíkem kbelíku kbelíky kbelíků [kbe] kbel kbely kbelích [kbelíče] kbelíček

s-třída agresivního stemmeru

[kbe] kbel kbely kbelích kbelík kbelíkem kbelíku kbelíky kbelíků kbelíček kbelíčku kbelíčků

[kbelíčk] kbelíčku kbelíčků

Z příkladu je patrné, jak je množina slov z prvního sloupce rozložena ve druhém a třetím sloupci na s-třídy lehkým a agresivním stemmerem. Výrazy v hranatých závorkách odpovídají výsledným kmenům. Všimněme si, že pokud bychom porovnávali stemmery jen na základě shodnosti kmenů, mohli bychom v tomto případě porovnávat jen s-třídy příslušející ke kmenu „kbe”, protože agresivní stemmer kmeny „kbelík”, „kbelíče” a „kbelíčk” nevytváří. Zároveň bychom pravděpodobně neodhalili skutečnost, že agresivní stemmer se narozdíl od lehkého dopouští overstemmingu (pražská část Kbely s kbelíkem nijak nesouvisí), jelikož tato informace by v množství rozdílů mezi stemmery zanikla. Po úvaze je patrné, že pokud chceme stemmery porovnávat pomocí jejich s-tříd, bude vhodné jednotlivá slova sdružovat do skupin, v jejichž rámci střídy stemmeru nějak souvisí. Například slova „kbelík” a „kbely” budou patřit do jedné takové skupiny,15 jelikož, jak jsme již viděli, z hlediska agresivního stemmeru náleží tato slova do jedné s-třídy. Naopak slova „kbelík” a „kočka” spolu souviset nebudou, neboť ani jeden ze stemmerů je neřadí do stejné s-třídy. Pojem „skupina souvisejících slov” je sice možná intuitivně jasný, ovšem formálně se s ním nemůžeme spokojit. Ke korektní definici porovnání dvou 15

Tato skupina odpovídá množině slov v prvním sloupci v uvedeném příkladu.

31

stemmerů pomocí s-tříd použijeme některé poznatky z teorie svazů. Nejdříve si uvedeme důležité pozorování: Pozorování 2.2.1 – S-třídy a dělení množiny Mějme stemmer S a množinu slov W = {w1 , w2 , ..., wn }. Potom množina všech s-tříd stemmeru S na množině W tvoří dělení množiny W . Tímto poznatkem se problém porovnání dvou stemmerů redukuje na porovnání dvou dělení stejné množiny. K porovnávání dělení množiny již formální prostředky máme, neboť, jak známo, všechna dělení množiny tvoří algebraickou strukturu svaz. Tento svaz definuje relaci částečného uspořádání <, přičemž A < B právě když dělení A je zjemněním dělení B. Z pohledu stemmerů lze tuto skutečnost interpretovat tak, že stemmer A pracuje na všech slovech agresivněji než stemmer B. Pro nalezení skupin „souvisejících” slov lze použít operaci supremum, která je nad každým svazem definována. Výsledkem této operace je v našem případě nejjemnější možné dělení, pro něž platí, že obě porovnávaná dělení definovaná stemmery jsou jejím zjemněním. Shrňme si tento poznatek v následujícím pozorování: Pozorování 2.2.2 – Porovnání s-tříd stemmerů Mějme stemmery S1 , S2 reprezentované množinou jejich s-tříd, které porovnáváme na množině slov W = {w1 , w2 , ..., wn }. Potom S = sup(S1 , S2 ) představuje dělení množiny W na třídy slov, která spolu souvisejí z hlediska porovnání stemmerů. Slova z různých tříd nemají z pohledu stemmerů S1 a S2 k sobě žádný (ani tranzitivní) vztah. sup je operace suprema ve svazu všech dělení množiny W . Nyní, když máme korektně definovanou operaci rozdělení slov na třídy význačné pro porovnání dvou stemmerů, je již snadné chování stemmerů na slovech z této třídy vyhodnotit a vizuálně znázornit. V rámci této práce byl vytvořen jednoduchý nástroj, který dokáže dva stemmery na zadané množině slov porovnat a toto porovnání exportovat ve formě HTML reportu. Vygenerované HTML reporty umožňující detailní porovnání stemmerů použitých v této práci naleznete na přiloženém DVD. Jejich přesné umístění a také vysvětlivky k těmto reportům jsou uvedeny v uživatelské dokumentaci (sekce 5.2.1).

32

2.2.6

Kvalita lemmatizace pomocí slovníku aspell

Jak již bylo řečeno, ve všech hybridních stemmerech použitých v této práci byla jako lemmatizační slovník použita data českého slovníku nástroje aspell. Je zřejmé, že slovník aspellu nebyl primárně vytvářen pro tyto účely, a proto se jevilo jako důležité jeho použitelnost coby lemmatizačního slovníku nějakým způsobem prokázat. To se podařilo srovnáním lemmatizace prováděné slovníkem aspellu spolu s lemmatizací pomocí dat morfologického slovníku češtiny [data05]. Data pro tento účel laskavě poskytla vedoucí práce Dr. Hlaváčová. Srovnání obou typů lemmatizace bylo provedeno manuálně na základě srovnávacího HTML reportu vytvořeného nástrojem na porovnávání s-tříd stemmerů zmíněného dříve. Na základě srovnání se zdá, že lemmatizace pomocí aspellu vykazuje v porovnání s lemmatizací pomocí morfologického slovníku zcela uspokojivou kvalitu. Report porovnávající oba typy lemmatizace naleznete společně s ostatními srovnávacími reporty na přiloženém DVD. Detailnější údaje k tomuto srovnání naleznete v uživatelské dokumentaci v sekci 5.3.

2.3

Stopwords

Běžnou vlastností fulltextových vyhledávačů je, že při vyhledávání se nezohledňují některá nejvíce frekventovaná slova daného jazyka. Takováto slova jsou označována jako tzv. stopwords. Stopwords nenesou význam podstatný pro fulltextové vyhledávání (slova „tak”, „a” apod.) a navíc se dá očekávat, že budou obsažena ve většině položek, nad kterými fulltextové vyhledávání provádíme, pročež jejich zahrnutí do kritérií vyhledávání by bylo zbytečné. Je zřejmé, že pokud jsou daná slova ignorována při vyhledávání, není ani nutné je brát v úvahu při samotném indexování prohledávaných dat. Tím se snižuje velikost výsledného indexu a urychluje vyhledávání. Na internetu je volně dostupné množství sad stopwords pro český jazyk. Jejich obsah je víceméně podobný, i když se tyto sady samozřejmě v zařazení některých slov liší. To je dáno tím, že určení stopwords je ovlivněno konkrétními požadavky na vyhledávač a druhem textu, který je fulltextově prohledáván. Sada stopwords, která byla použita pro indexování inzerátů obsahuje 192 slov a pochází ze dvou zdrojů: • Obecná stopwords pro češtinu, která jsou součástí přídavného balíčku knihovny Lucene.16 • Stopwords specifická pro inzeráty, získaná autorem této práce na základě seznamu nejfrekventovanějších slov vyskytujících se v inzerátech. Kompletní seznam použitých stopwords lze nalézt v příloze této práce. 16

Seznam těchto stopwords lze nalézt v balíčku org.apache.lucene.analysis.cz.

33

2.4

Tokenizace pro fulltextové indexování

Fulltextové indexování funguje na principu vytváření inverzního indexu slov, která se vyskytla v prohledáváném textu. Stejně jako v případě doplňovače diakritiky je text na vstupu reprezentován posloupností znaků a hranice slov v tomto textu je třeba rozpoznat pomocí tokenizeru. Tokenizer pro fulltextové indexování byl implementován pomocí nástroje JFlex, který se osvědčil již dříve při implementaci tokenizeru doplňovače diakritiky. Na tokenizer pro fulltextové indexování jsou ovšem kladeny jiné požadavky, a proto se definice jeho pravidel poněkud liší. Definovaná pravidla určující, co vše je tokenizerem považováno za slovo, jsou tato: • slovo z písmen české abecedy (např. žehlička nebo Čedok) • slovo z alfanumerických znaků (např. A100 nebo U2) • číslo celé, desetinné i v české tečkované notaci (např. 100, 3.14 nebo 1.000.000) • číslo s jednotkami (např. 100Kč) • slovo obsahující apostrof (např. O’Reilly nebo McDonald’s) • zkratka obsahující tečky (např. U.S.A nebo I.B.M) • název se znakem ampersand (např. C&A nebo AT&T) • e-mailová adresa (např. [email protected]) • jméno hostitele (např. seznam.cz) • označení typu výrobku (například GTX-25) . Rozdíly v definici pravidel oproti tokenizeru doplňovače diakritiky jsou způsobeny především tím, že tokenizer pro fulltextové indexování by měl podporovat tzv. normalizaci tokenů. Pro vysvětlení pojmu normalizace uvažme například zkratku U.S.A., která je tokenizerem označena za token. Z pohledu fulltextového vyhledávání je žádoucí, aby výskyty zkratky U.S.A. byly ztotožněny s výskytem slova USA, jelikož tyto dva výrazy evidentně označují totéž. Normalizace tokenů je tedy proces, který převádí některé často se vyskytující varianty podoby jednotlivých tokenů na normalizovaný tvar tak, aby byly z pohledu vyhledávání sdruženy vzájemně ekvivalentní hodnoty. Proces normalizace tokenů se provádí tzv. normalizačním filtrem, který může upravovat výstup samotného tokenizeru. Filtr může jednotlivé tokeny 34

zdrojového textu vzájemně spojovat, rozdělovat je na více podtokenů, měnit jejich typ a hlavně upravovat jejich textovou podobu. Normalizační filtr definovaný v rámci této práce definuje následující úpravy tokenů: • Odstranění zakončení „’s” z anglických posesivních tvarů (např. McDonald’s → McDonald). V rámci inzerátů je možné předpokládat zvýšený výskyt těchto tvarů. • Odstranění teček ze zkratek (např. U.S.A. → USA) • Rozdělení tokenů typu číslo s jednotkami na token obsahující samotné číslo a token obsahující jednotku (100Kč → (100, Kč)) • Rozdělení výrazů označujících rozměry předmětů na jednotlivé složky („100x200cm” → (100, x, 200, cm) ). Tokeny v této podobě jsou v inzerátech časté.

35

Kapitola 3 Úložiště a fulltextové vyhledávání 3.1

Apache Lucene

Nejdůležitější částí fulltextové komponenty je samotné úložiště dat. Úložiště musí umožňovat perzistentní ukládání dokumentů a zajišťovat jejich integritu. Dále by mělo být dostatečně výkonné, podporovat vícevláknový přístup k datům a umožňovat efektivní vytváření indexů a vyhodnocování dotazů. Jak vidno, na úložiště je kladeno mnoho rozličných požadavků a jeho implementace není v žádném případě triviální. Proto byla pro implementaci úložiště použita knihovna Apache Lucene, ktera již definuje vhodný formát, tzv. Lucene index. Zároveň knihovna definuje nad tímto formátem základní funkcionalitu potřebnou pro implementaci fulltextového vyhledávače.

3.1.1

Lucene index

Lucene index je kolekce strukturovaných dokumentů, které chceme prohledávat. Dokumenty jsou rozděleny do jednotlivých pojmenovaných polí (například u inzerátů se setkáme s poli „nadpis”, „popis” a „idenfitikátor inzerátu”). Nad těmito poli je možné volitelně vytvářet inverzní indexy. Inverzní index je datová struktura sloužící pro vyhledávání v dokumentech. Je představována seřazeným seznamem všech unikátních termů, které se v daném poli v uložených dokumentech vyskytují. Ke každému termu v tomto seznamu je přiřazen seznam dokumentů, které daný term obsahují. Pod pojmem term se v oblasti fulltextového vyhledávání rozumí jednotka, podle které vyhledáváme. V případě polí obsahujících text v přirozeném jazyce pojem term obvykle označuje slovo v textu. Vyhledávání podle termů – slov v takovýchto polích potom odpovídá fulltexovému vyhledávání. V případě polí, která nemají

36

vnitřní strukturu a představují jednoduchou hodnotu (například identifikátor inzerátu), se za term považuje hodnota celého pole. Tento případ odpovídá vyhledávání na rovnost, jak je známe například z SQL databází. Zajímavou vlastností Lucene indexu je, že dokumenty v něm uložené nemají definované žádné schéma, a nemusejí tedy být homogenní. Dokumenty uložené v jednom indexu mohou být složeny z různého počtu polí a tato pole mohou mít různé názvy. Dále je třeba poznamenat, že Lucene interně pracuje pouze s jedním datovým typem pole, kterým je řetězec znaků. Pokud chceme do indexu ukládat například číselné hodnoty a následně podle nich vyhledávat, musíme je uložit buď v kódované nebo ve vhodné textové podobě. Důsledkem neexistence schématu a netypovosti Lucene indexu je sice velká obecnost,1 ale zároveň je tím omezena jednoduchost použití ve většině běžných situací.

3.1.2

Vyhledávání pomocí Apache Lucene

Poté, co jsou dokumenty uloženy do Lucene indexu, je možno v nich vyhledávat. Existuje mnoho modelů pro získávání informací (Information Retrieval). Apache Lucene využívá při vyhledávání kombinaci booleovského a vektorového modelu. Dokumenty, které odpovídají booleovské podmínce určené dotazem (čili jsou „schváleny” booleovským modelem), jsou dále porovnávány s dotazem pomocí vektorového modelu. Výsledkem tohoto porovnání je skóre, vyjadřující míru podobnosti dotazu a daného dokumentu. Odpovědi na dotaz jsou poté (ve výchozím nastavení) řazeny sestupně podle zmíněného skóre. Detailnější informace o způsobu výpočtu skóre knihovnou Lucene najdeme v [3, str. 78] a v JavaDoc dokumentaci třídy org.apache.lucene.search.Similarity. V dalším textu využijeme pouze informaci, že vektorový model knihovny Lucene vypočítává váhy vektoru ve vektorovém modelu na základě frekvence termu v daném dokumentu a inverzní frekvence termu ve všech prohledávaných dokumentech. Tento způsob výpočtu se označuje TF-IDF. Apache Lucene implementuje efektivní systém vyhledávání, který je navíc vysoce rozšiřitelný a obsahuje množství konfigurovatelných parametrů, které se týkají například konkrétních detailů ohledně výpočtu skóre dokumentů. Dotaz je v knihovně Lucene reprezentován instancí třídy Query. Tato třída má množství implementací, které pokrývají většinu potřeb vyhledávání v praxi. Navíc je díky jednoduchému rozhraní možné další implementace přidávat. Elementární dotazy podporované knihovnou Lucene byly použity jako základ pro realizaci složitějších dotazů, které jsou podporovány fulltextovou komponentou vytvořenou v rámci této práce. Nejčastěji používané typy dotazů, které Lucene 1

Právě kvůli zachování velké obecnosti použití nebyla nízkoúrovňová podpora datových typů a schémat dokumentů do knihovny Apache Lucene nikdy zahrnuta.

37

podporuje, jsou tyto: TermQuery Představuje nejzákladnější dotaz, který vyhledává výskyt daného termu (slova). Je také základem složitějších fulltextových dotazů. PhraseQuery Vyhledává v dokumentech frázi, tj. skupinu bezprostředně po sobě následujících slov. RangeQuery Vyhledává termy v daném intervalu hodnot. Je použitelný například pro vyhledávání inzerátů vložených v daném časovém období. BooleanQuery Dotaz používaný pro spojování jednodušších dotazů do složitějších celků (operátory AND a OR). Z hodnot skóre subdotazů vypočítává výsledné hodnoty skóre.

3.2

Reprezentace dat

Jak již bylo řečeno, Lucene index nepodporuje datové typy a schémata dokumentů. Ve většině praktických případů ovšem indexované dokumenty své schéma přirozeně mají a datové typy jejich polí jsou rovněž pevně dány, přičemž mnoho polí ma jiný typ než řetězec. Tak je tomu i v případě inzerátů sbazar.cz. Vzhledem k tomu, že převádění hodnot jiných než řetězcových typů na kódovanou podobu a jejich zpětné dekódování není zcela triviální, je zřejmé, že přítomnost typového systému (a s tím spojená možnost definovat schéma dokumentů) by velmi zjednodušila používání celé fulltextové komponenty. Pro srovnání si můžeme představit, jaký je komfort dotazovaní nad klasickou SQL databází a jak složitá by byla formulace dotazů nad její obdobou, která nemá definovaný typový aparát a s hodnotami polí je nutné pracovat na úrovni jejich interní reprezentace. Pro zjednodušení práce s fulltextovou komponentou jako celkem byl v rámci této práce definován typový aparát, který pracuje jako součást vrstvy zapouzdřující práci s Lucene indexem a s API Apache Lucene. Tento typový aparát definuje sadu základních datových typů, které z většiny odpovídají primitivním typům jazyka Java, což je při použití Javy jako platformy výhodné. Fulltextová komponenta definuje tyto datové typy: INT Celé číslo odpovídající Java typu int. LONG Celé číslo odpovídající Java typu long. FLOAT Desetinné číslo odpovídající Java typu float. DOUBLE Desetinné číslo odpovídající Java typu double. 38

STRING Textový řetězec odpovídající Java typu String. FULLTEXT Textový řetězec pro fulltextové vyhledávání. V principu je shodný s typem STRING, ale liší se druhy dotazů, které lze nad ním spouštět. Pole tohoto typu lze používat ve fulltextových dotazech. DATE Datum/čas odpovídající Java typu java.util.Date. JAVAOBJECT Libovolný objekt jazyka Java, který je serializovatelný.2 Do úložiště je objekt ukládán v serializované podobě, při načtení entity je opět deserializován do původní podoby. Tento typ není (vzhledem k větší režii na práci s ním) vhodný pro vyhledávaní s vysokými požadavky na výkon. Nicméně je užitečný pro uložení dat s prakticky libovolnou strukturou, což může být v praxi užitečné. Pro číselné typy a typ datum jsou definovány konverzní metody, které typ převádějí z externí reprezentace na interní kódovanou reprezentaci. Základní požadavek na tuto konverzi je, že musí zachovávat přirozené uspořádání hodnot daného typu, čili že lexikograficky uspořádaná interní řetězcová reprezentace musí zachovávat stejné pořadí, jako přirozeně uspořádané hodnoty externí reprezentace. Zpracování některých typů dotazů (např. RangeQuery) pomocí knihovny Lucene totiž vyžaduje korektní uspořádání hodnot v inverzním indexu. Existenci datových typů je možné dále využít k definici schémat nad dokumenty v Lucene indexu, které, jak již bylo řečeno, samy o sobě žádné schéma nemají. Schéma dokumentu je jednoduše seznam pojmenovaných polí, které musí daný dokument definovat, a určení typů těchto polí. Dalšími doplňkovými informacemi ve schématu jsou například seznam sloupců, nad kterými má být vytvořen inverzní index, a definice primárního klíče dokumentu. Pro vyjádření rozdílu mezi dokumentem bez schématu a dokumentem se schématem označíme druhý případ pojmem entita. Z vnějšího pohledu pracuje fulltextová komponenta pouze s entitami, v následujícím textu budeme tedy používat především tento pojem.

3.3

Dotazování

Ačkoliv knihovna Lucene definuje vlastní rozhraní pro spouštění dotazů a získávání jejich výsledků, není toto rozhraní příliš intuitivní a uživatel bez důkladné znalosti knihovny může mít s jeho používáním problémy. Navíc toto rozhraní, stejně jako celá knihovna Lucene, není typové a neumožňuje automaticky provádět kontroly podle schématu konkrétní entity. Proto bylo v rámci této práce 2

Serializovatelné typy v Javě jsou ty, které implementují rozhraní Serializable.

39

vyhledávací rozhraní knihovny Lucene překryto vrstvou, která plně podporuje definovaný typový aparát i schémata entit a je mnohem intuitivnější pro uživatele. Navíc s použitím tohoto nového rozhraní je pro uživatele jednoduché začlenit do dotazu některé pokročilé funkce, jako je například uživatelská úprava skóre některých dokumentů, uživatelské filtrování výsledků dotazu nebo nestandardní uživatelsky definované řazení výsledků. S využitím samotné knihovny Lucene je implementace těchto funkcí poměrně náročná a vyžaduje výbornou znalost knihovny. Každý dotaz zpracovávaný fulltextovou komponentou může být podle jednotlivých fází zpracování rozdělen na několik logických celků. Vzhledem k bohatým možnostem konfigurace každého dotazu mohou být tyto celky až čtyři. Tři z těchto celků jsou nepovinné a nemusí být v definici dotazu obsaženy. Možné komponenty dotazu jsou tyto (uvedeny v pořadí zpracování): Prefilter představuje omezení množiny prohledávaných entit pomocí sady kritérií. Kritéria vybírají podle podmínky entity, které budou výsledkem dotazu (pokud nebudou vyřazeny postfilterem) a vypočítává jejich skóre podle vektorového modelu. Kritéria jsou hlavní a povinnou komponentou dotazu. Postfilter představuje plně uživatelsky definovatelnou složku zpracování výsledků dotazu z komponenty kritéria. Při zpracování dotazu je pro každou entitu, která odpovídá daným kritériím, zavolána callback metoda, která může rozhodnout o vyřazení entity z konečné množiny výsledků, případně upravit její skóre. Řadicí pravidla určují pořadí, ve kterém mají být vráceny výsledky dotazu.

3.3.1

Prefilter a kritéria

Na první pohled je patrné, že komponenty prefilter a kritéria jsou si velmi podobné. Později dokonce uvidíme, že omezení jimi daná jsou reprezentována objektem stejného typu. Rozdíl mezi nimi spočívá ve způsobu výpočtu skóre pro výsledky dotazu. Zatímco prefilter představuje pouhé omezení rozsahu prohledáváné množiny v booleovském modelu a nijak neovlivňuje skóre entit, kritéria naopak entitám vyhovujícím podmínce přiřazují skóre vypočítané podle vektorového modelu. Prefilter je tedy vhodné použít, pokud potřebujeme rozsah vyhledávání omezit na nějakou podmnožinu celého indexu. Jako praktický příklad uveďme vyhledávání inzerátů jen v rámci jedné kategorie (např. hledáme zboží jen v kategorii „Auta - Seat”). Komponentu kritéria pak použijeme jako

40

tu část dotazu, pro kterou chceme vyhodnocovat skóre shody výsledků s dotazem, čili obvykle pro fulltextovou část dotazu (např. hledáme „Seat Leon”). Prefilter vykazuje ještě jednu užitečnou vlastnost, která není na první pohled zřejmá, a proto ji zde uvádíme. Jak již bylo řečeno, Lucene pro výpočet skóre entit využívá výraz TF·IDF. Přitom inverzní frekvence termu v dokumentech (IDF) očividně závisí na rozsahu prohledávané množiny entit. Pokud tuto množinu prefilterem omezíme, měla by se hodnota IDF tomu adekvátně změnit, což také implementace prefilteru zajišťuje.3 Význam této vlastnosti si vysvětlíme na již zmíněném příkladu. Představme si, že vyhledáváme výraz „Seat Leon” nejprve v rámci všech inzerátů a následně se omezíme pouze na kategorii „Auta - Seat”. Dá se předpokládat, že v rámci inzerátů ze všech možných kategorií bude výskyt slova „Seat” velmi řídký, zatímco v rámci kategorie „Auta - Seat” bude slovo naopak velmi frekventované. Pokud bychom prohledávali inzeráty ručně, intuitivně bychom v prvním případě hodnotili významnost nalezení slova „Seat” v dokumentu podobnou měrou jako nalezení slova „Leon”. Naopak ve druhém případě bychom nalezení slova „Leon” hodnotili jako mnohem významnější, než nalezení slova „Seat” o kterém víme, že se v dané kategorii vyskytuje téměř v každém inzerátu. Toto je ovšem přesně typ „inteligentního” chování, kterého dosáhneme, pokud použijeme pro vyhledávání v rámci zvolené kategorie prefilter. Změna významnosti nalezení slova „Seat” mezi oběma případy bude způsobená velkou změnou v inverzní frekvenci výskytu tohoto slova v prohledávané množině. Vysvětleme si nyní způsob zápisu podmínek v rámci prefilteru a kritérií. V obou případech jsou podmínky vyjádřeny objekty stejného typu. Fulltextová komponenta definuje sadu elementárních podmínek (operátorů), které lze použít v dotazech. Tyto podmínky je možné kombinovat pomocí operátorů konjunkce (logické AND) nebo disjunkce (logické OR) a případně i operátoru negace (logické NOT) do libovolně složitého výsledného dotazu. Elementární podmínky jsou tyto: • Operátor fulltextového vyhledávání. Vrací entity, které odpovídají fulltextovému dotazu. Toto kritérium umožňuje fulltextové vyhledávání v AND i OR sémantice, a vyhledávání frází. Text dotazu může či nemusí být před jeho spuštěním zpracován jazykovým analyzátorem. (FulltextCriterion) • Operátor =, vracející entity, jejichž pole (dané názvem) má předepsanou hodnotu. (EqualsCriterion) 3

Prefiltery jsou implementovány pomocí objektů třídy org.apache.lucene.search.Filter a popsané chování je zajištěno samotnou knihovnou Lucene.

41

• Operátory < a ≤ vracející entity, jejichž pole (dané názvem) má hodnotu menší (nebo rovnou) než daná konstanta. (LessThanCriterion, LessOrEqualsCriterion) • Operátory > a ≥ vracející entity, jejichž pole (dané názvem) má hodnotu větší (nebo rovnou) než daná konstanta. (GreaterThanCriterion, GreaterOrEqualsCriterion) • Operátor IN, vracející entity, jejichž pole (dané názvem) má hodnotu z dané množiny možných hodnot. (InCriterion) • Operátor BETWEEN, vracející entity jejichž pole (dané jeho názvem) je v daném konstantním rozsahu. (BetweenCriterion) • Operátor 6= vracející entity, jejichž pole (dané názvem) má hodnotu různou od dané konstanty. (NotEqualsCriterion) • Operátor vracející všechny dostupné entity. (AllDocsCriterion) Více detailů o dotazování pomocí prefilteru a kritérií lze nalézt v uživatelské dokumentaci v kapitole 3, sekci 2. Informace o složitosti vyhodnocení komponent dotazu prefilter a kritéria se nacházejí v sekci 3.4.

3.3.2

Postfilter

Použití postfilteru v dotazu umožňuje provádět filtrování jeho výsledků, které by jinak muselo být složitě prováděno uživatelskou aplikací. Jako názorný příklad může posloužit třeba vyhledávání v inzerátech, které zohledňuje cenu zboží. Řekněme, že chceme vyhledávat inzeráty na zboží s cenou zhruba 1000 Kč. Nejjednodušší (a poněkud nepřesná) realizace je vrátit jako výsledky dotazu inzeráty s cenou v nějakém intervalu, např. 500–1500 Kč, čehož můžeme snadno docílit podmínkou v komponentě dotazu prefilter. Tato realizace ovšem vůbec nezohledňuje, jak moc je cena inzerátu odlišná od požadované, což může být potenciálně pro uživatele velmi důležitá informace, která by měla být ve výsledcích dotazů zohledněna. Elegantním řešením tohoto problému je použít kromě podmínky v prefilteru i postfilter, který pro každý výsledek komponenty prefilter porovná cenu s požadovanou cenou, a podle definované metriky upraví hodnotu skóre každého výsledku tak, aby reflektovalo podobnost ceny inzerátu a požadované ceny. V případě řazení výsledků podle jejich skóre potom obdržíme inzeráty s cenou nejbližší té požadované jako první. Vzhledem ke své velké obecnosti může být výkon postfilteringu mnohem menší, než výkon dříve zmíněných komponent dotazu. Proto je důležité omezit

42

počet záznamů procházejících postfilterem vhodným prefilterem nebo kritérii dotazu. Vytvoření uživatelského postfilteru se provede v závislosti na požadovaném výkonu výsledného filtru odvozením potomka od jedné ze dvou bázových tříd postfilteru. Rozhraní první bázové třídy4 nám nabízí možnost implementovat velmi výkonný postfilter, ovšem za cenu složitější implementace. Druhá zmíněná třída5 třída představuje implementačně jednoduchý postfilter, který sice nevykazuje příliš dobrý výkon, ale stále může být pro mnoho aplikací plně dostačující. Fulltextová komponenta obsahuje i jednoduché příklady implementace obou druhů postfilterů. Více detailů o používání a vytváření postfilterů lze nalézt v uživatelské dokumentaci v kapitole 3, sekci 2.

3.3.3

Řadicí pravidla

Řadicí pravidla v dotazu určují pořadí, ve kterém mají být vráceny jeho výsledky. Řadit je možné dle skóre entit vypočítaného vektorovým modelem, nebo podle některého z polí entity, a to vzestupně i sestupně podle přirozeného uspořádání. Je možné definovat i plně uživatelské řazení. Jednotlivá pravidla je možné kombinovat do víceúrovňového řazení podle více řadicích klíčů různé významnosti. Pokud není pravidlo pro řazení explicitně definováno, výsledky se budou řadit podle svého skóre sestupně.6 V případě, že je třeba výsledky dotazu řadit jinak než podle přirozeného uspořádání některých jeho sloupců, je možné nadefinovat řazení uživatelské. Uživatelské řazení je definováno komparátorem polí entity, určujícího vzájemné pořadí dvou hodnot daného pole. Komparátor vytvoříte odvozením potomka od bázové třídy uživatelského komparátoru.7 Více detailů o používání řadicích pravidel lze nalézt v uživatelské dokumentaci v kapitole 3, sekci 2.

3.4

Vyhodnocování dotazů

Způsob vyhodnocení dotazů hraje klíčovou roli ve výkonu dotazovací části fulltextové komponenty. Jeho znalost umožňuje odhadnout úzká hrdla při zpracování dotazů a také navrhovat dotazy tak, aby byla rychlost jejich zpracování maximalizována. 4

Jedná se o Jedná se o 6 Toto skóre 7 Jedná se o

5

třídu jfullcz.indexing.query.postfilter.QueryPostfilter. třídu jfullcz.indexing.query.postfilter.SimpleQueryPostfilter. je počítáno komponentou kritéria. třídu jfullcz.indexing.query.sort.CustomFieldComparator

43

Fulltextová komponenta vyhodnocuje dotazy deterministicky. To je rozdílem oproti většině SQL databází, které mají implementovaný systém adaptivního vyhodnocení dotazů. Plán vyhodnocení SQL dotazů je určen tzv. plánovačem, který na základě metadat (jako jsou velikost tabulek, rozdělení hodnot ve sloupci tabulky, informace o existenci a typu indexů) pomocí heuristik vytváří plán vyhodnocení dotazu tak, aby režie zpracování dotazu byla co nejnižší. Použití heuristik ovšem činí způsob (a tedy i rychlost) zpracování dotazu těžko předem odhadnutelným a optimální výkonnost vytvořeného plánu není zaručena. To není pro fulltextovou komponentu příliš vhodné. Na rozdíl od SQL databáze, která musí být schopna efektivně vyhodnocovat zcela neznámé dotazy, fulltextová komponenta bude v praxi optimalizována pro vyhodnocení menšího počtu nejčastějších dotazů.8 Dotazy na fulltextovou komponentu budou také pravděpodobně jednodušší než typické SQL dotazy, což umožní jejich ruční optimalizaci již ve fázi návrhu aplikace, která bude fulltextovou komponentu využívat. Hlavními částmi dotazu jsou komponenty prefilter a kritéria. Tyto komponenty dotazu jsou interně překládány na dotazy knihovny Lucene. Pravidla pro překlad dotazu a implementace knihovny Lucene tedy společně určují konkrétní způsob vyhodnocení každého dotazu. Překlad dotazu je poměrně přímočarý proces. Stejně jako mohou být elementární podmínky komponenty kritéria skládány do složitějších dotazů pomocí logických operátorů, je možné elementární dotazy knihovny Lucene skládat do složitějších celků pomocí nadřazeného dotazu, který reprezentuje logickou operaci nad výsledky svých podřízených dotazů (dotaz typu BooleanQuery). Způsob zpracování komponent dotazu postfilter a řadicí kritéria není z hlediska vyhodnocování dotazů tak zajímavý. Implementace řazení se napříč jednotlivými dotazy nemění a nedává příliš velký prostor výkon dotazu ovlivnit. Princip činnosti postfilteru je zase velmi jednoduchý a omezuje se na volání uživatelsky definované funkce pro každý výsledek dotazu. Měření výkonu dotazů a vyhodnocení vlivu jednotlivých komponent těchto dotazů na jejich celkový výkon lze nalézt v sekci 5.3.1.

3.4.1

Elementární podmínky

Nejprve se zaměříme na složitost zpracování elementárních podmínek komponenty kritéria.9 První fází zpracování je výběr dokumentů odpovídajících podmínkám pomocí booleovského modelu. K tomu se pro všechny elementární podmínky využívá inverzního indexu, ze kterého můžeme pro danou hodnotu 8

Například pro inzeráty sbazar.cz lze předpokládat, že nejčastější dotazy budou zahrnovat omezení na kategorii či region. 9 Jak jsme již dříve zmínili, reprezentace a způsob zpracování podmínek v komponentě prefilter jsou shodné.

44

hledaného termu získat množinu dokumentů, které tento term obsahují. Termy v inverzním indexu jsou lineárně uspořádané, takže jedno vyhledání termu v inverzním indexu má logaritmickou složitost vzhledem k velikosti množiny unikátních termů v daném poli entity. Nejjednodušší je zpracování elementárních podmínek = a IN (EqualsCriterion a InCriterion), pro které z inverzního indexu vyhledáním malého počtu termů získáme množinu dokumentů odpovídajících zadané podmínce. Pro operátor = vystačíme s jedním vyhledáním, pro operátor IN musíme provést stejný počet vyhledání jako je velikost množiny povolených hodnot výrazu. Výsledky jednotlivých vyhledání operátoru IN jsou následně sloučeny pomocí operací na bitovém poli. Složitost operátoru fulltextového vyhledávání (FulltextCriterion) je dána počtem slov, která jsou v dotazu obsažena. Pro každé slovo je provedeno jedno vyhledání v inverzním indexu, přičemž výsledky těchto vyhledání jsou sloučeny pomocí operací na bitovém poli. Při použití operátoru fulltextového vyhledávání je třeba také počítat s režií na výpočet skóre u všech dokumentů vybraných booleovským modelem. Výpočetně náročnějším může být zpracování podmínek <, ≤, >, ≥ a BETWEEN, které pracují s termy ve zvoleném rozsahu. Ty jsou vyhodnocovány průchodem termů v inverzním indexu v celém rozsahu přijímaném podmínkou a jejich postupném přidávání dokumentů odpovídajících těmto termů do množiny výsledků dotazu. Pokud je takto procházených termů velké množství, vyhodnocení podmínky se stává pomalým. Počet termů závisí na rozsahu intervalu daného podmínkou, granularitě uložených hodnot a počtu uložených dokumentů. Jako příklad, kdy může být výkon dotazu na rozsah problematický, uvedeme vyhledávání inzerátů podle udané ceny zboží. Pokud bude cena v úložišti uložena s vysokou granularitou (např. s přesností na 1 Kč), bude počet termů v inverzním indexu pole cena obrovský a například dotaz na zboží s cenou vyšší než 100Kč celý systém zahltí. Pro optimalizaci výkonu takovéhoto dotazu máme možnost zavést pomocné datové pole, ve kterém bude uložena cena zboží s nízkou granularitou (jednotlivé hodnoty mohou například reprezentovat intervaly ceny na logaritmické škále, tzn. 1–10 Kč, 11–100 Kč, 101–1000 Kč atd.). Nad tímto polem potom můžeme efektivně vybrat podmnožinu inzerátů, které jsou z podobného rozsahu jako určuje podmínka, a pomocí postfilteru následně odstranit z množiny výsledků ty inzeráty, které jsou mimo skutečný rozsah určený podmínkou. Další možností optimalizace dotazů na rozsah je využití podpory implementované v knihovně Lucene. Ta nabízí možnost realizace dokonalejší verze popsaného postupu interně, bez vědomí uživatele. Principem této funkcionality je, že do inverzního indexu se hodnoty pole vloží vícekrát s různou úrovní granularity.

45

Při vyhodnocení dotazu na rozsah se potom interval v podmínce rozdělí na jednotlivé podintervaly s různou granularitou tak, aby počet těchto podintervalů byl co nejmenší. Pro každý z těchto podintervalů následně stačí nalézt odpovídající dokumenty pouze jedním vyhledáním v inverzním indexu. Toto řešení na jedné straně vyžaduje více úložného prostoru (záleží na počtu úrovní uložených granularit), ovšem umožňuje snížit počet vyhledávaných termů v inverzním indexu až exponenciálně. Bohužel v době psaní této práce byla podpora tohoto řešení v knihovně Lucene pouze experimentální, a nebyla proto z důvodu stability fulltextové komponenty využita.

3.4.2

Skládání podmínek

Jak víme, jednotlivé elementární podmínky v komponentách prefilter a kritéria je možné kombinovat do složitějších podmínek pomocí logických operátorů AND, OR a NOT. Operátory AND a OR jsou interně vyhodnocovány pomocí Lucene dotazu BooleanQuery, který spojuje výsledky svých poddotazů. Ke spojení výsledků poddotazů jsou použity operace nad bitovými poli. Konkrétní použitá bitová operace samozřejmě odpovídá tomu, který z operátorů AND a OR je použit. Realizace operátoru NOT je poněkud složitější, protože knihovna Lucene žádnou implementaci tohoto operátoru neposkytuje. Poskytuje ovšem možnost z výsledků jednoho dotazu odstranit výsledky, které jsou zároveň výsledky jiného dotazu (lze to provést s využitím dotazu BooleanQuery). Pokud výsledkem prvního dotazu jsou všechny dokumenty v úložišti (tzn. použijeme-li podmínku AllDocsCriterion), získáme touto operací výsledek ekvivalentní použití operátoru NOT na druhý z dotazů. Popsaný způsob odpovídá realizaci operátoru NOT ve fulltextové komponentě. Elementární podmínka 6=, která je fulltextovou komponentou podporována, je syntaktickou zkratkou a je realizována stejným způsobem. Teoreticky může být problémem nadměrné používání operátorů NOT nad úložišti obsahujícími velký počet dokumentů, protože pro každý použitý operátor NOT je třeba vytvářet bitové pole obsahující jeden bit pro každý dokument obsažený v úložišti. Na druhé straně jsou ovšem operace s bitovými poli velmi rychlé a ve většině reálných situací by nemělo přiměřené použití operací NOT představovat žádný problém. Testy srovnávající výkon operátoru NOT s ostatními operátory nebyly v rámci této práce provedeny.

3.5

Ukládání a modifikace dat

Samozřejmou součástí fulltextového úložiště je rozhraní pro vkládání nových entit a modifikaci či mazání entit existujících. Implementace této funkcionality 46

je založena na rozhraní Apache Lucene, které podporuje vkládání dokumentů do Lucene indexu a jejich následné mazání. Operace modifikace odpovídá smazání původního dokumentu z indexu a následné vložení jeho modifikované verze jako nového dokumentu. Abychom mohli jednoduše definovat operaci modifikace entity a operaci jejího smazání z úložiště, je třeba mít možnost jednotlivé entity identifikovat. Tuto identifikovatelnost je nejsnazší zajistit zavedením primárního klíče, známého z relačních databází. V našem případě je pro jednoduchost implementace primární klíč entity tvořen vždy jen jedním polem.10 Název pole, ve kterém je uložen primární klíč entity je určen schématem entity. Například pro entitu inzerát je primárním klíčem pole id, jehož hodnoty jsou v rámci celého úložiště unikátní. Definování primárního klíče entity není povinné, avšak entity bez primárního klíče není možné z úložiště mazat ani je modifikovat.

3.5.1

Viditelnost změn

Fulltextová komponenta plně podporuje vícevláknový přístup. Proto je třeba ošetřit situaci, kdy dochází k modifikaci indexu paralelně s jeho čtením. Pokud by se data v indexu mohla měnit v průběhu provádění dotazu, byla by implementace provádění dotazů velmi složitá a výsledky dotazů by mohly být nekonzistentní. Na druhou stranu z hlediska výkonu a udržení dobré odezvy systému není možné přijmout triviální řešení zakazující čtení indexu v době, kdy jiné vlákno index modifikuje. Toto řešení by úplně vyloučilo paralelismus fulltextové komponenty. Apache Lucene implementuje jednoduché řešení, jak se s problémem paralelního čtení a modifikace vyrovnat. Čtení indexu se v knihovně Apache Lucene provádí pomocí objektu IndexReader. Veškeré instance třídy IndexReader, které z Lucene indexu čtou data, vidí data v indexu staticky ve stejné podobě, v jaké byla data v době vytvoření dané instance IndexReader. Jakékoliv změny provedené v indexu po otevření objektu IndexReader jsou pro tento objekt neviditelné. Tento přístup je jednoduchý a poměrně elegantně zajišťuje, že data indexu nebudou změněna v době provádění dotazu a že výsledek dotazu bude konzistentní. Na druhé straně, pokud potřebujeme vyhledávat v nejaktuálnějších datech, je třeba zajistit dostatečně častou obnovu objektů IndexReader. Obnova objektů IndexReader je poměrně nenáročná operace, kterou lze provádět prakticky po každé modifikaci dat v indexu. Použité objekty je ovšem také potřeba poté, co přestanou být používany, zavírat, aby nezabíraly cenné systémové zdroje. V jednovláknovém prostředí je problém zavírání objektů IndexReader triviální, protože stačí dříve otevřené objekty zavřít vždy, když získáme novou verzi objektu IndexReader. Ve vícevláknovém prostředí je 10

Primární klíč v relační databázi může být tvořen libovolným počtem sloupců.

47

ovšem třeba hlídat, zda nejsou starší instance objektů IndexReader stále používány jinými vlákny a teprve poté, co přestanou být používány všemi vlákny, je možné je uzavřít. Ve fulltextové komponentě je správa otevřených instancí IndexReader zajišťována správcovskou třídou,11 která za pomoci atomických čítačů12 udržuje informaci o počtu vláken právě používajících danou instanci IndexReader a která zajištuje zavírání neaktuálních instancí poté, co přestanou být používány. Tato funkcionalita není obsažena v knihovně Lucene a byla pro potřeby této práce zvlášť implementována.

3.6

Konfigurace

Ačkoliv fulltextová komponenta byla vyvíjena primárně pro vyhledávání v inzerátech serveru sbazar.cz, je použitelná v široké škále aplikací. Aby tomu tak mohlo být, bylo třeba komponentu vyvinout jako plně konfigurovatelnou tak, aby si uživatel mohl upravit její chování podle svých požadavků. Aby byla konfigurace celého systému shromážděna přehledně na jednom místě, zahrnují možnosti konfigurace nejen nastavení fulltextového úložiště, ale i veškerá potřebná nastavení komponenty analýzy českého textu.

3.6.1

Konfigurace analýzy textu

Protože konfigurace fulltextového úložiště se na některé části konfigurace komponenty analýzy textu může odkazovat, seznámíme se nejdříve s možnostmi nastavení analýzy textu. Tato konfigurace je složená z definic jednotlivých analyzátorů, kterých může být nadefinováno libovolné množství. Analyzátor je komponenta, která je zodpovědná za následující činnosti: • doplňování diakritiky • tokenizace • filtrování stopwords • stemming Každá definice analyzátoru je složena ze zmíněných částí a je pojmenována. Prostřednictvím zvoleného jména se na definici lze jednoduše odkazovat. V rámci konfigurace analyzátoru je možné nastavit parametry doplňovače diakritiky čili cestu ke slovníku n-gramů a nastavení vah pro unigramy, bigramy a trigramy. Volitelně je také možné doplňování diakritiky úplně vypnout. Dále 11 12

Jedná se o třídu IndexSearcherManager. Atomický čítač je v jazyce Java reprezentován třídou AtomicInteger.

48

lze nastavit cestu k textovému souboru obsahujícímu stopwords, která mají být při zpracování textu ignorována, nebo zvolit použití výchozí sady stopwords. Konfigurace stemmeru se provádí jednoduše zvolením konkrétního stemmeru, který má být použit. Hybridní stemmery jsou definovány cestou k souboru, který obsahuje slovník stemmeru a druh použitého sekundárního stemmeru. O konkrétních stemmerech vytvořených v rámci této práce bylo pojednáno v sekci 2.2. Pro lepší porozumění uvedeme příklad, jak může vypadat konfigurace analyzátoru. Konfigurace je pro jednoduchost uvedena v XML reprezentaci (více o využití XML v této práci viz sekce 3.7). Ukázku kompletní konfigurace fulltextové komponenty naleznete v příloze E. Následující výňatek z této konfigurace definuje analyzátor s názvem „default”, který doplňuje diakritiku pomocí slovníku diacritics.ngramdict, váhami (1.0, 25.0, 35.0, 0.5), používá výchozí přednastavenou sadu stopwords a využívá lehký hybridní stemmer definovaný v souboru hybrid light stemmer.dict. <weigths unigramWeight="1.0" bigramWeight="25.0" trigramWeight="35.0" uniformWeight="0.5"/> <defaultStopwords/>

3.6.2

Konfigurace fulltextového úložiště

Konfigurace fulltextového úložiště se skládá ze schématu entity a nastavení fyzického úložiště použitého pro uložení dané entity. Do jednoho úložiště jsou ukládány entity jen jednoho typu. Schéma entity obsahuje jméno entity, definici polí, ze kterých se entita skládá, a volitelně též informaci o tom, které z polí představuje primární klíč entity. Pole entity je definováno svým názvem a typem, kterým může být libovolný typ zmíněný v sekci 3.2. Pro pole typu FULLTEXT musí být též uveden název analyzátoru, který bude použit pro analýzu textu pole a fulltextových dotazů na něj. Dalšími parametry pole jsou volby indexed a stored.13 Příznak indexed značí, že nad daným polem má být vytvořen inverzní index. Přítomnost tohoto indexu je klíčová pro rychlost vyhledávání nad daným polem. Příznak stored značí, zda má být obsah pole přímo uložen v úložišti. Tato volba umožňuje 13

Tato nastavení odpovídají volbám, které definuje knihovna Apache Lucene pro ukládané dokumenty.

49

šetřit úložný prostor v případě, že podle některých polí potřebujeme pouze vyhledávat (k tomu bude využit inverzní index), ale nepotřebujeme ve výsledcích dotazů hodnotu daného pole vypisovat. V praxi můžeme například rapidně snížit velikost úložiště, pokud k indexovaným inzerátům nebudeme ukládat původní textovou podobu inzerátů (před analýzou), protože tuto informaci můžeme pomocí identifikátorů inzerátů snadno získat z databáze inzerátů.14 Velikost úložiště se stává velmi důležitou, pokud chceme úložiště udržovat v operační paměti kvůli zvýšení výkonu vyhledávání. Nyní předvedeme ukázku konfigurace entity s názvem „advertisement”. Tato entita představuje inzerát serveru sbazar.cz s tím, že některá pole byla pro jednoduchost příkladu vynechána. Z konfigurace je zřejmé, že entita definuje 10 polí (s datovými typy INTEGER, STRING, DATE, FULLTEXT a FLOAT). Nad všemi poli je vytvořen inverzní index a jejich hodnota je ukládána do úložiště. Primárním klíčem entity je pole „id”. Fulltextová pole budou analyzována pomocí analyzátoru „default”. <entity name="advertisement" key="id"> <string name="ad_type" stored="true" indexed="true"/> <string name="status" stored="true" indexed="true"/> Potom, co jsme představili způsob konfigurace schématu entity, můžeme vysvětlit nastavení týkající se fyzického úložiště entit. Konfigurace fyzického úložiště určuje konkrétní umístění úložiště v souborovém systému a volí implementaci přístupu k fyzickému úložišti. Dále je možné ovlivnit způsob výpočtu některých hodnot, na základě kterých Lucene vypočítává skóre entit ve vektorovém modelu. Tyto hodnoty jsou z důvodu zvýšení výkonu předpočítány při indexaci entit a ukládány do fyzického úložiště. Poslední možností konfigurace 14

Dá se předpokládat, že většina produkčních systémů využívajících fulltextovou komponentu bude obsahovat primární kopii indexovaných dat v relační databázi. Tato data budou následně indexována pomocí fulltextové komponenty.

50

je nastavení příznaku úložiště „pouze pro čtení” a příznaku smazání obsahu úložiště při jeho otevření (tento příznak je užitečný pro testování). Samozřejmou součástí této konfigurace je, jak již bylo řečeno, umístění úložiště v souborovém systému. Každé úložiště je reprezentováno adresářem, jehož struktura odpovídá formátu Lucene index.15 Cesta k adresáři ve formátu Lucene index je hodnotou atributu directory v konfiguraci fyzického úložiště. Ačkoliv na souborovém systému jsou data fulltextového úložiště vždy ukládána ve stejném formátu Lucene index, existuje více možných přístupů, jak implementovat čtení a zápis do tohoto úložiště. Tyto přístupy se liší zejména svým výkonem ve čtení a efektivitě paralelního přístupu. Zlepšení užitných hodnot je dosaženo buď lepším využitím dostupné operační paměti, nebo využitím dokonalejšího API pro přístup k souborovému systému.16 Fulltextová komponenta poskytuje celkem čtyři různé implementace přístupu k úložišti:17 SIMPLE Výchozí implementace přístupu k úložišti. Tato implementace je knihovnou Lucene nejdéle podporovaná a je velmi spolehlivá, což je ale vykoupeno nižším výkonem. NIO Implementace využívající nové API Javy pro přístup k souborovému systému. To umožňuje paralelní čtení indexu více vlákny bez nutnosti synchronizace. MMAP Implementace využívající pro čtení z indexu přímé mapování souborů do paměti. To za předpokladu dostatečného množství volné operační paměti a dostatečné velikosti volného adresního prostoru umožňuje radikální urychlení čtení z úložiště, a tedy i zvýšení rychlosti vyhodnocování dotazů. RAM MIRRORED Implementace udržující po celou dobu běhu fulltextové komponenty úplnou kopii úložiště jak na disku, tak v operační paměti. Veškeré modifikace úložiště jsou ukládány na disk a zároveň zrcadleny do operační paměti. Výkon úložiště pro čtení je radikálně zvýšen, protože potřebná data lze načíst rovnou z operační paměti. Logicky je rovněž zvýšena rychlost vyhodnocování dotazů. Detailnější informace o jednotlivých implementacích přístupových metod k úložišti jsou uvedeny v uživatelské dokumentaci v kapitole 4, sekci 3. 15

Podrobný popis formátu Lucene index je dostupný v [3, str. 393]. Java od verze 2 definuje nové API pro vstupně-výstupní operace java.nio, které má oproti staršímu java.io řadu výhod. 17 Každý z těchto přístupů je reprezentován konkrétní třídou dědící od třídy Directory z Lucene API. 16

51

Jak již bylo zmíněno, v rámci konfigurace fulltextového úložiště je možné rovněž ovlivnit výpočet některých komponent skóre entit ve vektorovém modelu. Toho lze dosáhnout dodáním uživatelské implementace třídy Similarity, která definuje způsob výpočtu těchto komponent. V tuto chvíli je třeba upozornit na to, že potřeba změny výpočtu některých komponent skóre je poměrně vzácná a tato možnost je fulltextovou komponentou podporována jen pro zachování co možná nejvyšší univerzálnosti. Detailnější informace o uživatelských implementacích třídy Similarity lze nalézt v uživatelské dokumentaci v kapitole 4, sekci 3. Na závěr si uvedeme ukázku konfigurace fyzického úložiště. Tato ukázka definuje úložiště, jehož data jsou uchovávána v adresáři tmp/jfullcz dir, pro práci s úložištěm je použita implementace RAM MIRRORED a úložiště je možné číst i do něj zapisovat. Při otevření úložiště zůstane jeho původní obsah zachován. Pro výpočet některých komponent skóre entit ve vektorovém modelu je použita uživatelská implementace UserSimilarity. <documentStorage directory="tmp/jfullcz_dir" storageType="RAM_MIRRORED" readOnly="false" recreate="false" similarityName="UserSimilarity"/> Ukázku kompletní konfigurace fulltextové komponenty naleznete v příloze E.

3.7

Využití XML

Vzhledem k tomu, že fulltextová komponenta je implementována v jazyce Java, jsou dotazy na komponentu a její konfigurace reprezentovány objekty. Dotazy a zejména konfiguraci je ovšem třeba v praxi často uchovávat. Java sice podporuje serializaci, která možnost perzistentního uchování objektů umožňuje, ovšem objekty uchovává v nesrozumitelné binární formě, která navíc nemusí být stabilní přes různé verze vyvíjeného softwaru ani Javy. Pro dotazy a konfiguraci je přitom lidská srozumitelnost jejich reprezentace poměrně zásadní, protože umožňuje uživatelům dotazy a konfiguraci jednoduše psát a měnit. Jako reprezentace, která je uživatelsky srozumitelná a umožňuje úplné uložení všech podstatných informací o dotazech a konfiguraci, bylo zvoleno XML. XML umožňuje jednoduše vyjádřit objekty se stromovou strukturou, kterými jsou i dotazy fulltextové komponenty a její konfigurace. Navíc existence XML reprezentace je možné s výhodou v budoucnu využít, pokud bychom měli zájem fulltextovou komponentu provozovat jako webovou službu. Pro převádění objektů jazyka Java do XML reprezentace a zpět existuje velké množství knihoven, které se liší možnostmi nastavení a způsobem použití. 52

Pro účely této práce byl využita knihovna Castor18 , která na rozdíl od konkurenčních knihoven transparentně podporuje polymorfismus objektů. To v praxi znamená, že pokud knihovna nalezne v XML reprezentaci objekt, u kterého zná pouze jeho nadřazenou třídu, je schopná skutečnou třídu objektu automaticky rozpoznat podle názvu XML tagu. To je velmi užitečné například při reprezentaci kritérií dotazu, která tvoří stromovou strukturu a konkrétní druh kritéria (např. zda se jedná o podmínku = či <) specifikovaného XML tagem je třeba rozpoznat na základě jména tohoto tagu (v tomto případě equals nebo lessThan).

18

Domovská stránka projektu Castor XML je http://www.castor.org/xml-framework.html

53

Kapitola 4 Vliv stemmingu a doplňování diakritiky na vlastnosti fulltextového vyhledávání 4.1

Měření kvality fulltextového vyhledávání

Abychom mohli vyhodnotit přínos stemmingu a doplňování diakritiky pro fulltextové vyhledávání, budeme potřebovat znát některé pojmy z oblasti IR (Information Retrieval). Nejznámějšími mírami, které je možné použít pro vyhodnocení kvality vyhledávání, je dvojice hodnot přesnost (P , angl. precision) a recall (R, český termín se nepoužívá). Předpokládejme, že máme množinu indexovaných dokumentů a chceme vyhodnotit kvalitu odpovědi fulltextového vyhledávače na daný dotaz. Přesnost je hodnota, která udává, do jaké míry jsou dokumenty vrácené vyhledávačem správnými výsledky zadaného dotazu. Pokud odpověď vyhledávače obsahuje dokumenty, které neodpovídají zadanému dotazu, hodnota

54

přesnosti se snižuje. Formálně je přesnost definována takto: Definice 4.1.1 – Přesnost (Precision) Mějme množinu dokumentů I a dotaz Q. Přesnost P je definována jako |RETQ ∩ RELQ | P = |RETQ | kde RETQ je množina dokumentů vrácená dotazem Q a RELQ je množina relevantních dokumentů z I pro dotaz Q. Pro |RETQ | = 0 lze dodefinovat P = 1. Na druhé straně recall představuje míru, do jaké množina výsledků dotazu pokrývá množinu relevantních dokumentů z indexované množiny. Pokud vyhledávač nalezne většinu kýžených dokumentů z prohledávané množiny, hodnota recall bude vysoká. Naopak pokud bude dotazem vrácena jen malá část relevantních dokumentů obsažených v indexované množině, hodnota recallu bude nízká. Pojem recall je definován následovně: Definice 4.1.2 – Recall Mějme množinu dokumentů I a dotaz Q. Recall R je definován jako R=

|RETQ ∩ RELQ | |RELQ |

kde RETQ je množina dokumentů vrácená dotazem Q a RELQ je množina relevantních dokumentů z I pro dotaz Q. Pro |RELQ | = 0 lze dodefinovat R = 1. Hodnoty precision a recall jsou spolu úzce provázané a pro vyhodnocení kvality fulltextového vyhledávání je třeba uvažovat vždy obě společně. Samotnou přesnost lze totiž triviálně maximalizovat vrácením prázdné množiny výsledků dotazu a maximální recall na druhé straně obdržíme vrácením celé množiny indexovaných dokumentů. Použitelné výsledky vyhledávání můžeme získat jen vhodným vyvážením hodnot P a R. Z toho také plyne, že pro porovnání kvality vyhledávání by bylo třeba porovnávat dvojice hodnot, a to by mohlo být problematické. Pro tento účel by se lépe hodila míra jednohodnotová. Jednohodnotovou mírou, která zohledňuje P i R je tzv. F-míra. Je funkcí P a R a umožňuje dokonce podle nastavení parametru přiřadit složce P či R různou váhu. Jejím nedostatkem je ovšem skutečnost, že nijak nezohledňuje 55

pořadí dokumentů vrácených dotazem. Většina vyhledávačů pořadí výsledků dotazu definuje, což je i případ této práce. Pořadí vrácených dokumentů je třeba zohlednit proto, že uživatel se obvykle nejvíce zajímá o několik prvních výsledků dotazu a případné nerelevantní dokumenty v nich vnímá velmi negativně. Na druhou stranu výskyt nerelevantního dokumentu na koncových pozicích seznamu výsledků obvykle ani nezaregistruje, a to tím spíše, že počet zobrazovaných výsledků dotazu bývá v praxi omezen.

4.1.1

Mean Average Precision

Stanovili jsme, že vhodná míra pro porovnávání kvality fulltextového vyhledávání by měla být jednohodnotová, zohledňovat pořadí dokumentů vrácených dotazem a nejlépe i zahrnovat obě složky kvality vyhledávání P a R. Nejoblíbenější mírou s těmito vlastnostmi je tzv. mean average precision (střední průměrná přesnost, český překlad se nepoužívá), čili MAP. Měření této míry předpokládá, že máme k dispozici více testovacích dotazů, u kterých jsme schopni vypočítat průměrnou přesnost (AP, average precision). MAP je potom střední hodnotou těchto průměrných přesností vypočítaných pro každý dotaz zvlášť. V následujícím textu budeme předpokládat, že odpovědi na dotazy jsou seřazené podle své relevance vzhledem k dotazu. Pro definování průměrné přesnosti se nejdříve musíme seznámit s pojmem přesnosti pro prvních n výsledků (označuje se P @n). Ta vystihuje, jaké je zastoupení relevantních dokumentů v prvních n výsledcích dotazu. P @n je definována takto: Definice 4.1.3 – Přesnost pro prvních n výsledků (P @n) Mějme množinu indexovaných dokumentů I a dotaz Q. Přesnost P @n je definována jako |RETQn ∩ RELQ | P @n = n kde RETQn je množina prvních n odpovědí na dotaz Q a RELQ je množina relevantních dokumentů z I pro dotaz Q. S využitím právě definovaného pojmu P@n již můžeme zadefinovat také

56

average precision. Formální vyjádření je následovné: Definice 4.1.4 – Average Precision (průměrná přesnost) Mějme množinu indexovaných dokumentů I a dotaz Q, přičemž výsledky dotazu mají definované uspořádání. Průměrná přesnost AP je definována jako PN P @r · rel(r) AP = r=1 |RELQ | kde P @r je přesnost pro prvních r výsledků dotazu a RELQ je množina relevantních dokumentů z I pro dotaz Q. rel(r) = 1 právě když dokument na r-té pozici výsledků dotazu Q je relevantní, jinak rel(r) = 0. Pro |RELQ | = 0 lze dodefinovat AP = 1. Jak již bylo zmíněno, MAP je střední hodnotou average precision přes více různých dotazů: Definice 4.1.5 – přesnost)

Mean

Average

Precision

(střední

průměrná

Mějme množinu dotazů Q1 , Q2 , ..., Qn , pro něž známe jejich průměrné přesnosti AP1 , AP2 , ..., APn . Střední průměrná přesnost M AP je definována jako: Pn APi M AP = i=1 n MAP je velmi oblíbenou mírou pro vyhodnocování kvality fulltextového vyhledávání a je o něm známo, že jeho hodnoty jsou stabilní vzhledem k velikosti množiny dotazů a také vůči odchylkám v určení relevance jednotlivých dokumentů (viz [8]). Tyto vlastnosti zvyšují vypovídací hodnotu námi provedeného měření.

4.2

Přínos stemmingu a doplňování diakritiky

K vyhodnocení přínosu stemmingu a doplňování diakritiky jsme použili porovnání hodnot MAP vypočítaných pro sadu testovacích dotazů. Střední průměrná přesnost byla vypočítána pro různé možné konfigurace fulltextového vyhledávače. Základním porovnáním je vztah hodnoty MAP pro konfiguraci využívající doplňování diakritiky i stemming a hodnoty MAP pro konfiguraci, která 57

používá pouze triviální filtr pro odstraňování diakritiky a stemming nepoužívá vůbec. Abychom mohli střední průměrnou přesnost změřit, potřebujeme testovací množinu dokumentů a k ní příslušnou sadu testovacích dotazů. K těmto dotazům dále potřebujeme mít k dispozici mapování dotaz → množina relevantních dokumentů z testovací množiny. Relevanci dokumentů k jednotlivým dotazům je třeba určit ručně, aby byla zaručena spolehlivost dat, ze kterých budeme při měření MAP vycházet. Nevýhoda nutnosti ručního zpracování všech dokumentů z testovací množiny je vyvážena tím, že jednou připravené podklady je možné použít vícekrát, například pro měření MAP nad více konfiguracemi vyhledávače, jako v našem případě. Pro určení množiny relevantních odpovědí by bylo třeba ručně projít celou testovací množinu dokumentů a pro každý dotaz určit relevanci daného dokumentu. Velikost testovací množiny byla ovšem v našem případě 270 tisíc inzerátů, takže ruční vyhodnocení relevance v plném rozsahu nebylo možné. Pro řešení tohoto problému jsme využili skutečnost, že inzeráty v testovací množině jsou členěné na tematické kategorie, které je možné využít pro omezení rozsahu inzerátů prohledávaných daným dotazem. Pro zajištění zvládnutelnosti přípravné fáze měření MAP byly tedy jednotlivé testovací dotazy omezeny tak, aby prohledávaly pouze kategorie o velikosti 100–400 inzerátů. Výběr kategorií byl takový, aby pokud možno představoval reprezentativní vzorek možných kategorií vyskytujících se v inzerátech. Přehled vybraných kategorií spolu s počtem inzerátů a testovacích dotazů je uveden v následující tabulce: ID

Název kategorie

43 Lodě a vybavení lodí 62 Umění a umělecké předměty 114 LG 162 Seat 236 Doučování 264 Kancelářské vybavení 280 Stavební a zemní stroje

Počet inzerátů

Počet test. dotazů

334 221 378 358 309 292 135

10 13 8 11 7 9 9

Celkově bylo pro účely měření MAP použito 67 dotazů nad zmíněnými kategoriemi. Tento počet dotazů by měl být pro spolehlivé určení MAP dostačující, jako vhodný počet testovacích dotazů pro určení MAP se udává 50 (viz např. [5] a [4]). Testovací dotazy byly vybrány jako reprezentativní vzorek z logu reálných dotazů zadaných uživateli serveru sbazar.cz, což by mělo pozitivně ovlivnit vypovídací hodnotu měření. Po ručním připravení podkladů pro měření MAP bylo již možné hodnoty MAP změřit pro všechny konfigurace fulltextového vyhledávače, které jsme 58

chtěli porovnat. Výsledky měření jsou k dispozici v následující tabulce: Konfig. 1 2 3 4 5 6 7

Doplňování diakritiky

Stemmer

MAP

ano ano ano ano ano odstranění diakritiky odstranění diakritiky

Hybrid Light Stemmer 0.8469 Hybrid Aggressive Stemmer 0.8492 Czech Light Stemmer 0.8375 Czech Aggressive Stemmer 0.8329 Part-of-Speech Aided Stemmer 0.8619 Hybrid Light Stemmer 0.8161 žádný 0.5348

Vliv stemmingu a doplňování diakritiky na kvalitu vyhledávání je nejlépe patrný z porovnání konfigurací 1–5 s konfigurací 7. Konfigurace 7, která neprovádí stemming a pouze odstraňuje z textu diakritiku, vykazuje o 29,8 % až 32,7 % nižší hodnotu MAP, což představuje v praxi velmi významný rozdíl. Konfigurace 1–5 naopak vykazují jen mírnější výkyvy v hodnotách MAP, které indikují rozdíly v kvalitě prováděného stemmingu. Poměrně překvapivý je relativně velmi dobrý výsledek konfigurace 6, která sice používala stemming, ale namísto doplňování diakritiky ji jen odstraňovala. Výsledek dosažený konfigurací 6 tedy ukazuje, že přínos stemmingu je z pohledu fulltextového vyhledávání větší, než přínos doplňování diakritiky. Na druhou stranu relativně malá zdánlivá významnost doplňování diakritiky může být způsobena tím, že měření MAP bylo omezeno na kategorie o velikosti pouze stovek inzerátů. Dá se předpokládat, že v malém množství inzerátů z jedné tematické kategorie je nízká úroveň výskytu slov, která mají více variant doplnění diakritiky. Právě větší míra výskytu takovýchto slov v rámci objemnějších kategorií nebo ve vyhledávaní bez kategorií je faktorem, který by mohl zvýšit významnost doplňování diakritiky v porovnání s jejím pouhým odstraňováním. Co se porovnání jednotlivých stemmerů týče, nejlépe v porovnání dopadl Hybrid Part-of-Speech Aided Stemmer. Důvodem k tomu je patrně již dříve zmíněná schopnost stemmeru rozpoznávat pomocí slovníku podstatná a přídavná jména. Jejich základní tvar je potom možné velmi agresivně převádět na kmen bez velkého nebezpečí overstemmingu. Dále si můžeme všimnout, že agresivní algoritmický stemmer (konfigurace č. 4) dosáhl horších výsledků než lehký algoritmický stemmer (konfigurace č. 3), což je nejspíše způsobeno právě tendencí agresivního stemmeru k overstemmingu. V případě lehkého hybridního a agresivního hybridního stemmeru naopak agresivní varianta dosáhla o něco lepších výsledků, což ukazuje na vhodnost použití hybridní kombinace slovník a algoritmický stemmer, ve které může slovník převodem slov na základní tvar částečně potlačit některé negativní vlastnosti algoritmického stemmeru, jako je v tomto případě právě tendence k overstemmingu u agresivního stemmeru. 59

Na základě srovnání jednotlivých konfigurací bychom pro praktické využití při indexování inzerátu doporučili konfiguraci 1 či 5. Konfigurace 1 nabízí velmi dobrou hodnotu MAP v kombinaci s jednoduchostí použitého sekundárního stemmeru. Výhoda jednoduchého stemmeru, který neobsahuje příliš mnoho pravidel pro odtrhávání suffixů, je stabilita jeho chování při použití na neznámých datech. Na druhé straně konfigurace 5, využívající stemmer, který rozpoznává slovní druhy, se vyznačuje nejvyšší hodnotou MAP. Pokud by se ukázalo, že je tento stemmer schopen své vlastnosti zachovat i při testování na větším objemu dat, byla by konfigurace 5 nejvhodnější variantou pro maximalizaci kvality odpovědí fulltextového vyhledávače.

60

Kapitola 5 Výkon a optimalizace 5.1

Optimalizace výkonu

Jedním z důležitých faktorů použitelnosti fulltextového vyhledávače je bezpochyby jeho vysoký výkon. Proto je logické, že optimalizace výkonu by měla být nedílnou součástí vývojového procesu fulltextové komponenty. Efektivním způsobem, jak provádět optimalizaci, je hledání problémových částí kódu, které představují úzké hrdlo z hlediska výkonu. Tyto části kódu je možné vyhledávat buď za pomoci specializovaných nástrojů analyzujících aplikaci za běhu (tzv. profilerů) nebo i jen pouhou ruční statickou analýzou kódu, při které potenciálně problematické části kódu vytipujeme. V této práci byly použity oba přístupy. Přesně dle očekávání se kritickým pro výkon komponenty zpracování českého textu ukázalo vyhledávání ve slovníku n-gramů a vyhledávání ve slovnících hybridních stemmerů. To vyplývá z toho, že oba druhy slovníku obsahují statisíce až miliony záznamů a vyhledávání v nich se provádí velmi často. Doplňovač diakritiky pro každé slovo ve vstupním textu provádí po jednom vyhledání ve slovníku unigramů, bigramů a případně i trigramů. Hybridní stemmer provádí pro každé vstupní slovo jedno vyhledání. V situaci, kdy potřebujeme zpracovat více textu najednou (například při importu inzerátů do úložiště), je potom rychlost prohledávání slovníku klíčovou. Jak známo, velmi dobrý výkon pro slovníkové vyhledávání poskytuje datová struktura trie, která k nalezení klíče omezené délky vyžaduje pouze konstatní počet operací. Naivní implementace této datové struktury je ovšem, zejména v jazyce Java, paměťově velmi neefektivní, a proto byla pro slovníky použita efektivnější verze trie, o které se ještě zmíníme v následující sekci. Potenciálně problematickou může být z hlediska zpracování českého textu rovněž tokenizace, která musí být při zapnutém doplňování diakritiky prová-

61

děna dokonce dvakrát.1 Výkon tokenizerů velmi závisí na konkrétní implementaci dělení vstupního textu na tokeny.2 V této práci byl ovšem pro generování kódu tokenizerů použit nástroj JFlex, jehož výstupem je vysoce efektivní kód stavového automatu, s výkonem tokenizerů tudíž nebyly zaznamenány žádné problémy. Výkonnost samotného zpracování dotazů závisí zejména na způsobu provádění dotazů přímo knihovnou Lucene. Knihovna Lucene umožňuje provádět dotazy velmi rychle a efektivně (viz sekce 5.3.1). Vysoký výkon knihovny Lucene je způsoben především využitím inverzních indexů pro elementární dotazy a použitím bitových polí pro spojování výsledků jednodušších subdotazů. Při výpočtu skóre jednotlivých výsledků dotazu jsou použity předpočítané hodnoty některých komponent skóre, které jsou uloženy v Lucene indexu. Rovněž řazení výsledků dotazu je implementováno efektivně. Pro zrychlení řazení výsledků dotazu se využívá skutečnosti, že v praxi je počet požadovaných výsledků dotazu vždy omezen. Úplné řazení je tedy třeba provést pouze pro prvních k vrácených výsledků dotazu. Při zpracování dotazu je tedy nejprve nalezena množina k nejlépe umístěných výsledků,3 a teprve tato množina je následně seřazena a vrácena jako výsledek dotazu. Řazení výsledků také využívá cache pro zrychlení přístupu k hodnotám polí, která jsou použita jako klíč řazení.

5.2

Optimalizace paměťové náročnosti

Optimalizace paměťové náročnosti je velmi důležitým faktorem výsledného výkonu fulltextové komponenty v praxi. V našem případě se budeme orientovat na efektivitu využití operační paměti. Velikost obsazeného diskového prostoru totiž v dnešní době není klíčová, a navíc je z velké části dána formátem Lucene index, jehož specifika můžeme jen těžko měnit. O operační paměti naopak platí, že čím více jí dokážeme ušetřit, tím více ji následně budeme schopni využít pro zlepšení výkonu celého systému. Pokud se například podaří udržovat kompletní kopii úložiště v operační paměti, výkon dotazování stoupne téměř o řád oproti řešení, kdy bychom museli číst data úložiště z disku. Problém optimalizace paměťové náročnosti je ztížen tím, že Java nepatří k programovacím jazykům, které by byly k operační paměti zrovna šetrné a i objekty nesoucí jen několik bajtů efektivní informace mohou reálně zabírat desítky i stovky bajtů paměti. Navíc v Javě nemáme díky vysoké míře abstrakce jazyka možnost použít některé nízkoúrovňové optimalizační techniky, které jsou 1

V kapitole 2 jsme zmíníli, že definice pravidel pro oba použité tokenizery se liší. Například „manuální” detekce tokenů pomocí regulárních výrazů může být značně neefektivní. 3 To lze provést průchodem všech výsledků v lineárním čase. 2

62

běžné v jazycích jako například C++. Vzhledem k tomu, že fulltextová komponenta pracuje především s textovými daty, je jedním z nejčastěji používaných datových typů typ String. Ten je ovšem v jazyce Java paměťově velmi neefektivní. Prázdný objekt řetězec zabírá v paměti celých 40 bajtů4 a každý další znak v řetězci zabírá 2 bajty díky tomu, že Java používá pro znaky unicode kódování UTF-16. Je jasné, že pokud bychom hodnoty ve slovnících uchovávali jako řetězcové objekty, spotřebovali bychom většinu použité operační paměti jen na neužitečnou režii typu String. V rámci této práce byl pro reprezentaci řetězců použit přístup, který režii na uchování řetězců minimalizuje. Před samotným uložením je řetězce vhodné převést do kódování UTF-8. V kódování UTF-8 jsou totiž jednotlivé znaky ze sady ASCII kódovány pouze jedním bajtem a znaky s českou diakritikou bajty dvěma. Z toho plyne, že oproti kódování UTF-16, které kóduje všechny znaky jako 2 bajty, ušetříme významnou část paměti. Efektivní možnost uložení velkého množství řetězců plyne z toho, že řetězec v kódování UTF-8 je pouze posloupnost bajtů o určité délce. Tato posloupnost a údaj o její délce představují dostatečnou informaci pro uchování daného řetězce. Délku této posloupnosti můžeme zakódovat do jednoho či dvou bajtů v závislosti na tom, jak dlouhé řetězce potřebujeme uchovávat. Například pro ukládání řetězců v rámci slovníku hybridního stemmeru si bohatě vystačíme s posloupnostmi o maximální délce 255 bajtů, jejich délku tedy můžeme kódovat jako jednobajtovou hodnotu. Pro minimalizaci režie při uložení velkého množství řetězců je vhodné ukládat všechny řetězce do jednoho pole bajtů (objektu typu byte[]). Namísto referencí na objekty typu String je potom jako odkazy na uložené řetězce možné používat offsety v rámci tohoto pole bajtů. Pro lepší srozumitelnost uvedeme způsob zakódování několika řetězců do pole bajtů na příkladu. V příkladu jsou do pole bajtů na uvedené offsety uloženy celkem čtyři řetězce. Délka kódovaných posloupností je určena jednobajtovou hodnotou. offset 0: "Java" offset 5: "Lucene" offset 12: "účř" offset 19: "slovník"

4

0x04 0x06 0x06 0x08 í 0xc3

J 0x4a L 0x4c ú 0xc3 s 0x73

a 0x61 u 0x75

v 0x76 c 0x63 č 0xba 0xc4 l o 0x6c 0x6f k 0xad 0x6b

Spotřeba paměti je uváděna pro 32-bitovou verzi JVM Sun.

63

a 0x61 e n e 0x65 0x6e 0x65 ř 0x8d 0xc5 0x99 v n 0x76 0x6e

Uvedeným způsobem jsou v rámci fulltextové komponenty ve slovníku hybridních stemmerů uloženy kmeny slov.5 Slovník n-gramů používá pro ukládání samotných unigramů, bigramů a trigramů podobný systém kódování. Rozdíl je jen v tom, že n-gramy musí kromě samotných slov uchovávat i informaci o jejich pravděpodobnosti. Tato informace je tedy v kódované reprezentaci ngramů rovněž přítomna. Zmíněná paměťově efektivní reprezentace řetězců je sice velice vhodná pro jejich uchovávání, ovšem neposkytuje žádný způsob pro vyhledávání. V případech, kdy je řetězce nutné používat jako vyhledávací klíč, je v této práci použita paměťově efektivní implementace datové struktury trie. Jak již bylo zmíněno, trie je datová struktura, která umožňuje velmi rychlé vyhledání klíče. Trie je v podstatě stavový automat, jehož stavy představují jednotlivé prefixy slov ve slovníku a přechodová funkce bere v potaz znaky na jednotlivých pozicích v hledaném klíči. Triviální implementace trie, která pro každý stav automatu obsahuje tabulku přechodů podle znaku nalezeného na dané pozici klíče, je paměťově velmi neefektivní a pro větší objem dat nepoužitelná. To je způsobeno tím, že tabulka přechodů pro stavy trie je obvykle velice řídká (z jednoho prefixu slova obvykle existuje několik málo variant přidání dalšího znaku tak, aby vznikl opět prefix slova obsaženého ve slovníku). Většina paměti, která je alokována trií, je tedy spotřebována na prázdná místa v tabulce přechodů. Velmi elegantní řešení, které umožňuje paměť využít efektivněji, je označováno jako triple array trie a je detailně popsáno v [7], včetně návodu k jeho implementaci. Hlavní myšlenka za touto datovou strukturou je uložit množinu stavů a přechodovou funkci do tří polí přirozených čísel. Vtip spočívá v tom, že kompletní přechodová funkce pro všechny stavy je uložena do dvou polí tak, aby bylo možné její část odpovídající některému ze stavů volně přesouvat. Tím, že je možné jednoduše realizovat relokaci přechodové funkce pro daný stav, můžeme volit umístění přechodové funkce tak, abychom využili prázdná místa v přechodových funkcích jiných stavů. Přesný význam položek v jednotlivých polích a princip relokace je popsán v [7]. Datová struktura triple array trie byla v rámci této práce v plném rozsahu implementována a bylo k ní navrženo objektové rozhraní, které zjednodušuje práci s ní a je v souladu s koncepty jazyka Java.6 Zmíněné rozhraní bylo použito pro implementaci slovníku n-gramů a slovníku hybridních stemmerů. Pro zajímavost uvedeme, že kompletní slovník n-gramů obsahující 150 989 unigramů a 1 858 268 bigramů, používající datovou strukturu triple array trie a 5

Použitá implementace zajišťuje, že více duplicitních kmenů bude uloženo pouze jednou, což dále šetří paměť. 6 Viz třídy TrieDictionary a TrieGenericDictionary.

64

uchovávající unigramy a bigramy v kódované podobě zabírá v paměti 180MB. Slovník hybridního stemmeru, který obsahuje 4 213 545 dvojic slovo — kmen zabírá v paměti 107MB. Slovník hybridního stemmeru rovněž používá datovou strukturu triple array trie a kmeny slov uchovává ve struktuře string index.

5.3

Měření výkonu

Aby bylo možné si udělat představu o výkonnosti fulltextové komponenty v praxi, byla provedena řada výkonnostních testů, jejichž výsledky jsou shrnuty v následujícím textu.

5.3.1

Dotazování

Hlavním měřítkem výkonu je samozřejmě rychlost zpracování dotazů a jejímu měření byla také věnována největší pozornost. Aby byla vypovídací hodnota měření co nejvyšší, byla prováděna nad úložištěm obsahujícím 2,7 milionu reálných inzerátů serveru sbazar.cz (viz [data01]). Nad touto sadou inzerátů bylo spouštěno velké množství testovacích dotazů a byla měřena doba jejich zpracování. Použité testovací dotazy byly založeny na logu skutečných fulltextových dotazů ze serveru sbazar.cz. Jak jsmě ovšem již zmínili v předchozích kapitolách, možnosti dotazování ve fulltextové komponentě nejsou omezeny jen na pouhé fulltextové vyhledávání, je možné konstruovat i složitější dotazy. Aby byla zajištěna úplnost měření výkonu, byly reálné fulltextové dotazy pomocí náhodného generátoru omezení doplněny o další složky. Doplňované složky byly omezení na kategorii inzerátu, jeho region, konkrétního autora inzerátu a stav zboží. Nahodný generátor určuje, která omezení budou přidána ke každému z dotazů (mohou to být všechna omezení nebo i žádné). Konkrétní kategorie, region a ostatní omezení jsou pro každý z dotazů určeny rovněž náhodně. Aby bylo zajištěno, že takto vygenerované dotazy jsou smyslupné, jsou z nich v přípravné fázi vybrány pouze ty, které vracejí nějaký minimální počet výsledků (např. 5). Omezení přidaná náhodným generátorem totiž mohou snadno způsobit, že množina výsledků daného dotazu bude prázdná. Čas zpracování dotazu, který nevrací žádné výsledky, přitom není hodnotou, kterou bychom chtěli v rámci měření zjišťovat. Je tomu tak proto, že zpracování dotazu, který nevrací žádné výsledky, obvykle nezahrnuje výpočet skóre dokumentů. Rychlost výpočtu skóre dokumentů je přitom velmi podstatná. Dotazy, jak víme, mohou sestávat z více komponent, kterými jsou prefilter, kritéria, postfilter a řadicí pravidla. Přítomnost těchto komponent dotazu může mít na rychlost zpracování dotazů podstatný vliv, takže měření bylo prováděno zvlášť pro různé možné kombinace komponent přítomných v dotazu. Nejjed65

nodušším měřeným druhem dotazu jsou dotazy obsahující pouze komponentu kritéria. Výkonově srovnatelnou variantou by měly být dotazy, jejichž náhodně generovaná část je přesunuta do komponenty prefilter (tedy dotazy obsahující prefilter a kritéria). Pro určení vlivu řadicích pravidel na dobu zpracování dotazů obsahuje další druh dotazů komponenty prefilter, kritéria a náhodně generovaná řadicí pravidla. Poslední druh měřených dotazů obsahuje všechny čtyři možné komponenty prefilter, kritéria, postfilter a řadicí kritéria. Výkon dotazů s postfilterem byl testován se dvěma implementacemi postfilteru, z nichž jedna používá jednoduché rozhraní postfilteru (tzv. simple postfilter) a druhá používá rozhraní nízkoúrovňové, umožňující dosáhnout nesrovnatelně vyššího výkonu (tzv. quick postfilter).7 Dále bylo měření rozděleno podle implementace přístupu k fyzickému úložišti. Pro demonstraci rychlosti zpracování dotazů nad diskovým úložištěm byl použit typ NIO,8 zatímco pro měření rychlosti zpracování dotazů nad úložištěm v operačním paměti byl použit typ RAM MIRRORED. Měření na úložištěm typu MMAP se nepodařilo z důvodu nedostatku logického paměťového prostoru na testovacím počítači realizovat.9 Kompletní přehled měřených konfigurací, spolu s naměřenými průměrnými časy zpracování jednoho dotazu, je v následující tabulce:

č. 1 2 3 4 5 6 7

Typ úložiště

Druh dotazu

NIO RAM MIRRORED NIO RAM MIRRORED NIO RAM MIRRORED NIO

pouze kritéria pouze kritéria prefilter a kritéria prefilter a kritéria prefilter, kritéria a řazení prefilter, kritéria a řazení prefilter, kritéria, quick postfilter a řazení prefilter, kritéria, quick postfilter a řazení prefilter, kritéria, simple postfilter a řazení prefilter, kritéria, simple postfilter a řazení

8 RAM MIRRORED 9 NIO 10 RAM MIRRORED 7

Počet test. dotazů 20 20 20 20 20 20 5

Trvání 1 dotazu (ms)

000 000 000 000 000 000 000

38.5 12.3 52.1 13.0 27.0 9.8 75.2

5 000

19.4

500

3 147

500

724

Výkon různých implementací postfilteru byl rozebrán v sekci 3.3.2. Možné typy přístupu k úložišti byly rozebrány v sekci 3.6.2. 9 Mapování souborů do paměti je vhodným řešením zejména pro 64-bitové architektury, jejichž logický paměťový prostor je takřka neomezený. 8

66

Na základě uvedené tabulky je možné porovnat výkon jednotlivých komponent dotazů. Z průměrné doby zpracování jednoho dotazu je zřejmé, že výkon konfigurací 2 a 4 (resp. 1 a 3) je srovnatelný, z čehož lze usoudit, že zahrnutí komponenty prefilter do dotazu výsledný výkon v praxi nijak významně neovlivňuje. Komponenta prefilter tedy poskytuje stejně dobrý výkon jako komponenta kritéria a prefiltery je tedy v dotazech možné používat bez omezení. Řazení výsledků podle hodnot některých polí entity (konfigurace 5 a 6) je dokonce rychlejší, než řazení výsledků podle skóre vektorového modelu (výchozí nastavení, konfigurace 1–4). To je patrně způsobeno tím, že v případě řazení podle hodnot polí není třeba pro výsledky dotazu vypočítávat jejich skóre, což představuje výpočetní režii navíc. Rychlá implementace postfilteru (konfigurace 7 a 8) sice čas zpracování dotazů o něco zvyšuje, ovšem uvážíme-li, že postfilter musí vykonávat uživatelsky definovanou operaci pro každý výsledek dotazu, je takovéto zvýšení pochopitelné. V absolutní hodnotě je navíc výkon dotazů s rychlým postfilterem zcela dostačující.10 Na druhou stranu simple postfilter vykazuje výpočetní režii velmi značnou a z měření konfigurací 9 a 10 vyplývá, že pro použitou velikost testovacího úložiště je výkon simple postfilteru nedostačující. To je způsobeno tím, že simple postfilter pro každý výsledek dotazu načítá z úložiště danou entitu a převádí hodnoty jejích polí do externí reprezentace. V konfiguraci 9 a 10 byl průměrný počet entit zpracovaných postfilterem v rámci jednoho dotazu 14 460. To dáva průchodnost simple postfilteru asi 20 000 entit za vteřinu, což lze považovat za dobrý výsledek. Co se týče porovnání výkonu konfigurací, které data úložiště četly z disku, a konfigurací používajících kopii úložiště v operační paměti, výsledek je zřejmý. Vyhledávání se čtením dat přímo z operační paměti poskytuje podle naměřených výsledků několikrát lepší výkon. Nárůst výkonu je dramatičtější, než by se mohlo zdát podle průměrných časů trvání jednoho dotazu. Tento průměrný čas je totiž ovlivněn dlouhou dobou zpracování některých výpočetně náročných dotazů. Takové dotazy se ovšem vyskytují v testovací množině poměrně vzácně. Lepší představu o vztahu rychlosti zpracování dotazů získáme porovnáním histogramů doby zpracování dotazů pro konfiguraci 1 a 2: 10

Výkon postfilteru samozřejmě záleží na složitosti prováděné operace. Pro měření byla použita operace triviální, aby vynikl vliv výpočetní režie postfilteru na výkon.

67

Podobné rozložení doby zpracování jednotlivých dotazů s ohledem na použití uložiště NIO či RAM MIRRORED vykazují i histogramy pro konfigurace 3–10, které ovšem nejsou z úsporných důvodů obsaženy přímo v této práci. Je možné je nalézt jako přílohu uživatelské dokumentace. 68

Jako zhodnocení výsledků měření rychlosti zpracování dotazů lze prohlásit, že výkon fulltextové komponenty v dotazování je zcela dostačující pro většinu praktických aplikací. Fulltextová komponenta zvládne zpracovat více než 50 fulltextových dotazů s doplňujícími omezeními za vteřinu nad úložištěm obsahujícím 2,7 milionu záznamů. Reálná potřeba serveru sbazar.cz je přitom výkon 10 dotazů za vteřinu, tedy mnohem méně. Zmíněná měření byla navíc provedena na obyčejném notebooku (Intel Core 2 Duo 1.6 GHz, 2.5 GB RAM) a při použití vhodnějšího hardwaru se výkon komponenty nepochybně ještě zvýší.

5.3.2

Import dat

Dalším důležitým faktorem výkonu je rychlost importu záznamů z externího zdroje (například z databáze). Import v podstatě představuje dávkové vložení velkého množství záznamů do úložiště najednou. Tím je reflektován jednak výkon komponenty zpracování českého jazyka a také výkon samotné knihovny Lucene při indexování dokumentů. Kompletní přeindexování celého úložiště je třeba provést například při změně použitého stemmeru a změně parametrů doplňovače diakritiky, což může být relativně častá operace.11 Proto je třeba čas na import záznamů do úložiště minimalizovat. Měření rychlosti importu (tedy dávkového vkládání záznamů) bylo provedeno na množině inzerátů serveru sbazar.cz.12 Kompletní vložení 2 723 632 inzerátů (včetně doplňování diakritiky a hybridního stemmingu) trvalo 3 062 vteřin. Předpokládaná rychlost importu je tedy zhruba 900 inzerátů za vteřinu. Jak již bylo zmíněno, rychlost importu záznamů souvisí s výkonem doplňovače diakritiky. Podle provedených měření je doplňovač diakritiky schopen zpracovat zhruba 40 000 slov za vteřinu. Vzhledem k tomu, že doplňování diakritiky je výpočetně složitější než stemming, je výkon stemmerů ještě vyšší než výkon doplňovače diakritiky.

11

V praxi se bude stemmer pravděpodobně doplňován o uživatelský slovník, například v případě inzerátů o skloňování názvu značek zboží. 12 Součástí této práce je i jednoduchá utilita pro import inzerátů sbazar.cz z tabulky v databázi MySQL do fulltextového úložiště.

69

Kapitola 6 Závěr V rámci této práce byla vytvořena komponenta umožňující vyhledávání ve strukturovaných datech a podporující české doplňování diakritiky a stemming. Komponenta byla napsána v jazyce Java a její implementace je tvořena více než než 18 000 řádky kódu.1 Tato komponenta disponuje jednoduchým programátorským rozhraním pro vyhledávání a modifikaci úložiště. Komponenta obsahuje bohaté možnosti konfigurace, což by mělo zajistit její dobrou použitelnost v praxi. Proces zpracování českého textu pro účely fulltextového vyhledávání sestává z doplňování diakritiky, stemmingu a dalších kroků (relativně méně významných). Doplňování diakritiky bylo implementováno na statistickém principu využívajícím n-gramy a použitá teorie byla diskutována v této práci. Dosažená úspěšnost doplňovače diakritiky natrénovaného na datech inzerátů sbazar.cz je 97,19 %. Komponentu doplňování diakritiky je možné používat i samostatně jako nástroj pro příkazovou řádku. Pro potřeby stemmingu bylo vyvinuto pět různých stemmerů, využívajících buď algoritmický přístup, nebo kombinaci přístupu algoritmického a slovníkového (tzv. hybridní stemmery). Dva algoritmické stemmery byly převzaty z literatury a další tři stemmery byly vyvinuty jako jejich vylepšení využívající lemmatizační slovník a v případě jednoho stemmeru také rozpoznávání slovních druhů. Vlastnosti těchto stemmerů byly porovnány a diskutovány. Byl také vyvinut nástroj, který umožňuje detailní srovnání chování jednotlivých stemmerů nad danou množinou slov. Komponenta, která je výsledkem této práce, umožňuje spouštět dotazy skládájící se z více podmínek a řadit výsledky dotazů podle různých kritérií. Uživatel má možnost na různých úrovních obecnosti upravit funkci relevance dokumentů vzhledem k dotazu. Rychlost zpracování dotazů byla testována a následně vyhodnocena jako zcela dostačující požadavkům stanoveným v úvodu 1

Uvedený údaj byl změřen utilitou CLOC a zahrnuje i unit testy.

70

práce. Měření byla také podrobena kvalita fulltextového vyhledávání s ohledem na použití stemmingu a doplňování diakritiky. Ze závěru tohoto měření vyplývá, že hodnota MAP (Mean Average Precision) nad testovacími dotazy byla zahrnutím doplňování diakritiky a stemmingu zvýšena (v závislosti na použitém stemmeru) až o 33 %. Toto měření také ukázalo, že stemmery vyvinuté v této práci vykazují lepší vlastnosti než stemmery převzaté. Pro zajištění dobrého výkonu komponenty byly v implementaci použity některé optimalizační techniky, které měly za následek zvýšení výkonu celého systému a snížení paměťové náročnosti.2 Provedené optimalizace byly popsány v této práci. Vytvořená komponenta by měla být v budoucnu použita jako vyhledávácí jádro serveru sbazar.cz.3

6.1

Budoucí vývoj

Zajímavým pro budoucí práci na fulltextové komponentě by jistě bylo další zlepšování kvality vyhledávání na základě zpětné vazby získané z jejího používání na serveru sbazar.cz, případně z jiných aplikací. Dále by bylo možné fulltextovou komponentu rozšířit o velké množství drobných vylepšení, která jsou ovšem spíše kosmetického rázu. Jedním z nich může být například zahrnutí podpory pro zvýrazňování shody v textu prohledáváných dokumentů oproti dotazu.

2

To bylo klíčové zejména pro slovníkové struktury používané pro doplňování diakritiky a stemming. 3 V době psaní této práce probíhalo testování fulltextové komponenty pro tento účel.

71

Literatura [1] Vrána J.: Obnovení diakritiky v českém textu, diplomová práce MFF UK, 2002. [2] Manning C. D., Raghavan P., Schütze H.: An Introduction to Information Retrieval, Cambridge University Press, 2009 [3] Gospodinetic O., Hatcher E.: Lucene in Action, Manning Publications, 2004 [4] Dolamic L., Savoy J.: Stemming Approaches for East European Languages, LNCS Advances in Multilingual and Multimodal Information Retrieval: CLEF 2007, Budapest, 2007 [5] Dolamic L., Savoy J.: Indexing and stemming approaches for the Czech language, Information Processing and Management, vol. 45, 2009 [6] Frakes W. B., Fox. C. J.: Strength and Similarity of Affix Removal Stemming Algorithms, ACM SIGIR Forum, 2003 [7] Karoonboonyanan T.: An Implementation of Double-Array Trie, 2006, http://linux.thai.net/~thep/datrie/datrie.html [8] Turpin A., Scholer F.: User performance versus precision measures for simple search tasks. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pages 11–18. ACM Press, 2006

72

Použitá data [data01] Historické (neaktivní) inzeráty serveru sbazar.cz, celkem 2 723 632 inzerátů (z období prosinec 2004 až listopad 2009) [data02] Inzeráty serveru sbazar.cz, celkem 269 078 inzerátů (z období listopad 2005 až listopad 2009) [data03] Log fulltextových dotazů serveru sbazar.cz (z období 1.1. až 11.1.2010, celkem 2 861 250 dotazů) [data04] Český slovník programu GNU Aspell 0.60, verze 20040614-1 [data05] Lemmata slov z inzerátů sbazar.cz, získaná pomocí morfologického slovníku češtiny (poskytla pro srovnávací účely Dr. Hlaváčová)

73

Příloha A Obsah DVD DVD příloha této práce obsahuje následující položky: • Elektronickou podobu této práce • Uživatelskou dokumentaci fulltextové komponenty (HTML) • Dokumentaci API fulltextové komponenty (JavaDoc) • Zdrojové kódy fulltextové komponenty (včetně testů) • Demonstrační aplikaci pro spouštění dotazů • Srovnávací HTML reporty jednotlivých stemmerů • Natrénovaný slovník n-gramů pro doplňovač diakritiky • Soubory s daty hybridních stemmerů

74

Příloha B Pravidla tokenizeru doplňovače diakritiky // basic word: a sequence of digits & letters, but has to start with a letter. ALPHANUM = {LETTER}+ ({LETTER}|[:digit:])+ // company names like AT&T and Excite@Home. COMPANY = {ALPHA} ("&"|"@") {ALPHA} // email addresses EMAIL = {ALPHANUM} (("."|"-"|"_") {ALPHANUM})* "@" {HOST} // hostname HOST =

{ALPHANUM} (("."|"-") {ALPHANUM})* "." {ALPHA}

// url (does not cover svn+ssh and another weird protocols) URL = ({ASCII_LETTER}+ "://" {HOST}) | ( [Ww] [Ww] [Ww] "." {HOST} ) // floating point, serial, model numbers, ip addresses, etc. // every other segment must have at least one digit MODEL_NUM = ({ALPHANUM} {P} {HAS_DIGIT} | {HAS_DIGIT} {P} {ALPHANUM} | {ALPHANUM} ({P} {HAS_DIGIT} {P} {ALPHANUM})+ | {HAS_DIGIT} ({P} {ALPHANUM} {P} {HAS_DIGIT})+ | {ALPHANUM} {P} {HAS_DIGIT} ({P} {ALPHANUM} {P} {HAS_DIGIT})+ | {HAS_DIGIT} {P} {ALPHANUM} ({P} {HAS_DIGIT} {P} {ALPHANUM})+) // punctuation (not with "," because this one would //sometimes connect too many words together") 75

P

= ("_"|"-"|"."|"/")

INT_NUM = [:digit:]+ // floating point number, integer number, number in czech notation NUMBER = ( {INT_NUM} | {INT_NUM} {NUM_P} {INT_NUM} | {CZECH_NUM} ) NUM_P = ("."|",") // number in czech notation (with dots for thousands), //possibly with decimal part CZECH_NUM = (({INT_NUM} ((".") [:digit:]{3})+) ((",") {INT_NUM})?) // at least one digit HAS_DIGIT = ({LETTER}|[:digit:])* [:digit:] ({LETTER}|[:digit:])* ALPHA

= ({LETTER})+

// From the JFlex manual: "the expression that matches everything of // not matched by is !(!|)" LETTER = !(![:letter:]) ASCII_LETTER =

[A-Za-z]

WHITESPACE = \r\n | [ \r\n\t\f] %% {ALPHA} { return {NUMBER} { return {ALPHANUM} { return {COMPANY} { return {EMAIL} { return {URL} { return {MODEL_NUM} { return {WHITESPACE} { return /* unknown token */ . { return

TokenType.ALPHA.ordinal(); } TokenType.NUMBER.ordinal(); } TokenType.ALPHANUM.ordinal(); } TokenType.COMPANY.ordinal(); } TokenType.EMAIL.ordinal(); } TokenType.URL.ordinal(); } TokenType.MODEL_NUM.ordinal(); } TokenType.WHITESPACE.ordinal(); } TokenType.UNKNOWN.ordinal(); }

76

Příloha C Pravidla tokenizeru pro fulltextové indexování // basic word: a sequence of digits & letters ALPHANUM = ({LETTER}|[:digit:])+ // internal apostrophes: O’Reilly, you’re, O’Reilly’s // use a post-filter to remove possessives APOSTROPHE = {ALPHA} ("’" {ALPHA})+ // acronyms: U.S.A., I.B.M., etc. // use a post-filter to remove dots ACRONYM = {LETTER} "." ({LETTER} ".")+ // company names like AT&T and Excite@Home. COMPANY = {ALPHA} ("&"|"@") {ALPHA} // email addresses EMAIL = {ALPHANUM} (("."|"-"|"_") {ALPHANUM})* "@" {HOST} // hostname HOST =

{ALPHANUM} (("."|"-") {ALPHANUM})* "." {ALPHA}

// floating point, serial, model numbers, ip addresses, etc. // every other segment must have at least one digit MODEL_NUM = ({ALPHANUM} {P} {HAS_DIGIT} | {HAS_DIGIT} {P} {ALPHANUM} | {ALPHANUM} ({P} {HAS_DIGIT} {P} {ALPHANUM})+ | {HAS_DIGIT} ({P} {ALPHANUM} {P} {HAS_DIGIT})+ 77

| {ALPHANUM} {P} {HAS_DIGIT} ({P} {ALPHANUM} {P} {HAS_DIGIT})+ | {HAS_DIGIT} {P} {ALPHANUM} ({P} {HAS_DIGIT} {P} {ALPHANUM})+) // punctuation P = ("_"|"-"|"/"|".") INT_NUM = [:digit:]+ // floating point number, integer number, number in czech notation NUMBER = ({INT_NUM} | {INT_NUM} {NUM_P} {INT_NUM} | {CZECH_NUM} ) NUM_P = ("."|",") // number in czech notation (with dots for thousands), //possibly with decimal part CZECH_NUM = (({INT_NUM} ((".") [:digit:]{3})+) ((",") {INT_NUM})?) // number with units (use post filter to split into number part and unit part) NUMBER_WITH_UNITS = ({NUMBER} ({LETTER}{1,3})) // at least one digit HAS_DIGIT = ({LETTER}|[:digit:])* [:digit:] ({LETTER}|[:digit:])* ALPHA

= ({LETTER})+

// From the JFlex manual: "the expression that matches everything of // not matched by is !(!|)" LETTER = !(![:letter:]) WHITESPACE = \r\n | [ \r\n\t\f] %% {ALPHA} { return TokenType.ALPHA.ordinal(); } {NUMBER} { return TokenType.NUMBER.ordinal(); } {NUMBER_WITH_UNITS} { return TokenType.NUMBER_WITH_UNITS.ordinal(); } {ALPHANUM} { return TokenType.ALPHANUM.ordinal(); } {APOSTROPHE} { return TokenType.APOSTROPHE.ordinal(); } {ACRONYM} { return TokenType.ACRONYM.ordinal(); }

78

{COMPANY} {EMAIL} {HOST} {MODEL_NUM}

{ { { {

return return return return

TokenType.COMPANY.ordinal(); } TokenType.EMAIL.ordinal(); } TokenType.HOST.ordinal(); } TokenType.MODELNUM.ordinal(); }

/** Ignore the rest */ . | {WHITESPACE}

{ /* ignore */ }

79

Příloha D Seznam použitých stopwords Obecná stopwords pro češtinu a aby aj ale ani asi atd atp až bez bude budem budeš by byl byla byli bylo být co což cz či další dnes do

ho i já jak jakmile jako jakož je jeho jehož jej její jejich jelikož jemu jen ještě jež ji jí jiné již jíž jsem jseš jsme

jsou jste k~kam kde kdo když ke která které kterou který kteří má máte mě mezi mi mít mne můj může my na načež nad nám

80

napište nás naši nebo neg nejsou němu němuž není než nic nové nový o~od on ona oni ono ony pak po pod podle pokud pouze pravé

pro proč proto protože před přes při přičemž s~se si strana své svých svým

svými ta tak také takže tato tedy těm téma těmu ten tento teto tím

tímto tipy to tohle toho tohoto tom tomto tomu tomuto tu tuto ty tyto

u~už v~vám vás vaše ve více však vy z~za zda zde ze zpět

Stopwords specifická pro inzeráty and ano bohužel cosi dle info jde

koupím koupit lze mají mé měl nabízím

nabízíme např ne něm nemám ní prodá

81

prodám prodávám teď the viz že

Příloha E Ukázka konfigurace fulltextové komponenty Tato příloha uvádí ukázku kompletní konfigurace fulltextové komponenty v XML formátu. Ukázka definuje schéma entity „advertisement” reprezentující inzerát serveru sbazar.cz a výchozí analyzátor využívající doplňování diakritiky, hybridní stemming a výchozí sadu stopwords. <entityStorage> <entity name="advertisement" key="id"> <string name="ad_type" stored="true" indexed="true"/> <string name="auction" stored="true" indexed="true"/> <string name="status" stored="true" indexed="true"/> 82

<string name="checked" stored="true" indexed="true"/> <string name="payment" stored="true" indexed="true"/> <string name="state" stored="true" indexed="true"/> <string name="url" stored="true" indexed="false"/> <string name="paid" stored="true" indexed="true"/> <string name="town" stored="true" indexed="false"/> <documentStorage directory="tmp/jfullczservice_dir" storageType="RAM_MIRRORED" readOnly="false"/> <weigths unigramWeight="1.0" bigramWeight="25.0" trigramWeight="35.0" uniformWeight="0.5"/> <defaultStopwords/>

83