Vyhledávání 1

32. hodina MVOP WBF

Matěj Cajthaml — SSPŠ

©

Opakování

Co je to vyhledávač?
Co je to crawler, co dělá?
Co spravuje indexer?
Co je to index?
K čemu slouží systém Promise?

Booleanový model

Booleanový model

  • počítejme, že máme stránku s textem (tj. bez tagů)
  • tento model nám dovoluje v takových textech hledat
  • máme 2D tabulku, kde řádky jsou slova a sloupce jsou stránky, na kterých se nachází
  • v každé buňce je 1, pokud je slovo na stránce, jinak 0

Ukázka tabulky

Stránka 1 Stránka 2 Stránka 3 Stránka 4
text 1 1 1 1
je 1 1 1 0
krásný 1 0 0 0
nejkrásnější 0 1 0 0
stránka 0 0 1 1

Jednoduché hledání

  • jednoduché dotazy: nejkrásnější
  • stačí se podívat na řádek s tímto slovem a vrátit hodnoty s 1

Ukázka jednoduchého dotazu

Stránka 1 Stránka 2 Stránka 3 Stránka 4
text 1 1 1 1
je 1 1 1 0
krásný 1 0 0 0
nejkrásnější 0 1 0 0
stránka 0 0 1 1

Co budeme dělat, když chceme ale najít nejkrásnější stránku?

Složitější dotazy

  • např. dotaz: nejkrásnější AND stránka
  • postupně zpracováváme slova a výsledky spojujeme pomocí AND
  • lze používat další operátory: AND, OR, NOT či další

Ukázka složitějšího dotazu

nejkrásnější OR stránka

Stránka 1 Stránka 2 Stránka 3 Stránka 4
text 1 1 1 1
je 1 1 1 0
krásný 1 0 0 0
nejkrásnější 0 1 0 0
stránka 0 0 1 1
VÝSLEDEK 0 1 1 1

Jak vypadají výsledky dotazu?

Předzpracování dat

  • před vytvořením tohoto indexu je nutné data předzpracovat
  • např. odstranit interpunkci, číslice, převedení na malá písmena
  • např. často se používá stemming (odstranění koncovky slova)
  • např. krásný a krásnější se spojí do jednoho slova
  • ... a další
  • je nutné provést i na samotný dotaz

Jak tato tabulka — index, bude velký? Kolik bude mít řádků a sloupců?

Invertovaný seznam

  • místo velké tabulky použijeme seznamy
  • každé slovo bude mít seznam stránek, na kterých se vyskytuje
  • seznam bude seřazený
  • nad seřazeným seznamem se dělají akce velmi jednoduše

Ukázka invertovaného seznamu

mám 1 3
rád 1 2
mvop 1 2 3 4
je 1 2 3 4
krásný 3 4 12 15 203

Může nastat, že dotaz (mvop AND krásný) AND rád bude rychlejší než mvop AND (krásný AND rád)?

Je to, že stránka obsahuje nějaké slovo, dostatečným ukazatelem, že je stránka dotazu relevatní?

Takto ale asi na Googlu nehledáte, ne?

Výhody

  • jednoduché pro uživatele
  • přesné

Nevýhody

  • velmi pomalé, mnoho zbytečného počítání
  • nevhodné pro složité dotazy, dotazy nejsou jen binární operace
  • ignoruje frekvenci slov, jejich relevanci a význam
  • vrací neseřazený seznam
  • ignorujeme sémantiku webu a jeho tagů

Toto vyhledávání se hodí právě tehdy, když víte co hledáte. Což skoro nikdy nevíte.

Rozšířený Booleanový model

Rozšířený Booleanový model

  • řešení toho, že výsledek dotazu není seřazený a je příliš přesný
  • jednotlivá slova místo toho, zda je stránka obsahuje, hodnotíme
  • hodnocení je číslo od 0.00 do 1.00, např. podle frekvence
  • výsledky jsou získány obyčejnými akcemi (> 0.0) a poté dle hodnocení seřazeny

Ukázka tabulky

Stránka 1 Stránka 2 Stránka 3 Stránka 4
mám 0.43 0.00 0.45 0.0
rád 0.43 0.11 0.00 0.03
mvop 0.43 0.43 0.43 0.43
je 0.95 1.00 0.23 0.47
krásný 0.00 0.00 0.00 0.01

Jak počítáme hodnocení celého dotazu vůči jedné stránce?

Výhody

  • jednoduché pro uživatele
  • řadí výsledky dotazu

Nevýhody

  • velmi, velmi časově náročné
  • ignorujeme sémantiku webu a jeho tagů

Děkuji za pozornost!

  • matej.cajthaml@ssps.cz
  • https://ssps.cajthaml.eu/