Šrotujeme text

Dosud jsme se zabývali pouze vlastní indexací textů. Ty jsme chápali jako dokumenty obsahující určitý počet rozdílných termů. Ovšem způsoby, jak si tyto termy vyrobit, jsou značně komplikované, přestože by se mohlo zdát, že jde o nejjednodušší fázi celé operace zvané fulltextové vyhledávání. Není tomu tak, a některé chyby mohou naopak posílit nekvalitní chování jádra vyhledávače.

V tomto díle projdeme postupně všechny jednotlivé kroky, jak jdou obyčejně za sebou. Budeme se snažit především o popis základní kostry datového toku strojem, abychom se k jednotlivým částem mohli v budoucnu vracet ve specializovaných kapitolách.

Lexikální analýza

První, co se s dokumentem musí stát, je jeho rozbor na úseky, které jsou buď čísla nebo slova, případně i oddělovače či speciální znaky. Tyto úseky pak tvoří vstupní jednotky – kandidáty na skutečné termy (slova, nad nimiž budeme opravdu stavět index).

Nejjednodušší, a zřejmě i ne příliš ideální způsob, je převod všech znaků netvořících slova na mezery. Poté již můžeme vlastní slova textu číst naprosto bez problémů. Je zde ovšem malý problém v podobě rozdělovačů nebo oddělovačů, které význam daných slov dosti podstatně mění.

Další obrovskou komplikací jsou čísla. Zvažte sami, zda je lepší spojení „480 př.n.l.“ rozčlenit na čtyři slova nebo je pojmout jako slovo jedno? Negativum prvního způsobu řešení můžeme demonstrovat dotazem „480 piv“. Myslím, že takového uživatele nepotěší na výstupu dokumenty z historie.

Stejná potíž může nastat u telefonních čísel (webové stránky s telefonními seznamy), kde je navíc problém s rozdílným zápisem. Taková čísla lze zapsat jako 123–45–678 nebo 12–34–56–78 či 12345678.

Jedno prosté řešení by mohlo být vypuštění všech teček a pomlček. Ale indexujeme-li celý Internet, často se do stránek zamíchá i kus programového kódu. Co si počít například s proměnnými „o.id“ a „oid“? Tím se nám celá věc začíná výrazně komplikovat, protože tečku bychom mohli vypustit, plní-li funkci zkrácení („př.n.l“), zatímco v jiném případě bychom ji nahradili mezerou (tečka za větou).

Eliminace stop slov

Jakmile máme kandidáty na slova, můžeme přikročit k jednoduché eliminaci nevýznamových slov. V češtině se jedná například o spojky, předložky atp. Nemáme-li seznam stop slov dostupný, můžeme přistoupit k jejich eliminaci na základě četnosti výskytu v dokumentech. Má-li slovo svůj idf cca 0,2 (vyskytuje se zhruba v 80 procentech dokumentů), je možné ho bez problémů ignorovat. Důvodem je to, že tak frekventované slovo neposkytuje dostatečnou odlišovací schopnost ve výsledkové listině.

Obrovským přínosem je, že se tak zmenšuje velikost později vytvářeného indexu. Toto zmenšení může nezřídka dosáhnout 40–50 procent původní velikosti. Ve webové praxi se ale eliminuje méně často, protože by mohlo docházet ke snižování hodnot úplnosti dotazů.

Stemming, převod na kořenové tvary

V průběhu našeho seriálu jsme se již mnohokrát zmiňovali o tajemném stemmingu. Nejde o nijak složitou operaci. Zjednodušeně ji můžeme chápat jako proces, při kterém jsou slova převáděna na svůj základní tvar. Není ani natolik podstatné, zda jsou převedena na tvar gramaticky správný, ale spíš o to, aby všechny tvary daného slova byly převedeny na něco, co za tento kořenový tvar prohlásíme (nebo můžeme se zavřenýma očima prohlásit).

Existuje několik metod, které popsanou operaci zajišťují. Mezi velice náročný můžeme řadit tabulkový model, při kterém čteme kořenový tvar z tabulky všech dvojic slovo a jeho kořen. Ten je značně nepopulární, přestože je na známých slovech nejpřesnější. Důvodem je paměťová náročnost.

Mnohem jednodušší a populárnější metody jsou založené na odstraňování přípon. O předpony se v tuto chvíli nebudeme starat, protože je lze téměř v každém jazyce spolehlivě odhalit a zpracovat, nehledě na to, že nepředstavují takový fundamentální problém (předpon bývá zpravidla méně než přípon).

Nejznámější metodou, která odstraňuje přípony, je bezesporu Porterův algoritmus. Ten byl původně realizován pouze pro angličtinu, v současné době existuje již v komplexnější verzi pro mnoho evropských jazyků (viz. projekt Snowball na  www.sourceforge.org).

Thesaurus

Posledním hráčem ve hře může být i modul thesauru. Ten obsluhuje bázi synonym daných slov a v rámci indexovací fáze může vymezit slova vhodná k indexování. Z velkých vyhledávačů implementoval thesaurové praktiky například Yahoo.

Termy thesauru mohou být buď jednotlivá slova, slovní spojení nebo celé fráze. Největší zastoupení má pochopitelně první případ.

Konstrukci thesauru se budeme věnovat v následující zvláštní kapitole, která bude zaměřena na způsoby modifikace uživatelských dotazů. Popíšeme i dvě fundamentální konstrukční techniky a jejich kompletní algoritmy včetně vzorců.

Výroba indexu

Na základě zvoleného modelu můžeme nad připravenými termy konstruovat vlastní index. Téměř všechny současné implementace vyhledávacích strojů používají techniku invertovaných seznamů. Jak něco takového vypadá?

Pro každý term indexu je vytvořen seznam jeho výskytů. V nejjednodušším případě je tento seznam tvořen pouze identifikátory (čísly) dokumentů, ve kterých je dané slovo obsaženo. Spolu s číslem dokumentu mohou být ukládány i další hodnoty, např. v případě vektorového modelu (viz. Architektury a modely vyhledávacích strojů) je ukládána zároveň hodnota w nebo alespoň četnost výskytu slova.

Invertovaný seznam je pak vzestupně seřazen podle čísel dokumentů. To není komplikované zajistit, protože stačí nově příchozím dokumentům přiřazovat stále vyšší a vyšší čísla. Hodnoty, které pak o nich ukládáme do jednotlivých invertovaných seznamů, jednoduše připisujeme vždy nakonec. Tím zabezpečíme požadované uspořádání, které je potřeba pro algoritmy řešící uživatelské dotazy. Tyto algoritmy čtou seznamy vždy sekvenčně (pozn.: ty skutečně nejrychlejší uplatňují i skoky).

Někdy bývá vhodné neukládat přímo identifikátory dokumentů, ale tzv. rozdíly. Tak se dostaneme k prostorově méně náročnému rozdílovému invertovanému seznamu, který si představíme nejlépe na příkladu.

Příklad: Máme invertovaný seznam pro slovo s, kde identifikátory jednotlivých dokumentů s výskytem slova s jsou: id1, id2, id3 atd.

jeho rozdílová verze vypadá takto (všechny rozdíly jsou díky vzestupnému uspořádání vždy kladné):

Výhoda plyne z toho, že menší hodnoty vzniklé ukládáním rozdílu můžeme reprezentovat kratší skupinou bytů, respektive bitů.

Závěr

V tomto díle jsme načrtli základní kostru průchodu dat fulltextovým strojem. Některé jeho části jsme popsali v předcházejících kapitolách a zbývající kamínky mozaiky začneme popisovat následujícími díly.