čtvrtek 15. března 2012

Plnotextová indexace webových archivů, 1. část


V článku Indexace sklizní 2011 jsme přiblížili indexaci souborů ARC, která slouží k vyhledávání, resp. prohlížení obsahu archivu pomocí URL. Dnes se zaměříme na indexaci plných textů (angl. full-text indexing).
 
Vytváření indexů plných textů slouží k vyhledávání v dokumentech pomocí klíčových slov, popřípadě frází. Plnotextová indexace není pro vyhledávání v plných textech nutná, ale značně jej ulehčuje. Bez indexace by bylo nutné prohledávat všechny dokumenty v archívu slovo po slovu přímo při vyhledávání, které by se tím značně zpomalovalo – v archívu s miliony dokumentů trvá vyhledávání v indexu několik milisekund, zatímco při neexistenci indexu by mohlo trvat i několik hodin.

Indexace probíhá zjednodušeně takto: Nejprve je třeba rozhodnout, jaké formáty souborů se mají indexovat – nabízí se např. pdf, html, doc, txt. Pro každý z těchto formátů existuje program, kterému se říká parser nebo také tokenizer. Parser musí být v prvé řadě schopný tyto formáty otevřít a správně zobrazit. Poté postupně prochází celý dokument a identifikuje jednotlivá slova. Pro počítač je text totiž pouze bitstream, tzn. řada jedniček a nul, která sama o sobě nemá žádný význam. Důležité je také “očistit” text – zbavit jej nepodstatného balastu, jako je např. formátování. Musí také určit, která slova jsou součástí vlastního textu a mají být indexována, a která jsou nepodstatná a neindexují se. Např. u webových stránek je třeba odlišit vlastní text od html značek a jiného šumu. Pokud by byl tento šum zahrnut do indexu, došlo by k jeho zkreslení a výsledky vyhledávání by byly nepřesné.

Nalezená slova jsou pak zapsána do indexu, což je v nejjednodušší podobě dvojice hodnot dokument-slovo. Z hlediska vytváření indexu je praktické při indexaci rovnou přiřazovat ke každému indexovanému dokumentu jednotlivá slova, která obsahuje, tzn. zapisovat index v podobě:

dokument A: kočka, leze, dírou, pes, oknem
dokument B: pes, a, kočka, jsou, domácí, zvířata

Tento typ indexu se nazývá dopředný (forward) index. Pro vyhledávání je ale užitečnější tzv. invertovaný index, protože umožňuje rychle vyhledat, ve kterých dokumentech se nachází hledané slovo:

a: dokument B
dírou: dokument A
domácí: dokument B
jsou: dokument B
kočka: dokument A, dokument B
.
.
.

Jak je vidět, rozdíl mezi dopředným a invertovaným indexem je pouze v uspořádání. Invertovaný index se jednoduše vytvoří z dopředného tak, že se setřídí podle slov, místo podle dokumentů, tzn. obrátí se pořadí – proto se jmenuje invertovaný. 

Jednoduchý index dokument-slovo lze využít pouze k vyhledání dokumentů, které obsahují hledané termíny. V obrovském množství dokumentů je ale třeba výsledky hledání take utřídit. Proto se indexy doplňují o další údaje, např. četnost výskytu jednotlivých slov nebo pozice slov v textu. Četnost umožňuje vypočítat relevantnost výsledků (zjednodušeně čím častěji se dané slovo objevuje v dokumentu, tím je tento dokument relevantnější), pozice slov zase umožňuje vyhledávat fráze (slova bezprostředně sousedící, v přesném pořadí) nebo slova, která se vyskytují blízko sebe. To umožňuje zpřesnit výsledky vyhledávání.

V příští části si vysvětlíme specifika indexace webových archivů.