Architektura vyhledávačů

Anotace článků z Lupy o vyhledávačích

Články vycházely v roce 2002 na Lupě.cz pod označením Jehla v kupce sena. Psal je autor s pseudonymem Karle Pánek. Žádné jiné odbornější texty o architektuře vyhledávačů jsem v češtině nenašel. Není to lehké čtení, je tam dost matiky. Musel jsem si to vytisknout a číst dvakrát. Jednotlivé články na sebe navazují, takže je to potřeba číst postupně. Nebo použít těchto subjektivních abstraktů:

Odkazy z tohoto článku původně vedly na lupa.cz. Protože provozovatelé tohoto serveru nemají dost úcty k cizím odkazům, články si přestěhovali na jiné URL adresy. Když nestojí o 9 odkazů, jejich blbost. Nebudu ztrácet čas jejich hledáním na "nové Lupě" a poprosím vás, abyste si je dohledali podle ztučněných názvů, chcete-li.

Proč nám fulltextový stroj nerozumí -- úvod do problematiky fulltextového hledání, statistiky o dotazech uživatelů, výpočet PageRanku, zmínění metavyhledávačů.

Jak pracuje metavyhledávač? -- metavyhledávač nemá svojí vlastní databázi dokumentů, ale pokládá dotaz jiným vyhledávačům (dílčí vyhledávač = DV). Nestejnorodost různých DV přináší problém s přesností a řazením výsledků. (To se řeší metaindexem, což je matice, kde ve sloupečcích jsou DV a v řádcích pozice výsledku. Hodnotami jsou čísla určující, jak moc tomu výsledku věříme. Není mi jasné, jak ta čísla získat.) U nás metavyhledávače nejsou, což je podle mého názoru způsobeno velkými náklady na vývoj po spuštění.

Architektury a modely webových strojů -- zmínka o centralizované a distribuované architektuře včetně odkazu na Harvest, což je implementace distribuované architektury používající systém gathererů a brokerů, který jsem z článku nepochopil. Důležitější jsou modely vyhledávání.

Modely vyhledávání:

Vektorový model je důležitý a používaný. Přišlo mi to hodně složité, ale když jsem si to přeložil do selského rozumu, řekl jsem si, že to je logické a přesně takhle bych to implementoval. Dokumenty i dotazy jsou v n-rozměrném prostoru (kde n je počet všech slov) reprezentovány vektory. Souřadnice v n-tém rozměru říká, jak moc je dokument pro n-té slovo relevantní. Dokumenty podobné dotazu mají vektor podobného směru jako vektor dotazu. Ta podobnost se zjistí skalárním součinem (dobře se počítá). Ještě před tím se vektory znormalizují na jednotkovou délku, aby delší dokumenty nebyly bezdůvodně zvýhodněny.

Váha (w) slova v dokumentu se dá počítat různě, v článku je vzoreček zohledňující délku dokumentu i obecnou vzácnost slova.

Rozšířený boolský model -- jak boolský, tak vektorový model potřebují zpřesnit ve chvíli, kdy se hledá více slov najednou. Omezení boolského modelu je dáno tím, že existují pouze stavy 0 - slovo v dokumentu nenalezeno a 1 - slovo nalezeno. Když se ale vezmou v úvahu hodnoty mezi 0 a 1 (jako ve vektorovém modelu) a  metoda výpočtu z boolského modelu, dají se dotazy nakreslit do grafu, z nějž je už vidět vzoreček pro výpočet podobnosti dotazu s dokumentem (podle kterého se budou řadit výsledky).

Ve vzorečku pro rozšířený boolský model je konstanta zvaná p-norma, jejímž nastavením se dají získat výsledky podobné boolskému modelu (p-norma = nekonečno) nebo vektorovému modelu (p-norma = 1). Ale hlavně se dá získat něco mezi! Rozšířený boolský model je teoretickým sjednocením boolského modelu s modelem vektorovým.

Šrotujeme text -- aby vyhledávač mohl přesně indexovat, měl by mít všechny dokumenty postahované. Při ukládání je dobré dokumenty předchroustat (teprve potom se indexují). Lexikální analýza se snaží řešit problémy s tečkami, čísly a podobnými znaky. "Stop slova" jako předložky a spojky se vyházejí, protože jsou stejně všude a nic neznamenají (tím se zmenší index). Stemming je jazykový převod slova na kořenový tvar. Podobně se chová thesaurus, což je slovník synonym. Indexování je předzpracování dat do takového tvaru, aby v tom šlo rychle hledat. Je zmíněna metoda, kdy se pro každé slovo dělá index obsahující id dokumentu plus váhu slova v tom dokumentu.

Jehla v kupce sena: Thesaurus -- thesaurus je slovník synonym. Ve vyhledávačích se používá pro zpřesnění dotazu (např. tak, že jsou do dotazu přidána skrytá slova -- synonyma). Článek se zabývá automatickou výstavbou thesauru (jsou tam vzorce), kdy se na bázi stažených dokumentů provádějí korelační výpočty určující, jak jsou dvojice slov navzájem související.

Sběr zpětné vazby -- vychází se z předpokladu, že uživatelé klikají na ty výsledky, které lépe odpovídají zadanému dotazu. Všechna kliknutí se pomocí redirectu dají monitorovat. Čekal bych, že se to bude nějak započítávat do indexu, v článku je ale popsána možnost ovlivňovat položený dotaz podle konkrétního uživatele. Moc jsem to nepochopil.

Fulltextový stroj na 72 řádcích -- praktický příklad zdrojového kódu (asi) funkčního fulltextového vyhledávače. Program je napsaný v unixovém/linuxovém interpretu sh. Používá běžné utility jako lynx, sort, tr nebo join. Pro jednoduchost indexuje jenom lokálně uložené dokumenty. Výstup je primitivní, ale pro ilustraci to stačí.

Jak vypadá Google uvnitř? -- přehled modulů vyhledávače Google s nástinem funkce. Moduly jsou URL server, crawler, úložiště, indexovač, URL resolver a třídič. Zmíněn algoritmus vyhodnocování dotazu.

Další články Karla Pánka na Lupě jsem pominul, protože mi nepřijdou tak zajímavé. Podle důvěryhodného vyjádření jednoho bývalého redaktora Lupy je autor článků jiná osoba než Karel Pánek, který provozoval vyhledávač Empyreum.

 

Publikováno 22.června 2003

Tento článek je původně z weblogu

 

Reklama

www.webhosting-c4.cz, webhosting s doménou v ceně. 20GB
o tvorbě, údržbě a zlepšování internetových stránek

Návody HTML CSS JavaScript Články Ostatní

Články Katalog zdrojů SEM SEO

Jak psát web píše Yuhů, Dušan Janovský. Kontakt.