Ý PV030 Textové informační systémy Petr Sojka Fakulta informatiky Masarykova univerzita v Brně Jaro 2006 Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Část I Informace o předmětu PV030 Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura Úvodem Petr Sojka, sojka@informatics.muni.cz Konzultační hodiny jaro 2006: úterý 15:15­16:00 a čtvrtek 14:00­15:30, po domluvě emailem i jindy. Místnost B304, 3. patro bloku B, Botanick á 68a. URL s materi ály k předmětu: http://www.fi.muni.cz/~sojka/PV030/ Rozdělení do cvičení (B410 B311). Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura Určení a klasifikace předmětu Prerekvizity 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 programov ání a 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í šk ála (změna vyhrazena) z/k/E/D/C/B/A odpovíd á zisku 48/54/60/66/72/78/84 bodů. Termíny z ávěrečného písemného testu budou zveřejněny cestou IS. Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura 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í. Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura 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ů (MP, KMP, AC, RV). Protism. 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. Google Scholar, CiteSeer. Vyhled ávací metody s předzpracov áním textu a vzorků ­ signaturové metody. Jazyky pro vyhled áv ání. Komprese dat, z ákladní principy (entropie). Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura Sylabus (pokr.) Statistické metody komprese dat. Slovníkové metody komprese dat. 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. Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura Knihy, skripta [MEL] Melichar, B.: Textové informační systémy, skripta ČVUT Praha, 2. vydání, 1996. [POK] Pokorný, J., Snášel, V., Húsek D.: Dokumentografické informační systémy, Karolinum Praha, 1998. [KOR] Korfhage, R. R.: 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, 1998. [WMB] Witten I. H., Moffat A., Bell T. C.: Managing Gigabytes: compressing and indexing documents and images, Second edition, Morgan Kaufmann Publishers, 1998. Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura Doplňkové zdroje informací [HEL] Held, G.: Data and Image Compression, Tools and Techniques, John Wiley & Sons, 4. vydání 1996. [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): 107­117 (1998). http://dbpubs.stanford.edu:8090/pub/1998-8 [MeM] Mehryar Mohri: On Some Applications of Finite-State Automata Theory to Natural Language Processing, Natural Language Engineering, 2(1):61­80, 1996. http://www.research.att.com/~mohri/cl1.ps.gz Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura Doplňkové zdroje informací (pokr.) [Sch] Schmidhuber J.: Sequential neural text compression, IEEE Transactions on Neural Networks 7(1), 142­146, 1996, http://www.idsia.ch/~juergen/onlinepub.html [SBA] 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 [WWW] stránky předmětu ~sojka/PV030/, semináře DIS http://www.inf.upol.cz/dis, http://nlp.fi.muni.cz/, The Prague Stringologic Club Workshop 1996­2004 http://cs.felk.cvut.cz/psc/ Jones, S. K., Willett: Readings in Information Retrieval, Morgan Kaufman Publishers, 1997. Petr Sojka PV030 Textové informační systémy Ý Úvodní informace Předpoklady předmětu a způsob klasifikace Sylabus předn ášky Doporučen á literatura Doplňkové zdroje informací (pokr.) Bell, T. C., Cleary, J. G., Witten, I. H.: Text Compression, Prentice Hall, Englewood Cliffs, N. J., 1991. Storer, J.: Data Compression: Methods and Theory, Computer Science Press, Rockwille, 1988. č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ý), materiály kursu TIS na MFF: http://service.felk.cvut.cz/courses/36TIS/ (skripta Melichar) Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Část II Základní pojmy TIS Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Pojmy (T)IS, zasazení PV030 do kontextu výuky na FI TIS ­ motivace realita data potřeba informace dotaz Abstrakce a mapov ání v informačním systému. Informační potřeba o realitě ­ dotazy nad daty. Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Pojmy (T)IS, zasazení PV030 do kontextu výuky na FI Základní 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: Ektosystém se sklád á z uživatelů IS, investora IS a toho, kdo systém provozuje (user, funder, server). Na příkladě IS MU jsou to uživatelé IS, MU reprezentovan á kvestorem a CVT a ÚVT MU. Ektosystém není pod kontrolou designéra IS. Definice: Endosystém sest áv á z použitého hardware (media, devices), a software (algorithms, data structures) a je plně pod kontrolou designéra IS. Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Pojmy (T)IS, zasazení PV030 do kontextu výuky na FI Požadavky na TIS efektivita (user) ekonomika (funder) efektivnost (server) a z toho vyplývající kompromisy. Naše hledisko bude hledisko architekta TIS respektujícího požadavky ektosystému IS. Pro problematiku ektosystému IS viz PV045 Management IS. Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Pojmy (T)IS, zasazení PV030 do kontextu výuky na FI Od dat k moudrosti Údaj ­ konkrétní vyj ádření 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: 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). Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Pojmy (T)IS, zasazení PV030 do kontextu výuky na FI Informační proces Definice: Informační proces ­ proces vzniku informací, jejich zobrazení ve formě údajů, zpracov ání, poskytov ání a využití. Tomuto procesu odpovídají operace nad informacemi. Data/sign ály Informace Znalost Moudrost. Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Minianketa Klasifikace IS podle převládající funkce ü dokumentografické vyhled ávací systémy (Information Retrieval Systems). ý datab ázové systémy (DMBS), relační DB (PB154, PB155, PV003, PV055, PV136, PB114). faktografické systémy pro řízení (Management Information Systems PV045). systémy pro podporu rozhodov ání (Decision Support Systems PV098). expertní (Expert Systems), dotazovací (Question Answering Systems) a znalostní (Knowledge-Based) systémy, (PA031). Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Minianketa Klasifikace IS podle převládající funkce (pokr.) specifické informační systémy (geografické PV019, PA049, PA050, medicínské PV048, enviroment ální PV044, podnikové PV043, ve st átní spr ávě PV058, PV059, knihovnické PV070); d ále též PV063 Aplikace datab ázových systémů. Související oblasti vyučované na FI: Technologie informačních systémů: PA102, PA105. Specifické aspekty indexov ání: Indexov ání multimedi álních dat: PA128. Implementace datab ázových systémů: PA152. Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Minianketa Různost pohledů na TIS Vyhled ávací systém Expertní systém DBMS Datab ázový systém Systém pro řízení Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Minianketa 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) Jak jste spokojeni? Vytv áření IS (server) a) Jaký (T)IS nebo jeho komponentu jste realizoval? Oblast, rozsah? b) Jak jste s tímto (T)IS spokojeni, slab á místa? Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Klasifikace a formalizace VS Vyhledávací systémy (VS) ­ princip DB Množina Dotaz - Dotazovací - vybraných stroj dokumentů Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Klasifikace a formalizace VS Pr ázdný vyhledávací systém DB Definice dokumentů Definice form átu výst. dok. VYHLED ÁVACÍ Množina Definice způsobu SYST ÉM vybraných vyhl. dokum. dokumentů Obsah dokumentů Dotazy Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Klasifikace a formalizace VS Vyhledáv ání ­ formalizace problému Zřetězení: Ř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 x a y existuje kladné k tak, že bud' x = succk(y) nebo x = predk(y). Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Klasifikace a formalizace VS 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ísmena abecedy. A+. Pr ázdný řetěz . Definice: Konečný řetěz A = A+ {}. Definice: Line ární řetězec nad A: prvek A+. Definice: Vzorek. Text. Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Klasifikace a formalizace VS Vyhledávací systémy ­ klasifikace ü Klasifikace dle směru průchodu vzorku: sousměrné/protisměrné ý Klasifikace dle (před)zpracov ání textu a vzoru: ad 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 do původního textu; signatura: řetězec příznaků indikující přítomnost významných prvků v textu Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Klasifikace a formalizace VS Vyhledávací systémy ­ klasifikace (pokr.) předzpracov ání textu ne ano předzpracov ání ne I III vzorků ano II IV I ­ element ární algoritmy II ­ vytvoření vyhled ávacího stroje III ­ indexové metody IV ­ signaturové metody Petr Sojka PV030 Textové informační systémy Ý Pojmy a klasifikace IS Klasifikace (T)IS Vyhled ávací systémy Klasifikace a formalizace VS 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ů P = {v1, v2, . . . , vk}. 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ů z L(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. Petr Sojka PV030 Textové informační systémy Ý I VS bez předzpracov áním vzorků i textu II ­ Přesné vyhled áv ání s předzpracov áním vzorků Karp-Rabinovo vyhled áv ání Část III Přesné vyhledáv ání Petr Sojka PV030 Textové informační systémy Ý I VS bez předzpracov áním vzorků i textu II ­ Přesné vyhled áv ání s předzpracov áním vzorků Karp-Rabinovo vyhled áv ání Element ární vyhled ávací algoritmus Naivní vyhledáv ání, vyhledáv ání hrubou silou, element ární vyhledávací algoritmus proc 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"; Petr Sojka PV030 Textové informační systémy Ý I VS bez předzpracov áním vzorků i textu II ­ Přesné vyhled áv ání s předzpracov áním vzorků Karp-Rabinovo vyhled áv ání Element ární vyhled ávací algoritmus Analýza časové složitosti naivního vyhledáv ání složitost měřena počtem porovn ání, délka vzorku V, délka textu T. horní odhad = V (T - V + 1), tedy O(V × T). nejhorší příklad VZOREK = aV-1b, TEXT = aT-1b přirozené jazyky: (průměrn á) složitost (počet porovn ání) výrazně menší, nebot' nedoch ází ke shodě počátků slov příliš často. Pro angličtinu = CE (T - V + 1), CE empiricky naměřeno 1.07, t. j. prakticky line ární. CCZ? CCZ vs. CE? urychlení? aplikace pro více vzorků? nekonečný počet? verze algoritmu (S, Q, Q) na cvičení. Petr Sojka PV030 Textové informační systémy Ý I VS bez předzpracov áním vzorků i textu II ­ Přesné vyhled áv ání s předzpracov áním vzorků Karp-Rabinovo vyhled áv ání Element ární vyhled ávací algoritmus 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 c je počet testů a platí: je-li nalezen index i, pak c = i a s = 1 není-li nalezen, pak c = T a s = 0 Petr Sojka PV030 Textové informační systémy Ý I VS bez předzpracov áním vzorků i textu II ­ Přesné vyhled áv ání s předzpracov áním vzorků Karp-Rabinovo vyhled áv ání Element ární vyhled ávací algoritmus Naivní vyhledáv ání ­ algoritmus S vstup: var TEXT : array[1..T] of slovo; VZOREK : slovo; výstup (v proměnné FOUND): Ano/Ne 1 I:=1; c while I T do begin c if TEXT[I]=VZOREK then break; c-s inc(I); end; 2 FOUND:=(IT); Nalevo od příkazů je uvedena jejich složitost. Celkov á časov á složitost tedy je O(T) = 3c - s + 3. Maxim ální složitost (kter á se běžně uv ádí) je O(T) = 3T + 3. Petr Sojka PV030 Textové informační systémy Ý I VS bez předzpracov áním vzorků i textu II ­ Přesné vyhled áv ání s předzpracov áním vzorků Karp-Rabinovo vyhled áv ání Element ární vyhled ávací algoritmus Algoritmus Q aneb jak je tomu s použitím zar ážek vstup: var TEXT : array[1..T+1] of slovo; VZOREK : slovo; výstup (v proměnné FOUND): Ano/Ne 1 I:=1; 1 TEXT[T+1]:=VZOREK; c while TEXT[I]<>VZOREK do c-1 inc(I); 2 FOUND:=(I<>T+1) Index je v tomto případě vždy nalezen; proto je v předposledním ř ádku algoritmu uvedena složitost c - 1 místo c - s (ačkoliv jsou shodné). D ále je potřeba si uvědomit, že maxim ální možn á hodnota c je o 1 větší než v předchozím algoritmu (ale uv ádět c + 1 místo c by nebylo spr ávné). Celkov á složitost O(T) = 2c + 3. Maxim ální složitost: O(T) = 2T + 5. Petr Sojka PV030 Textové informační systémy Ý I VS bez předzpracov áním vzorků i textu II ­ Přesné vyhled áv ání s předzpracov áním vzorků Karp-Rabinovo vyhled áv ání Element ární vyhled ávací algoritmus Algoritmus Q aneb jak je tomu s použitím expanze cyklu vstup: var TEXT : array[1..T+1] of slovo; VZOREK : slovo; výstup (v proměnné FOUND): Ano/Ne 1 I:=1; 1 TEXT[T+1]:=VZOREK; c/2 while TEXT[I]<>VZOREK do begin c/2 if TEXT[I+1]=VZOREK then break; (c - 1)/2 I:=I+2; end; 3 FOUND:=(I 0) and (text[i] = vzorek[j]) do j := h[j]; end while i := i + 1; j := j + 1 end while nalezen := j > V; pokud nalezen, je na pozici i - V Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Analýza (K)MP Složitost O(T) plus složitost předzpracov ání (vytvoření pole h). Animace trasov ání hlavní části KMP. Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Knuth-Morris-Prattův algoritmus h se uplatní, když předpona vzorku v1v2 . . . vj-1 je srovn ána s podřetězcem textu ti-j+1ti-j+2 . . . ti-1 a vj = ti mohu skočit o víc než 1? o j? jak h spočtu? h(j) největší k < j takové, že v1v2 . . . vk-1 je příponou v1v2 . . . vj-1, tj. v1v2 . . . vk-1 = vj-k+1vj-k+2 . . . vj-1 a vj = vk KMP: zpětné přechody tak dlouho, až j = 0 (předpona vzorku není v prohled ávaném textu obsažena) nebo ti = vj (v1v2 . . . vj = ti-j+1ti-j+2 . . . ti-1ti) animace lecroq, d ále [POK, strana 27], též viz podklady [MAR] pro detailní popis. Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Konstrukce h pro KMP i:=1; j:=0; h[1]:=0; while (i0) and (v[i]<>v[j]) do j:=h[j]; i:=i+1; j:=j+1; 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 O(V), celkem tedy O(T + V). Příklad: h pro ababa. KMP vs. MP. Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Univerz ální vyhledávací algoritmus, který použív á tabulku přechodů g odvozenou z hledaného vzorku. (g odpovíd á přechodové funkci KA): var i,T:integer; nalezen: boolean; text: array[1..T] of char; state,q0: TSTATE; g:array[1..maxstate,1..maxsymb] of TSTATE; F: set of TSTATE;... begin nalezen:= FALSE; state:= q0; i:=0; while (i <= T) and not nalezen do begin i:=i+1; state:= g[state,text[i]]; nalezen:= state in F; end; end; Jak předzpracovat vzorek do g? Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Vyhledávací stroj Vyhled ávací stroj (VS) pro sousměrné vyhled áv ání VS pro sousměrné vyhled áv ání A = (Q, T, g, h, q0, F) Q konečn á množina stavů. T konečn á vstupní abeceda. g: Q × T Q {::: fail} dopředn á přechodov á fce. h: (Q - q0) Q zpětn á přechodov á fce. q0 počáteční stav. F množina koncových stavů. hloubka stavu q: d(q) N0 je délka nejkratší dopředné posloupnosti přechodů z q0 do q. Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Vyhledávací stroj (pokr.) Vlastnosti g, h: g(q0, a) = ::: fail pro a T (neprov ádí se ž ádný zpětný přechod v počátečním stavu). 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. Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Konfigurace, přechod VS konfigurace VS (q, w), q Q, w T dosud neprohledan á část textu. poč áteční konfigurace VS (q0, w), w je celý prohled ávaný text. akceptující konfigurace VS (q, w), q F, w je dosud neprohled ávaný text, nalezený vzorek je bezprostředně před w. přechod VS: relace (Q × T) × (Q × T): g(q, a) = p, pak (q, aw) (p, w) dopředný přechod pro w T. h(q) = p, pak (q, w) (p, w) zpětný přechod pro w T. Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Osnova (Týden třetí) ü Vyhled áv ání pomocí VS ý Algoritmy pro sousměrné vyhled áv ání n vzorků. (AC, NKA DKA). Algoritmy pro sousměrné vyhled áv ání nekonečné množiny vzorků. Regulární výrazy. Přím á konstrukce (N)KA pro daný RV. Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje 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 však g(q, a) = ::: fail, provede se zpětný přechod bez čtení vstupního symbolu. = O(T) (měříme počet přechodů VS). Petr Sojka PV030 Textové informační systémy Ý (K)MP Vyhled ávací stroj Konstrukce KMP stroje Konstrukce VS pro KMP pro vzorek v1v2 . . . vV ü počáteční stav q0. ý g(q, vj+1) = q, kde q odpovíd á předponě v1v2 . . . vjvj+1. pro q0 definujme g(q0, a) = q0 pro a, pro kter á g(q0, a) nebylo definov áno v předchozím kroku. g(q, a) = ::: fail pro q a a, pro kter á g(q, a) nebylo definov áno v předchozích krocích. stav odpovídající úplnému vzorku je koncový. zpětnou přechodovou fci h definuje na straně 50 uvedený algoritmus. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Část V Vyhledáv ání (konečné) množiny vzorků Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Vyhledáv ání množiny vzorků VS pro sousměrné vyhled áv ání množiny vzorků p = {v1, v2, . . . , vP } Místo opakovaného proch ázení textu pro každý vzorek jen ,,jeden" průchod (KA). Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Obecný algoritmus VS var text: array[1..T] of char; i: integer; nalezen: boolean; state: tstate; g: array[1..maxstate,1..maxsymbol] of tstate; h: array[1..maxstate] of tstate; F: set of tstate; nalezen:=false; state:=q0; i:=0; while (i<=T) and not nalezen do begin i:=i+1; while g[state,text[i]]=fail do state:=h[state]; state:=g[state,text[i]]; nalezen:=state in F end Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Obecný algoritmus VS (pokr.) Konstrukce přechodových funkcí h, g? Jak pro P vzorků? Hlavní myšlenka? Aho, Corasickov á, 1975 (AC vyhled ávací stroj). Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Algoritmus Aho a Corasickové I Konstrukce g pro AC VS pro množinu vzorků p = {v1, v2, . . . , vP } ü Počáteční stav q0. ý g(q, bj+1) = q, kde q odpovíd á předponě b1b2 . . . bj+1 vzorku vi, pro i {1, . . . , P}. Pro q0 definujme g(q0, a) = q0 pro a, pro kter á g(q0, a) nebylo definov áno v předchozím kroku. g(q, a) = ::: fail pro q a a, pro kter á g(q, a) nebylo definov áno v předchozích krocích. Stav odpovídající úplnému vzorku je koncový. Příklad: p ={he, she, her} nad T ={h, e, r, s, x}, kde x je cokoliv jiného než {h, e, r, s}. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Chybov á fce h (AC II) Konstrukce h pro AC VS pro množinu vzorků p = {v1, v2, . . . , vP } Nejprve definujeme chybovou funkci f induktivně vzhledem k hloubce stavů takto: ü Pro q hloubky 1 bude f(q) = q0. ý Předpokládejme, že f je definov ána pro všechny stavy hloubky d a menší. Bud' qD stav hloubky d a g(qD, a) = q. Pak f(q) spočít áme takto: q := f(qD); while g(q, a) = ::: fail do q := f(q); f(q) := g(q, a). Cyklus skončí, nebot' g(q0, a) = ::: fail. Jestliže stavy q, r reprezentují předpony u, v nějakých vzorků z p, pak f(q) = r v je nejdelší vlastní přípona u. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Chybov á fce h (AC III) 1 2 r 4 5 6 q 8 a a b f(qD) f(f(qD)) f(q ) qD q Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Konstrukce h pro AC VS pro množinu vzorků p = {v1 , v2 , . . . , vP } (pokračov ání) Za zpětnou přechodovou fci h můžeme vzít f, mohou se však prov ádět zbytečné zpětné přechody. Funkci h definujeme induktivně vzhledem k hloubce stavů takto: Pro stav q hloubky 1 bude h(q) = q0. Předpokládejme, že h je definována pro všechny stavy hloubky d a menší. Necht' hloubka q je d + 1. Jestliže množina znaků, pro které je ve stavu f(q) hodnota funkce g jiná hodnota než ::: fail, je podmnožinou množiny znaků, pro které je hodnota funkce g ve stavu q jiná než ::: fail, pak h(q) := h(f(q)), jinak h(q) := f(q). Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Konstrukce h pro AC VS (pokr.) 1 2 3 4 5 6 a a f(q) h(q) q Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Vyhledávací konečné automaty Deterministický konečný automat (DKA) M=(K,T,,q0,F) ü K je konečn á množina vnitřních stavů. ý T je konečn á vstupní abeceda. je zobrazení z K × T do K. q0 K je počáteční stav. F K je množina koncových stavů. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Vyhledávací konečné automaty ü Úplně určený automat jestliže definov ána pro každou dvojici (q, a) K × T, jinak neúplně určený automat. ý Konfigurace M je dvojice (q, w), kde q K, w T je dosud neprohledan á část textu. Poč áteční konfigurace M je (q0, w), kde w je celý prohled ávaný text. Koncov á konfigurace M je (q, w), kde q F a w T. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Vyhledáv ání pomocí KA M Při přechodu je přečten jeden vstupní symbol a stroj přech ází do n ásledujícího stavu p. Přechod M: d án stavem a symbolem na vstupu; relace (K × T) × (K × T); jestliže (q, a) = p, pak (q, aw) (p, w) pro každé w T. k-t á mocnina, tranzitivní resp. tranzitivně-reflexivní uz ávěr relace : k, +, . L(M) = {w T : (q0, w) (q, w) pro nějaké q F, w T} jazyk přijímaný KA M. časov á složitost O(T) (měříme počet přechodů KA M). Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Nedeterministický KA Definice: Nedeterministický konečný automat (NKA) je M = (K, T, , q0, F), kde K, T, q0, F jsou stejné jako u deterministické verze KA, ale : K × T 2K (q, a) je nyní množina stavů. Definice: (K × T) × (K × T) přechod: jestliže p (q, a), pak (q, aw) (p, w) pro w T. Definice: Přijetí řetězce, L(M) analogicky jako u DKA. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Konstrukce VS (DKA) z NKA Věta: Pro každý nedeterministický konečný automat M=(K,T,,q0,F) můžeme sestrojit deterministický konečný automat M=(K,T,,q 0, F) takový, že L(M) = L(M). Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Konstrukce VS (DKA) z NKA (pokr.) Konstruktivní důkaz (algoritmus): Vstup: Nedeterministický KA M = (K, T, , q0, F) Výstup: Deterministický KA ü K={{q0}}, stav {q0} neoznačený. ý Jestliže v K jsou všechny stavy označeny, pokračuj krokem 4. Vybereme z K neoznačený stav q: (q, a) = {(p, a)} pro p q a a T; K = K (q, a) pro a T; označíme q a pokračujeme krokem 2. q 0 = {q0}; F = {q K : q F = }. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Konstrukce g pro VS Konstrukce g pro VS pro množinu vzorků p = {v1, v2, . . . , vP } ü Vytvoříme NKA M: Počáteční stav q0. Pro a T definujme g(q0, a) = q0. Pro i {1, . . . , P} definujme g(q, bj+1) = q, kde q odpovíd á předponě b1b2 . . . bj+1 vzorku vi. Stav odpovídající úplnému vzorku je koncový. ý a jemu odpovídající DKA M s g. Petr Sojka PV030 Textové informační systémy Ý Vyhled áv ání n vzorků Algoritmus Aho a Corasickové Osnova (Týden čtvrtý) ü Shrnutí předchozí předn ášky. ý Regulární výrazy, hodnota RV, vlastnosti. Derivace regulárních výrazů. Přím á konstrukce DKA ekvivalentního konečného automatu pro daný RV pomocí derivace RV. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Část VI Vyhledáv ání nekonečné množiny vzorků Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Regulární výraz (RV) Definice: Regul ární výraz V nad abecedou A: ü , 0 jsou RV a pro a A je a RV. ý Jestliže x, y RV nad A, pak: (x + y) je RV (sjednocení); (x.y) je RV (zřetězení); (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. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Hodnota RV ü h(0) = , h() = {}, h(a) = {a} ý h(x + y) = h(x) h(y) h(x.y) = h(x).h(y) h(x) = (h(x)) h(x) = x x.x x.x.x . . . Hodnotou RV je regulární jazyk (RJ). Každý RJ lze reprezentovat RV. Pro RV V KA M: h(V) = L(M). Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Axiomatizace RV (Salomaa 1966) A1: 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: .x = x jednotkový prvek pro zřetězení A8: 0.x = 0 nulový prvek pro zřetězení A9: x + 0 = x jednotkový prvek pro sjednocení A10: x = + x x A11: x = ( + x) Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Podobnost regulárních výrazů Věta: Tato axiomatizace RV je úpln á a bezesporn á. Definice: Regulární výrazy nazveme podobné, jestliže se mezi sebou dají navz ájem převést pomocí axiomů A1 až A11. Věta: Podobné regulární výrazy mají stejnou hodnotu. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Délka regulárního výrazu Definice: Délka d(V) regul árního výrazu V: ü Je-li V tvořen jedním symbolem, pak d(V) = 1. ý d(V1 + V2) = d(V1) + d(V2) + 1. d(V1.V2) = d(V1) + d(V2) + 1. d(V) = d(V) + 1. d((V)) = d(V) + 2. Pozn.: Délka odpovíd á syntaxi regulárního výrazu. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Konstrukce NKA pro daný RV Definice: Zobecněný NKA dovoluje -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: Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Konstrukce NKA pro daný RV (důkaz) ü V = a aq0 ý V = V 1 M1 automat pro V1 (h(V1) = L(M1)) M1 Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Konstrukce NKA pro daný RV (důkaz pokr.) V = V1 V2 M2M1 V = V1 + V2 M1, M2 automaty pro V1, V2 (h(V1) = L(M1), h(V2) = L(M2)) M1 M2 Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Konstrukce NKA pro daný RV (pokr.) Z každého stavu vych ázejí maxim álně 2 hrany. Z koncových stavů nevych ázejí ž ádné hrany. Počet stavů M 2 d(V). Simulace chov ání automatu M v čase O(d(V)T) a paměti O(d(V)). Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Simulace NKA Pro n ásledující metody simulace NKA je třeba odstranit -přechody. Toto můžeme provést zn ámým postupem: 1) q q a b b b a a q q 2) q q q q Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Simulace NKA (pokr.) Stav reprezentujeme booleovským vektorem a současně budeme proch ázet všemi možnými cestami. Dvě možnosti: Obecný program s použitím tabulky přechodů. Implementace automatu ve formě (generovaného) programu pro konkrétní automat. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Přím á konstrukce (N)KA pro daný RV Necht' V je RV nad abecedou T. Pak KA M = (K, T, , q0, F) takový, že h(V) = L(M) sestrojíme takto: ü Očíslujeme všechny výskyty symbolů z T ve výrazu V různými přirozenými čísly. Dostaneme V . ý Množina počátečních symbolů Z = {xi : symbolem xi může začínat nějaký řetězec z h(V ), xi = }. Množina sousedů P = {xiyj : symboly xi = = yj mohou být vedle sebe v nějakém řetězci z h(V )}. Množina koncových symbolů F = {xi : symbolem xi = může končit nějaké slovo z h(V )}. Množina stavů K = {q0} Z {yj : xiyj P}. Přechodová funkce : (q0, x) obsahuje xi pro xi Z vzniklá očíslováním x. (xi, y) obsahuje yj pro xiyj P takové, že yj vzniklo očíslováním y. F je množina koncových stavů, stav odpovidající V je q0. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Přím á konstrukce (N)KA pro daný RV Příklad 1: R = aba + ac + bab. Příklad 2: R = ab + ac + ba. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Derivace regulárního výrazu Definice: Derivace dV dx regul árního výrazu V podle řetězce x T: ü dV d = V. ý Pro a T platí: d da = 0 db da = 0 jestliže a = b jestliže a = b d(U + V) da = dU da + dV da d(U.V) da = dU da V + dV da jestliže h(U) dU da V jinak d(V ) da = dV da V Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Derivace regulárního výrazu (pokr.) Pro x = a1a2 . . . an, ai T platí dV dx = d dan d dan-1 d da2 dV da1 . Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Vlastnosti regulárních výrazů Příklad: Derivujte V = fi + fi + fifi podle i a f. Příklad: Derivujte (osle)cno podle o, s, l, c a osle. Věta: h dV dx = {y : xy h(V)}. Příklad: Dokažte výše uvedenou větu. N ávod: strukturní indukcí vzhledem k V a x. Definice: Regul ární výrazy x, y jsou podobné jestliže jeden z nich může být transformov án na druhý pomocí axiomů axiomatické teorie RV (Salomaa). Příklad: Existuje RV podobný V = fi + fi + fifi délek 7, 15? Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Přím á konstrukce DKA pro daný RV (pomocí derivací RV) Brzozowski (1964, Journal of the ACM) Vstup: RV V nad T. Výstup: KA M = (K, T, , q0, F) takový, že h(V) = L(M). 1 Položme Q = {V}, Q0 = {V}, i := 1. 2 Vytvořme derivace všech výrazů z Qi-1 podle všech symbolů z T. Do Qi vložíme všechny výrazy vzniklé derivací výrazů z Qi-1, které nejsou podobné výrazům z Q. 3 Jestliže Qi = , přid áme Qi do Q, položíme i := i + 1 a přejdeme na krok 2. 4 Pro dU dx Q a a T položíme dU dx , a = dU dx , v případě, že výraz dU dx je podobný výrazu dU d xa . (Přitom dU dx Q.) 5 Množina F = dU dx Q : h dU dx . Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Příklad: RV= R = (0 + 1)1. Q = Q0 = {(0 + 1)1}, i = 1 Q1 = {dR d0 = R, dR 1 } = {(0 + 1)1 + } Q2 = {(0+1)1+ d0 = R, (0+1)1+ d1 = (0 + 1)1 + } = Příklad: RV= (10)(00)1. Více viz Watson, B. W.: A taxonomy of finite automata construction algorithms, Computing Science Note 93/43, Eindhoven University of Technology, The Netherlands, 1993. citeseer.ist.psu.edu/watson94taxonomy.html Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Osnova (Týden pátý) ü Derivace regulárních výrazů pozičním vektorem. ý Protisměrné vyhled áv ání (BMH, CW, BUC). Nepřesné (proximitní) vyhled áv ání: metriky. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Derivace RV pozičním vektorem I Definice: Poziční vektor je množina čísel, které odpovídají pozicím takových symbolů abecedy, které se mohou vyskytnout na začátku zbytku řetězu, který je součástí hodnoty daného RV. Příklad: Mějme regulární výraz: a . b . c (1) K označení pozice budeme používat zobáček . Na začátku bude tedy výraz (1) označen takto: a . b . c (2) Derivací označeného regulárního výrazu dostaneme nově označený regulární výraz. Základní pravidlo pro derivaci je toto: 1 Je-li označen operand, podle kterého se derivuje, pak se označí místa následující za tímto operandem. Jeho označení se ruší. To znamená, že derivací výrazu (2) podle operandu a dostaneme: a . b . c (3a) Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Derivace RV pozičním vektorem II 2 Protože je označena konstrukce, která generuje také prázdný řetězec, označíme také konstrukci následující: a . b . c (3b) Nyní derivací podle operandu b výrazu (3b) dostaneme: a . b . c (4a) 3 Protože je označena konstrukce následující za konstrukcí v iteraci, musí se označit i předchozí konstrukce. a . b . c (4b) Derivací výrazu (4b) podle operandu c dostaneme: a . b . c (5) Takto označený regulární výraz odpovídá prázdnému regulárnímu výrazu . Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Derivace RV pozičním vektorem III Ke každé syntaktické konstrukci se vytvoří seznam počátečních pozic na začátcích členů. Je-li symbol v konstrukci roven symbolu, podle kterého se provádí derivace, a je-li na označené pozici, pak se označení posouvá před následující pozici. Je-li za konstrukcí operátor iterace a označení je na konci konstrukce, pak se do výsledného seznamu připojí také seznam počátečních pozic náležející této konstrukci. Je-li označení před nějakou konstrukcí, pak se do výsledného seznamu připojí seznam počátečních pozic této konstrukce. Je-li označení před konstrukcí, která generuje také prázdný řetěz, pak se do výsledného seznamu připojí také seznam počátečních pozic konstrukce následující. Má-li se označit konstrukce v z ávorce, pak je třeba označit začátky všech členů v z ávorce. Petr Sojka PV030 Textové informační systémy Ý Sousměrné metody Derivace regul árního výrazu Vlastnosti regul árních výrazů Derivace RV pozičním vektorem: příklad Příklad: a.b.c, derivace podle a, b, c. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku Část VII Protisměrné vyhledáv ání Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku Protisměrné vyhledáv ání Protisměrné vyhled áv ání ­ princip. Může být směr podstatný? V jakých případech? 1 vzorek ­ Boyer-Moore (BM, 1977), Boyer-Moore-Horspool (BMH, 1980), Boyer-Moore-Horspool-Sunday (BMHS, 1990). n vzorků ­ Commentz-Walterov á (CW, 1979). nekonečn á množina vzorků: reverzovaný regulární výraz ­ Bucziłowski (BUC). Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku Boyer-Moore-Horspool algoritmus 1: var: TEXT: array[1..T] of char; 2: VZOREK: array[1..V] of char; I,J: integer; NALEZEN: boolean; 3: NALEZEN := false; I := V; 4: while (I T) and not NALEZEN do 5: J := 0; 6: while (J < V) and (VZOREK[V - J] = TEXT[I - J]) do 7: J := J + 1; 8: end while 9: NALEZEN := (J = V); 10: 11: if not NALEZEN then 12: I := I + SHIFT(TEXT[I - J], J) 13: end if 14: end while SHIFT(A,J) = if A se nevyskytuje v ještě nesrovnalé části vzorku then V - J else nejmenší 0 K < V takové, že VZOREK[V - (J + K)] = A; Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku Kdy rychlejší než KMP? Kdy O(T/V)?Složitost O(T + V) Příklad: Hled ání vzorku BANANA v textu I-WANT-TO-FLAVOR-NATURAL-BANANAS. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku CW algoritmus Idea: AC + protisměrnost (BM) [1979] const LMIN=/délka nejkratšího vzorku/ var TEXT: array [1..T] of char; I, J: integer; NALEZEN: boolean; STATE: TSTATE; g: array [1..MAXSTATE,1..MAXSYMBOL] of TSTATE; F: set of TSTATE; begin NALEZEN:=FALSE; STATE:=q0; I:=LMIN; J:=0; while (I<=T) & not (NALEZEN) do begin if g[STATE, TEXT[I-J]]=fail then begin I:=I+SHIFT[STATE, TEXT[I-J]]; STATE:=q0; J:=0; end else begin STATE:=g[STATE, TEXT[I-J]]; J:=J+1 end NALEZEN:=STATE in F end end Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku Konstrukce CW vyhledávacího stroje VSTUP: Množina vzorků P = {v1, v2, . . . , vk} V ÝSTUP: CW vyhled ávací stroj METODA: Sestrojíme funkci g a zavedeme ohodnocení w jednotlivých stavů: 1 Počáteční stav q0; w(q0) = . 2 Každý stav vyhled ávacího stroje odpovíd á příponě bmbm+1 . . . bn nějakého vzorku vi z množiny P. Definujeme g(q, a) = q, kde q odpovíd á příponě abmbm+1 . . . bn vzorku vi: w(q) = bn . . . bm+1bm; w(q) = w(q)a. 3 g(q, a) = ::: fail pro všechna q a a, pro kter á g(q, a) nebylo definov áno v kroku 2. 4 Každý stav, který odpovíd á úplnému vzorku, bude koncový. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku CW ­ funkce shift Definice: shift[STATE, TEXT[I - J]] = min {A, shift2(STATE)}, kde A = max {shift1(STATE), char(TEXT[I - J]) - J - 1}. Jednotlivé funkce jsou definov ány takto: 1 char(a) je definována pro všechny symboly z abecedy T jako nejmenší hloubka stavu, do kterého se v CW vyhledávacím stroji přechází při symbolu a. Pokud symbol a není v ž ádném vzorku, je char(a) = LMIN + 1, kde LMIN je délka nejkratšího vzorku. Formálně: char(a) = min LMIN + 1, min{d(q)| w(q) = xa, x T } . 2 Funkce shift1(q0) = 1, pro ostatní stavy má hodnotu shift1(q) = min {LMIN, A}, kde A = min{k| k = d(q ) - d(q), kde w(q) je vlastní příponou w(q ) a stav q má větší hloubku než q}. 3 Funkce shift2(q0) = LMIN, pro ostatní stavy má hodnotu shift2(q) = min{A, B}, kde A = min{k| k = d(q ) - d(q), kde w(q) je vlastní příponou w(q ) a q je koncový stav}, B = shift2(q )| q je předchůdce q. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhled áv ání jednoho vzorku CW ­ funkce shift Příklad: P = {cacbaa, aba, acb, acbab, ccbab}. LMIN = 3, a b c X char 1 1 2 4 w(q) shift1 shift2 1 3 a 1 2 b 1 3 aa 3 2 ab 1 2 bc 2 3 ba 1 1 aab 3 2 aba 3 2 bca 2 2 bab 3 1 aabc 3 2 babc 3 1 aabca 3 2 babca 3 1 babcc 3 1 aabcac 3 2 Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Část VIII Vyhledáv ání nekonečné množiny vzorků Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Protisměrné vyhl. nek. mn. vzorků Definice: Reverzovaný regul ární výraz vznikne reverzí všech zřetězení ve výrazu. Příklad: Reverzovaný RV k V = bc(a + abc) je VR = (a + cba)cb: 4 b 3 + c m a 2 XXXXXXy c 5 b 1 Q Qkc ) a 0 Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Protisměrné vyhl. nek. mn. vzorků (pokr.) Bucziłowski: V vyhled áv áme tak, že vytvoříme VR a pro každý stav a nedefinovaný přechod z něho se určí shift[STAV, SYMBOL] analogicky jako u algoritmu CW: a b c X 0 1 3 1 1 1 2 (3!) 2 1 3 1 1 1 4 1 1 1 1 5 1 1 1 Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Cvičení Příklad : Mějme množinu vzorků P= {tis, ti, iti}: Vytvořte NKA pro vyhled áv ání P. 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. Srovnejte s výsledkem vyhled ávacího stroje AC. Řešte úlohu také algoritmem přímé konstrukce DKA (derivov áním) a diskutujte, zda výsledkem jsou izomorfní automaty. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Dvoucestný automat se skokem I Definice: 2DKAS je M = (Q, , , q0, k, , F), kde Q množina stavů vstupní abeceda zobr. Q × Q × {-1, 1, . . . , k} q0 Q počáteční stav k N max. délka skoku Q značka skoku F Q množina koncových stavů Definice: Konfigurace 2DKAS je řetězec z Q . Definice: Množinu konfigurací 2DKAS M značíme K(M). Příklad: a1a2 . . . ai-1 q ai . . . aj-1 aj . . . an K(M) : q čtecí hlava značka skoku Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Dvoucestný automat se skokem II Definice: Přechod 2DKAS je relace K(M) × K(M) taková, že a1 . . . ai-1ai q ai+1 . . . aj-1 aj . . . an a1 . . . ai-1 q aiai+1 . . . aj-1 aj . . . an pro i > 1, (q, ai+1) = (q , -1) (protisměrné srovnání), a1 . . . ai q ai+1 . . . aj-1 aj . . . an a1 . . . aiai+1 . . . at-1 q at . . . an pro (q, ai+1) = (q , m), m 1, t = min{j + m, n + 1} (protisměrný skok), a1 . . . aj q aj+1 . . . ai-1 ai . . . an a1 . . . ajaj+1 . . . at-1 q at . . . an pro (q, ai) = (q , m), m 1, t = min{i + m, n + 1} (sousměrný skok), . a1 . . . aj-1 q aj . . . ai-1 aiai+1 . . . an a1 . . . aj-1 q aj . . . ai-1ai ai+1 . . . an pro i > 1, (q, ai) = (q , 1) (sousměrné srovnání). (Sousměrná pravidla jsou pro sousměrné stroje, protisměrná pro protisměrné). Definice: k , analogicky jak u VS. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Hierarchie vyhledávacích strojů Definice: Jazyk přijímaný dvoucestným automatem M = (Q, , , q0, k, , F) je množina L(M) = {w : q0 T wfxw , kde f F, w , x }. Věta: L(M) pro 2DKAS M je regulární. Příklad: Zformulujte protisměrné vyhled áv ání vzorku BANANA v textu I-WANT-TO-FLAVOUR-NATURAL-BANANAS pomocí BM jako 2DKAS a vyhled áv ání trasujte jako posloupnost konfigurací 2DKAS. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Cvičení Mějme regulární výraz R = 1(0 + 102) nad abecedou A = {0, 1, 2}. Sestrojte DKA pro protisměrné vyhled áv ání R (Bucziłowski) a spočtěte chybovou funkci. Nakreslete přechodový diagram tohoto automatu včetně vizualizace chybové funkce. Zapište výsledný automat jako 2DKAS a trasujte vyhled áv ání v textu 11201012102. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Shrnutí přesného vyhledáv ání 2DKAS DKA BUC AC CW k KMP BM 1 směr -- # vzorků. Petr Sojka PV030 Textové informační systémy Ý Protisměrné vyhl. nek. mn. vzorků Zobecnění VS Hierarchie vyhled ávacích strojů Osnova (Týden šestý) ü 6D klasifikace vyhled ávacích problémů. ý Příklady vytv áření VS. 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. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů Část IX Proximitní vyhledáv ání Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů Metrika (pro proximitní vyhledáv ání) Jak měřit (metrika) podobnost řetězců? Definice: Funkci d : S × S R nazvete metrika jestliže platí 1 d(x, y) 0 2 d(x, x) = 0 3 d(x, y) = d(y, x) (symetrie) 4 d(x, y) = 0 x = y (pravidlo nerozeznatelných bodů) 5 d(x, y) + d(y, z) d(x, z) (trojúhelníkov á nerovnost) Hodnoty funkce d (distance) nazýv áme vzd álenost. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů Metriky pro proximitní vyhledáv ání Definice: Mějme řetězce X a Y nad abecedou . Minim ální počet editačních operací pro přeměnu X na Y je Hammingova vzd álenost, R-vzd álenost, pokud povolíme jen operaci Replace, Levenshteinova vzd álenost, DIR-vzd álenost, pokud povolíme operace Delete, Insert a Replace, Zobecněn á Levenshteinova vzd álenost, DIRT-vzd álenost, pokud povolíme operace Delete, Insert, Replace a Transpose. Transpozice je 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. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů Proximitní vyhledáv ání ­ příklady Příklad: Najděte takový příklad řetězců X a Y, ž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 a Y, ž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 a Y délky 2n, n N, že R(X, Y) = n a a) DIR(X, Y) = 2; b) DIRT(X, Y) = n 2 Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Klasifikace vyhledávacích problémů Definice: Necht' T = t1t2 . . . tn a vzorek P = p1p2 . . . pm. Možno se například pt át: 1 je P podřetěz T? 2 je P podsekvence z T? 3 je podřetěz či podsekvence P v T? 4 je P v T takový, že D(P, X) k pro k < m, kde X = ti . . . tj je částí T (D je R, DIR či DIRT)? 5 je řetěz P obsahující don't care symbol (*) v T? 6 je sekvence vzorků P 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. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO 6D klasifikace vyhledávacích problémů [MEH] ([MAR]) 2 3 6 5 1 4 seQuence Subpattern One Sequence of Don't care Care Full pattern One Finite Infinite Exact DIR-matching DIRT-matchingR-matching String Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO 6D klasifikace vyhledávacích problémů (pokr.) Dimenze 1 2 3 4 5 6 S F O E C O Q S F R D S I D G Celkem 2 × 2 × 3 × 4 × 2 × 2 = 192 vyhled ávacích problémů rozklasifikovaný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. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Příklady vytv áření VS Příklad: Necht' P = p1p2p3 . . . pm, m = 4, A je jakýkoliv znak ze . NKA pro SFOECO: 0 1 p1 A 2 p2 3 p3 4 p4 Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Hledání sekvencí znaků Příklad: NKA pro QFOECO (seQuence): 0 1 p1 A 2 p2 3 p3 4 p4 p2 p3 p4 p je jakýkoliv znak ze kromě p. Automat m á m + 1 stavů pro vzorek délky m. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Hledání podřetězce: NKA pro SSOECO Definice: Tento automat se nazýv á poč áteční -treelis a m á (m + 1) + m + (m - 1) + + 2 = m(m+3) 2 stavů. p1 A p2 p3 p4 p2 p3 p4 p3 p4 p4 " " " Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Hledání podsekvence Příklad: NKA pro QSOECO je podobný, jen přid áme cykly pro nesrovnalé znaky a 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 á -treelis. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Proximitní vyhledáv ání SFORCO Příklad: SFORCO pro Hammingovu (R) vzd álenost, k 3: Počet pater odpovíd á vzd álenosti. p1 A p2 p3 p4 p2 p3 p4 p3 p4 p4 p2p1 p2 p3 p3 p3 p4 p4 p4 Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Proximitní vyhledáv ání SFORCO Definice: Tento automat se nazýv á R-treelis, a m á (m + 1) + m + (m - 1) + + (m - k + 1) = (k + 1)(m + 1 - k 2 ) stavů. Číslo patra koncového stavu odpovíd á vzd álenosti nalezeného řetězce od vzoru. Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Proximitní vyhledáv ání SFODCO pro DIR-vzdálenost Příklad: SFOD3CO pro Levenshteinovu (DIR) vzd álenost, k 3: další ,,D-hrany" a ,,I-hrany. p1 A p2 p3 p4 p2 p3 p4 p3 p4 p4 p2 p1 p2 p3 p3 p3 p4 p4 p4 p2 p3 p3 p4 p4 p4 " " " " " " " " " Petr Sojka PV030 Textové informační systémy Ý Nepřesné vyhled áv ání: metriky Klasifikace vyhled ávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO SFOGCO Pro DIRT-vzd álenost ještě přid á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 Pojera pro diskutované vyhled ávací stroje je ke stažení z webové str ánky předmětu a je také instalov án v B311. Simulace NKA nebo determinizace? Hybridní přístup. Pražský stringologický klub a jeho konference. Petr Sojka PV030 Textové informační systémy Ý Část X Indexové metody Petr Sojka PV030 Textové informační systémy Ý Vyhledáv ání s předzpracov áním textu Velké množství textů? Předzpracov ání textu! index, indexové metody, indexový soubor, indexsekvenční soubor hierarchické členění textu, značkov ání textu, hypertext ot ázky uložení seznamu slov (lexikon) a seznamu výskytů (hitů), jejich aktualizace Petr Sojka PV030 Textové informační systémy Ý Vyhledáv ání s předzpracov áním textu granularita položek indexu: dokument ­ odstavec ­ věta ­ slovo slovo1 slovo2 slovo3 slovo4 dok1 1 1 0 1 dok2 0 1 1 1 dok3 1 0 1 1 invertovaný soubor, transpozice dok1 dok2 dok3 slovo1 1 0 1 slovo2 1 1 0 slovo3 0 1 1 slovo4 1 1 1 Petr Sojka PV030 Textové informační systémy Ý Vyhledáv ání v indexu 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, V délka vzorku O(V × log2(n)) Vyhled áv ání k slov, vzorek p = v1, . . . , vk k n opakované bin ární vyhled áv ání s průměrn á délka vzorku, složitost? O(s × k × log2 n) Pokud k a i srovnatelné: metoda dvojitého slovníku. Hašov ání. Rychlost O(n) ani O(log n) však obvykle nedostačuje, je třeba O(1). Petr Sojka PV030 Textové informační systémy Ý Osnova (Týden sedmý) Písemka. Způsoby implementace indexu. Exkurs do počítačové lingvistiky. Korpusov á lingvistika jako příklad TIS. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů I Pro implementaci indexu je klíčov á volba vhodných datových struktur a algoritmů. Použití invertovaného souboru: slovo1 1 0 1 slovo2 1 1 0 slovo3 0 1 1 slovo4 1 1 1 Použití seznamu dokumentů: slovo1 1, 3 slovo2 1, 2 slovo3 2, 3 slovo4 1, 2, 3 Souřadnicový systém s ukazateli m á 2 části: slovník s ukazateli do seznamu dokumentů a zřetězený seznam ukazatelů na dokumenty. Petr Sojka PV030 Textové informační systémy Ý Metody indexov ání ruční vs. automatické, pros/cons stop-list (slova s gramatickým významem ­ spojky, předložky, . . . ) 1 neřízené 2 řízené (speci ální slovník slov: stanovení indexovacího jazyka) ­ pass-list, tezaurus. synonyma a slova příbuzn á. flektivní jazyky: vytv áření rejstříku s jazykovou podporou ­ lemmatizace. Petr Sojka PV030 Textové informační systémy Ý Analýza textu ­ výběr slov do indexu Frekvence výskytu slov je při identifikaci dokumentu významná. Frekvenční slovník angličtiny: 1 the 69971 0.070 2 of 36411 0.073 3 and 28852 0.086 4 to 26149 0.104 5 a 23237 0.116 6 in 21341 0.128 7 that 10595 0.074 8 is 10099 0.088 9 was 9816 0.088 10 he 9543 0.095 Zipfův z ákon (princip nejmenšího odporu) pořadí × frekvence = konstanta Kumulativní podíl používaných slov KPS = N pořadí=1 frekvencepořadí počet slov textu Pravidlo 20­80: 20 % nejfrekventovanějších slov tvoří 80 % textu [MEL, obr. 4.19]. Petr Sojka PV030 Textové informační systémy Ý Metoda automatického indexov ání Metoda automatického indexování je založená na odvození významnosti slov z jejich frekvencí (cf. Collins-Cobuild dictionary); slova s nízkou a vysokou frekvencí jsou vyloučena: VSTUP: n dokumentů V ÝSTUP: seznam slov vhodných pro vytvoření indexu 1 Spočteme frekvenci FREQik pro každý dokument i 1, n a každé slovo k 1, K [K je počet různých slov ve všech dokumentech]. 2 Spočteme TOTFREQk = n i=1 FREQik. 3 Vytvoříme frekvenční slovník pro slova k 1, K . 4 Stanovíme práh pro vyloučení velmi frekventovaných slov. 5 Stanovíme práh pro vyloučení slov s nízkou frekvencí. 6 Zbývající slova zařadíme do indexu. Problematika určení prahů [MEL, obr. 4.20]. Petr Sojka PV030 Textové informační systémy Ý Vytv áření rejstříku ­ lemmatizace Využití morfologie při vytv áření slovníku kmen/ kořen slova (učit, uč); program ajka (abin), http://nlp.fi.muni.cz/projekty/ajka/ příklady; technika vzorů pro určení kmene. Petr Sojka PV030 Textové informační systémy Ý Vytv áření rejstříku ­ tezaurus Tezaurus ­ slovník, obsahující hierarchické a asociativní vztahy a vztahy ekvivalence mezi jednotlivými termíny. Vazby mezi termíny/lemmaty: synonyna ­ vazba na standardní termín (viz); vazba na příbuzný termín (viz také); RT ­ related term; vazba na obecnější termín; BT ­ broader term; vazba na užší termín; NT ­ narrower term; hyperonyma (auto:dopravní prostředek); hyponyma (pt ák:sojka); meronymum (dveře:z ámek); holonyma (ruka:tělo); antonyma (dobrý:zlý). Pes/Fík, Havel/president Petr Sojka PV030 Textové informační systémy Ý Konstrukce tezauru ručně/ poloautomatizovaně heuristiky konstrukce tezauru: hierarchick á struktura/y tezauru oborové tezaury, sémantika z ávislá kontextově (př. pole, strom v informatice) sdružov ání termínů s podobnou frekvencí vyloučení termínů s vysokou frekvencí šíře aplikací tezauru a lemmatiz átoru: kromě indexov ání spelov ání, z áklad pro grammar checker, plnotextové vyhled áv ání. projekty WORDNET, EUROWORDNET module add wordnet; wn wn faculty -over -simsn -coorn Petr Sojka PV030 Textové informační systémy Ý Hierarchický tezaurus Vytv áření znalostní b áze pro přesné vyhodnocení relevance dokumentů. topic ­ zpracov ání sémantických map termínů. Visual Thesaurus http://www.visualthesaurus.com. Tovek Tools, Verity. Petr Sojka PV030 Textové informační systémy Ý Osnova (Týden osmý) Exkurs do počítačové lingvistiky. Korpusov á lingvistika jako příklad TIS. Vyhled ávací metody s předzpracov ání textu i vzorku (dotazu). Google jako příklad TIS. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Část XI Exkurs do počítačové lingvistiky Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Počítačov á lingvistika vyhled áv ání řetězců ­ slova jsou řetězce písmen. slovotvorba ­ morfologick á analýza. gramatika (CFG, DFG) ­ syntaktick á analýza. význam vět (TIL) ­ sémantick á analýza. kontext ­ pragmatick á analýza. plné porozumění a schopnost komunikace ­ informace. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Corpus Query Procesor základní dotazy ,,Havel"; 45: Český prezident Václav se včera na 89: jak řekl Václav , každý občan 248: 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]"; ,,pravd.*"; ,,pravd.+"; ,,post?el"; posloupnost slov ,,prezident(a|u)" ,,Havl(a|ovi)"; ,,a tak"; ,,prezident"; []* ,,Havel"; ,,prezident" (,,republiky" ,,Vaclav")? ,,Havel"; Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Corpus Query Procesor dotazy na poziční atributy [word = ,,Havel"]; [lemma = ,,prezident"] []* [lemma = ,,Havel"]; ... ženu prezidenta Havla ... [lemma = ,,hn át"] [] [lemma = ,,Havel"]; [word = ,,žen(u|eme)" & lemma !=,,žena"]; I ...or ! . . . not některé další možnosti [lemma = ,,prezident"] []* [lemma = ,,Havel"] within s; ...10, 3 s [lemma = ,,Havel"] within 20 ,,Pravda" a:[word= ,,Žena|Muž|Člověk"] []* [lemma = a.lemma] Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů 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. Rád bych získal informace o prezidentu Václavu Havlovi. a/>HAVEL b/>přesnější dotazy c/... ... Počítač (výpočetní síla) + člověk (inteligence) = hodnotné informace + čas + peníze Cílem všech je přenést co největší část inteligence (času, peněz, ...) na počítač. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Rub a líc relevantního vyhledáv ání informace ide ál ide álů ne Vyhled áv ání pragmatick á analýza kontext ne informací Spravný semantick á analýza význam vět TIL v začátcích Kontrola překlad syntaktick á analýza gramatika CFG, DCG částečně pravopisu morfologick á analýza slovotvorba lemma ano Kontrola Překlad jedn. slova jsou ře- tězce písmen vyhled áv ání řetězců ano Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů 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 atribut1, atribut2, ... ˇ František Novák má rád pivo. ? klíč hodnota František Novák má rád Janu Novotnou ˇ 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 věty 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. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Korpusov á lingvistika Korpus: elektronick á kolekce textů, často indexovan á lingvistickými značkami. Korpus jako textový informační systém: korpusov á lingvistika. BNC, Penn Treebank, DESAM, PNK, . . . ; rozsahy ř ád milionů až miliard pozic (slov), speci ální metody nutné. Korpusové manažery CQP, GCQP, Manatee/Bonito, http://www.fi.muni.cz/~pary/korp/. Vnitřní architektura a implementace korpusu. viz podklady [MAR]. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Co je korpus? Definice: Korpus je rozs áhlý, vnitřně strukturovaný ucelený soubor textů v přirozeném jazyce elektronicky uložený a zpracovatelný. Indi ánské jazyky nemají písmo ­ pro nalezení gramatiky potřeba nejprve sepsat mluvené slovo. 1967 ­ 1. korpus v U. S. A. (Kučera, Francis) 1 000 000 slov. Noam Chomsky ­ odmít á korpusy. Dnes ­ masové rozšíření. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Korpusy na FI WWW str ánka Pavla Rychlého (PARY) odkaz na z ákladní informace. Bonito, Manatee. IMS CORPUS WORKBENCH ­ sada n ástrojů pro efektivní kódov ání, reprezentaci a dotazov ání nad velkými textovými soubory. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů 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 ­ věty, odstavce, nadpis, článek, SGML. LEMMA WORD POS1 POS2 Českého český prezidenta prezident V áclava vaclav Havla havel dnes dnes 107 0 1 2 43 Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Vnitřní architektura korpusu Dva klíčové pojmy interní reprezentace pozičních atributů jsou: Jednotn á reprezentace: položky jsou pro všechny atributy zakódov á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 (stejně jako 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 v jednom kroku. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů 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: 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é 000) 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 0, n ásledující 1 atd. Pro vyhled áv ání řetězce v našem seznamu je 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. . . Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů 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. Druhý je index do tohoto souboru. Tento index vrací pro každý kód položky vstupní bod n áležící výskytu v inverzním souboru. 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ů). Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Implementace indexových systémů Invertovaný soubor ­ indexový soubor s bitovým vektorem. Použití seznamu dokumentů ke každému klíčovému slovu. Souřadnicový systém s ukazateli [MEL, obr. 4.18, strana 46]. Indexace korpusových textů: Finlib http://www.fi.muni.cz/~pary/dis.pdf viz podklady [MAR]. Použití Eliasových kódů pro komprimaci seznamu hitů. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Implementace indexových systémů (pokr.) Efektivní uložení indexu/slovníku [lemmat]: packed trie, Patricia tree, a další stromové struktury. Syntactic neural network (S. M. Lucas: Rapid best-first retrieval from massive dictionaries, Pattern Recognition Letters 17, p. 1507­1512, 1996). Komerční implementace: Verity engine, webové vyhled ávače většinou svůj klíč k úspěchu až na výjimky tají. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Reprezentace slovníku KA I Článek M. Mohri: On Some Applications of Finite-State Automata Theory to Natural Language Processing viz podklady [MAR] Reprezentace slovníku konečným automatem. Nejednoznačnosti, sjednocení minimalizovaných deterministických automatů. Příklad: done,do.V3:PP done,done.A0 Morfologický slovník jako seznam dvojic [slovní tvar, lemma]. Kompaktace uložení datové struktury automatu (Liang, 1983). Kompresní poměr až 1:20 při line árním přístupu (vzhledem k délce slova). Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Reprezentace slovníku KA II Převodník (transducer) pro reprezentaci slovníku. 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,. . . ). 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). 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řirozeného jazyka však obvykle nenast áv á (nejsou zde cykly). Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Reprezentace slovníku KA III Přid ání stavu do převodníku odpovídajícího (w1,w2) bez porušení determiničnosti: nejprve stav pro (w1,), pak s výsledným stavem konečný stav s výstupem w2. Efektivní metoda, rychlá, leč není minim ální; existují minimalizační algoritmy, které vedou na prostorově úsporn á řešení. 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. Další použití i při efektivní indexaci, rozpozn áv ání řeči, atd. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Vyhledávací metody IV. Předzpracov ání textu i vzorku (dotazu): drtiv á většina dnešních TIS. Typy předzpracov ání: statistiky n-gramů (fragmentové indexy). speci ální algoritmy pro zpracov ání indexů (kódov ání, komprese) a vyhodnocení relevance (PageRank u Google). využití metod zpracov ání přírozeného jazyka (morfologie, syntaktick á analýza, sémantické datab áze) a agregace informací z více zdrojů (systémy AnswerBus, START). signaturové metody. Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Relevance Definice: Relevance (odpovědi na dotaz) je míra rozsahu, kterým se vybraný dokument shoduje s požadavky na něj kladenými. Ide ální odpověd' skutečn á odpověd' Definice: Koeficient úplnosti R (recall) R = m n , 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) P = m o , kde o je počet všech vybraných z áznamů dotazem. Chceme docílit maximum R i P, tradeoff. Standardní hodnoty: 80 % pro P, 20 % pro R. Kombinace úplnosti a přesnosti: koeficient Fb = (b2+1)PR b2P+R . (F0 = P, F = R, při F1 = F P a R v áženy stejně). Petr Sojka PV030 Textové informační systémy Ý Implementace indexových systémů Fragmentový index Fragment ybd je v angličtině pouze ve slově molybden. Výhody: pevný slovník fragmentů, odpadají problémy s aktualizací. Nevýhody: z ávislost na jazyce a tématické oblasti, snížen á přesnost vyhled áv ání. Petr Sojka PV030 Textové informační systémy Ý Část XII Kódov ání Petr Sojka PV030 Textové informační systémy Ý Osnova (Týden dev átý) Dokončení anatomie Google. Kódov ání. Entropie, redundance. Univers ální kódov ání celých čísel. Petr Sojka PV030 Textové informační systémy Ý Goooooooooooooogle Příklad anatomie glob álního (hyper)textového informačního systému (www.google.com). 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/1921com1921.htm Několik inovativních konceptů: PageRank, uklád ání lok álního komprimovaného archívu, výpočet relevance z textů hypetextových odkazů, indexace PDF, Google File System, Google Link. . . Anatomie systému. viz podklady [MAR] Petr Sojka PV030 Textové informační systémy Ý Google: Relevance Klíčové je určení relevance. Využití značek textu a typografie webu pro výpočet relevance termů dokumentu. Využití textu hypertextových odkazů na dokument odkazujících. Petr Sojka PV030 Textové informační systémy Ý Google: PageRank 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). Necht' na str ánku A ukazují str ánky, T1, . . . , Tn (citace), a necht' 0 < d < 1. Necht' C(A) je počet odkazů na str ánce A, celkový počet str ánek je m. PageRank PR(A) = (1 - d) m + d PR(T1) C(T1) + . . . PR(Tn) C(Tn) PageRank se d á spočítat jednoduchým iterativním algoritmem (pro desítky milionů str ánek za hodiny na běžném PC). PageRank je pravděpodobnostní rozdělení nad webovými str ánkami. Motivace s n áhodným surfařem, tlumicí faktor d, obvykle kolem 0,85. PageRank není jediným faktorem, ale součinitel více faktorů. Petr Sojka PV030 Textové informační systémy Ý Datové struktury Google Uložení signatur souborů Uložení lexikonu Uložení seznamu hitů Google File System Petr Sojka PV030 Textové informační systémy Ý 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 je pr ázdn á posloupnost symbolů. Množinu všech nepr ázdných slov nad A značíme A+. Definice: Kód K je trojice (S, C, f), kde S je konečn á množina zdrojových jednotek, C je konečn á množina kódových jednotek, f : S C+ je injektivní zobrazení. f lze rozšířit na S+ C+: F(S1S2 . . . Sk) = f(S1)f(S2) . . . f(Sk). C+ se někdy nazýv á kód. Petr Sojka PV030 Textové informační systémy Ý Základní vlastnosti kódů Definice: x C+ je jednoznačně dekódovatelný vzhledem k f, jestliže existuje maxim álně jedna posloupnost y S+ takov á, že f(y) = x. Definice: Kód K = (S, C, f) je jednoznačně dekódovatelný jestliže jsou 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 á sufixový, 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ě dekódovatelný. Petr Sojka PV030 Textové informační systémy Ý 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 = (S, C, f) nazveme bin ární, jestliže |C| = 2. Petr Sojka PV030 Textové informační systémy Ý Komprese a dekomprese Definice: Komprese (kódov ání), dekomprese (dekódov ání): - Komprese (kódov ání) - původní data komprimovan á data - Dekomprese (dekódov ání) - Definice: Kompresní poměr je poměr délky komprimovaných dat a 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. Petr Sojka PV030 Textové informační systémy Ý Entropie a redundance I Necht' 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) E(Y) = yY yp(y). Necht' S = {x1, x2, . . . , xn} množina zdrojových jednotek a necht' pravděpodobnost výskytu jednotky xi v informačním zdroji S je pi pro i = 1, . . . , n, n N. Definice: Entropie informačního obsahu jednotky xi (míra množství informace resp. neurčitosti) je H(xi) = Hi = - log2 pi bitů. Zdrojov á jednotka s větší pravděpodobností nese méně informace. Petr Sojka PV030 Textové informační systémy Ý Entropie a redundance II Definice: Entropie informačního zdroje S je H(S) = - n i=1 pi log2 pi bitů. Platí, že H(S) = yY p(y) log 1 p(y) = E log 1 p(Y) . Definice: Entropie zdrojové zpr ávy X = xi1 xi2 . . . xik S+ informačního zdroje S je H(X, S) = H(X) = k j=1 Hi = - k j=1 log2 pij bitů. Definice: Délka l(X) zakódované zpr ávy X l(X) = k j=1 |f(xij )| = k j=1 dij bitů. Věta: l(X) H(X, S). Petr Sojka PV030 Textové informační systémy Ý Entropie a redundance III Axiomatické zavedení entropie viz podklady [MAR], detaily odvození viz ftp://www.math.muni.cz/pub/math/people/Paseka/lectures/kodovan Definice: R(X) = l(X) - H(X) = k j=1 (dij + log2 pij ) je redundance kódu K pro zpr ávu X. Definice: Průměrn á délka kódového slova kódu K je AL(K) = n i=1 pidi bitů. Definice: Průměrn á entropie zdroje S je AE(S) = n i=1 piHi = - n i=1 pi log2 pi bitů. Definice: Průměrn á redundance kódu K je AR(K) = AL(K) - AE(S) = n i=1 pi(di + log2 pi) bitů. Petr Sojka PV030 Textové informační systémy Ý Entropie a redundance IV Definice: Kód je optim ální, když m á minim ální redundanci. Definice: Kód je asymptoticky optim ální, pokud pro dané rozložení pravděpodobností se poměr AL(K)/AE(S) blíží k 1, když se entropie blíží . Definice: Kód K je universální, jestliže existují c1, c2 R tak, že průměrn á délka kódového slova AL(K) c1 × AE + c2. Věta: Univers ální kód je asymptoticky optim ální, jestliže c1 = 1. Petr Sojka PV030 Textové informační systémy Ý Univers ální kódov ání celých čísel Definice: Fibonacciho posloupnost ř ádu m Fn = Fn-m + Fn-m+1 + . . . + Fn-1 pro n 1. Příklad: F ř ádu 2: F-1 = 0,, F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, F5 = 8,. . . Příklad: F ř ádu 3: F-2 = 0, F-1 = 0, F0 = 1, F1 = 1, F2 = 2, F3 = 4, F4 = 7, F5 = 13,. . . Příklad: F ř ádu 4: F-3 = 0, F-2 = 0, F-1 = 0, F0 = 1, F1 = 1, F2 = 2, F3 = 4, F4 = 8, F5 = 15,. . . Definice: Fibonacciho reprezentace R(N) = k i=1 diFi, kde di {0, 1}, dk = 1 Věta: Fibonacciho reprezentace není jednoznačn á, existuje však takov á, že v posloupnosti di je nejvýše m - 1 po sobě jdoucích jedniček. Petr Sojka PV030 Textové informační systémy Ý Fibonacciho kódy Definice: Fibonacciho kód ř ádu m FKm(N) = d1d2 . . . dk 1 . . . 1 m-1 krát , kde di jsou koeficienty z předchozí věty (jedničky ukončují slovo). Příklad: R(32) = 0 1 + 0 2 + 1 3 + 0 5 + 1 8 + 0 13 + 1 21, tedy F(32) = 00101011. Věta: FK(2) je prefixový, univers ální kód s c1 = 2, c2 = 3, tedy není asymptoticky optim ální. Petr Sojka PV030 Textové informační systémy Ý Osnova (Týden des átý) Univers ální kódov ání celých čísel. Huffmanovo kódov ání. Adaptivní Huffmanovo kódov ání. Aritmetické kódov ání. Slovníkové metody. Slovníkové metody s restrukt. slovníku. Petr Sojka PV030 Textové informační systémy Ý Univers ální kódov ání celých čísel II asymptoticky optimální universální kód, c1 = 1, do N = 514228 jsou lepší Fibonacciho kódy řádu n (FK(n)). unární kód (N) = 00 . . . 0 N-1 1. binární kód (1) = 1, (2N + j) = (N)j, j = 0, 1. není jednoznačně dekódovatelný (není prefixový). ternární (N) = (N)#. (1) = , (2N) = (N)0, (2N + 1) = (N)1, (N) = (N)#. : každý bit (N) je vložen mezi dvojici bitů z (|(N)|). příklad: (6) = 01001 C = {(N) : N > 0} = (0{0, 1}) 1 je regulární a tedy dekódovatelná konečným automatem. Petr Sojka PV030 Textové informační systémy Ý Univers ální kódov ání celých čísel III (N) = (|(N)|)(N) stejné délky (permutace bitů (N)), ale čitelnější C = {(N) : N > 0} = {0k1{0, 1}k : k 0} není regulární a dekodér potřebuje čítač (N) = (|(N)|)(N) příklad: (4) = (3)00 = 01100 dekodér : (?) = 0011? : K := 0; while log2(N) > 0 do begin K := (N)K; N := log2(N) end. Petr Sojka PV030 Textové informační systémy Ý Komprese dat ­ úvod Kódov ání informace pro komunikační účely; komprese dat. Přes bouřlivý vývoj kapacit pro uložení dat st ále nedostatek místa. Redundance - konstrukce minim álně redundantního kódu. Model dat: struktura ­ sada jednotek ke komprimaci + kontext výskytů; parametry ­ pravděpodobnost výskytu jednotlivých jednotek. Komprimace: 1 vytvoření modelu dat; 2 vlastní kódov ání. Petr Sojka PV030 Textové informační systémy Ý Komprese dat ­ vývoj 1838 Morse, kód e dle četnosti. 1949 Shannon, Fano, Weaver. 1952 Huffman; 5 bitů na znak. 1979 Ziv-Lempel; compress (Roden, Welsh, Bell, Knuth, Miller, Wegman, Fiala, Green, . . . ); 4 bity na znak. osmdes át á a devades át á léta PPM, DMC, gzip (zlib), SAKDC; 2­3 bity/znak přelom tisíciletí bzip2; 2 bity na znak. . . . ? Petr Sojka PV030 Textové informační systémy Ý Vývoj kompresních algoritmů s s s s ss s s 1980 1990 20001950 1960 1970 6 5 4 3 2 1 Komprese(bitůnaznak) rok Huffman LZ78 LZ77 compress GZip SAKDCPPM DMC Petr Sojka PV030 Textové informační systémy Ý Predikce a modelov ání redundance (nestejnoměrn á pravděpodobnost výskytu zdrojových jednotek) kodér, dekodér, model statické modelov ání (model nez ávisí na konkrétních datech) semiadaptivní modelov ání (model z ávisí na datech, 2 průchody, nutnost přenosu modelu) adaptivní modelov ání (1. průchod, model vytv ářen dynamicky u kodéra i dekodéra) Petr Sojka PV030 Textové informační systémy Ý Predikce a modelov ání modely ř ádu 0 ­ pravděpodobnosti izolovaných zdrojových jednotek (př. Morse, písmeno e) modely s konečným kontextem ­ Markovovy modely, modely ř ádu n (př. Bach), P(a|x1x2 . . . xn) modely založené na konečných automatech synchronizační řetěz, nesynchronizační řetěz automat s konečným kontextem vhodné pro regulární jazyky, nevhodné pro bezkontextové jazyky, P(a|qi) Petr Sojka PV030 Textové informační systémy Ý Statistické metody komprese I Znakové techniky null supression ­ nahrazení opakov ání 2 znaku null, 255, speci ální znak Sc run-length encoding (RLE) ­ ScXCc zobecnění na libovolný opakující se znak $ 55 $Sc 655 MNP Class 5 RLE ­ CXXX DDDDDBBAAAA 5DDDBB4AAA half-byte packing, (EBCDIC, ASCII) SI, SO diatomic encoding; nahrazov ání dvojic znaků jedním Byte Pair Encoding, BPE (Gage, 1994) pattern substitution Gilbert Held: Data & Image Compression Petr Sojka PV030 Textové informační systémy Ý Statistické metody komprese II Shannon-Fano, 1949, model ř ádu 0, prefixový kód, kódový strom. kódov á slova délky - log2 pi nebo - log2 pi + 1 AE AL AE + 1. kódový strom (2,2,2,2,4,4,8). obecně není optim ální, dva průchody kodéru textem, statický Petr Sojka PV030 Textové informační systémy Ý Shannon-Fano kódov ání Vstup: posloupnost n zdrojových jednotek S[i], 1 i n, v pořadí neklesajících pstí. Výstup: n binárních kódových slov. begin přiřad' všem kódovým jednotkám prázdný řetěz; SF-SPLIT(S) end procedure SF-SPLIT(S); begin if |S| 2 then begin rozděl S do posloupností S1 a S2 tak, že obě posloupnosti mají přibližně stejnou celkovou pst; přidej ke všem kódovým slovům z S1 0; přidej ke všem kódovým slovům z S2 1; SF-SPLIT(S1); SF-SPLIT(S2); end end Petr Sojka PV030 Textové informační systémy Ý Huffmanovo kódov ání Huffmanovo kódov ání, 1952. varianty statick á a dynamick á. AEPL = n i=1 d[i]p[i]. optim ální kód (ne jediný možný). O(n) za předpokladu utříděnosti zdrojových jednotek. stabilní rozložení příprava předem. Příklad: (2,2,2,2,4,4,8) Petr Sojka PV030 Textové informační systémy Ý Huffmanovo kódov ání ­ sourozenecká vlastnost Definice: Bin ární strom m á sourozeneckou vlastnost pr ávě tehdy, když 1 každý uzel kromě kořene m á sourozence, 2 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). Petr Sojka PV030 Textové informační systémy Ý Huffmanovo kódov ání ­ vlastnosti Huffmanových stromů Věta: Bin ární prefixový kód je Huffmanův m á sourozeneckou vlastnost. 2n - 1 uzlů, max. 2n - 1 možností, optim ální bin ární prefixový kód, který není Huffmanův AR(X) pn + 0,086, pn maxim ální pravděpodobnost zdrojové jednotky. Huffman je úplný, (špatn á detekce chyb). možno rozšírit na afixový kód, KWIC, levý a pravý kontext, hled ání X Petr Sojka PV030 Textové informační systémy Ý Adaptivní Huffmanovo kódov ání FGK (Faller, Gallager, Knuth) potlačení minulosti zapomínacím koeficientem, zaokrouhlov ání, 1, r, r2, rn. line ární čas kódov ání i dekódov ání vzhledem k délce slova. ALHD 2ALHS. Vitter ALHD ALHS + 1. implementační detaily, stromov á reprezentace kódové tabulky. Petr Sojka PV030 Textové informační systémy Ý Osnova (Týden jedenáctý) Aritmetické kódov ání. Slovníkové metody s restrukturalizací slovníku. Syntaktické metody. Kontrola spr ávnosti textu. Dotazov ání a modely TIS. Booleovský model dokumentů. Vektorový model dokumentů. Architektura TIS. Signaturové metody. Podobnost dokumentů. Petr Sojka PV030 Textové informační systémy Ý Princip aritmetického kódov ání zobecnění Huffmanova kódov ání (pravděpodobnosti zdrojových jednotek nemusí být z áporné mocniny dvou). uspoř ád ání na zdrojových jednotk ách; Kumulativní pravděpodobnost cpi = i-1 j=1 pj zdrojové jednotky xi s pravděpodobností pi. Výhody: libovoln á blízkost entropii. adaptivnost je možn á. rychlost. Petr Sojka PV030 Textové informační systémy Ý Slovníkové metody komprese dat Definice: Slovník je dvojice D = (M, C), kde M je konečn á množina slov zdrojového jazyka, C zobrazení M na množinu kódových slov. Definice: L(m) značí délku kódového slova C(m) v bitech, pro m M. Výběr zdrojových jednotek: statický (dohoda na slovníku předem) semiadaptivní (nutné dva průchody textem) adaptivní Petr Sojka PV030 Textové informační systémy Ý Statické slovníkové metody Zdrojov á jednotka délky n ­ n-gramy Nejčastější bigramy (n = 2) n pevné n proměnné (dle frekvencí výskytu) adaptivní (50 % anglického textu je tvořeno asi 150 nejfrekventovanějšími slovy) Nevýhody: nejsou schopny reagovat na rozdělení pravděpodobností komprimovaných dat předem připravený slovník Petr Sojka PV030 Textové informační systémy Ý Semiadaptivní slovníkové metody Slovník Komprimovan á data Komprimovaný slovník Komprimovan á data Výhody: rozs áhlá data (slovník je malá část dat ­ korpusy; CQP). Petr Sojka PV030 Textové informační systémy Ý Semiadaptivní slovníkové metody ­ postup vytvoření slovníku 1 Určí se frekvence N-gramů pro N = 1, 2, . . . . 2 Slovník se inicializuje vložením unigramů. 3 Do slovníku se postupně přid ávají N-gramy (N > 1) s největší frekvencí. Při vložení K-gramu se snižuje frekvence jeho složek (K - 1)-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. Petr Sojka PV030 Textové informační systémy Ý Adaptivní slovníkové metody LZ77 ­ metody posuvného okna LZ78 ­ metody rostoucího slovníku a b c b a b b a a b a c b zakódovaná část nezakód. část (okno, N 8192) (|B| 10­20 b) V zakódované části je vyhledána nejdelší předpona 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 S 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. Petr Sojka PV030 Textové informační systémy Ý LZR (Rodeh) |M| = (N - B) × B × t, t velikost abecedy L(m) = log2(N - B) + log2 B + log2 t Výhoda: hled ání nejdelší předpony [KMP] LZR použív á strom obsahující všechny předpony v dosud zakódované části. Je použita celá dosud zakódovan á část jako slovník. Protože i v (i, j, a) může být velké, je použit Eliasův kód pro zakódov ání celých čísel. Nevýhoda: růst velikosti stromu bez omezení po překročení vymezené paměti vymaz án a konstrukce začín á od začátku. Petr Sojka PV030 Textové informační systémy Ý LZSS (Bell, Storer, Szymanski) Kódem je posloupnost ukazatelů a znaků. Ukazatel (i, j) potřebuje pamět' jak p znaků ukazatel jen tehdy, když ušetříme, ale je třeba bit na rozlišení znaku od ukazatele. Počet položek slovníku je |M| = t + (N - B) × (B - p) (uvažují se jen podřetězy delší než p). Počet bitů na zakódov ání je L(m) = 1 + log2 t pro m T L(m) = 1 + log2 N + log2(B - p) jinak. (Délku d podřetězu můžeme reprezentovat jako B - p). Petr Sojka PV030 Textové informační systémy Ý LZB (Bell), LZH (Brent) Ukazatel (i, j) (analogie LZSS) Jestliže okno není plné (na začátku) a komprimovaný text je kratší než N, je plýtv ání použití log2 N bytů na zakódov ání i. 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 Eliasův kód . LZSS, kde pro kódov ání ukazatelů je použito Huffmanovo kódov ání (tj. dle rozložení jejich pravděpodobností 2 průchody) Petr Sojka PV030 Textové informační systémy Ý Metody s rostoucím slovníkem 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. Petr Sojka PV030 Textové informační systémy Ý LZ78 ­ příklad Vstupní a b ab c ba Index 1 2 3 4 5 Výstup (0,a) (0,b) (1,b) (0,c) (2,a) . . . . . . Vstupní bab aa aaa aaaa Index 6 7 8 9 Výstup (5,b) (1,a) (7,a) (8,a) 0 1 2 3 4 5 6 7 8 9 a a a a a b b b c Petr Sojka PV030 Textové informační systémy Ý LZFG (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. Petr Sojka PV030 Textové informační systémy Ý LZW (Welch), LZC Výstupem jsou pouze indexy, nebo 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 a b a b c b a b a b a a a a a Index 4 5 6 7 8 9 10 Výstup 1 2 4 3 5 8 1 10 11 Přeplnění další fráze není předávána a kódování pokračuje staticky. 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. Petr Sojka PV030 Textové informační systémy Ý LZT, LZMW, LZJ 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í. 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. 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í. Petr Sojka PV030 Textové informační systémy Ý Slovníkové metody s restrukturalizací slovníku Průběžné uspoř ád áv áv ání zdrojových jednotek kratší řetězce kódu. Varianty heuristik (četnost, přesun na začátek (BSTW), výměna s předch ázejícím, přesun o K vpřed). BSTW (výhoda: vysok á lokalita výskytů menšího počtu zdrojových jednotek). Příklad: J á do lesa nepojedu, . . . , 1n2nkn. Zobecnění: koeficient ned ávnosti, Intervalové kódov ání. Petr Sojka PV030 Textové informační systémy Ý Intervalové kódov ání Reprezentace slova celkovým počtem slov od posledního výskytu. Slovník obsahuje slova a1, a2, . . . , an, vstupní posloupnost x1, x2, . . . , xm. Hodnota LAST(ai) obsahující interval od posledního výskytu je inicializovan á na nulu. for t := 1 to m do begin {xt = ai} if LAST(xt = 0) then y(t) = t + i - 1 else y(t) = t - LAST(xt); LAST(xt):=t end . Posloupnost y1, y2,. . . ,ym je výstupem kodéru a může být zakódov ána některým kódem proměnné délky. Petr Sojka PV030 Textové informační systémy Ý Syntaktické metody je zn áma gramatika jazyka zpr ávy. levý rozklad derivačního stromu řetězce. glob ální číslov ání pravidel. lok ální číslov ání pravidel. jsou kódov ány rozhodovací stavy LR analyz átoru. Petr Sojka PV030 Textové informační systémy Ý Kontextové modelov ání pevný kontext ­ model ř ádu N. kombinovaný přístup ­ kontexty různých délek. p(x) = m n=0 wnpn(x). wn pevné, proměnné. n áročné na čas a pamět'. přiřazení pravděpodobnosti nové zdrojové jednotce: e = 1 Cn+1 . automaty s konečným kontextem. dynamické Markovovo modelov ání. Petr Sojka PV030 Textové informační systémy Ý Kontrola spr ávnosti textu Kontrola textu pomocí frekvenčního slovníku. Kontrola textu pomocí dvojitého slovníku. Interaktivní kontrola textu (ispell). Kontrola textu založen á na pravidelnosti slov, koeficient podivnosti. Petr Sojka PV030 Textové informační systémy Ý Koeficient podivnosti Koeficient podivnosti trigramu xyz KPT = [log(f(xy) - 1) + log(f(yz) - 1)]/2 - log(f(xyz) - 1), kde f(xy) resp. f(xyz) jsou relativní frekvence digramu resp. trigramu, log(0) je definov án jako -10. Koeficient podivnosti slova KPS = n i=1 (KPTi - SKPT2 ), kde KPTi je koeficient podivnosti i-tého trigramu SKPT je střední hodnota koeficientu podivnosti všech trigramů obsažených ve slově. Petr Sojka PV030 Textové informační systémy Ý Booleovský model Dotazov ání a modely TIS Různé metody hierarchizace a uložení dokumentů různé možnosti a efektivita dotazov ání. Booleovský model, SQL. Vektorový model. Rozšířené booleovské modely. Pravděpodobnostní model. Model shluků dokumentů. Petr Sojka PV030 Textové informační systémy Ý Booleovský model Blairovo ladění dotazu Vyhled áv ání spočív á ve zmenšov ání neurčitosti tazatele (ladění dotazu). 1 Najdeme dokument s vysokou relevancí. 2 Začneme se dotazovat s jeho klíčovými slovy. 3 Odstraňujeme deskriptory, resp. je nahrazujeme disjunkcemi. Petr Sojka PV030 Textové informační systémy Ý Booleovský model 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ů. Petr Sojka PV030 Textové informační systémy Ý Booleovský model Booleovský model 50. léta: reprezentace dokumentů pomocí množin termů a dotazov ání založené na vyhodnocov ání booleovských výrazů. Výraz dotazu: induktivně z primitiv: term 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, X or Y, X xor Y, not Y. disjunktivní norm ální forma, konjunktivní norm ální forma proximitní oper átory regulární výrazy použití tezauru Petr Sojka PV030 Textové informační systémy Ý Booleovský model Jazyky pro vyhledáv ání ­ SQL booleovské oper átory and, or, xor, not. poziční oper átory adj, (n) words, with, same, syn. 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 Petr Sojka PV030 Textové informační systémy Ý Booleovský model Dotazov ání ­ SQL příklady ORACLE SQL*TEXTRETRIEVAL SELECT specifikace_polozek FROM specifikace_tabulek WHERE polozka 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) Petr Sojka PV030 Textové informační systémy Ý Booleovský model Dotazov ání ­ SQL příklady Příklad: SELECT JMENO FROM ZAMESTNANEC WHERE VZDELANI CONTAINS RT(UNIVERSITA) AND JAZYKY CONTAINS 'ANGLICTINA' AND 'NEMCINA' AND PUBLIKACE CONTAINS 'KNIHA' OR NT('KNIHA',*) Petr Sojka PV030 Textové informační systémy Ý Booleovský model Stilesova technika/ asociační faktor asoc(QA, QB) = log10 (fN - AB - N/2)2N AB(N - A)(N - B) A ­ počet dokumentů ,,zasažených" dotazem QA B ­ počet dokumentů ,,zasažených" dotazem QB (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í) clustering/hnízdění 1. generace, 2. generace, . . . Petr Sojka PV030 Textové informační systémy Ý Booleovský model Vektorový model Vektorový model dokumentů: Necht' a1, . . . , an termy, D1, . . . , Dm dokumenty, a matice relevance W = (wij) typu m, n, wij 0, 1 0 není relevantní 1 je relevantní Dotaz Q = (q1, . . . , qn) S(Q, Di) = i qiwij koeficient podobnosti head(sort(S(Q, Di))) odpověd' Petr Sojka PV030 Textové informační systémy Ý Booleovský model Osnova (Týden dvanáctý) Vektorový model dokumentů (dokončení). Rozšířený boolovský model. Pravděpodobnostní model. Model shluků dokumentů. Architektura TIS. Petr Sojka PV030 Textové informační systémy Ý Booleovský model Vektorový model: pros & cons CONS: nebere v úvahu ?"a"? ?"nebo"? PROS: možné vylepšení: normov ání vah Frekvence termu TF Inverzní frekvence dokumentu IDF log2 m k Rozlišení termů normov ání vah pro dokument: TD j TD3 j normov ání vah pro dotaz: 1 2 × 1 2 TF max TFi × log2 m k [POK, strany 85­113]. Petr Sojka PV030 Textové informační systémy Ý Booleovský model Osnova (Týden třináctý) Automatické strukturov ání textů. Podobnost dokumentů. Uložení lexikonu. Signaturové metody. Komprese pomocí neuronových sítí. Petr Sojka PV030 Textové informační systémy Ý Booleovský model Automatické strukturov ání textů Vz ájemné vazby mezi dokumenty v TIS. Encyklopedie (OSN, Funk and Wagnalls New Encyclopedia). [SBA] http://columbus.cs.nott.ac.uk/compsci/epo/epodd/ep056gs Google/CiteSeer: ,,automatic structuring of text files" Petr Sojka PV030 Textové informační systémy Ý Booleovský model Podobnost dokumentů Nejčastější kosinov á míra ­ výhody. Detailní přehled používaných podobnostních funkcí viz kapitola 5.7 z [KOR] (podobnost). Petr Sojka PV030 Textové informační systémy Ý Booleovský model Uložení lexikonu [MeM] Mehryar Mohri: On Some Applications of Finite-State Automata Theory to Natural Language Processing, Natural Language Engineering, 2(1):61­80, 1996. http://www.research.att.com/~mohri/cl1.ps.gz Petr Sojka PV030 Textové informační systémy Ý Booleovský model Signaturové metody Vyhled ávací metody IV. Předzpracov ání textu i vzorku (signaturové metody). řetězené vrstvené D ále [POK, strany 65­76], viz podklady [MAR]. Petr Sojka PV030 Textové informační systémy Ý Booleovský model Seznam materi álů u Marečka [MAR] Materi ály k předmětu PV030 ke zkopírov ání v knihkupectví Mareček a v materi álech předmětu v ISu. 1 Slidy přednášek předmětu, 4 slidy na list A4. 2 kopie [MEL]. 3 kopie [POK]. 4 článek [MEH]. 5 materi ály o Google [GOO] (plus české shrnutí). 6 kapitola 5.7 z [KOR] (podobnost). 7 [MeM]. 8 ostatní (NLP, diagram s kompresními algoritmy,...). Petr Sojka PV030 Textové informační systémy