Google.cz/Google.com

Buďte informováni o tom, co vás zajímá na Facebooku! ZDARMA.

Google, provozovaný společností Google, je v současnosti nejpoužívanější internetový vyhledávač.

Vyhledávač původně navrhli Sergey Brin a Larry Page v rámci svého výzkumu na Stanfordově univerzitě, aby ověřili funkčnost svého algoritmu pro ohodnocování webových stránek PageRank. Záhy se ukázalo, že kvalita jeho výsledků natolik převyšovala tehdy dostupné vyhledávače, že je Google v krátké době téměř převálcoval.

Kromě řazení výsledků podle PageRanku bylo v Googlu novinkou i kladení důrazu na vyhledávání frází (takže se nestávalo, že víceslovný dotaz vrátil stránky, kde se tato slova vůbec nevyskytovala pohromadě) a ukládání plného textu indexovaných stránek (které umožňovalo u výsledných stránek rovnou zobrazovat relevantní fragmenty textu).

Indexy

Seznamy hitů obsahují údaje o výskytu slov v dokumentech, a to včetně informací o pozici, velikosti písma a kapitalizaci. Protože tvoří většinu obsahu indexu i zpětného indexu, je důležité je ukládat co možná nejefektivněji; Google pro uložení hitu používá dva bajty. Hity se rozlišují na obyčejné a důležité, přičemž do důležitých se počítají slova obsažená v URL, titulku, textu a odkazů a v meta tazích.

Ve vlastních indexech se před seznam hitů ukládá jeho délka. Aby se dále ušetřilo místo, je délka zkombinovaná s wordID (resp docID ve zpětném indexu), čímž pro délku zbývá 8, resp. 5 bitů. Pokud je hitů více, obsahuje pole pro délku escape kód, a samotná délka je uložena v následující dvou bajtech. Index se rozdělen do skupiny kontejnerů (barrels; prototyp používá 64), přičemž každý kontejner pokrývá určitou část wordID – index je už tedy částěčně setříděn. Pokud dokument obsahuje slova, jejichž wordID spadají do daného kontejneru, je do kontejneru přidáno jeho docID, následované příslušnými wordID a jejich hitlistu. To sice vyžaduje o něco více prostoru kvůli duplikovaným docID, ale zato významně zjednodušuje náročnost úkolu pro třídič(e). Současně umožňuje místo celých wordID (které mají 32 bitů) ukládat jen rozdíl od minimálního wordID v rozsahu – tím pádem pro wordID stačí jen 24 bitů a 8 je možno použít pro počet hitů.

Zpětný index se skládá ze stejných kontejnerů jako index normální; kontejnery jsou jen přetříděny podle wordID. Pro každé platné wordID je pak do slovníku doplněn odkaz do kontejneru s odpovídajícím seznamem dokumentů, které slovo obsahují. Důležitou otázkou je, v jakém pořadí uváděn docID v tomto seznamu. Jednoduchým řešením je řadit je dle docID – to umožňovalo snadné slučování seznamů při zpracování víceslovných dotazů. Další možností je řadit je dle PageRanku dokumentů. Potom jsou odpovědi na jednoslovné dotazy trivialitou a je pravděpodobné, že i nejlepší odpovědi na dotazy víceslovné budou blízko začátku. Google používá kompromisní řešení: má dvě sady kontejnerů: “krátká” obsahuje pouze hity v titulcích a odkazech, “dlouhá” je úplná. Při prohledávání se potom nejprve prověří první sada, a teprve při příliš malém počtu nalezených výsledků se zkoumá druhá.

Vyhledávání

Ohodnocování výsledků dotazů nezahrnuje pouze PageRank, ale i pozici hledaného slova v dokumentu. Hodnocení v Google byla navrženo tak, aby žádný jednotlivý faktor nemohl mít příliš velký vliv na výsledek.

Je-li vyhodnocován jednoslovný dotaz, zkoumá se seznam hitů pro dané slovo. Google má u každého hitu uložen i jeho druh (titulek, text odkazu, URL, obyčejný text velkým písmem, obyčejný text malým písmem, …); každému druhu je pak přiřazena určitá váha. Na tyto váhy lze nahlížet jako na vektor. Stejně tak je ohodnocen počet hitů pro každý druh – ohodnocení na začátku roste lineárně s počtem, ale pak se závislost “narovnává”, takže pokud počet výskytů překročí určitou mez, ohodnocení dále neroste.

Skalární součin vektoru vah a vektoru ohodnocení počtu výskytů tvoří ohodnocení relevance dokumentu, jehož kombinace s PageRankem určí konečné pořadí dokumentu ve výsledku.

Pro víceslovné dotazy je situace komplikovanější – musí se procházet několik seznamů hitů najednou, aby bylo možné ohodnocovat výsledky na základě vzdálenosti jednotlivých výskytů. Pro každou nalezenou skupinu hitů je spočítána vzdálenost výskytu všech nalezených slov v textu dokumentu (nebo odkazu), které je přiřazeno jedno z deseti ohodnocení. Počty výskytů se potom nepočítají jen pro různé druhy hitů, ale i pro každou dvojici druh-vzdálenost. Oba tyto údaje jsou převedeny na příslušná ohodnocení, a jejich skalární součin tvoří ohodnocení relevance dokumentu.