Dokumentografické informační systémy 1

Potřeba ukládat a hlavně následně vyhledávat velké informací v textových dokumentech na základě daného kritéria neustále roste. Vezměte si například libovolný vyhledávač na webu jako je Google, Altavista a jiné fulltexty. Kolikrát denně něco hledáte? Veškerá data zabírají desítky i stovky terabajtů diskového prostoru a přesto váš dotaz bývá zodpovězen téměř okamžitě.

Upozornění: Protože některé části textu vyžadují náročnější sazbu, se kterou jsou v případě HTML problémy, zapsal jsem taková místa v syntaxy LaTeXu. V případě zájmu si můžete stáhnout PDF offline verzi tohoto i druhého dílu, kde je sazba dle požadavků.

V našem povídání se zaměříme na tzv. dokumentografické informační systémy (zkráceně DIS), tedy na systémy pro práci s textovými daty, jejich zpracování, ukládání a výběr dokumentů odpovídajících uživatelskému dotazu.

Sledování informací o dokumentech je jistě všem dobře známo z knihovnictví, kde se tvořily (a leckde dodnes tvoří) různé lístky popisující knihy a následně zatřiďovaly do kartoték. Postupnou automatizací těchto procesů vznikaly první DIS, které vytvořily samostatnou podčást informačních systémů (viz dále). První zmínky o automatickém vyhledávaní informací jsou již více než padesát let staré. Původní systémy byly založeny na sekvenčním prohledávání dat, ovšem postupem času se vyvinuly různé metody indexace jako jsou hašovací funkce či signaturové metody a další (o některých bude řeč), které dobu odezvy výrazně zkrátily.

Nejprve si ale DIS alespoň částečně zařaďme do kontextu. Informační systémy můžeme rozdělit do dvou velkých části: faktografické a dokumentografické. První jmenované zpracovávají informace o pevně dané vnitřní struktuře, typicky uložené v tabulkách relačních databází. Jako příklad uveďme personální informační systém, kam se ukládají data o zaměstnancích. V databázi bývá tabulka OSOBA, která obsahuje sloupce JMÉNO, PŘÍJMENÍ a další. DIS oproti tomu uchovává informace o textech v přirozeném jazyce bez pevné vnitřní struktury jako mohou být zákony, životopisy, příspěvky v elektronických konferencí a podobně.

Dokumentografické informační systémy rozdělujeme do dvou relativně samostatných (nikoliv však nezávislých) částí. První je subsystém zpřístupnění dokumentu. Ten podle uživatelského dotazu poskytne tazateli seznam sekundárních informací (název dokumentu, autor, rok vydání, vydavatel, stručný obsah apod.) o dokumentech, které uvedenému dotazu vyhovují. Dále je ve výsledku informace o umístění dokumentu (při internetovém vyhledávání např. Googlem je to klasický odkaz na stránku). Druhou částí DIS je subsystém dodání dokumentu, který na základě výstupu ze subsystému zpřístupnění dokumentu poskytne tazateli celý požadovaný dokument. Jako příklad si můžeme vzít knihovnu. Pokud hledáte dostupné knihy od Karla Čapka, počítač vám zobrazí (či si v kartotéce najdete) seznam knih, které jsou v knihovně. Subsystémem dodání dokumentu je pak obsluhující personál, kterému povíte, jakou knihu chcete, a on vám ji donese.

Dotazování

Ukažme si nejprve, jak pokládání dotazu funguje ve faktografických informačních systémech. Tam lze vyhledávat pomocí různých kritérií (např. omezit výšku platu, místo bydliště), ale vždy vyhledáváte na úplnou shodu a to i v případě, kdy používáte např. operátor LIKE jazyka SQL. Vezměme si pro ukázku následující dotaz:

SELECT NAME, SURNAME
  FROM OSOBA
    WHERE NEJOBLIBENEJSI_POHADKA LIKE "%liška%"

Výsledkem dotazu budou všechna jména a příjmení osob, které mají oblíbenou pohádku, v jejímž názvu se vyskytuje slovo „liška“. Tedy na výsledek se nedostanou ti, kteří zbožňují pohádku „O lišce Bystroušce“, což sice naprosto přesně odpovídá položenému dotazu, ovšem uživatel DISu bude očekávat odlišné chování.

Tazatel, který hledá relevantní dokumenty v informačním systému, se dostává do křížku s kritériem predikce, tedy s problémem, jaké termy v dotazu zvolit, aby se na výstup dostaly vhodné dokumenty. Opět jeden příklad ze života. Kolikrát jste zadali např. na Altavistě dotaz a výsledkem byly desítky či stovky odkazů? A kolikrát jste dotaz upřesnili (zpřísnili) třeba jen o jediné slovo (v textu budu používat i širší pojem term) a výsledkem byla prázdná množina odkazů? Pokud ani jednou, pak nevěřím, že jste takový vyhledávač použili. Problémem je tedy schopnost uživatele klást dotaz. Položit správný dotaz je často kouzelnickým uměním než seriózní prací.

Kvalitní DIS vrátí všechny záznamy bez ohledu na pád a/nebo číslo uvedeného podstatného jména. Nástroj, kterým se převedou slova do základních tvarů se jmenuje lemmatizátor. Jeho implementace je poměrně složitá a je závislá na cílovém jazyku. Např. lemmatizátor pro češtinu je výrazně náročnější než třeba pro angličtinu (právě kvůli skloňování).

Některé DISy dovolují uživateli dotaz ladit. Interakce se systémem může vypadat následovně:

1. Uživatel zadá dotaz způsobem, který je pro DIS či jeho nadstavbu akceptovatelný (jako nadstavbu si můžete představit libovolný nástroj, který spojuje více internetových vyhledávačů v jedinou stránku). V dotazu jsou obsaženy termy, o kterých uživatel předpokládá, že budou v dokumentech, které jsou pro tazatele relevantní. Zde vstupuje na scénu již uvedené kritérium predikce — čím „lepší“ termy budou zvoleny, tím více relevantních dotazů se dostane na výstup.
2. Nyní dojde k vyhodnocování položeného dotazu (popis vyhodnocení viz dále v části Vyhodnocování dotazu).
3. Pokud je uživatel s výsledkem spokojený, pokračuje následujícím bodem, jinak se snaží upravit (ladit) dotaz tak, aby výsledek více odpovídal jeho potřebám. Účelem ladění je přidat některé termy, které omezí velikost výslednou množiny, nebo naopak některé vypustit či modifikovat (tedy uvést synonyma, jiný pád apod.).
4. V tomto kroku uživatel prochází některé dokumenty, na něž získal odkaz (a další sekundární informace) v druhé části (představte si to tak, že ve výsledku vyhledávače procházíte ty stránky, které vám — subjektivně — připadnou jako nejvíce vyhovující). Pokud není v DIS implementována část subsystém dodání dokumentu, je tento krok vynechán.

Problémem, se kterým se běžný uživatel setkává, je kritérium maxima. To říká, kolik výsledných dokumentů je ještě uživatel akceptovat a projít (pročíst). V praxi to bývá dvacet až padesát dokumentů a pokud jich je více (případně méně), pak typicky tazatel provádí další ladění dotazu. Od DIS se očekává, že výsledná množina dokumentů (odkazů na dokumenty) bude seřazena od nejvíce vyhovujícího dotazu až po nejméně odpovídající (o řazení výsledků si povíme přístě).

Vyhodnocování dotazu

Po položení dotazu vyhledávací algoritmus projde množinu dokumentů (tzv. fulltextové vyhledávání) a vrátí uživateli výsledek (viz následující obrázek).

Intuitivně je zřejmé, že čím jsou dokumenty delší a/nebo jejich počet je větší, není výsledek dodán v čase, který bychom mohli nazvat uspokojivý. Např. fulltextově vyhledávat dokumenty uložené na CD-ROMu by bylo značně časově náročné. Z tohoto důvodu vznikly metody, které prohledávání urychlují. Kromě vyhledávacích algoritmů popsaných v části Vyhledávací algoritmy to jsou další metody využívající indexy. Index je souhrn informací, které dokument reprezentují. Při prohledávání se pak neprochází celý text, ale pouze tyto indexy (viz další obrázek).

Indexace (tedy proces, kdy se dokumentu přiřadí množina indexových slov) probíhá dvěma možnými způsoby. Prvním z nich je indexace ruční, kde dokument indexuje živá osoba — indexátor. Ruční indexace ovšem s sebou přináší několik problémů: stejná osoba v různém čase nevytvoří pokaždé stejný index. Je to způsobeno např. její postupnou specializací, duševním rozpoložením a dalšími faktory. V případě, že dokument indexují dva či více lidí, opět nedojde ke shodným výsledkům. Uvedené problémy jdou ruku v ruce s kritériem predikce, protože výsledné indexy jsou nekonzistentní.

Druhý způsob je indexace strojová a výsledek spočívá v kvalitě DIS (ovšem i v případě, že se nepoužije příliš kvalitní algoritmus pro indexaci, výhodou bude konzistentní index). Při strojové indexaci se vychází z dodané množiny termů.

Proces indexace může probíhat řízeně i neřízeně. Při řízené indexaci je předem stanovena množina indexovaných termů a jediným problémem je vhodný výběr těchto termů (viz dále). Na druhou stranu při neřízené indexaci může (ale nemusí) být množina indexovaných termů prázdná a v průběhu indexování je upravována různými algoritmy. Jakýmsi hybridem mezi řízenou a neřízenou indexací je algoritmus, který na začátku prohledá všechny dokumenty a na základě četností jednotlivých slov (a případně dalších parametrů) vytvoří pevný index termů, podle kterého se dokumenty budou indexovat. Nevýhodou je pak přidávání nových dokumentů, kdy buďto dochází k reindexaci všech dokumentů a nebo se sice použije stávající index, ovšem leckdy za cenu špatně zvolených termů (zde záleží na povaze současných a nových dokumentů).

Jaké termy jsou pro indexaci nejvhodnější? Dejme tomu, že budeme tvořit index pro všechna čísla Softwarových novin. První, co nás může napadnout, že zvolíme jako indexové termy „software“, „hardware“ a „sítě“. Ovšem hned při prvním dotazu na ta čísla, kde se vyskytuje slovo např. „software“, zjistíme, že se na výsledek dostala všechna čísla. Tedy tudy cesta nevede. Je vidět, že zařazení těchto termů do indexu nijak výsledek neovlivní. Podobně jako tyto termy je špatné volit takové, které se v textu skoro vůbec nevyskytují. Optimální je tedy zvolit zlatou střední cestu a zvolit takové termy, které se vyskytují v přibližně polovině všech dokumentů (viz graf na následujícím obrázku):

Je samozřejmé, že existují termy, které nemá cenu do indexu vkládat. Jedná se o slova, která mají pouze doplňující charakter jako jde o zájmena, spojky, částice a podobně. Seznamu těchto termů se říká stop list.

Interval uvedený na obrázku lze samozřejmě zúžovat či rozšiřovat podle potřeby. V případě zúžení se sice zmenši velikost indexu, ale zároveň se při indexaci přijde o informace, které by mohly sloužit k lepším výsledkům vyhodnocování dotazů.

Některé indexy mohou mít termy mezi sebou provázány buďto vztahem synonymových a/nebo vztahem nadtermů a podtermů (tzv. strukturované indexy či tezaury). To do značné míry velmi pozitivně ovlivňuje kritérium predikce, protože uživatel nemusí přemýšlet o všech možných vztazích mezi termy, které v dotazu zadává. Pokud například v dotazu uvede, že potřebuje dokumenty obsahující term „operační systém“, pak díky strukturovanému indexu může DIS do výsledku zahrnout i ty dokumenty, které sice uvedený term neobsahují, ale obsahují podtermy „Windows“ či „MacOS“.

Vyhledávací algoritmy

Vyhledávání v textech je základním úkolem DIS. Na základně položeného dotazu případně při tvorbě indexů je potřeba projít všechny dokumenty a určit, zda se termy v systému vyskytují či nikoliv.

Algoritmy pro vyhledávání prošly poměrně velkým vývojem a v této části si představíme ty nejznámější. Vůbec v prvních DIS byl použit takzvaný triviální algoritmus (neboli průchod hrubou silou). Jde o nejjednodušší, ale zároveň o časově nejnáročnější algoritmus. Vyhledávaný vzorek se postupně přikládá k textu a porovnává se od první pozice vzorku. Při první neshodě se vzorek posune o jednu pozici doprava a porovnání začne opět od první pozice vzorku. V dalším textu budu označovat délku textu písmenem m a délku vzorku n. Časová složitost uvedeného algoritmu je pak O(m.n) (v přirozených jazycích ovšem nedochází ke shodám prvních písmen slov příliš často a složitost je tedy menší).

Knuth-Morris-Prattův algoritmus (dále jen KMP) se snaží odstranit nejvýraznější nevýhodu triviálního algoritmu, kterou je posun v případě neshody o jedinou pozici. Před vlastním prohledáváním dojde k předzpracování vzorku tak, aby v případě neshody došlo k jeho posunu o maximální možný počet znaků. Časová složitost je pak O(m+n).

V případě, že chceme vyhledávat více vzorků v textu najednou, museli bychom předchozí algoritmy použít několikrát, což by dramaticky zvýšilo časovou složitost. Na pomoc ovšem přichází Aho-Corasickové algoritmus, který je postaven na deterministickém automatu, který je definován množinou stavů, abecedou, počátečním stavem, koncovými stavy a dopřednou a zpětnou funkcí. Při vlastním vyhledávání je v případě shody vzorku s textem postupováno pomocí dopředné funkce na základě pozice v textu. V opačném případě se použije zpětná funkce. Pokud vyhledáváme jediný vzorek, dostaneme KMP algoritmus. Časová složitost je O(m+délka všech vzorků).

Zcela opačně (doslova i dopísmene) na to jde Boyer-Moore algoritmus. Ten prochází text protisměrně. Vzorek je porovnáván od konce a v případě neshody se posune o maximální možný počet znaků doleva a opět se začne porovnávat od konce vzorku. Pro přirozené jazyky a dostatečně mohutnou abecedu je složitost O(m/n).

Kombinací algoritmu předchozího a Aho-Corasickové získáváme Commentz-Walterové algoritmus.

Rychlým a hardwarově snadno implementovatelným je Shift-OR algoritmus. Protože se jedná o jednoduchý a poměrně i zajímavý algoritmus, popíšeme si jej důkladněji. Mějme abecedu \sigma = a₁,\dots,a_n Nad touto abecedou je dán vyhledávací vzorek V = v₁,\dots,v_m Definujeme si incidenční matici X o rozměrech m*n, kde prvek X_{ij} = 0, pokud v_i = a_j a X_{ij} = 1 jinak. Tedy každý sloupec této matice je tvořen m-bitovým binárním řetězcem (označme je jako A_j). Na začátku si inicializujeme ještě jeden binární řetězec R, který má na všech pozicích jedničku. V průběhu algoritmu se v každém kroku řetězec R posune o jednu pozici dolů (s tím, že horní pozice se naplní nulou) a ze vstupu se přečte jeden znak textu, ve kterém se vyhledává. Jestliže je přečtený znak textu roven znaku a_j, výsledek posunu se binárně sečte s řetězcem A_j. Dostaneme tedy přechodovou funkci \delta(R, a_j) = SHIFT ® OR A_j. Pokud se na dolní pozici řetězce R dostane nula, hledaný vzorek jsme našli.

Ač to vypadá celkem složitě, následující příklad ukáže, že jde o jednoduchý postup. Hledejme vzorek „DELPHI“, definovaný nad abecedou \sigma = {D, E, H, I, L, P, *}, kde * je libovolný znak nevyskytující se ve vzorku. Incidenční matice tedy bude vypadat následovně: $X = \pmatrix{ & D & E & H & I & L & P & * \cr D & 0 & 1 & 1 & 1 & 1 & 1 & 1 \cr E & 1 & 0 & 1 & 1 & 1 & 1 & 1 \cr L & 1 & 1 & 1 & 1 & 0 & 1 & 1 \cr P & 1 & 1 & 1 & 1 & 1 & 0 & 1 \cr H & 1 & 1 & 0 & 1 & 1 & 1 & 1 \cr I & 1 & 1 & 1 & 0 & 1 & 1 & 1 \cr }$ Text, ve kterém budeme hledat, může být např. „DEJ MI DELPHI“. Na následujícím obrázku je vidět, jak se postupně mění řetězec R: $R = \matrix{ & begin & D & E & J & \_ & M & I & \_ & D & E & L & P & H & I \cr D & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \cr E & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \cr L & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \cr P & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \cr H & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \cr I & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \cr }$

Další algoritmy mohou akceptovat regulární výrazy případně další vymoženosti. Zájemce o podrobný popis uvedených algoritmů (a potažmo DIS) odkazuji na http://www.ms.mff.cuni.cz/~kopecky/dis.

Měření úspěšnosti DIS

Posouzení kvality (informativnosti) DIS vychází ze subjektivní spokojenosti tazatele s nalezenou množinou dokumentů. S tím souvisí pojem relevantní dokument. Jde o takový dokument, který zcela odpovídá požadavku uživatele. To, že je nějaký dokument relevantní, ovšem ještě neznamená, že se dostane do výsledné množiny dokumentů a naopak dokumenty, které relevantní nejsou, se do výsledku dostat mohou. Tato skutečnost je důsledkem kritéria predikce.

Zaveďme si nyní dva důležité pojmy. Koeficient úplnosti (značí se R z anglického Recall) je podíl počtu relevantních dokumentů ve výsledné množině a počtu všech relevantních dokumentů v systému: $R = \frac{N_{\hbo­x{relevantních ve výsledku}}}{N_{\hb­ox{celkem relevantních}}} \in <0;1>$ Uvedený podíl nám tedy říká, jaká je pravděpodobnost, že bude relevantní dokument ze systému vybrán.

Druhým pojmem je koeficient přesnosti (značíme P z anglického precision), který je definován jako podíl všech vybraných relevantních dokumentů a počtu všech dokumentů ve výsledné množině: $P = \frac{N_{\hbo­x{relevantních ve výsledku}}}{N_{\hb­ox{celkem vybraných}}}\in <0;1>$ Oproti předchozímu koeficientu nám tento říká, jaká je pravděpodobnost, že vybrané dokumenty jsou relevantní.

V ideálním případě by měly být oba koeficienty rovny jedné, tedy že všechny vybrané dokumenty ve výsledku jsou relevantní a že v systému již žádný jiný relevantní není. Bohužel v praxi jdou hodnoty těchto koeficientů proti sobě: čím vyšší přesnost, tím menší úplnost a opačně. Hodnoty dvojit <R,P> se tedy pohybují v okolí hyperboly (viz obrázek níže).

Závěr

V tomto úvodním přehledu se představily dokumentografické informační systémy poněkud z jiného pohledu, než jak k nim v každodenní praxi přistupujeme. V příštím díle se podíváme na dva základní modely DIS — booleovské a vektorové. Popíšeme jejich principy, výhody i nevýhody a podíváme se na řazení výsledné množiny dokumentů odpovídajících položenému dotazu.