FVO'öO Textové Informační systémy Petr Sojka Fakulta informatiky Masarykova univerzita v Brně Jaro 2004 V 3 Část I Informace o předmětu FVOdO V a Úvodem • Petr Sojka, sojka@informatics.muni.cz o Konzultační hodiny jaro 2004: úterý-12:30—13:50 a čtvrtek-12:30—13:50, po domluvě emailem i jindy. • Místnost b304, 3. patro bloku b, botanická 6&a. • URL s materiály k předmětu: http://www.fi.muni.cz/~sojka/PV030/ a Rozdělení do cvičení (b204^ A-107 vs. b3-1-1). □ ► < g Určení a klasifikace předmětu Frerekvizity předmětu: U posluchače se předpokládají základní znalosti teorie formálních jazyků a automatů (IB005), zcela elementární základy teorie složitosti, znalosti programovania softwarových systémů. Klasifikace: Bodový systém sestává z ohodnocení práce v semestru (vnitrosemestrové písemky, které budou klasifikovány dohromady 30 body). Na závěr kurzu bude písemný test, na kterýje možno získat 70 bodů. Kromě toho je možno v průběhu semestru získat tzv. prémiové body. Klasifikační skála (změna vyhrazena) z/k/E/D/C/B/A odpovídá zisku 4Ô/54/60/66/72/7Ô/Ô4 bodů. Termíny závěrečného písemného testu budou 24.5. v -15 hodin (D-1) a 7.6.2004 ve -12 hodin (D-1); opravný termín pak patrně 2Ô.6.2004. □ g - = jš Předmět výuky My books focus on timeless truth. D.E. Knuth, Brno,-1996 Předmětem výuky tohoto předmětu je výklad základních principů, algoritmů a technik návrhu, vytváření a implementace textových informačních systémů (TIS)- ukládání (storage) a akvizice/vyhledávání (retrieval) informací. Sylabus © Základní pojmy informačních systémů. Klasifikace informačních systémů. Vyhledávací systémy. © Vyhledávací algoritmy a datové struktury. Sousm. vyhl. metody s předzpracováním vzorků (MF, KMF, AC, FV). ® Frotism. vyhl. metody s předzpracováním vzorků (algoritmy BM, BMH,CW, BUC). © Vyhledávací metody s předzpracováním textu - indexové metody. © Metody indexování, konstrukce tezauru. Jak to délal Google. © Vyhledávací metody s předzpracováním textu a vzorků -signaturove metody. © Jazyky pro vyhledávání. ® Komprese dat, základní principy (entropie). Sylabus (pokr.j ® Statistické metody komprese dat. ® Slovníkové metody komprese dat. O Efektivní datové struktury pro uchovánítextů a slovníkových dat s využitím korpusové lingvistiky. © Syntaktické metody. Kontextové modelování. Kontrola správnosti textu. Komprese textů s použitím neuronových sítí. Shlukování dokumentů a navigace v nich. Knihy, skripta ^ [MEL] Melichar, B.: Textové informační systémy, skripta ČVUT Vraha, 2. vydání, A996. ^s [POK] Pokorný, J., Snášel, V., Húsek D.: Dokumentografícké informační systémy, Karolinum Vraha, A99&. ^ [KOP] Korfhage, P. P.: Information Storage and Retrieval, Wiley Computer Publishing, -1997. ^ [SMY] Smyth, B.: Computing Patterns in Strings, Addison Wesley, 2003. ^ [KNU] Knuth, D. E.: The Art of Computer Programming, Vol. 3, Sorting and Searching, Second edition, A99&. ^ [WMB] Witten I. H., Moffat A., Bell T. C: Managing Gigabytes: compressing and indexing documents and images, Second edition, Morgan -^r Kaufmann Publishers, -199Ô. □ a> - = ■= Doplnkové zdroje informaci ^ [HEL] Held, G.: Data and Image Compression, Tools and Techniques, John Wiley & Sons, 4. vydání-1996. H [MEH] Melichar B., Holub J., A 6D Classification of Pattern Matching Problems, Proceedings of The Prague Stringology Club Workshop '97, Prague, July 7, CZ. | [GOO] Brin S., Page, L.: The anatomy of a Large-Scale Hypertextual Web Search Engine. WWW7/Computer Networks 30(1-7): A07-AA7 (A99&). http://dbpubs.Stanford.edu:8090/pub/1998-8 U [MeM] Mehryar Mohri: On Some Applications of Finite-State Automata Theory to Natural Language Processing, Natural Language Engineering, 2{A):6A-&0,A996. http://www.research.att.com/~mohri/cll.ps.gz Doplnkové zdroje informaci (pokr.) U [Sch] Schmidhuber J.: Sequential neural text compression, IEEE Transactions on Neural Networks 7(1), -142—146, -1996, http://www.idsia.ch/~juergen/onlinepub.html U [S BA] Salton G., Buckley Ch., Allan J.: Automatic structuring of text files, Electronic Publishing 5(1), p. -1—17 (March -1992). http://columbus.cs.nott.ac.uk/compsci/epo/epodd/ep056gs.htm ~D [WWW] stránky predmetu ~sojka/PV030/, semináře DIS http: //www. inf .upol. cz/dis,http: //nlp.f i .muni . cz/, The Prague Stringologic Club Workshop -1996-2004 http://es.felk.evut.cz/pse/ ^ Jones, S. K., Willett: Readings in Information Retrieval, Morgan Kaufman Publishers,-1997. ^ Doplnkové zdroje informací (pokr.) ^ Bell, T. C, Cleary, J. G., Witten, I. H.: Text Compression, Prentice Hall, EngIewood Cliffs, N.J.,-199-1. ^ Storer, J.: Data Compression: Methods and Theory, Computer Science Press, Rockwille, A9&&. | časopisy ACM Transactions on Information Systems, Theoretical Computer Science, Neural Network World, ACM Transactions on Computer Systems, Knowledge Acquisition, knihovna.muni. cz, umarecka. cz (skripta Pokorný) V Část Základní pojmy TIS V □ g - = TIS - motivace realita <—> data T T potřeba informace <—» dotaz es- Abstrakce a mapování v informačním systému. es- Informační potřeba o realitě - dotazy nad daty. a i^ms Základni pojmy Definice: Informační systém je systém, umožňující účelné uspořádání sběru, uchování, zpracování a poskytování informací. Definice: Ektoeyetém se skládá z uživatelů 15, investora IS a toho, kdo systém provozuje (user, funder, server). Na příkladě 15 MU jsou to uživatelé 15, MU reprezentovaná kvestorem a CVTa ÚVT MU. Ektosystém není pod kontrolou designéra 15. Definice: Endoeyetem sestává z použitého hardware (media, devices), a software (algorithms, data structures) a je plně pod kontrolou designéra 15. Požadavky na TIS Různost hledisek na TIS es* efektivita (user) es* ekonomika (funder) es* efektivnost (server) a z toho vyplývající kompromisy. Naše hledisko bude hledisko architekta TIS respektujícího požadavky ektosystemu IS. Pro problematiku ektosystemu IS viz FV045 Management IS. Od dať k moudrosti • Údaj - konkrétní vyjadrení zprávy ve formě posloupnosti symbolů nějaké abecedy. • Informace - odraz poznaného nebo předpokládaného obsahu skutečností. Informace závisí na subjektu, jemuž je určena. Hlediska: o kvantitativní (teorie informace); • kvalitativní (význam, sémantika); • pragmatické (hodnotové - význam, užitečnost, upotřebitelnost, periodicita, aktuálnost, hodnověrnost); ostatní (pohotovost, podrobnost, úplnost, jednoznačnost, dostupnost, náklady na získání). • Znalost (knowledge). • Moudrost (wisdom). Informační proces Definice: Informační procee - procee vzniku informací, jejich zobrazení ve formě údajů, zpracování, poskytovania využití. Tomuto procesu odpovídají operace nad informacemi. Data/signály —> Informace —> Znalost —> Moudrost. a i^ms V Klasifikace IS podle převládající funkce ® dokumentografické vyhledávací systémy (Information Retrieval Systems). © databázové systémy (DMBS), relační DB (FBI54, FBI55, FV003, FV055, FV136, FB114). ® faktografické systémy pro řízení (Management Information Systems FV045). ® systémy pro podporu rozhodování (Decision Support Systems FV09Ô). © expertní (Expert Systems), dotazovací (Question Answering Systems) a znalostní (Knowledge-Based) systémy, (PA031). Klasifikace IS podle převládající funkce (pokr.) © specifické informační systémy (geografické FVO-19, FA049, FA050, medicínské FV04Ô, enviromentální FV044, podnikové FV043, ve státní správé FV05Ô, FV059, knihovnické FV070); dále též FV063 Aplikace databázových systémů. Související oblasti vyučované na Fl: Technologie informačních systémů: FA-102, FA-105. Specifické aspekty indexování: Indexování multimediálních dat: FA-12Ô. Implementace databázových systémů: FA-152. Různost pohledů na TIS \ / Vyhledávací systém DBMS Expertn í systém Databázový systém Systém pro řízení / \ □ 3 T^sm Minianketa © Co očekáváte od tohoto předmětu? Co byste se zde chtěli dozvědět? Vyhovuje sylabus? © Co neočekáváte (čemu byste se raději vyhnuli)? ® Jaké příbuzné předměty jste absolvoval/hodláte absolvovat? © Použití IS (z hlediska uživatele) a) Jaké (T)IS používáte? b) Rozsah? Kolik hledání v (T)IS provádíte za měsíc? c) Jakjste spokojeni? © Vytváření IS (server) a) Jaký (T)IS nebo jeho komponentu jste realizoval? Oblast, rozsah? b) Jakjste s tímto (T)IS spokojeni, slabá místa? □ g - = Vyhledávací systémy (VS) - princip DB I Množina Dotaz — * Dotazovací — —> vybraných stroj dokumentů Prázdny vyhledávací systém DB I Definice dokumentu —> Definice formátu výst. dok. —> VYHLEDÁVACÍ Definice způsobu vyhl. dokům. —> SYSTEM Obsah dokumentu —> T Dotazy vybraných dokumentu Vyhledávací systémy - klasifikace © Klasifikace dle směru průchodu textem: sousměrné/protisměrné © Klasifikace dle (před )z pracován í textu a vzoru: a aá fontes (hledání v samotném textu) • text surrogate (hledání v náhražce textu) • náhražky: index: uspořádaný seznam významných prvků s odkazy áo původního textu; signatura: řetězec příznaků indikující přítomnost významných prvků v textu V Vyhledávací systémy - klasifikace (pokr.) předzpracování textu ne ano předzpracování vzorků ne 1 III ano II IV I - elementární algoritmy II - vytvoření vyhledávacího stroje III - indexové metody IV - signaturove metody Vyhledávání-formulace problému Klasifikace dle kardinality množiny vzorů: © Vyhledej jeden vzorek V v textu T. Výsledek.: ano/ne. ® Vyhledej konečnou množinu vzorků F = {v-\,V2.....i//;}. Výsledek: informace o tom, kde se v textu vyskytuje některý ze zadaných vzorků. ® Vyhledej nekonečnou množinu vzorků zadanou regulárním výrazem R. R definuje potenciálně nekonečnou množinu L{R). Výsledek.: Informace, kde se v textu vyskytuje některý ze vzorků zL{R). Alternativy formulace problému vyhledávání: a) první výskyt. b) všechny výskyty bez překrývání. c) všechny výskyty včetně překrývajících se. Vyhledávání-formalizace problému Řetízek korálků. Korálky —> element. Číslování elementů přirozenými čísly. Ne nutně čísla, ale návěští. 0) Každý element má návěští, které je jedinečné. •1) Každý element s návěštím x (s výjimkou nejlevějšího) má jednoznačného předchůdce označovaného pred(x). 2) Každý element s návěštím x (s výjimkou nejpravějšího) má jednoznačného následníka označovaného succ(x). 3) Pokud element x není nejlevější, x = succ(pred(x)). 4) Pokud element x není nejpravější, x = pred(succ(x)). 5) Pro každé různé elementy xa y existuje kladné k tak., že buď x = 5ucck(y) nebo x = predk(y). Vyhledávání-formalizace problému (pokr.) Pojem zřetězení: Definice: Řetězec je množina elementů splňujících pravidla 0)-5). Definice: Lineární řetězec: Řetězec, který má konečně mnoho prvků včetně nejlevějšího a nejpravějšího. Definice: Náhrdelník. Definice: Abeceda A. Píemena abecedy. A+. Prázdný řetěz e. A* = A+U{s}. Definice: Lineární řetězec nad A: prvek A+. Definice: Vzoreíc. Text. V Část Přesné vyhledávaní V □ g - = Naivní vyhledávání, vyhledávání hrubou silou, elementární vyhledávací algoritmus proč Brute-Force-Matcher(VZOREK,TEXT) : T:=length[TEXT]; V:=length[VZOREK]; for i:=0 to T-V do if VZOREK[1..V]=TEXT[i+1..i+V] then print "Vzorek nalezen na pozici i"; a Analýza časové složitosti naivního vyhledávaní o složitost měřena počtem porovnání, délka vzorku V, délka textu T. 9 horní odhad S = V ■ (T - V + A), tedy 0(1/ x T). • nejhorší příklad VZOREK = aY~Ab, TEXT = aT~Ab 9 přirozené jazyky: {průměrná) složitost (počet porovnání) výrazně menší, neboi nedochází ke shodě počátků slov příliš často. Pro angličtinu S = Ce • {T — V + A), Ce empiricky naměřeno -1.07, t.j. prakticky lineární. • Ccz? CczV6.Ce? o urychlení? aplikace pro více vzorků? nekonečný počet? • verze algoritmu (5, Q, G/) na cvičení. Vyhledavači šoustněme metody Při předzpracováníje prozkoumána struktura vzorku a na jejím základe vytvořen vyhledávací algoritmus (stroj). Definice: Přesná (vs. proximitní) vyhledávání cílí k přesnému nalezení vzorku. Definice: Soueměrné (vs. protisměrné) vyhledávání porovnává vzorek zleva doprava (vs. zprava doleva). Šoustněme metody © A vzorek: o Shift-Or algoritmus. • Knuth-Morris-Frattův algoritmus, (KMF, nalezen (MF) •1970, publikován -1977). • Karp-Fabinůvalgoritmus, (KF, -19Ô7). © n vzorků: Aho-Corasickové algoritmus, (AC, -1975). ® oo vzorků: konstrukce vyhledávacího stroje (KA) pro vyhledávání nekonečné množiny vzorků (regulární výrazy). □ g - = Shift-Or algoritmus es* Vzorek 1/^1/2 .. .vm nad abecedou I = a-\.....ac. O pokud v, = äj es* Incidenční matice X (m x c), X,-,- , • ' J ^ A jinak. es- Sloupec matice X odpovídající znaku a j označme Aj. es- Na začátku do R jednotkový sloupec. V každém kroku algoritmu se řetězec R posune o jednu pozici dolů (horní pozice se naplní nulou) a přečte se ze vstupu jeden znak aj. Výsledek posunu se zkombinuje s řetězcem Aj pomocí binární disjunkce: R:= SHIFT(R) OR Aj. es- Algoritmus skončí úspěšně pokud se na dolní pozici R dostane O. Shift-Or algoritmus (pokr. Příklad: V — vzorek nad I = {e,k, o, r, v,z}. Srv. [FOK, strana 3-1-32]. B^sm V 3 Naivní vyhledávání — algoritmy Vyjádřete časovou složitost následujících vyhledávacích algoritmů pomocí proměnných c a s, kde cje počet testů a platí: • je-li nalezen index /, pak c = i a 5 = A • není-li nalezen, pak c = T a s = O V 3 I^HB Naivní vyhledávání- aIgoritmus 5 vstup: var TEXT: arrays ..T] of slovo; VZOREK: slovo; výstup (v proměnné FOUND): Ano/Ne A \:=A; c while l< T do begin c if TEXT[l]=VZOt?EK then break; c-s inc(l); end; 2 FOUND:=(l index do textu j:=1; > index do vzorku while {i 0) and (textp] 7^ vzorek[J]) do j ■■= n[jj, end while i:=i + A; j:=j + A end while nalezen := j > 1/; > pokud nalezen, je na pozici i — V — A Analýza (K) M P es* Složitost 0(7") plus složitost předzpracování (vytvoření pole h). es* Animace trasování hlavní části KMF. V a T^sm Knuth-Morris-Prattuv algoritmus es* h se uplatní, když předpona vzorku v-\V2 ■ ■ ■ Vj-a je srovnána s podřetězcem textu ť,-_j+-i t/-j+2 • • • t/--i a i/j 7^ t,- es* mohu skočit o víc než -1? o j? ja k h spočtu? es* h(j) největší /c < j takové, že 1^ 1/2 ... i/n je příponou va 1/2 ... 1//--1, tj. V A V2 ■ ■ ■ Vk-A = Vj-k+A Vj-k+2 ■ ■ ■ Vj-A a V j f Vk es* KMF: zpětné přechody tak dlouho, až j = O {předpona vzorku není v prohledávaném textu obsažena) nebo t,- = Vj {VA V2 ■ ■ ■ V j = tj-j+A tj-j+2 ■ ■ ■ t i-A tí) es* animace lecroq, dále [FOK, strana 27], též viz podklady [MAR] pro detailní popis. Konstrukce h pro KM P i:=l; j:=0; h[l]:=0; while (i0) and (v[i]Ov[j]) do j :=h[j] ; i:=i+l; j:=j+l; if (i<=V) and (v[i]=v[j]) then h[i] :=h[j] else h[i] :=j (*MP*) end; Složitost konstrukce, t.j. předzpracování, je 0(1/), celkem tedy 0{T + V). Fntíad: h pro ababa. KMF vs. MP. □ g - Univerzální vyhledávací algoritmus, který používá tabulku přechodů q odvozenou z hledaného vzorku (g odpovídá přechodové funkci 5 KA): var i,T:integer; nalezen: boolean; text: array[l..T] of char; state,qO: TSTATE; g:array[l..maxstate,1..maxsymb] of TSTATE; F: set of TSTATE;... begin nalezen:= FALSE; state:= qO; i:=0; while (i <= T) and not nalezen do begin i:=i+l; state:= g[state,text [i]]; nalezen:= state in F; end; end; Jak předzpracovat vzorek do g? □ a> Vyhledávací stroj Vyhledávací stroj (VS) pro sousměrné vyhledávání es* VS pro sousměrné vyhledávám A = (Q, T, g, h, qo, F) o Q konečná množina stavů. • T konečná vstupní abeceda. o g:QxT—>QU {fail} dopředná přechodová fee. o h: (Q - íjo) —> 0 zpětná přechodová fee. • íjo počáteční stav. • F množina koncových stavů. es* hloubka stavu cj: d(cj) £ No je délka nejkratší dopředně posloupnosti přechodů z cjo do q. □ g - Vyhledávací stroj (pokr.) es* Vlastnosti q, h: • g{qp, a) ^ fajl pro Va e T [neprovádí se žádný zpětný přechod v počátečním stavu). o je-li h[q) = p, pak. d[p) < d[q) [počet zpětných přechodů bude shora omezen součinem maximální hloubky stavu c a celkového počtu dopředních přechodů V). Rychlost vyhledávání tedy bude lineární vzhledem k V. Konfigurace, přechod VS es* konfigurace VS (q, w), q e Q, w e T* doeud neprohledaná část textu. es* počáteční konfigurace VS {qo,w), w\e celý prohledávaný text. es* akceptující konfigurace VS {q,w), q e F, tv je dosud neprohledávanýtext, nalezený vzorek je bezprostredne před iv. es" přechod VS: ve\ace hC (Q x T*) x (Q x T*): • g{q,a) = p, pak. {q,aw) h {p,w) dopředný přechod pro Viv e T. • /i(cj) = p, pak (q, w) h (p, w) zpětný přechod pro \fw £ T*. Vyhledávání pomocí VS Při dopředném přechodu je přečten jeden vstupní symbol a stroj přechází do následujícího stavu p. Je-li vsak g{q,a) = fai], provede se zpětný přechod bez čtení vstupního symbolu. Časová složitost S = 0(7") (měříme počet přechodů VS). Konstrukce VS pro KMP pro vzorek v^vz ■ ■ ■ vy © počáteční stav qo- ® g(q, Vj+-\) = q', kde q' odpovídá předponě v-\V2--- V}V}+-\ ■ ® pro qo definujme g{qo,a) = qo proVa, pro která g{qo,a) nebylo definováno v předchozím kroku. © g{q,a) = fajj pro Vcj a a, pro která g{q,a) nebylo definováno v předchozích krocích. © stav odpovídající úplnému vzorkuje koncový. © zpětnou přechodovou fci h definuje na straně 47 uvedený algoritmus. □ g - ■== Karp-Rab'movo vyhledávání Zcela jiný přístup: použití hashovací funkce. Místo přikládání vzoru k textu na všech pozicích kontrolujme shodu jen tam, kde podřetězec textu vypadá „podobně". Podobnost určuje hashovací funkce. Ta by měla být es* efektivně vyčíslitelná, es* a měla by dobře separovat různé řetězce. Vyhledávání KRje v nejhorším případě kvadratické, ale průměrně 0{T + V). □ g - = Karp-Rab'movo vyhledávání (pokr.) #define REHASH(a, b, h) ( ( (h-a*d)«l+b) void KR(char *y, char *x, int n, int m) { int hy, hx, d, i; /* předzpracováni: vypočet d = 2I"~A */ d=l; for (i=l; i v je nejdelší vlastní přípona u. Chybová fee h (AC /(to) /(/(to)) /(iv) I-* (cj.wO pro nějaké ej e F, w' E T*} jazyk přijímaný KA M. es* časová složitost 0(7") (méříme počet přechodů KA M). Nedeterministický KA Definice: Nedeterminietický konečný automat (NKA) je M = (K,T,ó,qo,F), kde K, T, qo, Fjsou stejnejako u deterministické verze KA, ale ô : K x T -» 2K ô (q, a) je nyní množina stavů. Definice: he (K x T*) x (K x T*) přechod: jestliže p e stav {qo} neoznačený. © Jestliže v K' jsou všechny stavy označeny, pokračuj krokem 4. ® Vybereme z K/ neoznačený stav q'\ o o'(o(,á) = []{ô{p,a)} proVp E q' a a ET; • K'= K'uč'(q',a) pro ^a ET; • označíme q' a pokračujeme krokem 2. © qó = M; F' = {q' EK': q'nFŕ 0}. V □ g - = jj Konstrukce q pro VS Konstrukce q' pro VS pro množinu vzorku p = {i/1 ,v2.....vp} © Vytvoríme N KAM: • Počáteční stav cjo- o Pro Va e T definujme g{qo,a) = qp- o Pro V/ £ {A.....F} definujme g(q, bj+-\) = c(, kde c( odpovídá předponě b-\bz ■ ■ ■ bj-n vzorku v'. o Stav odpovídající úplnému vzorkuje koncový. © a jemu odpovídající DKA M/ s q'. V Osnova (Týden třetí) © Opakování: animace KMF, AC. © Algoritmy pro sousměrne vyhledávání nekonečné množiny vzorků. ® Regulární výrazy. © Fřímá konstrukce (N)KA pro daný FV. Cast VI Vyhledávání nekonečné množiny vzorků V □ g - = f^ms Regulární výraz (RV) Definice: Regulární výraz V nad abecedou A: © 6,0 jsou RV a pro Va e A je a RV. © Jestliže x, y RV nad A, pak: • (x + y) Je ^ (sjednocení); • (x.y) je RV (zřetězení); o (x)*je RV (iterace). Konvence o prioritě regulárních operací: sjednocení < zřetězení < iterace. Definice: Pak za (zobecněný) regulární výraz považujeme i takové termy, které neobsahují vzhledem k této konvenci nepotřebné závorky. Hodnota KV Hodnota h (x) RV x: © h{0) = 0, h{e) = {e}, h{a) = {a} © • h(x + y) = /i(x) U h(y) • tí(x.y) = tí(x)./i(y) o h(x*) = (h(x))* cs- h(x*) = e U x U x.x U x.x.x U ... es* Hodnotou RVje regulárni jazyk (RJ). cs" Každý RJ lze reprezentovat RV. es" Fro V RV V 3 KA M: h(/) = L{M). Axiomatizace RV (Salomaa i966) A-1: x+(y + z) = (x + y)+z = x + y + z asociativnost sjednocení A2: x.(y.z) = {x.y).z = x.y.z asociativnost zřetězení A3: x + y = y + x komutativnost sjednocení A4: (x + y).z = x.z + y.z distributivnost zprava A5: x.(y + z) = x.y + x.z distributivnost zleva A6: x + x = x idempotence sjednocení A7: s.x = x jednotkový prvek pro zřetězení AÔ: O.x = O nulový prvek pro zřetězení A9: x + O = x jednotkový prvek pro sjednocení MO: x* =6 + x*x A-1-1: x* = (s + x)* □ g - = Podobnost regulárních výrazů Věta: Tato axiomatizace RVje úplná a bezesporná. Definice: Regulární výrazy nazveme podobné, jeetWže se mezi sebou dají navzávem převést pomocí axiomů M azhAA. Veta: Podobné regulární výrazy mají stejnou hodnotu. Délka regulárního výrazu Definice: Délka d(V) regulárního výrazu V: © Je-li 1/tvořen jedním symbolem, pakd(V) = A. © d{VA + V2) = d{VA) + d{V2) + A. © d{VA.V2) = d{VA) + d{V2) + A. ® d{V*) = d{V) + A. © d{{V)) = d{V) + 2. Konstrukce NKA pro daný RV Definice: Zobecněný NKA dovoluje e-přechody (přechody bez čtení vstupního symbolu). Věta: Pro každý RV V je možno sestrojit KA M takový, že h(V) = L(M). Důkaz: Strukturní indukcí vzhledem k RV V: V □ g T^sm Konstrukce NKA pro daný RV (důkaz) © V = a Ho V = v; M a automat pro VA {h{VA) = L{MA)) s V □ g - = f^ms Konstrukce NKA pro daný RV (důkaz pokr. V = VA ■ V 2 V = VA + V2 M,|, M2 automaty pro V^, V2 {h{V^) = L{M^), h(V2) = L(M2)) V □ g - = B^sm Konstrukce NKA pro daný RV (pokr.) Vlastnosti takto vytvoreného NKA: es* Z každého stavu vycházejí maximálně 2 hrany. es* Z koncových stavů nevycházejí žádné hrany. es- Počet stavů M < 2 • d(K). es* Simulace chování automatu M v čase 0{d{V)T) a paméti 0(d(V)). Simulace NKA Eliminace e-přechodů Pro následující metody simulace NKA je třeba odstranit e-přechody. Toto můžeme provést známým postupem: 1) 2) S1 = f^ms Simulace NKA (pokr. Metody implementace simulace NKA Stav reprezentujeme booleovským vektorem a současně budeme procházet všemi možnými cestami. Dvě možnosti: es* Obecný program s použitím tabulky přechodů. es* Implementace automatu ve formě (generovaného) programu pro konkrétní automat. V 3 ^HB5 Přímá konstrukce (N)KA pro daný RV Nechť 1/je RV nad abecedou T. Vak KA M = (K,T,6,q0,F) takový, že /i(l/) = L(M) sestrojíme takto: © Očíslujeme všechny výskyty symbolů z ľ ve výrazu V různými přirozenými čísly. Dostaneme V. © Množina počátečních symbolů Z = {x, : symbolem x, může začínat nějaký řetězec z h(K')> x/ ^ s}-® Množina sousedů P = {x,yj : symboly x, ^ s ^ yj mohou být vedle sebe v nějakém řetězci z h(K')}. © Množina koncových symbolů F = {x, : symbolem x, ^ s může končit nějaké slovo zh(V')j. © Množina stavů K = {tjo} U ZU {yj : x,yj G P}. © Přechodová funkce ô: • (?(tjo. x) obsahuje x, proVx, G Z vzniklá očíslováním x. • H3 v □ g T^sm Protisměrné vyhl. nek. mn. vzorků (pokr. Buczifowski: V vyhledáváme tak., že vytvoříme VR a pro každý stav a nedefinovaný přechod z něho se určí 5híft[5TAV', SYMBOL] analogicky jako u algoritmu CW: a b c X 0 1 3- A 1 A 2(3!) 2 A 3 A A 1 4 A A A 1 5 A A 1 ^HB5 v a Cvičení Příklad : Mějme množinu vzorků F= {tis, ti, iti}: es* Vytvořte NKA pro vyhledávání F. es* Vytvořte DKA příslušný tomuto NKA a zminimalizujte jej. Nakreslete přechodové diagramy obou automatů (DKA a minimálního DKA) a popište postup minimalizace. es* Srovnejte s výsledkem vyhledávacího stroje AC. es" Řešte úlohu také algoritmem přímé konstrukce DKA (derivováním) a diskutujte, zda výsledkem jsou izomorfní automaty. V a T^sm Dvouceetný automat ee skokem Definice: 2DKA6 je M = (Q, I, ô, q0, k, T> F), kde Q množina stavu I vstupní abeceda (5 zobr. öxl^öx {-1,1.....k} íjo £ Q počáteční stav k e N max. délka skoku T£ Q UI značka skoku F C Q množina koncových stavů Definice: Konfigurace 2DKA6je řetězec z I*(21* T £*• Definice: Množinu konfigurací2DKAS M značíme K(M). Příklad: a-i 32 ... a,'-i íj čtecí hlava i aj-1 T ?j... a„ e K(M): značka skoku V 3 I^HB Dvoucestný automat se skokem II Definice: Přechod 2DKAS je relace h C K(M) x K(M) taková, že _1 a,' q a,'-H ...aj-i ] aj.. ,a„ \- a^ ...a,_^ q7 a/a/+i ...aj-i t pro / > A, (5(q, a,+^) = (q'', —A) (protisměrné srovnání), < q ai+A :/-i T. h, ií-M ... at-A q' ] at. an pro ô(q,aj+>\) = (q',m), m>A, t = min{ j + m, n + A } (protisměrný skok), "S" a^ ... aj q a^ ... a,_^ t a,... a„ h a^ ... afi^ ... at_^ q7 t at... an pro 8{q,ai) = {q\m), m>A, t = min{ŕ + m,n + A } (sousměrný skok),. "S" a-i ... aj-i q aj... a,_^ t a/a/+-i ... a„ Y- a-\ ... aj-i q7 aj... a,_^ a, t a,--H ... a„ pro / > A, ô(q, a,) = (q/, A) (sousměrně srovnání). (Sousměrná pravidla jsou pro sousměrně stroje, protisměrná pro protisměrné). Definice: \-k, h* analogicky jak u VS. a f^ms Hierarchie vyhledávacích strojů Definice: Jazyk přijímaný dvouceetným automatem M = (Q, 1,5, qo, k, T, F) Je množina L{M) = {w e I* : q0 T T h* w'fxw |, kde f eFyeľ.xel}. Věta: L(M) pro 2DKA5 M je regulárni. Příklad: Zformulujte protisměrné vyhledávání vzorku BANANA v textu l-WANT-TO-FLAVOUR-NATURAL-BANANAS pomocí BM Jako 2DKAS a vyhledávání trasujte jako posloupnost konfigurací 2DKAS. V Cvičeni Mějme regulární výraz R = A (O + -1*02) nad abecedou A = {O, A,2}. es* Sestrojte DKA pro protisměrné vyhledávání R (Buczilowski) a spočtěte chybovou funkci. Nakreslete přechodový diagram tohoto automatu včetně vizualizace chybové funkce. es* Zapište výsledný automat jako 2DKAS a trasujte vyhledávání v textu A A 20A OA 2A 02. Shrnuti přesného vyhledávaní 2DKAS DKA I AC I KMF BUC co i C\N k I BM A <— směr — # vzorků. 3 V ^HB5 Cast IX Proximitní vyhledávání V □ g - = Metrika (pro proxi m itní vyhledávání) Jak měřit {metrika) podobnost řetězců? Definice: Funkci d : 5x5 —> R nazvete metrika jestliže platí O d(x,y)>0 O d(x,x) = 0 O d(x,y) = d(y, x) (symetrie) O d(x,y) = 0=> x = y {pravidlo nerozeznatelných bodů) © d{x,y) + d{y,z) > d{x,z) (trojúhelníková nerovnost) Hodnoty funkce d {distance) nazývame vzdálenost. □ g - Metriky pro proximitní vyhledávání Definice: Mějme řetězce X aY nad abecedou I. Minimální počet editačních operací pro přeměnu X na Y je es* Hammingova vzdaienoet, R-vzdá lenost, pokud povolíme jen operaci Replace, es* Levenehteinova vzdaienoet, D/R-vzdá lenost, pokud povolíme operace Peletě, Insert a Replace, er Zobecněná levenehteinova vzdaienoet, D/KT-vzdálenost, pokud povolíme operace Peletě, Insert, Replace a Transpose. Transpoziceje možná jen u sousedních znaků. Jde o metriky, Hammingova je nad řetězci stejné délky, Levenshteinovy i délek různých. □ g - = Proxi m itní vyhledávání- příklady Příklad: Najděte takový příklad řetězců X aY,že platí zároveň R(X,Y) = 5, DIR{X,Y) = 5 i DIRT{X,Y) = 5, nebo dokažte neexistenci takových řetězců. Příklad: Najděte takový příklad řetězců X aY.že platí zároveň R(X,Y) = 5, DIR{X,Y) = 4 i DIRT{X,Y) = 3, nebo dokažte neexistenci takových řetězců. Příklad: Najděte takový příklad řetězců X aY délky 2n, n e N, že K{X,Y) = naa) DIR{X,Y) = 2; b) DIRT{X,Y) = \§ 1 □ g - = Klasifikace vyhledávacích problému Definice: Nechť T = t^t2 ••-tn a vzorek P = p^p2---pm- Možno se například ptát: O je F podřetěz T? O je F podsekvence z T? Q je podřetěz či podsekvence PvT? O je F v T takový, že D(P, X) < k pro k < m, kde X = tř... tj je částí T {D je R, DIK c\ DIPT)? O je řetěz F obsahující don't care symbol 0 (*) v T? Q je sekvence vzorků F v T? Dále varianty pro více vzorků, plus instance problému pro hledání ano/ne, první výskyt, všechny výskyty nepřekrývající se, všechny výskyty i překrývající se. li»j:miMfli»j:mjgsWJ:W 6D klasifikace vyhledávacích problémů [MEH] ([MAR]) Infinite Finite R- mat chingDIRT- matching —I—C4y seQuence String \Exact DIR-matching Care Don't care 6D klasifikace vyhledávacích problémů (pokr.) Dimenze A 2 3 4 5 6 S F 0 E C 0 Q S F 1 D G D S Celkem 2x2x3x4x2x2 = i92 vyhledávacích problémů rozklasiflkovaných všestirozmšrném prostoru. Například SFO??? značí všechny VS pro hledání jednoho (celého) řetězce. Pro všechny tyto problémy se naučíme vytvářet vyhledávací NKA. Příklady vytvářeni VS Příklad: Hechí P = p^p2/?3 • • ■ Pm> m NKA pro SFOECO: 4, A je jakýkoliv znak ze I. _£i ^ V a li»j:milFfli»j:mjgsWJ:W Hledání sekvencí znaků Příklad: NKA pro QFOECO (seQuence): A p2 p3 p je jakýkoliv znak ze I kromě p. Automat má m + A stavů pro vzorek délky m. V □ g T^sm li»j:milFfli»j:mjgsWJ:W Hledání podřetězce: NKA pro SSOECO Definice: Tento automat se nazývá počáteční e-treeiie a má (m + 1) + m + (m - 1) + • • • + 2 = ^^ stavů. □ g f^ms li»j:miMfli»j:mjgsWJ:W Hledání podsekvence Příklad: NKA pro QSOECO je podobný, jen přidáme cykly pro nesrovnalé znaky a 6 přechody ke všem existujícím dopředným přechodům {nebo zřetězíme automat m-krát). Definice: Automat pro QSOECO se nazývá e-treelie. V a T^sm li»j:miMfli»j:mjgsWJ:W Proximitní vyhledávání SFOPCO Příklad: SFORCO pro Hammingovu (R) vzdálenost, /c < 3: Počet pater odpovídá vzdálenosti. □ g T^sm Proximitní vyhledávání SFORCO Definice: Tento automat se nazývá R-treelie, a má (m + A) + m + (m - A) + ■ ■ ■ + (m - k + A) = (k + A)(m + A - |) stavů. Číslo patra koncového stavu odpovídá vzdálenosti nalezeného řetézce od vzoru. li»j:miMfli»j:mjgsWJ:W Proximitní vyhledávání 5F0DC0 pro DIR-vzdálenost lenost, ewGco Fro D/Kľ-vzdálenost ještě pridáme nové stavy do automatu SFODCO odpovídající operaci transpozice a odpovídající dvojici hran pro každou transpozici. Animační program pana Fojera pro diskutované vyhledávací stroje je ke stažení z webové stránky predmetu a je také instalován v B5AA. Simulace NKA nebo determinizace? Hybridní přístup. Pražský stringologický klub a jeho konference. V Část X Indexové metody V □ g - = r^B? Osnova (Týden šestý) © Uzavření kapitoly vyhledávání bez předzpracování textu. © Vyhledávání s předzpracováním textu; indexové metody. ® Metody indexování. © Automatické indexování, konstrukce tezauru. © Způsoby implementace indexu. Vyhledávání s předzpracováním textu Velké množství textů? Předzpracování textu! Základní pojmy es* index, indexové metody, indexový soubor, indexsekvenční soubor es* hierarchické členění textu, značkování textu, hypertext es* otázky uložení seznamu slov (lexikon) a seznamu výskytů (hitů), jejich aktualizace Vyhledávání s předzpracováním textu es* granularita položek indexu: dokument-odstavec-věta - slovo slovo-1 slovo2 slovo3 slovo4 dokA A A O A dokZ O A A A dok5 A O A A es* invertovaný soubor, transpozice dokA dok2 dok3 slovo-1 -10-1 slovo2 -1-10 slovo3 0-1-1 slovo4 -1-1-1 Vyhledávání v indexu Indexové metody es* Uspořádání slov (primární klíč) v indexu —> binární vyhledávání Časová složitost vyhledávání jednoho slova v indexu: n délka indexu, 1/délka vzorku 0(1/ x log2(n)) es* Vyhledávání/c slov, vzorek p = ^.....i//; K Corpus Query Frocee>or základní dotazy • „Havel"; 45: Český prezident Václav se včera na 09: jak řekl Václav , každý občan 24Ô: více než rokem řekl Pravda vítězí regulární výrazy • „Pravda | pravda"; • ,,(P|p)ravda"; • ,,(P|p)ravd[a,u,o,y]"; O „pravd.*"; „pravd.+"; „post?el"; Corpus Query Frocee>or dotazy na poziční atributy • [word = „Havel"]; • [lemma = „'prezident"] []* [lemma = „Havel"]; • ... ženu prezidenta Havla ... [lemma = „hnát"] [] [lemma = „Havel"]; O [word = ,,žen(u|eme)" & lemma !=„žena"]; I ...or I... not některé další možnosti O [lemma = „prezident"] []* [lemma = „Havel"] within s; ... AO, 3 e • [lemma = „Havel"] within 20 „Pravda" • a:[word= „Žena|Muž|Clověk"] []* [lemma = a.lemma] Rub a líc relevantního vyhledávání Velká výpočetní síla dnešních počítačů umožňuje: • efektivní uložení velkého objemu textových dat (komprese, indexování); • efektivní vyhledávání textových řetězců. To všechno využije člověk sedící za počítačem, aby z takto zpracovaných textů získal informace, které ho zajímají. Opravdu? Příklad: V textové databázi je uloženo několik posledních ročníků denního tisku. Pád bych získal informace o prezidentu Václavu Havlovi. a/>HAVEL b/>přesnější dotazy cl... Vocítac (výpočetní síla) + člověk (inteligence) hodnotné informace ca s + + peníze přenést co největší část inteligence (času, peněz, Cíl nás všech ■ .) na počítač. a Osnova (Týden sedmý) es* Exkurs do počítačové lingvistiky. es* Korpusová lingvistika jako příklad TIS. es* Vyhledávací metody s předzpracování textu i vzorku (dotazu). es* Google jako příklad TIS. > a líc relevantního vyhledávání Úrovně zpracování (indexování, adresování) textů v přirozené jazyce informace pragmatická analýza sémantická analýza syntaktická analýza morfologická analýza slova jsou řetězce písmen ideál ideálu kontext význam vět TIL gramatika CFG, DCG slovotvorba lemma vyhledávání řetězců ne v začátcích částečně ano ano Vyhledávání informací Kontrola pravopisu Kontrola Správný překlad Překlad jedn. Rub a líc získávání Informací z přirozeného jazyka Víme opravdu, co je informace obsažená v textu v přirozeném jazyce? • František Novák váží -100 kg. ------> RDB objekt vlastnost hodnota atribute, atríbut2,... • František Novák má rád pivo. ? klíč hodnota František Novák má rád / Janu Novotnou O • F. N.je starý poctivec. ------> . Jaro propuklo v plné síle. Slova přirozeného jazyka označují objekty, jejich vlastnosti a vztahy mezi nimi. Na slova a vety je možné pohlížet také jako na „funkce" svého druhu, definované významem. Textovou informaci (konkrétní objekty o nichž hovoříme, pragmatické informace, ...) lze pak chápat jako „výpočet" téchto funkcí. Tento výpočet je pro nejednoznačnost často nepřesný nebo nemožný. • Muž, který vystoupil na nejvyšší českou osmitisícovku, je můj vnuk. □ g - = Korpusová lingvistika es" Korpue: elektronická kolekce textů, často Indexovaná lingvistickými značkami. es" Korpusjako textový informační systém: korpusová lingvistika. es" BNC, Fenn Treebank, DESAM, FNK,...; rozsahy řád milionů až miliard pozic (slov), speciální metody nutné. es" Korpusové manažery CQF, GCQF, Manatee/Bonito, http://www.fi.muni.cz/~pary/korp/. ES" Vnitřní architektura a implementace korpusu, viz podklady [MAR]. □ g - ■== Co je korpus? Definice: Korpus je rozsáhlý, vnitřně strukturovaný ucelený soubor textů v přirozeném jazyce elektronicky uložený a zpracovatelný. Historie/motivace • Indiánské jazyky nemají písmo- pro nalezení gramatiky potřeba nejprve sepsat mluvené slovo. o A 967 - A. korpus v U. 5. A. (Kučera, Francis) A OOO OOO slov. a Noam Chomsky-odmítá korpusy. • Dnes - masové rozšíření. V Korpusy na Fl o WWW stránka Pavla Rychlého (~PARY) odkaz na základní informace. Bonito, Manatee. o IMS CORPUS WORKBENCH - sada nástrojů pro efektívni kódovaní, reprezentaci a dotazování nad velkými textovými soubory. a i^ms Logický pohled na korpus Posloupnost slov na očíslovaných pozicích (první slovo, n-té slovo), kterým jsou přidány značky (přidávání značek nazývané značkování korpusu). Značky nesou morfologické, gramatické a libovolné další údaje o daném slovu. To vede k obecnéjšímu pojmu pozičních atributů, které jsou nejdůležitější značkovací typ. Atributy z této třídy mají hodnotu (řetézec) na každé korpusové pozici. Na každou z nich je navázáno jedno slovo textu jako základní a poziční atribut word. Kromé tohoto atributu mohou být s každou pozicí svázány další poziční atributy libovolného textu představující morfologické a jiné značky. Strukturální atributy - vety, odstavce, nadpis, článek, SGML. P0S2 VOSA LEMMA český prezident vaclav havel dnes Vnitřní architektura korpusu Dva klíčové pojmy interní reprezentace pozičních atributů jsou: • Jednotná reprezentace: položky jsou pro všechny atributy za kód ovány jako čísla typu integer, kde stejné hodnoty mají stejný číselný kód. Posloupnost položek je pak reprezentována jako posloupnost integerů. Interní reprezentací atributu word (stejnejako každého jiného poz. atributu) je array(0. .p-1) of Integer, kde p je počet pozic v korpusu. • Invertovaný soubor: pro posloupnost čísel reprezentující posloupnost hodnot daného atributu je vytvořen invertovaný soubor. Tento soubor pro každou hodnotu (lépe kód hodnoty) obsahuje množinu výskytů položky v pozičním atributu. Inverzní soubor je potřebný pro vyhledávání, protože přímo ukazuje množinu výskytů dané položky, výskyty pak mohou být počítány vjednom kroku. □ g - = jš Vnitřní architektura korpusu (pokr.) Soubor se zakódovanými hodnotami atributu i inverzní soubor mají pomocné indexové soubory. Pro soubor se zakódovanými hodnotami: o První datovou strukturou je seznam položek či „lexikon": ten obsahuje množinu rozdílných hodnot. Interné se jedná o množinu řetézců vyskytujících se v posloupnosti položek, kde znak Null (osmičkové OOO) je vložen za každé slovo. Seznam položek už definuje kód pro každou položku, protože předpokládáme, že první položka v seznamu má kód O, následující-1 atd. • Pro vyhledávání řetézce v našem seznamuje užitečné mít index na pozici začátku řetězce v tomto souboru. Tento index pro každý kód položky dává konverzi z kódu položky na relativní adresu (v bytech) v seznamu položek... Vnitřní architektura korpusu (pokr.) Pro invertovaný soubor existují tři datové struktury: • První je samostatný invertovaný soubor, který obsahuje množinu korpusových pozic. o Druhý je index do tohoto eouboru. Tento index vrací pro každý kód položky vstupní bod náležící výskytu v inverzním souboru. o Třetí je tabulka frekvence kódu položek, která dává pro každý kód položky číslo výskytu kódu v korpusu (které je samozřejmě stejné jako velikost množiny výskytů). Implementace indexových systémů Přehled možných přístupů a implementací es* Invertovaný soubor - indexový soubor s bitovým vektorem. es* Použití seznamu dokumentů ke každému klíčovému slovu. es" Souřadnicový systém s ukazateli [MEL, obr. 4/1 £>, strana 46]. es" Indexace korpusových textů: Finlib http://www.fi.muni.cz/~pary/dis.pdf viz podklady [MAP]. es" Použití Eliášových kódů pro komprimaci seznamu hitů. V Implementace indexových systémů (pokr.) es- Efektívni uložení indexu/slovníku [lemmat]: packed trie, Patricia tree, a další stromové struktury. es- Syntactic neural network (S. M. Lucas: Rapid best-first retrieval from massive dictionaries, Pattern Recognition Letters -17, p.-1507-15-12,-1996). es* Komerční implementace: Verity engine, webové vyhledávače většinou svůj klíč k úspěchu až na výjimky tají. Reprezentace slovníku KA I Článek M. Mohri: On Some Applications of Finite-State Automata Theory to Natural Language Processing viz podklady [MAR] es* Reprezentace slovníku konečným automatem. es* Nejednoznačnosti, sjednocení minimalizovaných deterministických automatů. es" Příklad: done,do.V3:PP done,done.AO es* Morfologický slovník jako seznam dvojic [slovní tvar, lemma]. es* Kompaktace uložení datové struktury automatu (Liang, -19Ô3). es* Kompresní poměr až-1:20 při lineárním přístupu (vzhledem k délce slova). rezentace slovníku KA II es* Převodník (transducer) pro reprezentaci slovníku. es* Deterministický převodník s -1 výstupem (subsequential transducer) pro reprezentaci slovníku včetně jednoho řetězce na výstupu (informace o morfologii, dělení slov,...). es* Deterministický převodník s p výstupy (p—subsequential transducer) pro reprezentaci slovníku včetně více řetězců na výstupu (víceznačnosti). es* Determinizace převodníku obecně neuskutečnitelná (třída deterministických převodníků s výstupem je vlastní podtřída nedeterministických převodníků); pro účely zpracování při rozeného jazyka vsak obvykle nenastává (nejsou zde cykly). □ g - ■== rezentace slovníku KA III es* Přidání stavu do převodníku odpovídajícího (w^,W2) bez porušení determiničnosti: nejprve stav pro {w-\ß), pak s výsledným stavem konečný stav s výstupem W2- es" Efektivní metoda, rychlá, leč není minimální; existují minimalizacni algoritmy, které vedou na prostorově úsporná řešení. es" Postup: rozdělení slovníku na části, vytvoření det. převodníků s p výstupy, jejich miminalizace, pak deterministické sjednocení převodníků a minimalizace výsledného. es" Další použití i při efektivní indexaci, rozpoznávání řeči, atd. Vyhledavači metody IV. Předzpracování textu i vzorku (dotazu): drtivá většina dnešních TIS. Typy předzpracování: es* statistiky n-gramů (fragmentové indexy). es* speciální algoritmy pro zpracování indexů (kódování, komprese) a vyhodnocení relevance (PagePank u Google). es* využití metod zpracování přirozeného jazyka (morfologie, syntaktická analýza, sémantické databáze) a agregace informací z více zdrojů (systémy AnswerBus, STAPT). es" signaturove metody. Relevance Definice: Relevance (odpověď] na dotaz) je míra rozsahu, kterým se vybraný dokument shoduje s požadavky na něj kladenými. Ideální odpověď = skutečná odpověď Definice: Koeficient úplnosti R (recall) K = jr kde m je počet vybraných relevantních záznamů a n je počet všech relevantních záznamů v TIS. Definice: Koeficient přesnosti P (precision) F = ^, kde oje počet všech vybraných záznamů dotazem. Chceme docílit maximum R i F, tradeoff. Standardní hodnoty: &0% pro F, 20% pro K. Kombinace úplnosti a přesnosti: koeficient Fi, = ŕ2^+R ■ (Fo = F Fa, = F> při Fi = F P a R váženy stejně). □ g - = Fragmentový index Vyhledávání pomocí f ragmentových indexů es* Fragmentybd je v angličtině pouze ve slově molybden. es" Výhody: pevný slovník fragmentů, odpadají problémy s aktualizací. es- Nevýhody: závislost na jazyce a tématické oblasti, snížená přesnost vyhledávání. V a T^sm Gooooooooooooooq \e Fřítíad anatomie globálního (hypertextové h o Informačního systému (www.google.com). es* Jeden z mála kvalitních vyhledávacích strojů, jehož základní principy a architektura jsou aspoň v principech známy- proto detailnější rozbor dle článku [GOO] http://www7.conf.au/programme/fullpapers/1921coml921.h1 es* Několik inovativních konceptů: FageRank, ukládání lokálního komprimovaného archívu, výpočet relevance z textů hypetextovych odkazů, indexace PDF, Google File System, Google Link... es* Anatomie systému, viz podklady [MAR] V Google: Relevance Klíčové je určení relevance. es* Využití značek textu a typografie webu pro výpočet relevance termů dokumentu. es* Využití textu hypertextových odkazů na dokument odkazujících. V a i^ms Google: FaqeRank es* PageRank: objektivní míra důležitosti stránky na základě citační analýzy (vhodné pro utřídění odpovědí na dotaz, tedy určení relevance stránek). es* Nechť na stránku A ukazují stránky, T-i.....Tn (citace), a nechť O < d < A. Nechť C (A) je počet odkazů na stránce A. PageRank es* PageRank se dá spočítat jednoduchým iterativním algoritmem (pro desítky milionů stránek za hodiny na běžném PC). es* PageRankje pravděpodobnostní rozdělení nad webovými stránkami. es* Motivace s náhodným surfařem, faktor d. Datové struktury Google es* Uložení signatur souborů es* Uložení lexikonu es* Uložení seznamu hitů es" Google File System 19! V a Část XII Kódování V a I^HB Osnova (Týden osmý) es" Dokončení anatomie Google. es" Kódování. es" Entropie, redundance. es- Universální kódování celých čísel. V a rnitm Kódování-základní pojmy Definice: Abeceda A je konečná neprázdná množina symbolů. Definice: Slovo [řetězec, zpráva) nad A je posloupnost symbolů z A. Definice: Prázdný řetězec e je prázdná posloupnost symbolů. Množinu všech neprázdných slov nad A značíme A+. Definice: Kód K je trojice [5,C,f), kde S je konečná množina zdrojových jednotek, C\e konečná množina kódových jednotek, f : 5 —> C+ je injektivní zobrazení. f lze rozšířit na 5+ -» C+: F[5AS2..-Sk) = f[5A)f[52) ■ ■ ■ f{Sk). C+ se někdy nazývá kód. V Základní vlastnosti kódu Definice: x e C+ je Jednoznačně dekodovatelný vzhledem k f, jestliže existuje maximálně jedna posloupnost y e 5+ taková, že f (y) = x. Definice: Kód K = (5,C,f) je jednoznačně dekodovatelný jeetWžejeou jednoznačně dekódovatelné všechny řetězy v C+. Definice: Kód se nazývá prefixový, jestliže žádné kódové slovo není prefixem jiného. Definice: Kód se nazývá sufixo^ý, jestliže žádné kódové slovo není sufixem jiného. Definice: Kód se nazývá afixový, jestliže je prefixový i sufixový. Definice: Kód je úplný jestliže po přidání libovolného dalšího kódového slova vznikne kód, který není jednoznačně dekodovatelný. Základní vlastnosti kódů Definice: Blokový kód délky n je takový kód, při kterém všechna kódová slova mají délku n. Příklad: blokový ? prefixový blokový => prefixový, ale ne naopak. Definice: Kód K = {5,C,f) nazveme binární,jestliže \C\ = 2. V SP = B^sm Komprese a dekomprese Definice: Kompreee [kódování), dekomprese [dekódování): _____\ Kompreee _____x (kódování) původní komprimovaná data data z_____ Dekomprese z_____ (dekódování) Definice: Kompresní poměr je poměr délky komprimovaných data délky původních dat. Příklad: Navrhněte binární prefixový kód pro desítkové číslice, jestliže se často vyskytují čísla 3 a 4, a zřídka 5 a 6. □ g - ■== Entropie a redundance I Nechť Y je náhodná proměnná s pravděpodobnostním rozdělením p(y) = P(Y = y). Pak matematické očekávání (střední hodnota) Nechť 5 = {x^,X2.....xn} množina zdrojových jednotek a nechť pravděpodobnost výskytu jednotky x,- v informačním zdroji S je p, pro i = A.....n, n e N. Definice: Entropie informačního obsahu jednotky x,- (míra množství informace resp. neurčitosti) je H(x,-) = Hř = - log2/?í bitů. Zdrojová jednotka s větší pravděpodobností nese méně informace. V Entropie a redundance II n Definice: Entropie informačního zdroje S je H(S) = - V Pí '°32 Pí í=-i bitů. Platí, že H(S) = V p(y) \oq——=e! loa —— ). Defi nice: Entropie zdrojové zprávy X — x,-,, x,-2... x/t GS informačního zdroje S je H(X, S) = H(X) = V H' = ~~ X '°32 Po bitů. Definice: Dá/íca /(X) zafcódo/a/iá zprávy X k k /(X) = £ |f(xřj.)| = £>,-. bitů. Věta:/(X) >H(X,S). Entropie a redundance III Axiomatické zavedení entropie viz podklady [MAR], detaily odvození viz ftp://www.math.muni.cz/pub/math/people/Paseka/lectures/kod< k Definice: R(X) = l(X) - H(X) = y\d\j + log2 Píj) je redundance kódu K pro zprávu X. n Definice: Průměrná délka kódového e\ova kódu K je AL(K) = / p\d\ bitů. Definice: Průměrná entropie zdroje S je n n AE{5) = ^T přHř = - ^T př log2 př bitů. í=-i í=-i Definice: Průměrná redundance kódu K je AR(K) = AL{K) - AE{5) = J^ p,(di + log2 př) bitů. ^ í—i Entropie a redundance IV Definice: Kód je optimální, když má minimální redundanci. Definice: Kód je aeymptoticky optimální, pokud pro dané rozložení pravděpodobností se poměr AL{K)/AE{5) blíží k A, když se entropie blíží oo. Definice: Kód K je universální, jestliže existují c-\,C2 E R tak, že průměrná délka kódového slova AL(K) < c^ x AE + C2- Věta: Universální kód je aeymptoticky optimální, jestliže c-i = 1. Universální kódování celých čísel Fibonacciho posloupnost a reprezentace Definice: Fibonacciho posloupnost řádu m Fn = Fn_m + Fn_m_M + ... + Fn_^ pro n > A. Příklad: F řádu 2: F_^ = 0„ F0 = -1, F^ = A, F2 = 2, F3 = 3, F4 = 5, F5 = ô,.. Příklad: F řádu 3: F_2 = O, F_A = O, F0 = A, FA = A, F2 = 2, F3 = 4, F4 = 7, F5 = -13,... Příklad: F řádu 4: F_3 = O, F_2 = O, F_^ = O, F0 = A, Fa. = A, F2 = 2, F3 = 4, F4 = 0, F5 = -15,... Definice: Fibonacciho reprezentace R(N) = ^Í=A d\F\, kde d-,E{0,A},dk = A Veta: Fibonacciho reprezentace není jednoznačná, existuje vsak taková, že v posloupnosti d, je nejvýše m - A po sobě jdoucích jedniček Fibonacciho kódy Definice: Fibonacciho kód řádu m FKm(N) = d^d2---dk A...A , kde m-A krát d\ jsou koeficienty z předchozí věty (jedničky ukončují slovo). Příklad: R(32) =0*A+0*2+A*3+0*5+A*8+0* A3 + A*2A, tedyF(32) =OOAOAOAA. Věta: FK(2) je prefixový, universální kód s c^ = 2, C2 = 3, tedy není asymptoticky optimální. Universální kódování celých čísel II Eliášovy kódy «s* asymptoticky optimální universální kód, c-\ = A, do N = 5-14220jsou lepší Fibonacciho kódy řádu n (FK(n)). vse unární kód a{N) = 00... O A. M-A «s- binární kód ß{A) = A,ß{2N + j) = ß(N)j, j = 0,A. «s* P není jednoznačně dekódovatelný (není prefixový). vse ternámí v{N) = ß(N)#. rar p (A) = 6,P'{2H) = ß'{H)0, ß'{2H + A) = ß'{H)A,v'{H) = ß'{H)#. ra" y. každý bit ß'{N) je vložen mezi dvojici bitů z a(\ß(N)\). » příklad: r(6) = OTOÖI "* CK = {k(W) : W > 0} = (0{0, -1 })M je regulární a tedy dekódovatelná konečným automatem. Universální kódování celých čísel III es- /{N) = a{\P{H)\)P'{H) stejné délky (permutace bitů y{H)), ale čitelnější es- cr = {/(N) :N>0} = {0kA {0,A}k :k> 0} není regulární a dekodér potřebuje čítač ^ ó(N) = Y(\P(N)\)f>'(N) es- příklad: 5{A) = k(3)00 = OAAOO rar dekodér 5: 0 do begin K := ß{N)K; N:= \\0Q2(M)\ end. Komprese dat - úvod es- Kódování informace pro komunikační účely; komprese dat. es- Přes bouřlivý vývoj kapacit pro uložení dat stále nedostatek místa. es* Redundance —» konstrukce minimálně redundantního kódu. es- Model dat: • struktura- sada jednotek ke komprimaci + kontext výskytů; • parametry- pravděpodobnost výskytu jednotlivých jednotek. es- Komprimace: O vytvoření modelu dat; O vlastní kódování. V Komprese dat - vývoj es- -1Ô3Ô Morse, kód £ dle četnosti. es* -1949 Shannon, Fano, Weaver. es* -1952 Huffman; 5 bitů na znak. es" -1979 Ziv-Lempel; compress (Roden, Welsh, Bell, Knuth, Miller, Wegman, Fiala, Green,...); 4 bity na znak. es" osmdesátá a devadesátá léta PPM, DMC, gzip (zlib), SAKDC; 2-3 bity/znak ES" přelom tisíciletí bzip2; 2 bity na znak. ES" ...? V 2 znaku null, 255, speciální znak 5C es- run-length encoding (RLE) - 5CXCC zobecnění na libovolný opakující se znak $***** *55 —> $5C * 655 csř MNP Class 5 RLE - CXXX DDDDDBBAAAA -» 5DDDBB4AAA cy half-byte packing, (EBCDIC, ASCII) SI, SO es- diatomic encoding; nahrazování dvojic znaků jedním es- Byte Fair Encoding, BFE (Gage, -1994) es- pattern substitution es- Gilbert Held: Data & Image Compression □ g - ■== Statistické metody komprese II es* Shannon-Fano, -1949, model řádu O, prefixový kód, kódový strom. es* kódová slova délky |_— log2 /9,-J nebo |_— log2 p,- + -1J es- AE Shannon-Fano kódování Vstup: posloupnost n zdrojových jednotek 5[i], A < i < n,v pořadí neklesajících pstí. Výstup: n binárních kódových slov. begin přiřaď všem kódovým jednotkám prázdný řetěz; SF-SPLIT(S) end procedure SF-SPUT(S); begin if |S| > 2 then begin rozděl 5 do posloupností 5-1 a 52 tak, že obe posloupnosti mají přibližně stejnou celkovou pst; přidej ke všem kódovým slovům z 5-1 O; přidej ke všem kódovým slovům z 52 -1; SF-SPUT(S-I); SF-SPUT(S2); end end □ ► < g Osnova (Týden desátý) es* Huffmanovo kódování. es- Adaptivní Huffmanovo kódování. es- Aritmetické kódování. es- Slovníkové metody. es- Slovníkové metody s restrukt. slovníku. Huffmanovo kódování es* Huffmanovo kódování, -1952. es* varianty statická a dynamická. es* AEPL = 2L, d[f]p[f]. es- optimální kód (ne jediný možný). es* 0{ri) za předpokladu utříděnosti zdrojových jednotek. es- stabilní rozložení—> příprava předem. Příklad: (2,2,2,2,4,4,0) HufFmanovo kódovaní - sourozenecka vlastnost Definice: Binární strom má eourozeneckou viaetnoet právě tehdy, když O každý uzel kromě kořene má sourozence, O uzly mohou být seřazeny v pořadí neklesající posloupnosti tak, že každý uzel (kromě kořene) sousedící v seznamu s nějakým uzlem je jeho sourozenec (leví synové budou na lichých místech v seznamu a praví synové na sudých). Huff manovo kódování-vlastnosti Huff manových stromů Věta: Binární prefixový kód je Huff manův š=> má sourozeneckou vlastnost. es* 2n — A uzlů, max. 2n — A možností, es* optimální binární prefixový kód, který není Huff manův es* R(X) < pn + 0,0&6, pn maximální pravděpodobnost zdrojové jednotky. es* Huffman je úplný, (špatná detekce chyb). es" afixový kód, KWIC, levý a pravý kontext, hledání *X* V Adaptivní H uff ma novo kódování es- FGK (Faller, Gallager, Knuth) es- potlačení minulosti zapomínacím koeficientem, zaokrouhlování, A, es* lineární čas kódování i dekódování vzhledem k délce slova. es" ALhd < 2ALHS- es- Vitter ALhd < ALHs + "1. es- implementační detaily, stromová reprezentace kódové tabulky. Princip aritmetického kódování es* zobecnění Huff manová kódování (pravděpodobnosti zdrojových jednotek nemusí být záporné mocniny dvou). es* uspořádání na zdrojových jednotkách; Kumulativní pravděpodobnost cp-, = £j=-i pj zdrojové jednotky x,-s pravděpodobností/?,-. es* Výhody: o libovolná blízkost entropii. • adaptivnostje možná, o rychlost. □ g - ■== Slovníkové metody komprese dat Definice: Slovník je dvojice D = (M, C), kde M je konečná množina slov zdrojového jazyka, CzobrazeníM na množinu kódových slov. Definice: L{m) značí délku kódového slova C{m) v bitech, pro m G M. Výběr zdrojových jednotek: • statický {dohoda na slovníku předem) o semiadaptivní (nutné dva průchody textem) • adaptivní Statické slovníkové metody Zdrojová jednotka délky n - n-gramy Nejčastější bigramy (n = 2) • n pevné o n proměnné {dle frekvencí výskytu) • adaptivní (50 % anglického textuje tvořeno asi -150 nejfrekventovanějším Nevýhody: o nejsou schopny reagovat na rozdelení pravdepodobností komprimovaných dat o předem připravený slovník □ g - Semiadaptivní slovníkové metody Slovník Komprimovaná data Komprimovaný slovník Komprimovaná data Výhody: rozsáhlá data (slovníkje malá část dat- korpusy; CQF). V a i^ms Semiadaptivní slovníkové metody - postup vytvoření slovníku O Určí se frekvence N-gramů pro N = -1,2..... O Slovník se inicializuje vložením unigramů. O Do slovníku se postupně přidávají N-grámy (N > 1) s největší frekvencí. Při vložení K-gramu se snižuje frekvence jeho složek (K — A )-gramů, (K - 2)-gramů — Jestliže se díky snižování frekvencí frekvence nějaké položky velmi sníží, je ze slovníku vyloučena. Adaptivní slovníkové metody Lempel, ZÍVÍ977, 7& LZ77 - metody posuvného okna LZ7Ô - metody rostoucího slovníku Metoda posuvného okna a b c b a b b a a b a c b zakódovaná část nezakód. cast (okno, N < ÔA92) (\B\ ~-1O20b) Krok kódování LZ77 V zakódované části je vyhledána nejdelší predpona P řetězu v nezakódované oblasti. Pokud je takový řetěz S nalezen, pak P je zakódováno pomocí (I, J, A), kde I je vzdálenost prvního znaku 5 od hranice, J je délka řetězu S a A je první znak za předponou P. Okno je posunuto o J + -1 znaků doprava. Jestliže podřetěz S nalezen nebyl, pak je vytvořena trojice (0,0, A), kde A je první znak nezakódované části. LZR (Rodeh) \M\ = (N - ß) x ß x t, t velikost abecedy L(m)= pog2(N-ß)1 + pog2ß1 + \\oq2ť\ Výhoda: hledání nejdelší předpony [KMF] LZR (Rodeh) • LZR používa strom obsahující všechny předpony v dosud zakódované části. o Je použita celá dosud zakódovaná část jako slovník. • Protože / v (/, j, a) může být velké, je použit Eliášův kód pro zakódování celých čísel. Nevýhoda: růst velikosti stromu bez omezením po překročení vymezené paméti vymazán a konstrukce začíná od začátku. □ g LZSS (Bell, Storer, Szymanski) Kódem je posloupnost ukazatelů a znaků. Ukazatel (i, j) potřebuje paměť jak p znaků => ukazatel jen tehdy, když ušetříme, aleje třeba bit na rozlišení znaku od ukazatele. Počet položek slovníku je \M\ = t + (N - 3) x (3 - p) (uvažují se jen podřetězy delší než p). Počet bitů na zakódováníje o L(m) = A + [log2 ť] pro m ET o L{m) = A + pog2Nl + \\oq2{& ~ PÍ\ jinak. (Délku d podřetězu můžeme reprezentovat jako 3 - p). LZB (Bell), LZH (Brent) LZB (Bell) Ukazatel (/, j) (analogie LZSS) Jestliže a okno není plné (na začátku) a o komprimovaný text je kratší než N, je plýtvání použití log2 N bytů na zakódování/. LZB používá fázování při bin. kód. - prefixový kód s rostoucím počtem bitů pro rostoucí hodnoty čísel. Pro kódování j používá LZB Eliášův kód y. LZH (Brent) LZSS, kde pro kódování ukazatelů je použito HufFmanovo kódování (tj. dle rozložení jejich pravděpodobností^» 2 průchody) Metody s rostoucím slovníkem LZ7Ô Hlavní myšlenka: slovník obsahuje fráze. Nová fráze tak, že již existující fráze je rozšířena o symbol. Fráze je zakódována indexem předpony a přidaným symbolem. V a T^sm LZ7Ô - pnklad Vstupní a b ab C Index A 2 3 4 Výstup (0,a) (0,b) (1.b) (0.C) Vstupní bab aa 333 Index 6 7 ô Výstup (5,b) "sa (7,a) I^HB ba 5 (2,a) 3333 9 (ô,a) LZF(3 (Fiala, Green] LZR3 (Fiala, Green) Slovník uložen ve stromové struktuře, hrany ohodnoceny řetězy znaků. Tyto řetězy jsou v okně a každý uzel stromu obsahuje ukazatel do okna a identifikující symboly na cestě z kořene do uzlu. V a T^sm LZW (Welch), LZC LZW Výstupem jsou pouze indexy, nebo O slovník je iniciován položkami pro všechny vstupní symboly, • poslední symbol každé fráze je prvním symbolem následující fráze. Vstup ababcbababaa a a a index 4 5 6 7 ô 9-10 Výstup -12 4 3 5 Ô-1 -10-1-1 Přeplnění =^ další fráze není předávána a kódování pokračuje staticky. LZC compress je to LZW + • Ukazatele jsou kódovány s prodlužující se délkou. • Jakmile se kompresní pomér začne snižovat, slovník se vymaže a začíná se od začátku. a LZT, LZMW, LZJ LZT (Tischer) Jako LZC, ale při přeplnění slovníku se ze slovníku vylučujífráze, které byly v nedávné minulosti nejméné použity. Používá frázování při bin. kód. indexů frází. LZMW (Miller, We^man) Jako LZT, ale nová fráze se nevytváří přidáním jednoho symbolu k předchozí, ale konstruuje novou frázi zřetězením dvou posledně zakódovaných. LZJ (Jakobsson) Jiný princip konstrukce slovníku: • Na začátku vloženy jednotlivé symboly. • Slovník uložen ve stromu a obsahuje všechny podřetězy zprac. řetězem do délky h. • Plný slovník => • statický postup, • vynechávání uzlů s nízkou frekvencí použití. Osnova (Týden jedenáctý) es* Slovníkové metody s restrukturalizací slovníku. es- Syntaktické metody. es- Kontrola správnosti textu. es- Dotazování a modely TIS. es- Booleovský model dokumentů. es- Vektorový model dokumentů. es- Architektura TIS. es- Signaturové metody. es- Podobnost dokumentů. Slovníkové metody s restrukturalizací slovníku es* Průběžné uspořádávávání zdrojových jednotek —> kratší řetězce kódu. es* Varianty heuristik (četnost, přesun na začátek (BSTW), výměna s předcházejícím, přesun o K vpřed). es" BSTW (výhoda: vysoká lokalita výskytů menšího počtu zdrojových jednotek). es" Příklad: Já do lesa nepojedu.....An2nkn. es" Zobecnění: koeficient nedávnoeti, Intervalové kódování. V Intervalové kódování Reprezentace slova celkovým počtem slov od posledního výskytu. Slovník obsahuje slova a-\, a-z.....an, vstupní posloupnost x-i, X2..... xm. Hodnota LAST(a,-) obsahující interval od posledního výskytu je Inicializovaná na nulu. for t := A to m do begin {xt = a,-} if LAST(xt = O) then y(t) = t + i-A elsey(t) = t - LAST(xt); LAST(xt):=t end. Posloupnost y^, y2.....ym je výstupem kodéru a může být zakódována některým kódem proměnné délky. Syntaktické metody Derivační kódování es* je známa gramatika jazyka zprávy. es* levý rozklad derivačního stromu řetězce. es* globální číslování pravidel. es* lokální číslování pravidel. Analytické kódování es* jsou kódovány rozhodovací stavy LR analyzátoru. Kontextové modelování es" pevný kontext-model řádu N. es* kombinovaný přístup - kontexty různých délek. ^ P(X) = ľ!n=0WnPn{x)- es- wn pevné, proménné. es- náročné na čas a paměť. es- přiřazení pravdepodobnosti nové zdrojové jednotce: e — j^pp es- automaty s konečným kontextem. es- dynamické Markovovo modelování. V Kontrola správnosti textu es* Kontrola textu pomocí frekvenčního slovníku. es* Kontrola textu pomoci dvojitého slovníku. es* Interaktivní kontrola textu (ispell). es* Kontrola textu založená na pravidelnosti slov, koeficient podivnosti. Koeficient podivnosti Koeficient podivnoeti trigramu xyz KPT = [log(f(xy) - A) + log(f(yz) - 1)]/2 - log(f(xyz) - 1), kde f(xy) resp. f (xyz) jsou relativní frekvence digramu resp. trigramu, log (O) je definován jako —-10. Koeficient podivnoeti slova KP5 = a/JjKPT",- - 5KPT"2), kde KPT",- je koeficient podivnosti i-tého trigramu 5KPT}e střední hodnota koeficientu podivnosti všech trigramu obsažených ve slově. Dotazování a modely TIS Různé metody hierarchizace a uložení dokumentů —> různé možnosti a efektivita dotazování. es* Booleovský model, SQL. es* Vektorový model. es* Rozšířené booleovské modely. es* Fravdépodobnostní model. es" Model shluků dokumentů. $\a'\rovo ladění dotazu Vyhledávání spočívá ve zmenšování neurčitosti tazatele (ladění dotazu). Q Najdeme dokument s vysokou relevancí. O Začneme se dotazovat s jeho klíčovými slovy. 0 Odstraňujeme deskriptory, resp. je nahrazujeme disjunkcemi. Infomap - snaha o sémantické dotazování Systém http://infomap. stanford.edu- pro práci s hledaným významem/konceptem (na rozdíl od pouhých řetězců znaků). Správný dotaz je polovina odpovědi. Vyhledávání spočívá v určení sémanticky nejbližších termů. a i^ms V Booleovský model es* 50. léta: reprezentace dokumentů pomocí množin termů a dotazování založené na vyhodnocování booleovských výrazů. es* Výraz dotazu: induktivně z primitiv: • term o jméno_atributu = hodnota^atributu (porovnání) • jméno_funkce(term) (aplikace funkce) a dále pomocí závorek a logických spojek X and Y, Xor Y, Xxor Y, notY. es* disjunktivní normální forma, konjunktivní normální forma es* proximitní operátory es* regulární výrazy es* použití tezauru Jazyky pro vyhledávání - SQL es* booleovské operátory and, or, xor, not. es* poziční operátory adj, (n) words, with, same, syn. ca" SQL rozšíření: operace/dotazy s využitím tezauru BT(A) Broader term NT(A) Narrower term PT(A) Preferred term SYN(A) Synonyma termu A RT(A) Related term TT(A) Top term □ ► < a Dotazování- SQL příklady ORACLE SQL*TEXTRETRIEVAL SELECT specifikace_polozek FROM specifikace_tabulek WHERE položka CONTAINS textovy_vyraz Příklad: SELECT TITLE FROM BOOK WHERE ABSTRACT CONTAINS 'TEXT' AND RT(RETRIEVAL) 'řetěz' 'řetěz'* *'řetěz' 'ře?ěz' 'ře°/„těz' 'řetěza' (m,n) 'řetězb' 'víceslovná fráze' BT('řetěz',n) BT('řetěz',*) NT('řetěz',n) Dotazování- SQL příklady Příklad: SELECT JMENO FROM ZAMESTNANEC WHERE VZDELANÍ CONTAINS RT(UNIVERSITA) AND JAZYKY CONTAINS 'ANGLIČTINA' AND 'NEMČINA' AND PUBLIKACE CONTAINS 'KNIHA' OR NT('KNIHA',*) Stí lesová technika/ asociační faktor (fN -Aß- N/2)2N a5oc(QA,Qe) = lo^0 Aß{N_A){N_ß) A - počet dokumentů „zasažených" dotazem Q/\ b - počet dokumentů „zasažených" dotazem Qg, (jehož relevanci počítáme) f - počet dokumentů „zasažených" oběma dotazy N - celkový počet dokumentů v TIS cutoff (relevantní/ nerelevantní) cluetering/hnízdění A. generace, 2. generace,... Vektorový model Vektorový model dokumentů: Nechť a-\.....an termy, D-\.....Dn dokumenty, a matice relevance W = (wij) typu m, n, ,_ ., f O nem relevantní WnE (0,1 W . . . J L Je relevantni Dotaz Q = (c}>i.....c}n) • 5(Q, Dj) = ^Tf qjWjj koeficient podobnosti » head(sort(S(Q,Dj))) odpověď Osnova (Týden dvanáctý) es* Vektorový model dokumentů (dokončení). es* Pravděpodobnostní model. es* Model shluků dokumentů. es* Architektura TIS. es" Signaturové metody. es" Podobnost dokumentů. es" Komprese pomocí neuronových sítí. Vektorový model: pros & cons CONS: nebere v úvahu ?"a"? ?"nebo"? PROS: možné vylepšení: • normovaní vah • Frekvence termu TF a Inverzní frekvence dokumentu IDF: 9 Rozlišení termů o normovaní vah pro dokument: TD • normování vah pro dotaz: (i x 2 rĽ r V 2 max Tr, [POK, strany 85-A-13]. E^5H log2f x iog2 f V □ g - = Automatické strukturování textu es* Vzájemné vazby mezi dokumenty v TIS. es* Encyklopedie (OSN, Funk and Wagnalls New Encyclopedia). rar [SBA] http://columbus.es.nott.ac.uk/compsci/epo/epodd/ep056g£ es* Google/CiteSeer: „automatic structuring of text files" V Signaturwé metody Vyhledávací metody IV. Předzpracování textu i vzorku (signaturové metody). Signatury es* řetězené es* vrstvené Dále [FOK, strany 65-76], viz podklady [MAR]. Seznam materiálů u Marečka [MAR] Materiály k predmetu FV050 ke zkopírování v knihkupectví Mareček. Q Slidy přednášek předmětu, 4 slidy na list A4. Q kopie [MEL]. O kopie [POK]. Q článek [MEH]. Q materiály o Google [GOO] (plus české shrnutí). Q kapitola 5.7 z [KOR] (podobnost). O [MeM]. @ ostatní (NLP, diagram s kompresními algoritmy,...). V