Algoritmus internetového vyhľadávača - Stromy a stop slovo
Na internete každú sekundu pribudne 5 miliónov nových stránok a táto rýchlosť sa neustále zvyšuje. Aby bolo možné tomuto obrovskému mori informácií dať nejaký poriadok a niečo v ňom nájsť, tak existujú vyhľadávače. Nasledujúce práce má za cieľ oboznámiť s problematikou vyhľadávanie a vysvetlenie celého postupu od vzniku novej stránky až po jej nájdení vo vyhľadávači.
Úloha nájdenie a zotriedenia množiny miliárd dokumentov nie je vôbec jednoduchý. Samotný Google na túto disciplínu potrebuje 300 tisíc webových serverov, aby túto úlohu zvládol už za niekoľko hodín. Vyhľadávanie vášho dotazu totiž prebieha ďaleko pred tým, než ho položíte. Už teraz má Google v pamäti uložené výsledky hľadania, na ktorej sa budete pýtať v nasledujúcich dňoch.
Architektúra vyhľadávače
Správne navrhnutý vyhľadávač obsahuje veľa komponentov, ktorých je rádovo niekoľko stoviek. Táto schéma opisuje najzákladnejšie prvky, ktoré musia minimálne vyhľadávač obsahovať, aby mohol fungovať. Jedná sa o starú a už nepoužívanú architektúru, ktorá fungovala približne do roku 2005, kým na webe bolo len niekoľko miliónov dokumentov. Táto architektúra nepočíta s "nekonečným" množstvom obsahu a tiež s možnou odstávkou vyhľadávacích serverov (base search). V prípade odstávky hoci aj jediné komponenty by prestal fungovať celý systém a vyhľadávač by bol nedostupný.
Kompletné popísanie aktuálnych trendov v návrhu nových architektúr nie je v silách tejto práce, pretože sa spravidla jedná o obchodné tajomstvo veľkých spoločností. Cieľom tohto textu bude vysvetliť, ako táto základná architektúra pracuje. Jednotlivé komponenty sú podrobne vysvetlené v ďalších kapitolách.
Vstup dotazu
Najviac viditeľnú komponentom aj pre bežných užívateľov je práve vstup dotazu, ktorý je v súčasnej dobe najčastejšie reprezentovaný ako textové políčko. Vstupné políčko je umiestnené na špeciálnej stránke, ktorá je zvyčajne určená len pre vstup.
V ďalšej fáze užívateľ vloží hľadaný reťazec a odošle formulár na servery vyhľadávače a tým začne komunikáciu s výdajovú komponentom, niekedy nazývanú tiež Main search. Výdajové servery sú stavané na obrie záťaže od používateľov a musia zvládať obsluhovať všetky vyhľadávajúci užívateľa naraz.
Architektúra výdajového servera je spravidla obyčajný Apache server so základnou inštaláciou a výbornou dátovou priepustnosťou do siete. Pri vstupe dotaze na server dôjde k jeho spracovaniu cez regresné rozhodovacie stromy a je vytvorená "mapa dotazu", ktorá vystihuje kompletné sémantiku okolo ostatných významov, aby bolo zrejmé, čo používateľ skutočne hľadá. Metódy prepisu dotazu sú až príliš nad rámec tejto práce, preto si len ukážeme všeobecné opisy toho, ako môže a naopak ako nemôže prepis vyzerať.
Majme nasledovný dotaz:
"O pejskovi a kočičce"
Tento dotaz bude prevedený na binárny strom, ktorý zachytáva jeho sémantickú podstatu:
Podstatou celého stromu je zachytenie toho, ako sa bude vyhľadávač na výsledky hľadania pozerať. Tento strom je spolu s dotazom rozoslaný na pomocné vyhľadávacie servery (v tejto práci sú značené ako Base search), kde dôjde k vyhľadanie jednotlivých kľúčových slov (čítanie indexov) a následne k zotriedenia podľa pravidiel (podľa operácií).
| operátor | triediace operácie |
|---|---|
| AND | prienik |
| OR | súčet |
| NOT | doplnok |
O tom, ako funguje samotné radenie výsledkov vyhľadávania pre stránku výsledkov budú pojednávať nasledujúce kapitoly. Výdajové server slúži iba na spojenie mnohých dát z rôznych vyhľadávacích serverov, aby sa zvyšoval celkový výkon a rozkladala záťaž a následne zistené hodnoty vkladá do stránky s výsledkami (tej sa hovorí "webovky") a obsahuje zložené informácie z mnohých desiatok serverov.
Prepis na binárny strom
Ako už bolo povedané v predchádzajúcej kapitole, tak celé vyhľadávanie je stavané na binárnych stromoch, ktoré hovoria, ako budú výsledky vyzerať a čo sa má hľadať. Celá "logika" a "inteligencia" vyhľadávače je priamo závislá na tom, ako kvalitne je vytvorený program, čo taký strom vytvára - totiž, popisovač.
Správne vytvorený strom by mal obsahovať všetky potrebné meta informácie o dotazu v takej podobe, aby ho bolo možné ľahko spracovať aj za pomoci sekvenčného čítania z disku a mal by eliminovať náhodné prístupy do pamäte, preto spravidla obsahuje jednotlivé hľadané slová (od užívateľa), jeho prepisy (a vyskloňované tvary) a v neposlednom rade väzby medzi slovami, teda ich relatívnej vzdialenosti v texte.
Metódy prepisu dotazu
Úplne najzákladnejšie prepis dotazu je jeho parsovanie na jednotlivé slová (podľa medzier), s ktorými sa bude ďalej pracovať. Druhým krokom je vyhľadávanie stop slovo a ich nahradenie za premenlivý ukazovateľ (pretože ako si neskôr ukážeme, tak nemá zmysel stop slovo vôbec vyhľadávať).
Majme nasledujúce otázka: "O psíkovi a mačičke", jeho prepis v úplne najzákladnejším stave vyzerá takto:
"O (and) pejskovi (and) a (and) kočičce"
Druhým krokom je eliminácia slov, ktoré nenesú žiadny význam pre vyhľadávanie. Samozrejme, napríklad slovo "o" alebo "a" pre nás ľudí zmysel má, ale pre hľadanie v databáze nie, pretože ho možno nahradiť iným slovom a vypísať výsledky. Cieľom nemá byť nájdenie doslovné zhody dopytu voči indexu, pretože by to viedlo na zlé výsledky, pretože často bývajú slová v textoch na internete v iných pádoch a táto metóda sa snaží nájsť výsledky aj v iných tvaroch, než ako sme ich získali od užívateľa. Ide teda o prvý náznak "inteligentného" vyhľadávače.
Týmto slovám bez významu sa často hovorí "stop slovo", každý vyhľadávač by si mal viesť register takýchto slov a tento register by mal byť často aktualizovaný (ručne).
["pejskovi (and) * (and) kočičce"]
V tejto chvíli vyhľadávame 2 rôzne slová ( "psíkovi" a "mačičke"), medzi ktorými bolo nejaké ďalšie slovo (interne ho označíme hviezdičkou).
Zmyslom tejto úpravy nie je zvýšenie kvality hľadanie, ale zvýšenie výkonu. Keď totiž hľadáme nejaké príliš frekventované slovo, tak dochádza k rapídnej záťaži a táto úprava tomuto procesu pomáha - najmä tým, že sa nevyhľadáva slovo, ktoré vo väčšine dokumentov rovnako na tejto pozícii bude k dispozícii.
Tiež je dôležité poznamenať, že túto úpravu nemôžeme urobiť vždy (vynechanie slova), preto by si každý vyhľadávač mal viesť samostatný register fráz, ktoré sa na internete vyskytujú, aby mohol overiť, ktorá úprava vedie na dobré výsledky a ktorá nie. Občas túto úpravu ale vyhľadávač vykoná, aj keď túto frázu v indexe nemá - a to najmä vo chvíli, keď používateľ hľadá nejaké významné slovo, na ktoré sa očakáva, že na prvých pozíciách budú významné stránky, čo túto "chybovosť" prebijú, pretože je užívatelia rovnako väčšinou požadujú.
Posledným krokom je práca s češtinou a "čistenie" dopytu od zbytočných znakov. Napríklad na otázky: "práčka," užívateľ zvyčajne očakáva výsledky len na slovo "práčka" a znak čiarky môžeme ignorovať.
Presné metódy toho, ako tento systém funguje, nie sú známe a každý vyhľadávač má svoje. Predpokladá sa, že ide väčšinou len o štatistický model, ktorý tieto úpravy vykonáva na základe znalostí miliárd textov v databáze.
Prepis češtiny je tiež veda sama o sebe, a preto tu bude tiež len základný popis. Vo väčšine prípadov stačí ku každému slovu pridať jeho vyskloňované tvary (podľa slovníka) a tie vyhľadávať spoločne so slovom, čím docielime efektu, že vyhľadávač zvláda nájsť aj dokumenty, kde sa slová nevyskytujú len v základnom tvare (tak, ako je zadal užívateľ), ale nájde i sklonené verzia - čo je veľmi užitočná vlastnosť. Problém tohto prístupu je vo skloňovanie nejasných a problémových slov a tiež vo skloňovanie otázok, ktoré sú krátke (a nemožno preto z kontextu určiť, ako sa má slovo skloniť). Príkladom problémového sklonenie nech slovo "hier".
Majme anglický otázka: "I love hier", zle navrhnutý skloňovač slovo "hier" vyskloňujete napríklad ako: "hry, herné, herňa, ...", preto je tiež potrebné indexovať okolité slová ako frázy a vykonávať skloňovanie len v známych situáciách, alebo použiť iný postup (tu často nastupujú fonetickej algoritmy).
Posledným krokom je odoslanie hotového stromu na Base search servery, kde prebehne samotné vyhľadávanie v bareloch - o tom bude nasledujúca kapitola.
Viac nabudúce u dátových barelov a pavúkov 
