Úvod do databázových systémů B RNDr. Jan Lánský, Ph.D. 1. přednáška
Fulltextové vyhledávání
Slajdy 3-26 převzaty z Michal Kopecký: Databázové Aplikace (DBI026, MFF UK)
Obsah přednášky • Teoretické základy fulltextového vyhledávání (slajdy 3-26) • Webové vyhledávače (slajdy 27-34) • Webový vyhledávač google (slajdy 35-47) • Příklady na cvičení (slajdy 48-50) • Databáze odborných článků ProQuest 2
Fulltextové vyhledávání – Prohledávají se volně psané texty, kde můţe být stejná událost popsaná více autory rozdílně • Různá slova stejného významu (Synonyma) • Různé slovní obraty a opisy •…
3
Porozumění textu • Posloupnost slov v přirozeném jazyce. • Kaţdé slovo zastupuje pro autora nějakou představu, kterou v něm slovo vyvolá - význam. • Tyto představy reprezentují reálné předměty.
... 4
Porozumění textu • Synonymie slov – Více slov můţe mít pro autora stejný význam • krychle = kostka • buldozer = nakladač
... 5
Porozumění textu • Homonymie slov – Jedno slovo můţe mít pro autora několik významů • • • •
taška: střešní, nákupní koruna: platidlo, královská k., k. stromu třída: školní, kategorie v teorii mnoţin los: zvíře, poukázka ke slosování
... 6
Porozumění textu • Homonymie slov – Jedno slovo můţe pouţívat stejný tvar pro různé pády a další gramatické jevy (gramatická homonymie) • kontroly: 1. p. m.č., 2. p. j.č. není zřejmé, zda se jedná o jednu, nebo více kontrol
– Jeden tvar slova můţe mít různý význam • • • • •
plesy: podst. jm. ples, podst. jm. pleso žena: podst. jm. žena, sloveso hnát hnát: sloveso hnát, podst. jm. hnát tři: číslovka tři, sloveso třít pět: číslovka pět, sloveso pět 7
Porozumění textu • Významy slov se mohou překrývat. – Hierarchicky • zvíře > kůň > hřebec
– Asociace • kalkulátor ~ počítač ~ procesor
... 8
Porozumění textu • Jednotlivá přiřazení jsou navíc závislá na subjektu, který dokument píše nebo čte. – Dva lidé mohou jednomu slovu přikládat zcela nebo jen částečně jiný význam. – Dva lidé si i pod stejným významem mohou představit jiný konkrétní předmět nebo mnoţinu předmětů. • máma, pokoj, ...
• Výsledkem je situace, kdy dva různí čtenáři nemusí přečtením získat stejnou informaci jako autor, ani navzájem. 9
Porozumění textu • Homonymie a nejednoznačnosti narůstají při přechodu od slov k větám. – Homonymie vlastních jmen na začátku věty • Dohnal zvítězil. (Čtrnáctý zvítězil.) • Dohnal předešel gen. Kvapila velmi výrazně. - jedna, nebo dvě věty?
– Homonymie spojky a v předmětu věty • Funkce rezistoru a zesilovače v radiotechnice. (funkce rezistoru v radiotechnice) a (funkce zesilovače v radiotechnice) (funkce rezistoru) a (funkce zesilovače v radiotechnice) (funkce rezistoru) a (zesilovače v radiotechnice)
– Homonymie podmětu a předmětu • Popílek přikryl sníh. – co leţí navrchu? 10
Porozumění textu • Příklad české věty s více gramaticky moţnými významy – viz např. Podivné fungování gramatiky, http://www.scienceworld.cz/sw.nsf/lingvistika
– věta „Ženu holí stroj“ můţe - podle volby přísudku ve větě - znamenat: • • • •
Poháním stroj pomocí hole (hnát) Ţena pouţívá depilační přístroj (holit) Návod k nekonvenčnímu způsobu oblékání (strojit) … a další 11
Porozumění textu • Příklad anglické věty s více gramaticky moţnými významy – viz např. Podivné fungování gramatiky, http://www.scienceworld.cz/sw.nsf/lingvistika
– věta „Time flies like an arrow“ můţe - podle volby přísudku ve větě - znamenat: • Čas letí jako voda (fly) • Časové mouchy/zipy mají rády šíp (like) • … a další 12
Fulltextové vyhledávání • Samotná formulace dotazu, který by vrátil všechny dokumenty, které tazatele zajímají a ţádné jiné obvykle nelze zformulovat – Spolu s vyhovujícími – relevantními – odpověďmi se obvykle vrací i odpovědi nerelevantní
13
Fulltextové vyhledávání • Striktní boolská logika není pro formulaci dotazů příliš vhodná – Dokument buďto vyhovuje dotazu, nebo nevyhovuje – Dotazování v textech vyţaduje třídit odpovědi podle předpokládané vhodnosti pro tazatele • Je potřebné mít moţnost definovat míru shody dotazu s dokumentem 14
Přesnost a úplnost • Dva DIS mohou vrátit na shodný dotaz různé odpovědi, které se nemusí překrývat ani v jediném vráceném dokumentu Jak porovnat kvalitu odpovědí navzájem?
Dokumenty v databázi Vrácené v DIS2 Relevantní dokumenty Vrácené v DIS1
15
Přesnost a úplnost • Dva tazatelé mohou mít při poloţení shodného dotazu různý názor na relevanci vrácených dokumentů Jak vyhovět subjektivnímu názoru tazatelů?
Dokumenty v databázi
Relevantní
Relevantní Vrácené dok.
16
Přesnost a úplnost • Kvalita výsledné mnoţiny dokumentů se měří na základě těchto čísel – Přesnost (Precision) • P = Nvr / Nv • Pravděpodobnost, ţe dokument zařazený v odpovědi je skutečně relevantní
– Úplnost (Recall) • R = Nvr / Nr • Pravděpodobnost, ţe skutečně relevantní dokument je zařazený v odpovědi 17
Přesnost a úplnost • Koeficienty jsou opět závislé na subjektivním názoru tazatele • Dokument vrácený na výstupu můţe uspokojovat poţadavky dvou uţivatel, kteří poloţili stejný dotaz, různou měrou.
18
Přesnost a úplnost • V ideálním případě 1 – P=R=1 – V odpovědi jsou zařazeny právě a pouze všechny relevantní dokumenty
Optimum
• V běţném případě – Odpověď na první verzi dotazu není ani přesná, ani úplná
Počáteční odpověď
0
0
1 19
Přesnost a úplnost • Ladění dotazu – Postupná modifikace dotazu s cílem zvýšit kvalitu odpovědi
R 1
Optimum
• Teoreticky je sice moţné dosáhnout optima, ale … 0
0
1
P 20
Přesnost a úplnost • … vlivem víceznačností jsou v praxi oba koeficienty na sobě nepřímo závislé, tj. P*R konst. < 1 – Při snaze zvýšit P se na výstup dostane méně relev. dokumentů. – Při snaze zvýšit R se na výstup dostane s více relev. dok. i mnohem více těch nerelevantních.
R 1
0
Optimum
0
1
P 21
Kritérium predikce • Při formulaci dotazů je potřebné uhádnout, které termy (slova) byly v dokumentu autorem pouţity pro vyjádření dané myšlenky – Problémy m.j. způsobují • Synonyma (autor mohl pouţít synonymum, které si tazatel při formulaci dotazů ani nemusí neuvědomí) • Překrývající se významy slov • Opisy jedné situace jinými slovy 22
Kritérium predikce • Částečným řešením je zařazení tezauru, který obsahuje – Hierarchie slov a jejich významů – Synonyma slov – Asociace mezi slovy
• Tazatel můţe tezaurus vyuţít při formulaci svých dotazů 23
Kritérium predikce • Při ladění dotazů má uţivatel tendenci postupovat konzervativně – V dotazu zůstávají často ty jeho části, které uţivatele napadly na začátku a mění se jen podruţné části, které nekvalitní výsledek nemusí nijak zásadně ovlivnit
• Vhodné je uţivateli pomoci s odstraněním nevhodných částí dotazu, které nepopisují relevantní dokumenty a naopak s přidáváním formulací, které relevantní dokumenty popisují 24
Kritérium maxima • Tazatel obvykle není schopen (nebo ochoten) procházet příliš mnoho dokumentů do té míry, aby se rozhodl, zda jsou pro něj relevantní nebo ne • Obvykle 20-50 podle velikosti Potřeba nejen dokumenty rozlišovat na odpovídající/neodpovídající dotazu, ale řadit je na výstupu podle míry předpokládané relevance 25
Kritérium maxima • V důsledku kritéria maxima se při ladění dotazu uţivatel obvykle snaţí zvýšit přesnost – Malé mnoţství dokumentů v odpovědi, obsahující co největší poměr relevantních dokumentů
„lepší“ Vr.
Rel.
„horší“ Vr.
Rel.
• Některé oblasti pouţití vyţadují co nejvyšší přesnost i úplnost – Právnictví 26
Internetové vyhledávače Sluţba, která umoţňuje najít webové stránky, které obsahují poţadované informace (zadané ve vyhledávacím poli) Cílem vyhledávačů je poskytnout co nejrelevantnější informace. Světové: Google Bing AltaVista Yahoo …
České: Seznam Centrum Atlas Jyxo … 27
Jak vyhledávače fungují? Zjednodušeně ve třech krocích: 1. Sběr dat pomocí crawlerů (robotů) 2. Zpracování do databáze (indexování) 3. Zpřístupnění uţivatelům pomocí vyhledávacího okna
Jak vyhledávače fungují?
Zdroj: http://computer.howstuffworks.com/in ternet/basics/search-engine1.htm
Nejsou však všemocné… • Neviditelný web – – – – – – –
Intranety Zaheslovaný obsah Obsah přístupný přes formuláře Flash prezentace Robots.txt Databáze …
Jak poznat kvalitní informační zdroj? • Odborná erudice autora (vyhledání informací o autorovi) • Scientometrie – metoda stanovení kvality vědecké práce – čím více si vědecká (odborná) komunita všímá určité publikace, tím větší má hodnotu • Spolehlivost informačního zdroje – míra citovanosti, zjišťovaná impact faktorem (kolikrát byl časopis citován během dvou let od jeho publikování)
Jak poznat kvalitní informační zdroj? • Stáří informace – uţitná hodnota informace klesá v závislosti na čase (existují však informace, jejichţ uţitná hodnota v čase neklesá). • Informační cyklus se díky moţnosti publikovat online dramaticky zrychlil.
Problémy při vyhledávání nevýznamová a nespecifická slov • Vyuţití negativního slovníku, seznam stopslov • Vytvoření negativního slovníku: – Volba druhů slov, které nenesou význam a slouţí pouze pro syntaktické účely – Volba slov s vysokou frekvencí v textu dokumentu – Volba velmi krátkých slov
Četnost anglických slov • Tipnete si 5 nejčastějších? 5. a 4. and 3. to 2. of 1. the • Co je v seznamu dříve, sloveso nebo podstatné jméno? – Sloveso (be, 21. místo) • Jaké je první podstatné jméno? Kolikáté je v pořadí? – Word (45. místo) Zdroj: http://www.world-english.org/english500.htm
Google • Internetový vyhledávač stejnojmenné firmy • 25 miliard webových stránek, 400 miliónů dotazů za den, 1,3 miliardy obrázků (rok 2006) • 47,7 % podíl na světovém trhu (rok 2006) • 44 % podíl na trhu ČR (rok 2010) • www.google.com • www.google.cz 35
Google – Základní vyhledávání
• Napíšeme klíčové slovo nebo slova, která má hledaná stránka obsahovat • Zkusím štěstí – vrátí jednu (nejrelevantnější stránku) • Vyhledávání google – vrátí seznam nejvíce relevantních stránek řazených dle relevance 36
Google - výsledky
37
Google výsledky • Stránky řazeny dle relevance (nejvíce relevantní nahoře). • Zobrazí prvních 10 výsledků. • Na další výsledky se lze přepnout pod obrázkem dole.
38
Google výsledky • V levém panelu rozklikneme Více nástrojů • Prohledat web / stránky pouze česky • Časové omezení, kdy byla stránka naposledy aktualizována • Jen stránky s obrázky • Náhledy stránek 39
Google - obrázky • V levém panelu přepneme na Obrázky • Velikost obrázků • Typ obrázků (obličej, fotka) • Barva
40
Google – videa • • • • • • •
V levém panelu přepneme na Videa Prohledat web / stránky pouze česky Délka trvání videa Poslední aktualizace Kvalita Titulky Zdroj 41
Google – specializace • V levém panelu rozklikneme poloţku Více • Vše, Obrázky, Videa • Mapy • Zprávy, Nakupování, Knihy, Blogy, Aktualizace, Diskuze
42
Google - mapy
43
Google – rozšířené vyhledávání
44
Google – rozšířené vyhledávání
• Přesná fráze – slova v textu za sebou, přesný gramatický tvar 45
Google – rozšířené vyhledávání
• jazyk dokumentu, stát • formát (pdf, ppt, doc, xml, …) • konkrétní doména (com, vsfs.cz,) 46
Google kalkulačka • Matematické operace + - * / • Matematické funkce sin, cos, log, exp, … • Převody jednotek – 5 mil v kilometrech – 10 galonu v litrech
47
Google - Úkoly • Jak se jmenoval čínský kosmonaut, který letěl do vesmíru v roce 2003? • Který z amerických prezidentů neměl za rodný jazyk angličtinu? • Jak se jmenuje algoritmus pouţívaný v kompresním programu RAR ?
48
Google - Úkoly • • •
Najděte původní slajdy, ze kterých jsou převzaty slajdy 3 – 26 v naší prezentaci. Najděte fotografii autora původních slajdů z předchozího úkolu. Na kterých vysokých školách v Praze se vyučují databázové systémy ? Naplánujte mezi těmito školami vhodnou cestu, určete její délku. 49
Google - Úkoly • • • •
Jaké je oblíbené zvíře rektorky VŠFS? Spočítejte: sin (pi/6) + log (100) Kolik váţí celkem 151 unci a 12 liber? Co vše můţe znamenat slovo METRO? Ke kaţdému významu najděte obrázek (či video).
50