PV030 Textové informační systémy Petr Sojka Fakulta informatiky Masarykova univerzita v Brně J ar'o 2004 <□► < fil ► < -š ► < w •T) c^ (%• Úvodem • Petr Sojka, sojka@informatics.muni.cz • Konzultační hodiny jaro 2004: úterý i 2:30—i 3:50 a čtvrtek i 2:30—13:50, po domluvě emailem i jindy. • Místnost B304, 3. patro bloku B, Botanická 6&a. o UPL s materiály k předmětu: http://www.fi.muni.cz/~sojka/PV030/ • Pozdělenído cvičení (B204^ A107 vs. B311). □ S1 ^ ■T) q_ £V Část Informace o předmětu PV030 ^ □ S1 ^ -ŕ) c\o Určenia 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 programovania softwarových systémů. Klasifikace: Bodový systém sestává z ohodnocení práce v semestru (vnitrosemestrové písemky, které budou klasifikovány dohromady 30 body). Na závěr kurzu bude písemný test, na kterýje možno získat 70 bodů. Kromě toho je možno v průběhu semestru získat tzv. prémiové body. Klasifikační škála (změna vyhrazena) z/k/E/D/C/B/A odpovídá zisku 4Ô/54/60/66/72/7Ô/Ô4 bodů. Termíny závěrečného písemného testu budou 24.5. v i 5 hodin (Di) a 7.6.2004 ve i 2 hodin (Di); opravný termín pak patrně 20.6.2004. w □ s1 ^ ~T) Q^ (% Předmět výuky My books focus on timeless truth. D.E. Knuth, Brno, A996 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í. □ g w •T) C^ (%• Sylabus (pokr.) ® Statistické metody komprese dat. ® Slovníkové metody komprese dat. O Efektivní datové struktury pro uchovánítextů a slovníkových dat s využitím korpusové lingvistiky. © Syntaktické metody. Kontextové modelování. Kontrola správnosti textu. Komprese textů s použitím neuronových sítí. Shlukování dokumentů a navigace v nich. □ S1 w ■f)(\(y 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, PV). © 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. © Vyhledávací metody s předzpracováním textu a vzorků -signaturové metody. © Jazyky pro vyhledávání. © Komprese dat, základní principy (entropie). Knihy, skripta W ^ [MEL] Melichar, B.: Textové informační systémy, skripta ČVUT Praha, 2. vydání, -1996. ^ [POK] Pokorný, J., Snášel, V., H úsek D.: Dokumentografícké informační systémy, Karolinum Praha, -1998. ^ [KOP] Korfhage, P. P.: Information Storage and Retrieval, Wiley Computer Publishing,-1997. ^ [SMY] Smyth, B.: Computing Patterns in Strings, Addison Wesley, 2003. ^ [KNU] Knuth, D. E.: The Art of Computer Programming, Vol. 3, Sorting and Searching, Second edition, -1998. ^ [WMB] Witten I. H., Moffat A., Bell T. C: Managing Gigabytes: compressing and indexing documents and images, Second edition, Morgan ^j7 Kaufmann Publishers, -1998. □ Si - = -š -OQ.O Doplnkové zdroje Informací ^ [HEL] Held, G:. Data and Image Compression, Toole and Techniques, John Wiley & Sons, 4. vydaní -1996. Q [MEH] Melichar B., Holub J., A 6D Classification of Pattern Matching Problems, Proceedings of The Prague Stringology Club Workshop '97, Prague, July 7, CZ. H [GOO] Brin S., Page, L.: The anatomy of a Large-Scale Hypertextual Web Search Engine. WWW7/Computer Networks 30(1-7): 107-117 (199Ô). http://dbpubs.Stanford.edu:8090/pub/1998-8 Q [MeM] Mehryar Mohri: On Some Applications of Finite-State Automata Theory to Natural Language Processing, Natural Language Engineering, 2(1 ):61-00,1996. http://www.research.att.com/~mohri/cll.ps.gz 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, Pockwille, 19ÔÔ. | č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ý) Doplnkové zdroje Informací (pokr.) Íl [Sch] Schmidhuber J.: Sequential neural text compression, IEEE Transactions on Neural Networks 7(1), 142-146,1996, http://www.idsia.ch/~juergen/onlinepub.html Q [SBA] Salton G., Buckley On., 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 H [WWW] stránky predmetu ~sojka/PV030/, semináře DIS http: //www. inf .upol.cz/dis,http://nlp.fi .muni. cz/,The Prague Stringologic Club Workshop 1996-2004 http://es.felk.evut.cz/pse/ ^! Jones, S. K., Willett: Readings in Information Retrieval, Morgan Kaufman Publishers, 1997. ^f Cast II Základní pojmy TIS TIS - motivace realita T potřeba informace <—> data T <—> dotaz bs Abstrakce a mapování v informačním systému. bs Informační potřeba o realitě - dotazy nad daty. «□► < S> ► < -š ► « ^ •T) C^ (%• Požadavky na TIS Různost hledisek na TIS is efektivita (user) is ekonomika (funder) Bs 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. □ S1 ^ ■T) q_ £V -ny a klasifikace IS Klasifikace (T)IS iledávací systémy y (T)IS, zasazení PV030 do kontextu výuky r 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 CVTa ÚVT MU. Ektosystém není pod kontrolou designéra IS. Definice: Endosystem sestává z použitého hardware {media, devices), a software (algorithms, data structures) a je plně pod kontrolou designéra IS. -ny a klasifikace IS Klasifikace (T)IS iledávací systémy w □ s1 ^ -ŕ) c\o y (T)IS, zasazení PV030 do kontextu výuky r Od dat k moudroôti • Ú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), o Moudrost (wisdom). w □ s1 ^ ~T) Q^ (% Informační proces Definice: Informační proces - proces vzniku informací, jejich zobrazení ve formě údajů, zpracování, poskytovania využití. Tomuto procesu odpovídají operace nad informacemi. Data/signály —> Informace —> Znalost —> Moudrost. □ g w •T) C^ (%• Klasifikace 15 podle převládající funkce (pokr.) © specifické informační systémy (geografické PV0Í9, PA049, PA050, medicínské PV04Ô, enviromentálníPV044, podnikové PV043, ve státní správe PV05Ô, PV059, knihovnické PV070); dále též PV063 Aplikace databázových systémů. Související oblasti vyučované na Fl: Technologie informačních systémů: PAÍ02, PAÍ05. Specifické aspekty indexování: Indexování multimediálních dat: PAÍ2Ô. Implementace databázových systémů: PAÍ52. □ S1 w ■f)(\(y Pojmy a klasifikace IS Klasifikace (T)IS Vyhledávací systémy Míníanketa Klasifikace 15 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, PVÍ36, PB114). © faktografické systémy pro řízení (Management Information Systems PV045). © systémy pro podporu rozhodování (Decision Support Systems PV09Ô). © expertní (Expert Systems), dotazovací (Question Answering Systems) a znalostní (Knowledge-Based) systémy, (PA03Í). ny a klasifikace IS Klasifikace (T)IS iledávací systémy Různost pohledů na TIS / S Vyhledávací systém Expertní systém DBMS Databázový systém Systém pro řízení w □ S1 ~ = -š -Oo^O Minianketa © Co očekáváte od tohoto predmetu'? 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)1S používáte? b) Rozsah? Kolik hledání v (T)1S provádíte za měsíc? c) Jakjste spokojeni? © Vytváření IS (server) a) Jaký (T)IS nebo jeho komponentu jste realizoval? Oblast, rozsah? b) Jakjste s tímto (T)IS spokojeni, slabá místa? □ g - ■= w •T) C^ (%• Prázdný vyhledávací systém DB I Definice dokumentů VYHLEDÁVACÍ SYSTEM Definice formátu výst. dok. _> Množina Definice způsobu vyhl. dokům. _^ —> vybraných dokumentů Obsah dokumentů -* T Dotazy H S> ^^ffi ^ ■T) q_ £V Pojmy a klasifikace IS Klasifikace (T)IS Vyhledávací systémy Klasifikace VS Vyhledávací systémy (VS) - princip DB I Množina Dotaz — * Dotazovací — —> vybraných stroj dokumentů w □ s1 ^ -ŕ) c\o ny a klasifikace IS Klasifikace (T)IS iledávací systémy Vyhledávací systémy - klaôifikace © Klasifikace dle směru průchodu textem: 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 w □ s1 ^ ~T) Q^ (% Vyhledávacíeyetémy- klaôifikace (pokr.) předzpracování textu ne ano předzpracování vzorků ne 1 III ano II IV I - elementární algoritmy II -vytvořenívyhledávacího stroje III - indexové metody IV - signaturové metody «□► < S> ► < -š ► « w •T) C^ (%• Vyhledávání-formalizace problému Řetízek korálků. Korálky —> element. Číslování elementů přirozenými čísly. Ne nutně čísla, ale návěští. 0) Každý element má návěští, které je jedinečné. 1) Každý element s návěštím x (s výjimkou nejlevějšího) má jednoznačného předchůdce označovaného pred(x). 2) Každý element s návěštím x (s výjimkou nejpravějšího) má jednoznačného následníka označovaného succ(x). 3) Pokud element x není nejlevější, x = succ{pred{x)). 4) Pokud element x není nejpravější, x = pred{succ{x)). 5) Pro každé různé elementy x a y existuje kladné k tak, že buď x = 5ucck{y) nebo x = predk{y). ^ ■T) q_ £V 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 = {/i,/2.....^fc}- Výsledek: informace o tom, kde se v textu vyskytuje některý ze zadaných vzorků. © Vyhledej nekonečnou množinu vzorků zadanou regulárním výrazem R. R definuje potenciálně nekonečnou množinu L(R). Výsledek: Informace, kde se v textu vyskytuje některý ze vzorků zL{R). Alternativy formulace problému vyhledávání: a) první výskyt. b) všechny výskyty bez překrývání. c) všechny výskyty včetně překrývajících se. Vyhledávání-formalizace problému (pokr.) Pojem zřetězení: Definice: Řetězecje množina elementů splňujících pravidla 0)-5). Definice: Lineární řetězec: Řetězec, který má konečně mnoho prvků včetně nejlevějšího a nejpravějšího. Definice: Náhrdelník. Definice: Abeceda A. Píemena abecedy. A+. Prázdný řetěz e. A* = A+ U {e}. Definice: Lineární řetězec nad A: prvek A+. Definice: Vzorek. Text. 1 VS bez předzpracováním vzorků í textu II - Přesné vyhledávání s předzpracováním vzorků Část Přesné vyhledávání <□► < fil ► < -š ► < ^ •T) C^ (%• 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 S = V ■ [T - V + A), tedy 0{V x T). • nejhorší příklad VZOREK = av~Ab, TEXT = ar~Ab • přirozené jazyky: [průměrná) složitost (počet porovnání) výrazně menší, neboť nedochází ke shodě počátků slov příliš často. Pro angličtinu S = Ce • (T — V + i), Ce empiricky naměřeno i.07, t.j. prakticky lineární. • Ccz? Ccz ve. CE? 9 urychlení? aplikace pro více vzorků? nekonečný počet? o verze algoritmu (S, Q, Gt) na cvičeni. ^ ■T) q_ £V Naivní vyhledávání, vyhledávání hrubou silou, elementární vyhledávací algoritmus proč Brute-Force-Matcher(VZOREK,TEXT): T:=length[TEXT]; V:=length[VZOREK]; for i:=0 to T-V do if VZOREK[1..V]=TEXT[i+1..i+V] then print "Vzorek nalezen na pozici i"; Vyhledávací sousmérné metody Při předzpracování je prozkoumána struktura vzorku a na jejím základě vytvořen vyhledávací algoritmus (stroj). Definice: Přeené (vs. p roxi mit ní) vyhledávání cílí k přesnému nalezení vzorku. Definice: Sousměrné (vs. protisměrné) vyhledávání porovnává vzorek zleva doprava (vs. zprava doleva). 1 VS bez předzpracováním vzorků í textu II - Přesné vyhledávání s předzpracováním vzorků Sousměrné metody © i vzorek: • Shift-Or algoritmus. • Knuth-Morris-Prattůvalgoritmus, (KMP, nalezen (MP) 1970, publikován 1977). • Karp-Pabinůvalgoritmus, (KP, 19Ô7). © n vzorků: Aho-Corasickové algoritmus, (AC, 1975). © co vzorků: konstrukce vyhledávacího stroje (K.A) pro vyhledávání nekonečné množiny vzorků (regulární výrazy). «□► < S> ► < -š ► « ^ •T) C^ (%• Shift-Or algoritmus (pokr.) Příklad: V = vzorek nad I = {e, /c, o, r, /, z}. Srv. [POK, strana 31-32]. □ S1 ^ ■T) q_ £V 1 VS bez předzpracováním vzorků í textu II - Přesné vyhledávání s předzpracováním vzorků Shift-Or algoritmus es" Vzorek iai 1/2 ... vm nad abecedou I = a^.....ac. ^ , . j v , ,.. .. , ^ .. í O pokud /,■ = a-, ks* Incidenční matice a (m x c , A,-,-= ^ r , J v ; J i 1 jinak. es* Sloupec matice X odpovídající znaku aj označme Aj. ks* Na začátku do P jednotkový sloupec. V každém kroku algoritmu se řetězec P posune o jednu pozici dolů (horní pozice se naplní nulou) a přečte se ze vstupu jeden znak a y Výsledek posunu se zkombinuje s řetězcem Aj pomocí binární disjunkce: P:= SHIFT(P) OP Aj. ks* Algoritmus skončí úspěšně pokud se na dolní pozici P dostane O. w □ S1 ~ = ■= •ŕ) c\o Petr Sojka I VS bez předzpracováním vzorků í textu II - Přesné vyhledávání s předzpracováním vzorků PV030 Tex tové informační systémy 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í: o je-li nalezen index /', pak c = i a 5 = 1 o není-li nalezen, pak c = T a s = O ^ □ S1 ^ -T) Q^ ^V 1 VS bez předzpracováním vzorků í textu II - Přesné vyhledávání s předzpracováním vzorků Naivní vyhledávání - algoritmus S vstup: var TEXT : array[/I..T] of slovo; VZOREK: slovo; výstup (v proměnné FOUND): Ano/Ne A Y.=A; c while l< T do begin c if TEXT[l]=VZOREK then break; c-s inc(l); end; 2 FOUND:=(KT); Nalevo od prikazuje uvedena jejich složitost. Celková časová složitost tedy je 0(7") = 3c — s + 3. Maximální složitost (která se běžně uvádí) je 0(7") = 37" + □ g ^ •T) C^ (%• Algoritmuô Q' aneb jak je tomu 6 použitím expanze cyklu vstup: var TEXT : array[1..T+l] of slovo; VZOREK : slovo; výstup (v proměnné FOUND): Ano/Ne A I:=l; A TEXT[T+l]:=VZOREK; fc/2j while TEXT[I]OVZOREK do begin [c/2j if TEXT[I+1]=VZ0REK then break; \ic-A)/2\ I:=I+2; end; 3 FOUND: = (KT)or(TEXT[T]=VZOREK) ; Celková složitost: 0(7") = c + |_(c —/l)/2j + 5. Maximální složitost: 0(7") = 7"+ |_T/2j +6. Podmínka v závěru algoritmu zajišťuje jeho funkčnost (není to ale jediná možnost, jak vyřešit inkrementaci cyklu o 2). □ S1 W ■f)t\(y Algoritmuô Q aneb jak je tomu 6 použitím zarážek vstup: var TEXT : array[1..T+l] of slovo; VZOREK : slovo; výstup (v proměnné FOUND): Ano/Ne A I:=l; A TEXT [T+l]:=VZ0REK; c while TEXT[I]OVZOREK do c-A inc(I); 2 FOUND : = (K>T+1) Indexje v tomto případě vždy nalezen; proto je v předposledním řádku algoritmu uvedena složitost c — A 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 i větší než v předchozím algoritmu (ale uvádět c + i místo c by nebylo správné). Celková složitost 0(7") = 2c + 3. Maximální složitost: 0(T) = 2T + 5. = Část IV Přesné sousměrné vyhledáváníjednoho vzorku (K)MF Vyhle dávai ~Á stroj Konstrukce KMP ' stroje Ka rp-Rí ibínovc yyhle ;dávání Osnova (Týden druhý © Zhodnocení ankety, administrativní poznámky. © Přesné vyhledávací metody II (s předzpracováním vzorku, sousměrné): KMP (animace), Pabin-Karp, AC. © Vyhledávací stroj. © Vyhledávání pomocí konečných automatů. © Vyhledávání nekonečné množiny vzorků. □ g w •T) c^ (%• Morris-Prattův algoritmus (MP) Idea: Ztráty naivního algoritmu vznikajítím, že v případě neshody vzorku s textem se vzorek posune o jednu pozici doprava a znovu se celý kontroluje. To znehodnocuje informaci, která byla získána předchozími porovnáními znaků. Snahou je se v případě neshody posunout se vzorkem doprava tak, aby nebylo nutné se ve vlastním textu vracet. □ S1 w ■f)(\(y Ka (K)MF 1 Vyhledávací stroj Konstrukce K.MP stroje rp-Rabínovo vyhledávání Zhodnocení úvodní ankety © Ano: sylabus vyhovuje; kladně hodnoceno pitvání Google; indexace a vyhledávání; příklady. © Ne: „navázání na formály"; komprimace (známo z organizace souborů); SQL; implementační detaily; příliš obecný a nezáživný výklad; teorie. © Velká variabilita zkušeností, názorů, konstruktivnosti i kultury anketních odpovědí (zapsaných okolo sta studentů od prvního do šestého ročníku studia). © Domácí úkoly—> vnitrosemestrová písemka. w □ fl] - = _š -o^O Hlavní část algoritmu (K)MP var text: array[i..T] of char; vzorek: arra\j\A..V] of char; i, j: integer; na/ezen: boolean; / := i; > index do textu j:=i; > index do vzorku while (/ < T) and [J < V) do while (j > O) and [text[i] ^ vzorek[J\) do j ■= hiß; end while /:=/ + 1; j:= J + 1 end while nalezen := j > V; > pokud nalezen, je na pozici i — V — A w □ S1 ~ = -E -OQ^O (K)MF Vyhle dávai ~Á stroj Konstrukce KMP ' stroje Ka rp-Rí ibínovc yyhle ;dávání Analýza (K)MP is" Složitost 0(7") plus složitost předzpracování (vytvoření pole h). «s Animace trasování hlavní části KMP. □ g - = ^ ■ŕ) q_ Q» Konstrukce h pro KMP i:=l; j:=0; h[l]:=0; while (i0) and (v[i]<>v[j]) do j:=h[j]; i:=i+l; j:=j+l; if (i<=V) and (v[i]=v[j]) then h[i]:=h[j] else h[i] :=j (*MP*) end; Složitost konstrukce, t.j. předzpracování, je 0(V), celkem tedy 0{T + V). Příklad: h pro ababa. KMP vs. MP. □ s> - ■= Ka (K)MF Vyhledávací stroj Konstrukce K.MP stroje rp-Rabínovo vyhledávání Knuth-Morris-Prattův algoritmus es* h se uplatní, když předpona vzorku y^... ^j-i je srovnána s podřetězcem textu ť/-j+i t/-j+2 • • • ť/-i a v j ^ t-, es* mohu skočit o víc než i? o J?jak /i spočtu? es- h(j) největší k < j takové, ze y^ ... /fc_i je příponou y^... ^j-i. tj. y^ y2 ... /fc_^i = /j-fc+^i yj-fc+2 • • • Vj-a a Vj ± vk es- KMP: zpětné přechody tak dlouho, až j = 0 (předpona vzorku není v prohledávaném textu obsažena) nebo t\ = Vj (y-i y2 ... v j = tj-j+A ti-j+2 ■ ■ ■ ť/-i ti) Eg" animace lecroq, dále [POK, strana 27], též viz podklady [MAP] pro detailní popis. w □ s1 ^ -ŕ) c\o Univerzální vyhledávací algoritmus, který používá tabulku přechodů g odvozenou z hledaného vzorku. [g odpovídá prechodové funkci ô K.A): var i,T:integer; nalezen: boolean; text: array[1..T] of char; state,qO: TSTATE; g:array[1..maxstate,1..maxsymb] of TSTATE; F: set of TSTATE;... begin nalezen:= FALSE; state:= qO; i:=0; while (i <= T) and not nalezen do begin i:=i+l; state:= g [state,text [i]]; nalezen:= state in F; end; end; Jak předzpracovat vzorek do q? w □ s1 ^ ~T) Q^ (% (K)MF Vyhle dávat ~Á stroj Konstrukce KMP ' stroje Ka rp-Rí ibínovc yyhle ;dávání Vyhledávací stroj Vyhledávací stroj (VS) pro sousměrné vyhledávání is" VS pro sousměrné vyhledávání A = (Q, 7", g, h, q0, F) • Q konečná množina stavů. • T konečná vstupní abeceda. • g: Q x T —> Q U {fa||} dopředná přechodová fee. o h: (Q — cjo) —> Q zpětná přechodová fee. • cjo počáteční stav. • F množina koncových stavů. «s hloubka stavu q: d{q) G No je délka nejkratší dopředně posloupnosti přechodů z cjo do q. □ g - = (K)MP Vyhledávací stroj Konstrukce K.MP stroje Karp-Rabínovo vyhledávání Konfigurace, přechod VS ^ •T) C^ (%• «s konfigurace VS [q,w), q G Q, tv G T* dosud neprohledana část textu. «s počáteční konfigurace VS [qp.w), w }e celý prohledávaný text. «s akceptující konfigurace VS {q, w), q G F, w]e dosud neprohledávanýtext, nalezený vzorek je bezprostředně před w. «s přechod VS: relace hC (Q x T) x (Q x T): • g{q,a) = p, pak {q,aw) h [p,w) dopředný přechod pro \fw G T*. o /i(q) = p, pak (q, w) h (p, tv) zpětný přechod pro Vtv G T*. □ g - = ■T) c^ £v Ka (K)MP 1 Vyhledávací stroj Konstrukce K.MP stroje rp-Rabínovo vyhledávání Vyhledávací stroj (pokr.) •s- Vlastnosti g, h: o g{qo, a) ^ fjj[ pro Va ET {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 poctu dopředných přechodů V). Rychlost vyhledávání tedy bude lineární vzhledem kV. w □ s1 ^ -ŕ) c\o Vyhledávání pomocí VS Při dopředném přechodu je přečten jeden vstupní symbol a stroj přechází do následujícího stavu p. Je-li vsak g{q,a) = fail, provede se zpětný přechod bez čtení vstupního symbolu. Časová složitost S = 0(7") (měříme počet přechodů VS). w □ s1 ^ ~T) Q^ £V (K)MP Vyhle dávai ~Á stroj Konstrukce KMF ' stroje Ka rp-Rí ibínovc yyhle ;dávání Konôtrukce VS pro KM P pro vzorek v^2---Vv © počáteční stav cjo © g{q, Vj+^) = q\ kde q' odpovídá předponě 1^1/2 ... ///j+i • © pro op definujme g{qo,a) = qo proVa, pro která g{qo,a) nebylo definováno v předchozím kroku. ® g{q, a) = fa][ pro Vq 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 fei h definuje na straně 47 uvedený algoritmus. □ g - = w •T) c^ (%• (K)MF Vyhledávací stroj Konstrukce KMP stroje Karp-Rabínovo vyhledávání Karp-Rabinovo vyhledávání (pokr.) #define REHASH(a, b, h) (((h-a*d)«l+b) void KR(char *y, char *x, int n, int m) { int hy, hx, d, i; /* předzpracováni: vypočet d = 2m~A */ d=l; for (i=l; i w) h* (q, m/) pro nějaké qF), kde K, T, q0, F jsou stejné jako u deterministické verze KA, ale ô : K x T -» 2K c5(q, a) je nyní množina stavů. Definice: he (K x T*) x (K x T*) přechod: jestliže p G í%,}; F = {of E K': q'nF^). □ g - "S ^ ■T) q_ £v Konôtrukce VS (DKA) z NKA Veta: Pro každý nedeterministický konečný automat M=(K,T,ô,qo,F) můžeme sestrojit deterministický konečný automat M'={K.' ,X ,ô' ,q'0, F) takový, že L{M) = LÍM'). w □ S1 ~ = -š -oc\o Konetrukce g pro VS Konetruk.ee q' pro VS pro množinu vzorků p = {v ,v.....v } © Vytvoříme NKA M: • Počáteční stav qp. • Pro Va G T definujme g{qo, a) = qp. • Pro V/ G {i.....P} definujme g{q,bj+^) = q'', kde q' odpovídá predpone b^b-z ■ ■ ■ bj+^ vzorku i/'. o Stav odpovídající úplnému vzorkuje koncový. © a jemu odpovídající DKA M' s q'. w □ S1 ~ = -E -OQ^O 0en ova (Týden tretí) © Opakování: animace KMP, AC. © Algoritmy pro sousměrne vyhledávání nekonečné množiny vzorků. © Regulární výrazy. © Přímá konstrukce (N)KA pro daný PV. «□► < s> ► < .s ► « w •T) C^ (%• Regulární výraz (RV) Definice: Regulární výraz V nad abecedou A: © s, O jsou PVa pro Va G AjeaPV. © Jestliže x, y PV nad A, pak: • (x + y) je PV (sjednocení); • (x.y) je PV (zřetězení); • (x)*je PV (iterace). Konvence o prioritě regulárních operací: ejednocení < 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. ^ ■T) q_ (jt- wWBHBWSW Část VI Vyhledávání nekonečné množiny vzorku ^ □ S1 ^ -ŕ) c\o Hodnota RV Hodnota h(x) RV x: © h(O) = 0, h(e) = {s}, h{a) = {a} © 9 h{x + y) = /i(x) U h{y) • h(x.y) = h{x).h{y) • h(x*) = (h(x)T m- h(x*) = s U x U x.x U x.x.x U ... es" Hodnotou PVje regulární jazyk (PJ). es- Každý PJ lze reprezentovat PV. vs? Pro V PV V 3 KA M: h{V) = L(M). ^ □ S1 ^ -T) Q^ ^V Axiomatizace RV (5a\omaa A966) M: x+(y+z) = (x + y)+z = x + y+z asociativnost sjednocení A2: x.(y.z) = (x.y).z = x.y.z asociativnost zřetězení A3: x + y = y + x komutativnost sjednocení A4: (x + y).z = x.z + y.z distributivnost zprava A5: x.(y + z) = x.y + x.z distributivnost zleva A6: x + x = x idempotence sjednocení A7: s.x = x jednotkový prvek pro zřetězení AÔ: O.x = O nulový prvek pro zřetězení A9: x + O = x jednotkový prvek pro sjednocení MO: x* =e + x*x MA: x* = {e + x)* w •T) C^ (%• 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) = i. ® d{VA + V2) = d{VA) + d{V2) + A. ® d{VA.V2) =d{VA) + d{V2) + A. ® d{V*) = d{V) + A. © d[[V)) = d{V) + 2. w □ s1 ■f)t\(y Fodobnoet regulárních výrazu Věta: Tato axiomatizace PVje úplná a bezesporná. Definice: Regulární výrazy nazveme podobné, jestliže se mezi sebou dají navzávem převést pomocí axiomů Ai až Aii. Věta: Podobné regulární výrazy mají stejnou hodnotu. w □ fl] - = _š -o^O Konôtrukce NKA pro daný RV Definice: Zobecněný NK.A dovoluje e-přechody (přechody bez čtení vstupního symbolu). Věta: Pro každý PV V je možno sestrojit KA M takový, ze h [V] = L{M). Důkaz: Strukturní indukcí vzhledem k PV V: Konstrukce NKA pro daný RV (důkaz) © V = a © Y = V\ MA automat pro VA [h{VA) = L{MA)) Konstrukce NKA pro daný RV (pokr.) Vlastnosti takto vytvořeného NK.A: t®' Z každého stavu vycházejí maximálně 2 hrany. is' Z koncových stavů nevycházejí žádné hrany. «ar Počet stavů M < 2 • d{V). «s" Simulace chování automatu M v čase 0(d(V)T) a paměti 0{d{V)). Konstrukce NKA pro daný RV (důkaz pokr.) Y = YA +V2 MA,M2 automaty pro Va,V2 (Aj(V-i) = L{MA), h(V2) = L{M2)) 5\mu\ace NKA ^ □ S - = -š -oo^o Eliminace s-přechodů Pro následující metody simulace NKA je třeba odstranit e-přechody. Toto můžeme provést známým postupem: a Vv ) a 2) wWBHIWSW Simulace NKA (pokr.) Metody implementace simulace NK.A 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ů. «s" Implementace automatu ve formě (generovaného) programu pro konkrétní automat. «□► < S> ► < -š ► « ^ •T) C^ (%• Přímá konôtrukce (N)KA pro daný PV Příklad i: K = ab* a + ac + b*ab*. Příklad 2:K = ab* +ac + b*a. □ S1 ^ ■T) q_ £V Přímá konôtrukce (N)KA pro daný PV Nechť V je PV nad abecedou T. Pak KAM = (K,T,ô,q0 F) takový, že h(V) = L{M). O Položme Q = {V}, Q0 = {V}, / := 1. Q Vytvořme derivace všech výrazů z Qf_^ podle všech symbolů z T. Do Q,- vložíme všechny výrazy vzniklé derivací výrazů z Qf_^, které nejsou podobné výrazům z Q. © Jestliže Qj ^ 0, přidáme Q,- do Q, položíme /':=/' + i a přejdeme na krok 2. Q Pro Vf G Q a a G T položíme ô (fx,a) = %,v prípade, že výraz %]e podobný výrazu £-a. (Přitom % G Q.) © Množina F = {f G Q:. G h (f)}. ^ □ S1 ^ -T) Q^ ^V Príklad: PV= K = (0 + 1)*1. Q = Q0 = {(0 + 1)*1},/ = 1 Qi={i = K.f} = {(0 + iri+6} Příklad: PV=(10)*(00)*1. Vice 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 □ g - = w •T) c^ (%• Derivace RV pozičním vektorem © Protože je označena konstrukce, která generuje také prázdný řetězec, označíme také konstrukci následující: a . b* . c /"zu\ A A \.°V) Nyní derivací podle operandu b výrazu (3b) dostaneme: (4a) a . b* . c A Protože je označena konstrukce následující za konstrukcí v iteraci, musí se označit i předchozí konstrukce. a ' a ' A Derivací výrazu (4b) podle operandu c dostaneme: a . b* . c A Takto označený regulární výraz odpovídá prázdnému regulárnímu výrazu s. □ g - = (4b) (5) w ■f)(\(y 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 PV. Příklad: Mějme regulární výraz: a . b* . c (1) K označení pozice budeme používat zobáček A. 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: © 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 rusí. To znamená, že derivací výrazu (2) podle operandu a dostaneme: * ■ l ■ c (3a) w □ s1 ^ -ŕ) c\o Derivace RV pozičním vektorem Shrnutí postupu derivování: 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ů ^7 v závorce. □ Si - - ^ -qc^o Derivace PV pozičním vektorem: přiklad Příklad: a.b*.c, derivace podle a, b, c □ g - = ^ •T) C^ (%• Protisměrné vyhledávání Protisměrné vyhledávání-princip. Může být směr podstatný? V ja kých případech? Přehled vyhledávacích algoritmů: «s" i vzorek- Boyer-Moore (BM, 1977), Boyer-Moore-Horspool (BMH, 19Ô0), Boyer-Moore-Horspool-Sunday (BMHS, 1990). ns n vzorků - Commentz-Walterová (CW, 1979). is nekonečná množina vzorků: reverzovaný regulární výraz-Buczitowski (BUC). Část VII Protisměrné vyhledávání ^ □ rgi - = _š -o^O Boyer-Moore-Horspool algoritmus 2 3 4 5 6: 7 ô 9: 10: 11 12: 13: 14: var: TEXT: array[1..T] of char; VZOREK: array[1..V] of char; l,J: integer; NALEZEN: boolean; NALEZEN := fa/se; / := K; while (/ < T) and not NALEZEN do J:=0; while (J < I/) and {VZOKEK[V - J] = TEXT[/ - J]) do J:= J + 1; end while NALEZEN := (J = |/); if not NALEZEN then /:= l + 5HIFT(TEXT[l-J],J) end if end while SHIFT(A, J) = if A se nevyskytuje vještě nesrovnalé části vzorku then V — J elee nejmenší K takové, že KZOKEK[l/ - (J + K)] = A; ^ □ S1 ^ -T) Q^ ^V Kdy rychlejší než KMP? Kdy 0{T/V)? Příklad: Hledání vzorku BANANA v textu I-WANT-TO-FLAVOR-NATURAL-BANANAS. <□► ^ 3 ► < -š ► < w •T) c^ (%• Konstrukce CW vyhledávacího stroje VSTUP: M nožina vzorků P — {y-\ ,1/2...../(-} VÝSTUP: CW vyhledávací stroj METODA: Sestrojíme funkci q a zavedeme ohodnocení w jednotlivých stavů: O Počáteční stav qo\ w{qp) = s. O Každý stav vyhledávacího stroje odpovídá příponě bmbm+^ ... bn nějakého vzorku /,■ z množiny p. Definujeme g{q,bm-^) = q', kde q' odpovídá příponě bm-^bmbm+^ ... bn vzorku /,■: w(q) = bn...bm-Mbm; w(q') = w(q)bm-i. O g{q, a) = fjajN pro všechna q a a, pro která g{q, a) nebylo definováno v kroku 2. O Každý stav, který odpovídá úplnému vzorku, bude koncový. w ■f)(\(y 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 (K=T) & not (NALEZEN) do begin if g [STATE, TEXT [I-J] ]=f ail 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 w ^ -ŕ) c\o CW-funkce shift Definice: 5hift[STATE, TEXT[l - J]] = min {A,5hift2{STATE)}, kde A = max {sfoftl {STATE), char{TEXT[l - J]) - J - 1}. Jednotlivé funkce jsou definovány takto: O 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 vzorkuje char(a) = LMIN + A, kde LMIN je délka nejkratšího vzorku. Formálně: char(a) = min {LMIN + A, min{d(cj) : w(q) = ax, x £ T*}J. Q Funkce shiftA(q0) = A, pro ostatní stavy má hodnotu shiftA(q) = min {LMIN, A}, kde A = min {fc : k = d(q') - d(q), w(q') = w(q)u pro nějaké neprázdné slovo u}. Stav q' má větší hloubku než q a w(q) je vlastní předponou w(q'). Q Funkce shift2(qo) = LMIN, pro ostatní stavy má hodnotu 6hift2(q) = min{A, B}, kde A = min{k : k = d(q') — d(q), w(q') = w(q)u pro nějaké neprázdné slovo u,q' je koncový stav}, B = 6hift2(q') : q'je předchůdce q. W □ s1 ^ ~T) Q^ (% CW-funkce shift Příklad: P = {cacbaa, aba, acb, acbab, ccbab}. LMIN = 3,- char stav sbiftA sWft2 <\o A 3 a A 2 b A 3 aa 3 2 ab 1 2 be 2 3 ba 1 1 aab 3 2 aba 3 2 bca 2 2 bab 3 1 aabc 3 2 babe 3 1 aabca 3 2 babca 3 1 babec 3 1 aabcac 3 2 □ S1 < 5 ► < 5 Protisměrné vyhl. nek. mn. vzorku ^ •T) C^ (%• Definice: Reverzovaný regulární výraz vznikne reverzí všech zřetězení ve výrazu. Příklad: Reverzovaný RV k V = bc(a + <3*bc) je VR = (a + cb<3*)cb: b ^ □ g < .^ ► < .^ ► _š -oo^o Část Vyhledávání nekonečné množiny vzorku ^ □ S1 ~ = -š -oc\o Protisměrné vyhl. nek. mn. vzorků (pokr.) Buczitowski: V vyhledáváme tak, že vytvoříme VR a pro každý stav a nedefinovaný přechod z něho se určí shíft[STAV, SYMBOL) analogicky jako u algoritmu CW: a b c X 0 A 3 • i A A 2(3!) 2 A 3 A A A 4 A A A A 5 A A A w □ S1 ~ = -š -Oo^O 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. «s" Srovnejte s výsledkem vyhledávacího stroje AC. ts Řešte úlohu také algoritmem přímé konstrukce DKA (derivováním) a diskutujte, zda výsledkem jsou izomorfní automaty. «□► < S> ► 4 -š ► « Dvouceôtný automat ee ekokem II Definice: Přechod 2DKAS je relace h C K(M) x K(M) taková, . 3\—y\ 3\ Q 3\-\--ai . . . 3 í—-j I 3i... 3fi \ 3-\ . . . 3\—-^ Q 3\3\-\--^ . . . 3 í—-j | , ze os- án a j... a„ pro i > A, ;, a\+.\) = (q', — A) (protisměrné srovnání), os* a^ ... a; cj a+1 ... aj_^ *\ aj.. .an\- a^ ... aa+i ... at—i c( \ a^... an pro m), m>A, t = min{/ + m,n + -1} (protisměrný skok), os* a^ ... aj ej aJ+^ ... a^ | aj... an \ a^ ... ajaj^ ... a^_^ ŕ^ | a^... an pľ'c t,aj) = (q',m), m>A, t = min{/ + m,n + A} (sousmerný skok) >ro os* a^ ... aj_^ qaj... a;_^ | <9/a/+-i ... a„ h a^ ... aj_^ q' aj ■ ■ ■ aj-^aj | aí+^ ...a„ pro i > A, 6{q,a{) = {g', A) (sousmérné srovnání). (Sousmérná pravidla jsou pro sousmerné stroje, protisměrná pro protisměrné). Definice: \-k, h* analogicky jak u VS. w •ŕ) c^ (%• □ S1 ^ ■T) q_ £V Dvouceôtný automat ôe ôkokem I Definice: 2DKA5je M = (Q, I, í, íj0, k, T, F), kde Q množina stavů I vstupní abeceda ô zobr. Öxl^Öx {--1,-1.....ŕc} cjo £ Q počáteční stav fc £ N max. délka skoku t^ Q U I značka skoku FCQ množina koncových stavů Definice: Konfigurace 2DKASje řetézec z X*QX* T X*. Definice: Množinu konfigurací 2DKAS M značíme K(M). Příklad: a-i 32 ... a^ q a(... aj_i T aj... a„ £ K(M) : čtecí hlava í í značka skoku Hierarchie vyhledávacích ôtroju Definice: Jazyk prijímaný dvouceetným automatem M = (Q, I, <5, qo, k, T, F) je množina L{M) = {w E X* : q0 T T r~* w'fxw |, kde f EF,w' El*,xEl}. Věta: L(M) pro 2DKAS M je regulárni. Příklad: Zformulujte protisměrné vyhledávání vzorku BANANA v textu l-WANT-TO-FLAVOUP-NATUPAL-BANANAS pomocí BM jako 2DKAS a vyhledávání trasujte jako posloupnost konfigurací 2DKAS. Cvičeni Mějme regulární výraz R = 1(0 + 1*02) nad abecedou A = {O, i, 2}. is" Sestrojte DKA pro protisměrné vyhledáváním (Bucziiowski) a spočtěte chybovou funkci. Nakreslete přechodový diagram tohoto automatu včetně vizualizace chybové funkce. «s Zapište výsledný automat jako 2DKAS a trasujte vyhledávání v textu 11201012102. □ S1 ^ •T) C^ (%• Část IX Proximitní vyhledávání Shrnuti přesného vyhledávaní 2DKAS ■/ DKA I AC I KMP BUC co i CW k I BM 1 <— směl-----# vzorků. Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů Metrika (pro proximitní vyhledávání) ^ □ S - = -š -oo^o Jak měřit (metrika) podobnost řetězců? Definice: Funkci d : SxS^R nazvete metrika jestliže platí O d(x,y)>0 © d(x, x) = O © d{x, y) = d(y,x) (symetrie) O d(x, y) = O => x = y (pravidlo nerozeznatelných bodů) © d(x, y) + d(y, z) > d{x,z) {trojúhelníková nerovnost) Hodnoty funkce d (distance) nazýváme vzdálenost. w □ [5i - = _= -qq^o 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 I. Minimální počet editačních operací pro přeměnu X na Y je «s" Hammingova vzdálenost, P-vzdá lenost, pokud povolíme jen operaci Replace, «s Levenshteinova vzdálenost, DIR-vzdálenoet, pokud povolíme operace Delete, Insert a Replace, «s Zobecněná Levenehteinova vzdálenost, DIRT-vzdálenoet, pokud povolíme operace Peletě, Insert, Replace a Transpose, Transpoziceje možná jen u sousedních znaků. Jde o metriky, Hammingova je nad řetězci stejné délky, Levenshteinovy i délek různých. □ g w •T) C^ (%• Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů Klaôifikace vyhledávacích problémů Defi nice: Necht T — t^t2 ■ ■ 'ín a vzorek P — p^f2 ■ ■ ■ Pm- Možno se například ptát: O je P podřetěz T? © je P podsekvence z T? Q je podřetěz či podsekvence P v T? O je P v T takový, že D(P, X) < k pro k < m, kde X = ťř... tj je částí T (DJe P, D/P či D/Pf)? © je řetěz P obsahující don't care symbol 0 (*) v T? © 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. w □ s1 ■f)t\(y 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 aY ,ze 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ý príklad řetězců X aY,že platí zároveň R{X,Y) = 5, DIR{X,Y) = 4 i DIRT{X,Y) = 3, nebo dokažte neexistenci takových řetězců. Příklad: Najděte takový příklad řetězců X aY délky 2n, n e N, že R{X, Y) = naa) DIR{X, Y) = 2; b) DIRT{X, Y) = f f ] w □ S1 ~ = -š -oc\o 6D klaôifikace vyhledávacích problémů [MEH] ([MAR]) Subpattern rull pattern r rOne Infinite Finite R- mat chingD IKT- matching 4 seQuence Stri Exact DIR-matching Care Don't care w □ S1 ~ = -E -Oo^O Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO 6D klaôifikace vyhledávacích problémů (pokr.) Dimenze i 2 3 4 5 6 S F 0 E C 0 Q S F D G D S Celkem 2x2x3x4x2x2 = i 92 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. □ g - ■= Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů w •T) C^ (%• Hledání ôekvencí znaku Příklad: NKA pro QFOECO (seQuence): A P2 P3 P4 pje jakýkoliv znak ze I kromě p. Automat má m + i stavů pro vzorek délky m. ^ □ g < f ► < f ► _š -oo^o Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů 9FOE CO, QFOE CO, £ >90E CO CO, 9FOf 3FOC CO Příklady vytváření VS Příklad: Nechť P = p^p2pz> ■ ■ ■ pm, m = 4, A je jakýkoliv znak ze I. NKA pro SFOECO: w □ S1 ~ = -š -oc\o Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů Hledání podřetězce: NKA pro SSOECO Definice: Tento automat se nazývá počátečnís-treelis amá{m + A) + m + {m-A) + --- +2 = ^^L stavů. □ S1 Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Hledání podôekvence Příklad: NKA pro QSOECOje podobný,jen přidáme cykly pro nesrovnalé znaky a e prechody ke všem existujícím dopředným přechodům (nebo zřetězíme automat m-krát). Definice: Automat pro QSOECO se nazývá e-treelie. □ g - = w •T) C^ (%• Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů Proximitní vyhledávání SFOPCO Definice: Tento automat se nazývá R-tree\ie, a má (m + i) + m + (m-i)H--------h(m-/c + i) = (/c + i)(m + i-|) stavů. Číslo patra koncového stavu odpovídá vzdálenosti nalezeného řetězce od vzoru. □ g - = w ■f)(\(y Nepřesné vyhledávání: metriky Klasifikace vyhledávacích problémů SFOECO, QFOECO, SSOECO QSOECO, SFORCO, SFODCO Proximitní vyhledávání SFOPCO Příklad: SFOPCO pro Hammingovu (ř\) vzdálenost, k < 3: Počet pater odpovídá vzdálenosti. Proximitní vyhledávání SFODCO pro D/^-vzdálenoôt Příklad: SFOD3CO pro Levenshteinovu [DIR) vzdálenost, k < 3: další „D-hrany" a „/-hrany. □ S1 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 E33Ü. Simulace NKA nebo determinizace? Hybridní přístup. Pražský stringologický klub a jeho konference. «□► < S> ► < -š ► « ^ •T) C^ (%• Oenova (Týden šestý) © Uzavření kapitoly vyhledávání bez předzpracování textu. © Vyhledávání s předzpracováním textu; indexové metody. © Metody indexování. © Automatické indexování, konstrukce tezauru. © Způsoby implementace indexu. □ S1 w ■f)(\(y ČástX Indexové metody ^ □ fli - = _š -o^O Vyhledávání s předzpracováním textu Velké množství textů? Předzpracování textu! Základní pojmy es* index, indexové metody, indexový soubor, indexsekvenčnísoubor es- hierarchické členění textu, značkování textu, hypertext es- otázky uložení seznamu slov {lexikon) a seznamu výskytů (hitů) jejich aktualizace w □ S1 ~ = -š -Oo^O Vyhledávání 6 předzpracováním textu ta" granula rita položek indexu: dokument- odstavec -věta - slovo doki dok2 dok3 slovoi i O A slovo2 i A O slovo3 O A A slovo4 A A A ks- invertovaný soubor, transpozice slovoi slovo2 slovo3 slovo4 doki A A O A doV.2 O A A A dok3 A O A A □ S1 W •T) C^ (%• Implementace indexových ôyôtému I Pro implementaci indexuje klíčová volba vhodných datových struktura algoritmů. 10 souboru: slovoi i 0 i slovo2 i i 0 slovo3 0 i i slovo4 i i i ks" Použití seznamu dokumentů: slovoi 1,3 slovo2 1,2 slovo3 2,3 slovo4 1,2,3 is" Souřadnicový systém s ukazateli má 2 části: slovník s ukazateli ^ do seznamu dokumentů a zřetězený seznam ukazatelů na Vyhledávání v indexu Indexové metody ks- Uspořádání slov {primární klíč) v indexu —> binární vyhledávání Caeová složitost vyhledávání jednoho slova v indexu: n délka indexu, V délka vzorku 0(Vx log2(n)) ks- Vyhledávání/c slov, vzorek p = ia|...../(- KQ^O Hierarchický tezaurus es* Vytváření znalostní báze pro přesné vyhodnocení relevance dokumentů. es* top/c-zpracování sémantických map termínů. Visual Thesaurus http://www.visualthesaurus.com. es* Tovek Tools, Verity. w Počítačová lingvistika Úrovně zpracování (indexování) textů v přirozeném jazyce es* vyhledávání řetězců - slova jsou řetězce písmen. es* slovotvorba - morfologická analýza. es* gramatika (CFG, DFG) - syntaktická analýza. es* význam vět (TIL) - sémantická analýza. es* kontext-pragmatická analýza. es* plné porozumění a schopnost komunikace - informace. Implementace indexových systémů Corpue Query Froceeor základní dotazy • „Havel"; 45: Český prezident Václav se včera na 09: jak řekl Václav , každý občan 24Ô: více než rokem řekl Pravda vítězí regulární výrazy • „Pravda | pravda"; • „(P|p)ravda"; O „(P|p)ravd[a,u,o,y]"; • „pravd.*"; „pravd.+"; „post?el"; poeloupnoet e\ov O „prezident(a|u)" „Havl(a|ovi)"; • „atak"; • „prezident"; []* „Havel"; • „prezident" („republiky" „Vaclav")? „Havel"; □ g w •T) C^ (%• 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í); O efektivní vyhledávání textových řetězců. To všechno využije člověk sedící za počítačem, aby z takto zpracovaných textů získal informace, které ho zajímají. Opravdu? Příklad: V textové databázi je uloženo několik posledních ročníků denního tisku. Pád bych získal informace o prezidentu Václavu Havlovi. a/> HAVEL b/>přesnější dotazy cl... Fočítač (výpočetní síla) + + človek inteligence) hodnotné informace cas peníze přenést co největší část inteligence (času, peněz,. Cíl nás všech ■ na počítač. □ S1 Implementace indexových systémů Corpue Query Proceôor dotazy na poziční atributy • [word = „Havel"]; O [lemma = „prezident"] []* [lemma = „Havel"]; • ...ženu prezidenta Havla ... [lemma = „hnát"] [] [lemma = „Havel"]; • [word = ,,žen(u|eme)" & lemma !=„žena"]; I ... or I ... not některé další možnoeti O [lemma = „prezident"] []* [lemma = „Havel"] within s; ...10, 3 s • [lemma = „Havel"] within 20 „Pravda" • a:[word= „Zena|Muž|Clověk"] []* [lemma = a.lemma] □ t5> Implementace indexových systémů w ^ -ŕ) c\o Oenova (Týden ôedmý) ks- Exkurs do počítačové lingvistiky. es- Korpusová lingvistika jako príklad TIS. es- Vyhledávací metody s předzpracování textu i vzorku (dotazu) ks" Google jako príklad TIS. w □ s1 ^ -ŕ) Q^ (% Implementace indexových systémů Rub a líc relevantního vyhledávání Úrovně zpracování (indexování, adresovém) textů v přirozeném jazyce informace ideál ideálů ne Vyhledávání informací pragmatická analýza kontext ne Správný překlad sémantická analýza význam vět TIL v začátcích Kontrola pravopisu syntaktická analýza gramatika CFG, DCG částečně morfologická analýza slovotvorba lemma ano Kontrola Překlad jedn. slova jsou řetězce písmen vyhledávání řetězců ano □ ö - = w •T) C^ (%• Korpuôová lingviôtika «s 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/. «s Vnitřní architektura a implementace korpusu, viz podklady [MAP]. □ S1 ^ ■f)t\(y Implementace indexových systémů Rub a líc zÍ6ká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ážMOO kg. ------> RDB objekt vlastnost hodnota atribute, atribut2 • František Novák má rád pivo. 2 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 vety je možné pohlížet také jako na „funkce" svého druhu, definované významem. Textovou informaci (konkrétní objekty o nichž hovoříme, pragmatické informace,...) lze pak chápat jako „výpočet" těchto funkcí. Tento výpočet je pro nejednoznačnost často nepřesný nebo nemožný. • Muž, který vystoupil na nejvyšší českou osmitisícovku, je můj vnuk. □ s1 - - w ^ -ŕ) c\o Implementace indexových systémů Co je korpuô? Definice: Korpus}e rozsáhlý, vnitřně strukturovaný ucelený soubor textů v přirozeném jazyce elektronicky uložený a zpracovatelný. Historie/motivace • Indiánské jazyky nemají písmo - pro nalezení gramatiky potřeba nejprve sepsat mluvené slovo. o A967 -1. korpus v U. S. A. (Kučera, Francis) 1 000000 slov. • Noam Chomsky-odmítá korpusy, o Dnes - masové rozšíření. w □ s1 ^ ~T) Q^ (% Implementace indexových systémů Korpusy na Fl o WWW stránka Pavla Rychlého (~PARY) odkaz na základní informace. Bonito, Manatee. 0 IMS CORPUS WORKBENCH - sada nástrojů pro efektivní kódování, reprezentaci a dotazování nad velkými textovými soubory. □ g w •T) C^ (%• Vnitrní architektura korpusu Dva klíčové pojmy interní reprezentace pozičních atributů jsou: • Jednotná reprezentace: položky jsou pro všechny atributy za kó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 vjednom kroku. □ S1 w ■f)(\(y 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 poztční atribut word. Kromě tohoto atributu mohou být s každou pozicí svázány další poziční atributy libovolného textu představující morfologické a jiné značky. Strukturální atributy - vety, odstavce, nadpis, článek, SGML. P0S2 ?0SA 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 O, následující i atd. • Pro vyhledávání řetézce v našem seznamuje užitečné mít index na pozici začátku řetězce v tomto souboru. Tento index pro každý kód položky dává konverzi z kódu položky na relativní adresu (v bytech) v seznamu položek... Implementace indexových systémů Vnitrní architektura korpuôu (pokr.) Pro invertovaný soubor existují tři datové struktury: • První je samostatný invertovaný soubor, který obsahuje množinu korpusových pozic. o Druhý je index do tohoto 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ů). □ g w •T) C^ (%• Implementace indexových ôyôtému (pokr.) bs* Efektivní uložení indexu/slovníku [lemmat]: packed trie, Patricia tree, a další stromové struktury. is* Syntactic neural network (S. M. Lucas: Papid best-first retrieval from massive dictionaries, Pattern Recognition Letters i7, p. Í507-Í5Í2, A996). «s* Komerční implementace: Verity engine, webové vyhledávače většinou svůj klíč k úspěchu až na výjimky tají. □ S1 w ■f)(\(y Implementace indexových systémů Implementace indexových ôyôtému Přehled možných přístupů a implementací es* Invertovaný soubor - indexový soubor s bitovým vektorem. es* Použití seznamu dokumentů ke každému klíčovému slovu. es* Souřadnicový systém s ukazateli [MEL, obr. 4.ÍÔ, strana 46]. es- Indexace korpusových textů: Finlib http://www.fi.muni.cz/~pary/dis.pdf viz podklady [MAP]. es* Použití Eliášových kódů pro komprimaci seznamu hitů. □ s1 Implementace indexových systémů w ^ -ŕ) c\o Reprezentace olovníku KA Článek M. Mohri: On Some Applications of Finite-State Automata Theory to Natural Language Processing viz podklady [MAP] es* Reprezentace slovníku konečným automatem. es* Nejednoznačnosti, sjednocení minimalizovaných deterministických automatů. es* Příklad: done,do.V3:PP done.done.AO es* Morfologický slovník jako seznam dvojic [slovní tvar, lemma]. es* Kompaktace uložení datové struktury automatu (Liang, Í9Ô3). es* Kompresní poměr až i :20 při lineárním přístupu (vzhledem k délce slova). w □ s1 ^ ~T) Q^ (% Implementace indexových systémů Reprezentace olovníku KA bs Převodník (transducer) pro reprezentaci slovníku. bs Deterministický převodník s i výstupem (subsequential transducer) pro reprezentaci slovníku včetně jednoho řetězce na výstupu (informace o morfologii, dělení slov,...). is 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). is 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 vsak obvykle nenastává (nejsou zde cykly). □ g - ■= w •T) C^ (%• Vyhledávací metody IV. Předzpracování textu i vzorku (dotazu): drtivá většina dnešních TIS. Typy předzpracování: BS statistiky n-gramů (fragmentové indexy). Bs speciální algoritmy pro zpracování indexů (kódování, komprese) a vyhodnocení relevance (PagePank u Google). bs využití metod zpracování přirozeného jazyka (morfologie, syntaktická analýza, sémantické databáze) a agregace informací z více zdrojů (systémy AnswerBus, STAPT). bs signaturove metody. □ S1 w ■f)(\(y Implementace indexových systémů Reprezentace olovníku KA •s- Přidání stavu do převodníku odpovídajícího (w^,W2) bez porušení determiničnosti: nejprve stav pro (w-\,s), pak s výsledným stavem konečný stav s výstupem iV2. Efektivní metoda, rychlá, leč není minimální; existují minimalizacní 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. «s* Další použití i při efektivní indexaci, rozpoznávání řeči, atd. ES" ES" □ gl w ^ -ŕ) c\o 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ěď = skutečná odpověď Definice: Koeficient úplnosti R (recall) P = ^, 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 = 7, kde oje počet všech vybraných záznamů dotazem. Chceme docílit maximum P i P, tradeoff. Standardní hodnoty: 00% pro P, 20% pro P. Kombinace úplnosti a přesnosti: koeficient ft, = r2p+K ■ (Po = P> Fco = P. při Fa = F P a P váženy stejně). w □ s1 ^ ~T) Q^ (% Implementace indexových systémů Fragmentový index Vyhledávání pomocí f ragmentových indexů bs* Fragment ybd je v angličtině pouze ve slově molybden. bs" Výhody: pevný slovník fragmentů, odpadají problémy s aktualizací. bs' Nevýhody: závislost na jazyce a tématické oblasti, snížená přesnost vyhledávání. «□► < S> ► < -š ► « ^ •T) C^ (%• Google: Relevance Klíčové je určení relevance. BS" Využití značek textu a typografie webu pro výpočet relevance termů dokumentu. bs" Využití textu hypertextových odkazů na dokument odkazujících. □ S1 w ■f)(\(y Implementace indexových systémů Gooooooooooooooß\e Příklad anatomie globálního (hypertextového informačního systému (www.google.com). «s* Jeden z mála kvalitních vyhledávacích strojů, jehož základní principy a architektura jsou aspoň v principech známy- proto detailnější rozbor dle článku [GOO] http://www7.conf.au/programme/fullpapers/1921coml921.h1 es* Několik inovativních konceptů: PagePank, 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... es* Anatomie systému, viz podklady [MAP] w □ s1 ^ -ŕ) c\o Implementace indexových systémů Google: PagePank es* PageRank: objektivní míra důležitosti stránky na základě citační analýzy (vhodné pro utřídění odpovědí na dotaz, tedy určení relevance stránek). es* Nechť na stránku A ukazují stránky, X-\.....Tn (citace), a nechť O < d < i. Nechť C{A) je počet odkazů na stránce A. PagePank PR = (i - d) + d PR{TA C(Tn) es* PagePank se dá spočítat jednoduchým iterativním algoritmem (pro desítky milionů stránek za hodiny na běžném PC). es* PagePank je pravděpodobnostní rozdělení nad webovými stránkami. es* Motivace s náhodným surfařem, faktor d. w □ s1 ^ ~T) Q^ (% Implementace indexových systémů Datové struktury Google ts Uložení signatur souborů •^ Uložení lexikonu •^ Uložení seznamu hitů is Google File System Oenova (Týden osmý) □ g - = W •T) C^ (%• is Dokončení anatomie Google. is Kódování. •^ Entropie, redundance. «s Universální kódování celých čísel. □ g - = ^ ■T) q_ (y Část XII Kódování ^ □ S1 ^ -ŕ) c\o Kódování - základní pojmy Definice: Abeceda Aje konečná neprázdná množina symbolů. Definice: Slovo [řetězec, zpráva) nad Aje posloupnost symbolů z A. Definice: Prázdný řetězec e je prázdná posloupnost symbolů. Množinu všech neprázdných slov nad A značíme A+. Definice: Kód K je trojice (5, C,f), kde S je konečná množina zdrojových jednotek, C je konečná množina kódových jednotek, f : 5 —> C+ je injektivní zobrazení. f lze rozšířit na 5+ -> C+: F^Ss • • • Sk) = f (S-i )f (S2) • • • f (Sk). C+ se někdy nazývá kód. Základní vlaetnoetl kódů Definice: x G C+ je jednoznačně dekodovatelný vzhledem k f, jestliže existuje maximálně jedna posloupnost y G 5+ taková, že f (y) = x. Definice: Kód K = (S, C, f) je jednoznačně dekodovatelný 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á eufixový, 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 úp/ný jestliže po přidání libovolného dalšího kódového slova vznikne kód, který není jednoznačně dekodovatelný. □ g - = Kompreee a dekompreee W •T) C^ (%• Definice: Komprese [kódování), dekomprese [dekódování): ---------> původní data <--------- Komprese (kódování) ---------> komprimovaná data Dekompreee [dekódování) <- Definice: Kompresnípoměr je poměr délky komprimovaných data délky původních dat. Příklad: Navrhněte binární prefixový kód pro desítkové číslice, jestliže se často vyskytují čísla 3 a 4, a zřídka 5 a 6. □ g - = Základní vlaetnoetl kódu Definice: Blokový kód délky n je takový kód, při kterém všechna kódová slova mají délku n. Příklad: blokový ? prefixový blokový => prefixový, ale ne naopak. Definice: Kód K = [5,C, f) nazveme binární, jestliže \C\ = 2. Entropie a redundance W □ S - = -š -oo^o Nechť Y je náhodná proměnná s pravděpodobnostním rozdělením p(y) = P[Y = y). Pak matematické očekávání [strední hodnota) E(Y) = £yp(y). y€Y Nechť S = {x-i,X2.....xn} množina zdrojových jednotek a nechť pravděpodobnost výskytu jednotky x,- v informačním zdroji Sjep,- pro / = i.....n,nEH. Definice: Entropie informačního obsahu jednotky x-, [míra množství informace resp. neurčitosti) je H(x,-) = Hř = — log2/?í bitů. Zdrojová jednotka s větší pravděpodobností nese méně informace. Entropie a redundance II n Definice: Entropie informačního zdroje S je H(S) = — V p,- log 2 P i=1 bitö. Platí, že H(S) = £ p(y) log -i- = E Lg -?-Defi nice: Entropie zdrojové zprávy X — x\A x,-2... x/fc GS k k informačního zdroje S je H(X, S) = H(X) = V H,- = — V log21 bitů. Definice: Délka l(X) zakódované zprávy X k k 'M = 2>(x,,)| = 2>, bitů. Věta:/(X) >H(X,S). 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{5) blíží k i, když se entropie blíží oo. Definice: Kód K je universální, jestliže existují c^,c2 G K tak, že průměrná délka kódového slova AL{K) < c^ x AE + c2. Věta: Universální kód je asymptoticky optimální, jestliže c^ = i. □ g - = ^ ■f)t\(y Entropie a redundance III Axiomatické zavedení entropie viz podklady [MAR], detaily odvození viz ftp://www.math.muni.cz/pub/math/people/Paseka/lectures/kod< k Definice: R{X) = /(X) — H(X) = V(dřj. + log2 f^) je redundance kódu K pro zprávu X. n Definice: Průměrná délka kódového slova kódu K je AL(K) = TV/d,- i=A bitů. Definice: Průměrná entropie zdroje S je n n AE(S) = £/?/r/, = -^Pi \oq2Pi bi*0' Definice: Průměrná redundance kódu K je Universální kódování celých čísel Fibonacciho posloupnost a reprezentace Definice: Fibonacciho posloupnost rádu m fVi = FVi-rn + Fn-m+1 + . . . + F„_i pro H > i. Příklad: F řádu 2: F_^ = 0„ F0 = 1, FA = 1, F2 = 2, F3 = 3, F4 = 5, F5 = Ô,.. Příklad: F řádu 3: F_2 = O, F_-i = O, F0 = 1, FA = 1, F2 = 2, F3 = 4, F4 = 7, F5 = 13,... Příklad: F řádu 4: F_3 = O, F_2 = O, F_-i = O, F0 = 1, FA = 1, F2 = 2, F3 = 4, F4 = ô, F5 = 15,... Definice: Fibonacciho reprezentace K{N) = ^j=yl d\F\, kde d, E {O,A},dk = A Věta: Fibonacciho reprezentace není jednoznačná, existuje vsak taková, že v posloupnosti dřje nejvýše m — 1 po sobě jdoucích jedniček. ^ □ Si - = -š -OQ.O Fibonacciho kódy Definice: Fibonacciho kód řádu m FKm(N) = d^d^ ■ ■ ■ dk i ... i , kde ^-> m-i krát d\ jsou koeficienty z předchozí věty (jedničky ukončují slovo). Příklad: £(32) = 0*1+0*2 + 1*3 + 0*5 + 1*0 + 0*13 + 1*21, tedyF(32) =00101011. Věta: FK{2) je prefixový, universální kód s c^ = 2, c~2 = 3, tedy není asymptoticky optimální. □ g - = Universální kódování celých čísel III m- /{N) = a(\ß(N)\)ß'{N) stejné délky (permutace bitů )/(N)), ale čitelnější ■s- Cr/ = {/(N) :N>0} = {Ok1{0,1}k :k>0} není regulární a dekodér potrebuje čítač -s- <5(N) = K|P(W(N) «s- příklad: (5(4) = )/(3)00 = 01100 «s- dekodér (5: (5(?) = 0011? «3s co: K:=0; while Uog2(N)J >0 do begin K := ß{N)K; N := LN2(N)J end. w •T) q_ (y □ S1 - = ■T) Q^ (j* Universální kódovaní celých cisel II Eliášovy kódy «s- asymptoticky optimální universální kód, c^ = 1, do N = 5-14228 jsou lepší Fibonacciho kódy řádu n (FK(/i)). «• unární kód íí(N) = 00... 01. N-1 «• binární kód p{A) = A,ß(2N + j) = ß(N)j, j = 0,1. «s- p nem jednoznačne dekódovatelný (není prefixový). «s- ternárnít(N) = ^(N)#. ■s- ^(1) = e,p'{2H) =ß/{N)0,ß/{2N + 1) = ß'{M)1, ť (N) = ß'{H)#. «• y. každý bit/^(N) je vložen mezi dvojici bitů z a{\ß{M)\). «s- příklad: y(6) = 01001 «- CK = (KN) :N >0} = (0{0,-1})*-1 je regulární a tedy dekódovatelná Komprese dat - úvod ks* Kódování informace pro komunikační účely; komprese dat. es- Přes bouřlivý vývoj kapacit pro uložení dat stále nedostatek místa. ks* Redundance —> konstrukce minimálně redundantního kódu. ks* Model dat: • struktura - sada jednotek ke komprimaci + kontext výskytů; • parametry- pravděpodobnost výskytu jednotlivých jednotek. ks* Komprimace: O vytvoření modelu dat; © vlastní kódování. Komprese dat - vývoj is- ÍÔ3Ô Morse, kód e dle četnosti. bs' A949 Shannon, Fano, Weaver. BS' i 952 Huffman; 5 bitů na znak. bs' A979 Ziv-Lempel; compress (Roden, Welsh, Bell, Knuth, Miller, Wegman, Fiala, Green,...); 4 bity na znak. BS" osmdesátá a devadesátá léta PPM, DMC, gzip (zlib), SAKDC; 2-3 bity/znak bs' přelom tisíciletí bzip2; 2 bity na znak. B3T ...? □ g - ■= ^ •T) C^ (%• Predikce a modelování bs' redundance (nestejnoměrná pravděpodobnost výskytu zdrojových jednotek) bs" kodér, dekodér, model BS" statické modelování (model nezávisí na konkrétních datech) bs' semiadaptivní modelování (model závisí na datech, 2 průchody, nutnost přenosu modelu) daptivní modelování (i. průchod, model vytvářen dynamicky L- r\Aov* 2 znaku null, 255, speciální znak Sc «s run-length encoding (RLE) - SCXCC zobecnění na libovolný opakující se znak $***** *55 —> $SC * 655 as MNP Class 5 RLE - CXXX DDDDDBBAAAA -» bDDDBBAAAA as half-byte packing, (EBCDIC, ASCII) SI, SO BS diatomic encoding; na hrázování dvojic znaků jedním BS Byte Pair Encoding, BPE (Gage, Í994) BS pattern substitution BS Gilbert Held: Data & Image Compression □ g - ■= w •T) C^ (%• Shannon-Fano kódování Vstup: posloupnost n zdrojových jednotek S[/], -1 < / < 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-SPUT(S) end procedure SF-SPLIT(S); begin if \5\ > 2 then begin rozděl 5 do posloupností 5A a 52 tak, že obe posloupnosti mají přibližné stejnou celkovou pst; přidej ke všem kódovým slovům z 5A O; přidej ke všem kódovým slovům z 52 A; SF-SPUT(S-I); SF-SPUT(S2); end end w □ s1 - ■f)(\(y Statiôtické metody kompreôe •s- Shannon-Fano, Í949, model řádu O, prefixový kód, kódový strom. •s- kódová slova délky [—\oq2Pi\ neb° [_— log2 p,- + ■i J es AE příprava předem. Příklad: (2,2,2,2,4,4,0) □ fll - = w •T) C^ (%• Huffmanovo kódování- vlaôtnoôti Huff manových otromů Věta: Binární prefixový kód je Huffmanův<=> má sourozeneckou vlastnost. bs 2n — i uzlů, max. 2n — i možností, bs optimální binární prefixový kód, který není Huff manův bs ^(X) < pn + 0,006, pn maximální pravděpodobnost zdrojové jednotky. bs Huffman je úplný, (špatná detekce chyb). bs afixový kód, K.W1C, levý a pravý kontext, hledání *X* Huffmanovo kódování-ôourozenecká vlastnost Definice: Binární strom má sourozeneckou vlastnost právě tehdy, když O každý uzel kromě kořene má sourozence, O uzly mohou být seřazeny v pořadí neklesající posloupnosti tak, že každý uzel (kromě kořene) sousedící v seznamu s nějakým uzlem je jeho sourozenec (leví synové budou na lichých místech v seznamu a praví synové na sudých). w □ s1 ^ -ŕ) c\o Adaptivní Huffmanovo kódování •s- FGK (Faller, Gallager, Knuth) es" potlačení minulosti zapomínacím koeficientem, zaokrouhlování, i, 2 n •s* lineární čas kódování i dekódování vzhledem k délce slova. bs aLhd < 2ALHS. es Vitter ALhd < ALHs + I. bs implementační detaily, stromová reprezentace kódové tabulky. w □ S1 ~ = -š -Oo^O Princip aritmetického kódování ts zobecnění HufFmanova kódování (pravděpodobnosti zdrojových jednotek nemusí být záporné mocniny dvou). «s uspořádání na zdrojových jednotkách; Kumulativní pravděpodobnost cp-, = ^'JL^ p j zdrojové jednotky x,-s pravděpodobností p,-. «s Výhody: • libovolná blízkost entropii. • adaptivnostje možná. • rychlost. □ g - = w •T) c^ (%• Statické ôlovníkové metody Zdrojová jednotka délky n - n-qramy Nejčastější big rámy (n = 2) o n pevné • n proměnné (dle frekvencí výskytu) • adaptivní (50 % anglického textuje tvořeno asi i 50 nejfrekventovanějšími slovy) Nevýhody: • nejsou schopny reagovat na rozdělení pravděpodobností komprimovaných dat • předem připravený slovník w ■f)(\(y Slovníkové metody kompreôe dat Definice: Slovník }e dvojice D = {M, C), kde M}e 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 E M. Výbér zdrojových jednotek: • statický (dohoda na slovníku předem) • semiadaptivní (nutné dva průchody textem) • adaptivní w □ s1 ^ -ŕ) c\o Semiadaptivní ôlovníkové metody Slovník Komprimovaná data Komprimovaný slovník Komprimovaná data Výhody: rozsáhlá data (slovníkje malá část dat- korpusy; CQP). Semiadaptivní ôlovníkové metody- poetup vytvoření olovníku O Určí se frekvence N-gramů pro N = i, 2..... © Slovník se inicializuje vložením unigramů. © Do slovníku se postupně přidávajíN-grámy (N > i) s největší frekvencí. Při vložení K-gramu se snižuje frekvence jeho složek (K — i)-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. w 4 □ ► < fil ► < -š ► < LZR (Roden) •T) C^ (%• \M\ = {N - B) x B x ť, ť velikost abecedy L(m) = pog2(N-ß)1 + pog2ß1 + pog2ť| Výhoda: hledání nejdelší předpony [KMP] LZR (Rodeh) • 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. o Protože / v (/', j, a) může být velké, je použit Eliášův kód pro zakódování celých čísel. Nevýhoda: růst velikosti stromu bez omezení => po překročení vymezené paměti vymazán a konstrukce začíná od začátku. □ g - " w ■f)(\(y Adaptivní olovni kove metody Lem pel, Z\v 1977, 7b VĽ11 - metody posuvného okna LZ7Ô - metody rostoucího slovníku Metoda posuvného okna a b c b a b b a a b a c b zakódovaná část nezakód. cast (okno,N<Ô-192) (|ß| —10-20 b) Krok kódování LZ77 V zakódované části je vyhledána nejdelší předpona P řetězu v nezakódované oblasti. Pokud je takový řetěz 5 nalezen, pak P je zakódováno pomocí (/, J, A), kde /je vzdálenost prvního znaku 5 od hranice, J je délka řetézu 5 a A je první znak za předponou P. Okno je posunuto o J + -1 znaků doprava. Jestliže podřetéz 5 nalezen nebyl, pak je vytvořena trojice (O, O, A), kde A je první znak nezakódované části. LZSS (Bell, Storer, Szymanôki) Kódem je posloupnost ukazatelů a znaků. Ukazatel (/', j) potřebuje paměť jak p znaků => ukazatel jen tehdy, když ušetříme, aleje třeba bit na rozlišení znaku od ukazatele. Počet položek slovníku je |M| = t + {N — B) x [B — p) (uvažují se jen podřetězy delší než p). Počet bitů na zakódováníje • L{m) = i + f log2 ť] pro m ET • L(m) = i + pog2 N"! + pog2(ß - p)'] jinak. (Délku d podřetězu můžeme reprezentovat jako B — p). LZB (Bell), LZH (Brent) LZB (Bell) Ukazatel (/', 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í/. LZB používá fázování při bin. kód. - prefixový kód s rostoucím počtem bitů pro rostoucí hodnoty čísel. Pro kódování j používá LZB Eliášův kód y. LZH (Brent) LZSS, kde pro kódování ukazatelů je použito Huffmanovo kódování (tj. dle rozložení jejich pravděpodobností => 2 průchody) □ s> - ► « ^ ► .i ^ •T) C^ (%• LZ7Ô - příklad Vstupní a b ab c ba Index i 2 3 4 5 Výstu p (0,a) (0,b) (1,b) (O.C) (2,a) Vstupní bab aa ßßß ßßßß Index 6 7 ô 9 Výstup (5,b) (U) (7,a) (ô,a) □ [l? ^ ■f)(\(y Metody 6 roôtoucim olovníkem LZ7Ô Hlavní myšlenka: slovník obsahuje fráze. Nová fráze tak, že již existující fráze je rozšířena o symbol. Fráze je zakódována indexem předpony a přidaným symbolem. w □ ťS1 ^ -ŕ) c\o LZFG (Fiala, Green) 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. LZW (Welch), LZC LZW 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. a a Vstup Index Výstup ababcbababaa a 4 5 6 7 ô 9 -10 1 2 4 3 5 ô 1 -10 AA Přeplněním další fráze není předávána a kódování pokračuje staticky. LZC compress je to LZW + • Ukazatele jsou kódovány s prodlužující se délkou. • Jakmile se kompresní poměr začne snižovat, slovník se vymaže a začíná se od začátku. Oônova (Týden jedenáctý) «s" Slovníkové metody s restrukturalizací slovníku. ks- Syntaktické metody. «s Kontrola správnosti textu. ks" Dotazování a modely TIS. ks" Booleovský model dokumentů. ks" Vektorový model dokumentů. ks- Architektura TIS. ks" Signatu rove metody. ks" Podobnost dokumentů. ^ □ S1 ■T) q_ £V LZT, LZMW, LZJ LZT (Tischer) Jako LZC, ale při přeplnění slovníku se ze slovníku vylučují fráze, které byly v nedávné minulosti nejméně použity. Používá frázování při bin. kód. indexů frází. LZMW (Miller, Wegman) Jako LZT, ale nová fráze se nevytváří přidáním jednoho symbolu k předchozí, ale konstruuje novou frázi zřetězením dvou posledně zakódovaných. LZJ (Jakobsson) Jiný princip konstrukce slovníku: • Na začátku vloženy jednotlivé symboly. • Slovník uložen ve stromu a obsahuje všechny podřetězy zprac. řetězem do délky h. • Plný slovník => » statický postup, • vynechávání uzlů s nízkou frekvencí použití. ^ □ fli - = _š -o^O Slovníkové metody 6 reôtrukturalizací olovníku ks- Průběžné uspořádávávání zdrojových jednotek —> kratší řetězce kódu. ks- Varianty heuristik (četnost, přesun na začátek (BSTW), výměna s předcházejícím, přesun o K vpred). ks- BSTW (výhoda: vysoká lokalita výskytů menšího počtu zdrojových jednotek). es" Příklad: Já do lesa nepojedu.....A"2"k". es- Zobecnění: koeficient nedávnoeti, Intervalové kódování. w □ S1 ~ = -š -Oo^O Intervalové kódovaní Reprezentace slova celkovým počtem slov od posledního výskytu. Slovník obsahuje slova a^, a-z.....an, vstupní posloupnost x^, X2..... xm. Hodnota LAST(<3ř) obsahující interval od poeledního výskytu je inicializovaná na nulu. for t := i to m do begin {xt = a,} if LAST(xt = O) then y(ť) = t + i - A else y(ť) = ť - LAST(xt); LAST(xt):=ť end. Posloupnost yi, y2.....ym je výstupem kodéru a může být zakódována některým kódem proměnné délky. Kontextové modelování bs pevný kontext - model řádu N. bs kombinovaný přístup - kontexty různých délek. bs tvn pevné, proměnné. bs náročné na čas a paměť. «s přiřazení pravděpodobnosti nové zdrojové jednotce: e is automaty s konečným kontextem. Bs dynamické Markovovo modelování. c„+r Syntaktické metody Derivační kódování •s- je známa gramatika jazyka zprávy. bs levý rozklad derivačního stromu řetězce. bs globální číslování pravidel. bs lokální číslování pravidel. Analytické kódování bs jsou kódovány rozhodovací stavy LP analyzátoru. w □ s1 ~ = ^ -ŕ) c\o Kontrola eprávnoetl textu bs Kontrola textu pomocí frekvenčního slovníku. «s* Kontrola textu pomocí dvojitého slovníku. bs Interaktivní kontrola textu (ispell). bs Kontrola textu založená na pravidelnosti slov, koeficient podivnosti. w □ s1 ^ ~T) Q^ (% Koeficient poďwnoetl Koeficient podivnosti trig ram u xyz KPT = [log(f(xy) - A) + log(f(yz) - 1)]/2 - log (f (xyz) - A), kde f(xy) resp. f (xyz) jsou relativní frekvence digramu resp. trigramu, log(0)je definován jako —AO. Koeficient podivnosti slova KPS = , /^JKPTí - SKPT2), kde KPT{\e koeficient podivnosti /-té h o trigramu SKPT je střední hodnota koeficientu podivnosti všech trigramu obsažených ve slově. w □ ö - = -š-O^O 3\a\rovo ladění dotazu Vyhledávání spočívá ve zmenšování neurčitosti tazatele (ladění dotazu). Q Najdeme dokument s vysokou relevancí. © Začneme se dotazovat s jeho klíčovými slovy. O Odstraňujeme deskriptory, resp. je nahrazujeme disjunkcemi. □ g - = w ■f)(\(y Dotazovaní a modely TIS Různé metody hierarchizace a uložení dokumentů —> různé možnosti a efektivita dotazování. es- Booleovský model, SQL. es* Vektorový model. es* Rozšířené booleovské modely. es- Pravděpodobnostní model. es- Model shluků dokumentů. Infomap - enaha o ôé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ů. Booleovôký model bs 50. léta: reprezentace dokumentů pomocí množin termů a dotazování založené na vyhodnocování booleovských výrazů. bs Výraz dotazu: induktivně z primitiv: • term • jméno_atributu = hodnota^atributu (porovnání) o 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, notY. bs disjunktivní normálníforma, konjunktivní normální forma «s proximitní operátory is regulární výrazy is použití tezauru □ s> - ► « ^ ► .i w •T) C^ (%• Dotazování- SQL příklady ORACLE SQL*TEXTRETRIEVAL SELECT specifikace_polozek FROM specifikace_tabulek WHERE položka CONTAINS textovy_vyraz Příklad: SELECT TITLE FROM BOOK WHERE ABSTRACT CONTAINS 'TEXT' AND RT(RETRIEVAL) 'řetěz' 'řetěz'* *'řetěz' 'ře?ěz; 'ře°/,těz' 'řetěza' (m,n) 'řetězb' 'víceslovná fráze' BT('řetěz',n) BT('řetěz',*) NT('řetěz',n) w □ s1 ■f)t\(y Jazyky pro vyhledávaní - SQL •s- booleovské operátory and, or, xor, not. es poziční operátory adj, (n) words, with, same, syn. BS 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 PT(A) Related term TT(A) Top term w □ s1 ^ -ŕ) c\o Dotazování- SQL příklady Příklad: SELECT JMENO FROM ZAMESTNANEC WHERE VZDELANÍ CONTAINS RT(UNIVERSITA) AND JAZYKY CONTAINS 'ANGLIČTINA' AND 'NEMČINA' AND PUBLIKACE CONTAINS 'KNIHA' OR NT('KNIHA',*) w □ s1 ~ = ^ ~T) Q^ (% Stilesova technika/ asociační faktov asoc(Q/\,Qß) = log10 (fN - Aß - N/2)2N Aß(N-A)(N-ß) A - počet dokumentu „zasažených" dotazem Qa ß - počet dokumentu „zasažených" dotazem Qß (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í'I. generace, 2. generace,... «□► < S> ► < -š ► « ^ •T) C^ (%• Oenova (Týden dvanáctý) is' Vektorový model dokumentů (dokončení) bs Pravděpodobnostní model. bs Model shluků dokumentů. is Architektura TIS. BS Signaturove metody. Bs Podobnost dokumentů. BS Komprese pomocí neuronových sítí. □ S1 ^ ■T) q_ (jt- Vektorový model Vektorový model dokumentů: Nechť a^.....an termy, D^,.. dokumenty, a matice relevance IV = (w,j) typu m,n, -.0» w,,E {O,A) O není relevantní i je relevantní Dotaz (2= (^.....q„) • S{Q,Dj) = J^jCiiWij koeficient podobnosti • head(dort(5(Q.,Dj))) odpověď w □ S1 ~ = -š -oc\o Vektorový model: pro6 & cons CONS: nebere v úvahu ?"a"? ?"nebo"? PPOS: možné vylepšení: • normování vah • Frekvence termu TF • Inverzní frekvence dokumentu IDF = log2 j • Rozlišení termů o normování vah pro dokument: TO I,"3? • normování vah pro dotaz: ( ^ x m^^ j x log2 j [POK, strany 05-113]. TF w □ S1 ~ = -š -Oo^O Automatické ôtrukturevaní textů •^ Vzájemné vazby mezi dokumenty v TIS. •^ Encyklopedie (OSN, Funk and Wagnalls New Encyclopedia). ■s- [SBA] http://columbus.es.nott.ac.uk/compsci/epo/epodd/ep056g£ «s Google/CiteSeer: „automatic structuring of text files" □ g - = ^ •T) C^ (%• Seznam materiálů u Marečka [MAP] Materiály k predmetu PV030 ke zkopírovánív knihkupectví Mareček. © Slidy přednášek predmetu, 4 slidy na list A4. O kopie [MEL], © kopie [POK], O článek [MEH], © materiály o Google [GOO] (plus české shrnutí). © kapitola 5.7 z [KOR] (podobnost). © [MeM], © ostatní (NLP, diagram s kompresními algoritmy,...). □ g - = ■T) q_ (j* Signaturové metody Vyhledávací metody IV. Předzpracování textu i vzorku (signaturové metody). Signatury «s* řetězené «s* vrstvené Dále [POK, strany 65-76], viz podklady [MAP].