Textove informacne systemy	-- Juraj Michalek (georgik@host.sk)

==== Uvod ====

Informacny sysytem
	- system umoznujuci ucelne usporiadanie, zber, uchovavanie
	  a spracovavanie dat

Ekosystem IS
	- uzivatelia IS (user)
	- investor (funder)
	- prevadzkovatel (server)
	- mimo kontrolu designera

Endosystem IS
	- media
	- devices
	- algorithms
	- data structures
	- pod kontrolou designera

Udaj
	- konkretne vyjadrenie spravy vo forme postupnosti znakov abecedy

Informacia
	- odraz poznaneho stavu skutocnosti
	- zavisi od subjektu 
	- kvalitativne (teorie informacie)
	- kvalitativne (vyznam, semantika)
	- pragmaticke (hotnotove)
	- ostatne (dostupnost)

Informacny proces
	- proces vzniku informacii
	- ich zobrazenie vo forme udajov
	- spracovanie, poskytovanie, vyuzivanie

Spracovanie textu
	- ad fontes - vyhladavanie v samotnom texte
	- text surrogate - vyhladavnie v nahradnom texte
	- index - usporiadany zoznam vyznamnych prvkov textu s odkazmi na
	  povodny text
	- signatura - retazec priznakov vyznamnych pre text

Naivne vyhladavanie
	- V - vzor
	- T - text
	- horny odhad O(VxT)

Upraveny algoritmus S
	- O(3T+3)

Upraveny algoritmus Q
	- zarazky
	- O(2T+5)

Upraveny algoritmus Q'
	- zarazky + expanzia cyklu
	- O(T+[T/2]+6)

Predspracovanie vzorku
	- na zaklade vzorku je zostaveny vyhladavaci stroj
	- proximitne - presne vyhladanie vzorku
	- susmerne - porovnavanie zlava doprava

Shift-Or
	- incidencna matica
	- stlpce zodpovedaju znaku aj
	- na zaciatku je v R jednotkovy stlpec
	- po kroku sa posunie
	- prevedie sa OR
	- algoritmus konci uspesne ako na dolnom rohu je 0



==== Predspracovanie vzorku ====

Knuth-Morris-Pratt
	- straty v pripade naivneho algoritmu vznikaju tak,
	  ze v pripade nezhody sa vzor posuva uba o jednu poziciu.
	- texte je nasledne opat kontrolovany
	- v pripade nezhody je dobre posunut vzorku, tak aby nebolo nutne
	  sa vracat
	1. porovnaj znak so vzorkou
		1.1 ak sa zhoduje pokracuj s dalsim
		1.2 ak sa nezhoduje skoc o h
	- zlozitost O(T) + prespracovanie O(V) = O(T+V)
	- h sa uplatnuje na predponu vzorku
	- vybudovanie H:
		- zober si dve sipky - i,j
		- sipku i umiestni pod druhe pismeno
		- sipku j umiestni pre prve pismeno
		- do policka h si na prvu poziciu umiestni 0
		- teda: j^ai^bcda
		- testujes ci sa znaky na ktore sipky ukazuju zhoduju
		- ak sa nezhoduju cyklis:
			- posunies obe sipky doprava
			- ak sa pismenka pod sipkami nezhoduju, zapis si,
			  do h, ze i sa skace na poziciu j
			- ak sa zhoduju, potom si zapis do h,
			  ze skaces z i tam, kde sa z skace z j (h[j])
			  to uz mas totiz zapisane
			  (break vnutorneho cyklu)


==== Vyhladavacie algoritmy ====

Axiomy (Salomaa)
	- x+(y+z)	= (x+y)+z
	- x.(y.z)	= (x.y).z
	- x+y		= y+x
	- (x+y).z	= xz+yz
	- x.(y+z)	= xy+xz
	- x+x		= x
	- e.x		= x
	- 0.x		= 0
	- x+0		= x
	- x*		= e+x+x.x+x.x.x ...
	- x*		= (e+x)*

Dlzka regularneho vyrazu
	- pocet vsetkych symbolikov

Derivacia
	- dV/de = V	(pri derivovani podla epsilon sa nic netrha)
	- derivacia podla jedneho pismena:
	 - de/da = 0
	 - db/da = 0
	 - da/da = e
	 - d(U+V)/da = dU/da + dV/da
	 - d(U.V)/da = dU/da.V + dV/da - ak vyraz U generuje prazdne slovo 
	 - d(U.V)/da = dU/da.V - ak vyraz U negeneruje prazdne slovo
	 - dV*/da = dV/da.V*
	- derivacia podla viacerych znakov
	 - zderivuje sa vyraz podla prveho znaku
	 - to sa zderibuje podla druheho
	 - a tak dalej

==== Vyhladavacie stroje ====

2DKAS
	- deterministicky automat
	- okrem citacej hlavy ma este znacku skoku
	- maximalna abstrakcia nad vyhladavacimi strojmi
	- 2DKAS -> DKA -> AC -> KMP	- dopredne vyhladavanie
	- 2DKAS -> BUC -> CW -> BM	- protismerne vyhladavanie

R-vzdialenost - dvoch vyrazov
	- Hammingova - replace
	- pocet nahradenych znakov

DIR-vzdialenost
	- Levenshteinova - delete, insert, replace
	- pocet zmazanych, vlozenych a nahradenych znakov

DIRT-vzdialenost
	- zovseobecnena Levenshteinova - delete, insert, replace, transpose
	- pribudla moznost nahrady

Dimenzie
	- seQuence, String
	- Sub pattern, Fullpattern
	- Infinite, Finite, One
	- Exact, R-matching, DIR-matching, DIRT-matching
	- Care, Don't care
	- One, Sequence of
	
	- SFOECO - pocet stavov m+1
	- QFOECO - pocet stavov m+1 (do kazdeho vedie loopback)
	- SSOECO - pocet stavov m(m+3)/2 - treelis - stromcek
	- SFORCO - Hamming-R - pyramidka - k je pocet replacov
		- (k+1)(m+1+k/2) - R-treelis
	- SFODCO - DIR - pocet stavov je rovnaky
		- pribudaju prechody

Karp-Rabin
	- odlisny pristup
	- namiesto prikladania vzorku k textu a jeho porovnavania
	  sa kontroluje zhoda iba tam, kde to vyzera podretazec vyzera podobne
	- podobnost urcuje hash funkcia
	- najhorsi pripad je kvadraticka zlozitost
	- priemerna O(T+V)
	- vypocita sa hash pre vzorku
		- napr. kazdy znak je umocneny
	- pri kazdom kroku sa porovnava vysledok hashu
		- pokial dojde k zhode porovnaju sa retazce
	- pri kazdom kroku sa prepocita hash na zaklade predchadzajucej
	  hodnoty a aktualneho znaku



=== Dokoncenie vyhladavania ====

Index
	- dlzka indexu = i
	- dlzka slova = V
	- O(V * log_2(i))

Dvojity slovnik
	- k a i su zrovnatelne

Invertovany subor
	- slovo -> priznaky na dokumenty, kde sa nachadza
	- kuk -> 0 0 1 1 0 1

Zoznam dokumentov
	- slovo -> zoznam dokumentov
	- kuk -> 1,2,6

Suradnicovy system
	- ukazatel do zoznamu dokumentov
	- zoznam dokumentov ukazujuce na dokumenty

Indexovanie
	- stop-list - slova s gramatickym vyznamom
	  (nema zmysel indexovat)
	- pass-list - slova relevantne - tezaurus

Zipfov zakon
	- poradie x frekvencia = konstanta

Automaticke indexovanie
	- Collins a Cobuild
	- pre kazde slovo je spocitany vyskyt
	- urci sa hranica a slova s vacsim vyskytom sa vyhodia

Lematizacia
	- vytvaranie tezuru na zaklade slovnych kategorii
	- flektivne jazyky
	- urcuje sa kmen slova
	- pri budovani indexu sa casto stava, ze rovnake slova su v texte sklonovane

Tezaurus
	- hierarticke a asociativne vztahy medzi slovami
	- vazba na synonnymum - vazba na iny termin
	- vazba na pribuzny termin - related term
	- vazba na obecnejsi termin - broader term
	- vazba na uzsi termin - narrower term

Indexovacie projekty
	- WORDNET
	- EUROWORDNET

Spracovavanie indexov pre prirodzeny jazyk
	- vyhladavanie retazcov
	- slovotvorba, morfologicka analyza
	- gramaticka, syntakticka analyza (CFG, DFG)
	- vyznam viet, semanticka analyza - TIL
	- kontextova pragmaticka analyza

Korpusy
	- BNC, Pen Treebank, DESAM, PNK

Korpusove manazery
	- CQP, GCQP, Bonito

GARLSH
	- gramatical hierartical statical lexicons



==== Spracovanie indexov ====

topic
	- spracovanie semantickych map
	- Tovek Tools, Verity

Patricia tree
	- packed tree
	- S. M. Lucas

Aplikacia automatu
	- M. Mohri
	- reprezentacia slovniku ako konecneho automatu
	- Liang - ulozenie datove struktury automatu
	- kompresny pomer 1:20
	- linearny vzhladom k dlzke slova
	- transducer - prevodnik na slovnikovu reprezntaciu
	- determinizacia transducer-u je vo vacsine pripadou nerealizovatelna

Fragmentovany index
	- indexovanie nie celymi slovami ale iba podretazcami
	- nie su problemy a aktualizaciou
	- je zavisly na konkretnom jazyku

Relevancia
	- miera rozsahu, ktorymi sa dokument zhoduje s poziadavkami
	- idealna odpoved - skutocna odpoved

Koeficient uplnosti - R
	- recall
	- R = m/n - m je pocet vybranych relevantnych, n je celkovy pocet relevantnych

Koeficient presnosti - P
	- precision
	- P = m/o - o je pocat vsetkych zaznamov vybranych dotazom
	- idealny tradeoff R = 20%, P = 80%

PageRank
	- !!!OBJEKTIVNA!!! miera dolezitosti stranky na zaklade citacnej 
	  dolezitosti
	- umoznuje vhodne zotriedenie stranok
	- pravdepodobnostne rozlozenie nad webovymi strankami

Blairove ladenie dotazu
	- vyhladavanie spociva v zmensovani neurcitosti dotazovatela
	- ladenie dotazu
	1. najdeme dokument s vysokou relevanciou
	2. zacneme sa dotazovat jeho klucovymi slovami
	3. odstranujeme deskriptory dokumenty, ktore nie su podstatne
	   a tym padom vylucujeme dokumenty, ktore maju nepodstatne
	   vlastnosti

Boolovsky model
	- dokument je reprezentovany mnozinou termou
	- vyhodnotenie je realizovane formou vyhodnotenia boolovskeho
	  vyrazu
	- pouzivaju sa boolovske operatory

SQL
	- BT(A) - broader term
	- NT(A) - narrower term
	- PT(A) - preffered term
	- SYN(A) - synonym
	- RT(A) - related term
	- TT(A) - top term

Stilesova technologia
	- aosciacny faktor
	- Q1, Q1 dotazy
	- A pocet zasiahnutych dokumentov dotazom Q1
	- B pocet zasiahnutych dokumentov dotazom Q2
	- f pocet zasiahnutych oboma
	- N celkovy pocet dokumentov
	- cutoff - hranica urcujuca zobrazenie relevantnych dotazov



==== Kodovanie ====

Jednoznacne dekodovatelny kod
	- kazdy kod je jednoznacne zobrazitelny na prvok z abecedy

Prefixovy
	- ziadne slovo nie je prefixom ineho

Sufixovy
	- ziadne slovo nie je sufixom ineho

Afixovy
	- kod je zaroven sufixovy aj afixovy

Uplny kod
	- pri pridani noveho kodoveho slova vznikne kod, ktory uz
	  nie je jednoznacne dekodovatelny

Blokovy kod dlzky n
	- vsetky slova maju rovnaku dlzku

Entropia jednotky
	- p_i je pravdepodobnost (<=1)
	- H_i = - log_2 p_i bitov
	- zdrojova jednotka s vacsou pravdepodobnostou nesie menej informacie

Entropia informacneho zdroja
	- H(S) = sum p_i * H_i
	- H(S) = - sum p_i * log_2 p_i

Entropia zdrojovej spravy
	- H(S,X) = - sum log_2 p_i

Redundancia kodu pre spravu
	- R(X) = dlzka spravy - H(X)

Priemerna dlzka kodoveho slova
	- d_i je dlzka slova
	- AL(K) = sum p_i * d_i

Priemerna entropia zdroja
	- AE(S) = - sum p_i * log_2 p_i

Priemerna redundancia kodu
	- AR(K) = AL(K) - AE(S)

Optimalny kod
	- ma minimalnu redundanciu

Asymptoticky optimalny kod
	- priemerna dlzka slova / entropia zdroja
	- AL(K)/AE(S) sa blizi 1
	- inak povedane entropia sa blizi nekonecnu

Univerzalny kod
	- existuje horna hranica pre dlzku slova
	- ked je hranica priamo entropia - jedna sa o symptoticky optimalny kod

Fibonaciho kod n-teho radu
	- n predstavuje pocet cisel, ktore tvoria svojho naslednika
	- pri normalnom kode je to 2
	- FK(2) - prefixovy, univerzalny, nie je asymptoticky optim.

Eliasove kody
	- asymptoticky optimalny kod
	- unarny kod - alpha
		- n-1 nul a na zaver 1
	- binarny kod - beta
		- nie je jednoznacne dekodovatelny
	- gama kod
		- kazdy bit bety je vlozeny medzi alfa kod
	- delta kod
		- ako gama, ale na konci sa nachadzaju 2
		  jednicky vedla seba
		- predstavuje to akusi zarazku
	- omega kod
		- postupne retazenie beta kodov
		- zapisem 0
		- zapisem pred zapisany retazec - beta(n)
		- zmensim n = log_2 n




==== Tvorba kodu ====

Staticke modelovanie
	- model nezavisi na datach

Semiadaptivne modelovanie
	- zavislost na datach
	- nutne dva priechody
		- vybudovanie modelu
		- kodovanie

Adaptivne modelovanie
	- model je dynamicky tvoreny priamo zo vstupnych dat

Predpovedanie
	- model radu 0 - pravdepodobnost izolovanych jednotiek
	- modely s konecnym kontextom - Markov
	- modely zalozene na konecnych automatoch - synchronozacne retazce

Znakove techniky
	- null supression - mahradenie opakovania >2
		- vyuziva sa specialny znak (napr.255)
		- vo vyzname escape sekvencie (si myslim :)
	- Run-lenght encoding - kodovanie za behu
		- escape znak, opakovany znak, pocet opakovani

Shano-Fannovo
	- zotried podla frekvencie vyskytu
	- rozdel frekvencie zhruba na rovnake skupiny podla ich suctu
	- jednej skupine prirad 0 a druhej 1
	- opakuj pokial nerozbijes zoznam na sastatne prvky - tie sa listy
	- nie je optimalny
	- 2 priechody pri statickom modele

Hufman
	- zotried zoznam frekvencii vyskytu
	- sprav z nich uzly
	- zober dva najmenej frekventovane
	- vytvor im rodica a daj mu frekvenciu = suctu frekvencii deti
	- deti vyhod zo zoznamu a vloz tam uzol
	- opakuj - zober najmenej frekventovane
	- s uzlom pocitas ako by bol pismenkom :o)
	- simple nie?
	- optimalny kod (existuje viac moznosti kodovania)
	- O(n) - v pripade, ze jednotky su uz dopredu zotriedene
	- surodenecka vlastnost - kazdy uzlik okrem korienku ma surodenca
	- binarny prefixovy kod je hufmanov <=> ma surodenecku vlastnost
	- uplny kod - problematicka detekcia chyb

!!!Optimalny binarny, ktory nie je prefixovy!!!
	- staci narusit strom, tak aby nie kazdy uzol mal surodenca

Afixovy kod
	- KWIC - key word in context
	- berie sa lavy a pravy kontext

Adaptivne kodovanie
	- Faller, Gallager, Knuth - FGK
	- minulost je potlacena zabudacim koeficientom

Aritmeticke kodovanie
	- zovseobecnene huffmanove kodovanie
	- pravdepodobnost nemusi byt mocninou dvojky




==== Slovniky ====