Student1 – Nikola Kolovic RA133/2017
Trie stablo
Trie stablo je struktura podataka koja je pogodna za cuvanje stringova. (primer: cuvanje svih reci iz teksta). Za potrebe programa Search Engine koristili smo standardni trie. Standardni trie ima osobinu da svaki cvor osim korena sadrzi jedan karakter i putanja od korena do lista daje jedan string.















Standardni trie trosi O(n) prostora gde n predstavlja ukupnu duzinu stringova.
Za dodavanje i pretragu elemenata trosi O(dm) vremena, m- duzina stringa, d- velicina alfabeta
TrieNode se sastoji od elemenata (char(karakter), children(niz dece za svaki cvor), endOfWord(Boolean koji cuva da li se u datom cvoru zavrsava rec) i polje stranice koje predstavlja set html linkova koje sadrze datu rec (polje stranice je neprazno samo ukoliko je endOfWord=True)
Dodavanje elemenata u trie:
add_word(word,file)
Input: word: rec koja se unosi
Input: file: fajl u kojem je pronadjena
1.	Za trenutni cvor postavljamo root cvor
2.	Prolazimo kroz sve karaktere koji se nalaze u reci
3.	Ako se karakter ne nalazi u polju children tekuceg cvora
a.	U children trenutnog cvora dodajemo cvor sa tekucim karakterom
4.	Za trenutni cvor postavljamo cvor koji sadrzi dati karakter u children
5.	Ukoliko nismo prosli kroz sve karaktere u reci vracamo se na korak 2
6.	U suprotnom, trenutnom cvoru postavljamo vrednost endOfFile na true
7.	U polju stranice dodajemo u skup dati html file

Pretraga elemenata u trie:
search(word)
Input: word – rec koja se pretrazuje
1.	Za trenutni cvor postavljamo root cvor
2.	Prolazimo kroz sve karaktere koji se nalaze u reci
3.	Ako se karakter ne nalazi u polju children tekuceg cvora
a.	Rec nije pronadjena, vracamo string “False” i None
4.	Za trenutni cvor postavljamo cvor koji sadrzi dati karakter u children
5.	Ukoliko nismo prosli kroz sve karaktere u reci, vracamo se na korak 2
6.	U suprotnom, rec je pronadjena, vracamo “True” i polje stranice

Parsiranje i validacija unosa obicne pretrage
Parsiranje obicne pretrage:
	Parsiranje obicne pretrage parsira uneti kriterijum tako sto pomocu funckije .strip() otklanja
	sve praznine ispred prvog karaktera i iza poslednjeg. Zatim zamenjuje sve tabove sa praznim
	stringom(brise unete tabove sa tastature) pomocu funkcije .replace(‘\t’,’’). Zatim kreira novi
	niz kriterijuma pomocu komande re.split(‘  ‘, kriteterijum) tako sto splituje string po razmaku
	i stavlja u niz kriterijuma. U slucaju da je korisnik uneo vise razmaka jedan pored drugog u
	nizu kriterijuma ce se pojaviti razmak, koji moramo ukloniti da bi niz kriterijuma sadrzao
              samo operatore i reci koje pretrazujemo.
	Primer: input: “    python    		and	java		“
		output: [“python”,”and”,”java”]
Validacija unosa obicne pretrage:
Validacija unosa pretrage sluzi da proveri da li je kriterijum u pravilnom formatu. Za potrebe
ovog programa uzeli smo da je skup operatora (OR,AND,NOT, “ “ prazan string ce gledati kao OR operator).
Pravilan format unosa: Uslov1 OPERATOR Uslov2 | NOT Uslov1 | Uslov1 Uslov2 … UslovN
U prvom slucaju izmedju 2 uslova mora se nalaziti operator, u drugom slucaju se radi negacija uslova tako sto nakon operatora “NOT” ide uslov, treci slucaj je kada unosimo N uslova izmedju kojih se nalazi razmak koji se ponasa kao operator “OR”
U slucaju kada je ispostovan format unosa funkcija vraca True, u suprotnom False.



Obicna pretraga
slozenijaPretraga(kriterijum, operacija)
input: kriterijum – niz kriterijuma pretrage
input: operacija – string koji pokazuje koju operaciju izvrsiti nad nizom kriterijuma(“OR”,”AND”,”NOT”,”KOMPLEMENT”)
Algoritam:
	1.Pomocu if-elif proveravamo koji je operator pretrage i ulazimo u odgovorajuci blok
	2.Ukoliko je operacija “OR”
		a. Iteriramo kroz sve uslove u kriterijumu
		b. Pozivamo pretrazivanje iz globalnog trie stable
		c. Ukoliko je rec iz uslova pronadjena u RESULT_SKUP dodajemo skup html stranica
                                 u kojima se ta rec nalazi
		d. Ukoliko nismo dosli do kraja niza kriterijuma vracamo se na korak a), u suprotnom
		e. Prolazimo kroz sve skupova HTML dokumenata koji ispunjavaju uslov i pomocu
                                 operacije | ugradjene u Set odredjujemo RESULT_SET
	3.Ukoliko je operacija “AND”
		a. Iteriramo kroz sve uslove u kriterijumu
		b. Pozivamo pretrazivanje iz globalnog trie stable
		c. Ukoliko je rec iz uslova pronadjena
			c1. Ukoliko je kriterijum prvi, u RESULT_SET stavljamo pretrazeni skup
                                                  stranica da ne bi radili operaciju & sa praznim skupom
			c2. Ukoliko je kriterijum drugi, njega smestamo u drugu promenljivu
		d. Kada prodjemo kroz sve uslove, pomocu operacije & ugradjene u Set odredjujemo
                                  RESULT_SET
	3.Ukoliko je operacija “NOT”
		a. Ponavljamo korake a), b),c) iz koraka 3.
		b. Pomocu operacije – ugradjene u Set odredjujemo RESULT_SET
	4.Ukoliko je operacija “KOMPLEMENT”
		a. Pretrazujemo trie za zadati kriterijum
		b. Ako je za dati kriterijum pronadjen skup html fajlova taj skup stavljamo kao
		    rezultujuci
		c. U odnosu na taj rezultujuci skup radimo komplement pomocu funkcije u Set-u
                                 i dobijamo trazeni RESULT_SET




Napredna pretraga(#parser)
Parsiranje za naprednu pretragu je napravljeno tako sto se kriterijum pretrage prebacuje iz infiksne u postfiksnu notaciju, zatim iz postfiksne notacije u stablo parsiranja. Stablo parsiranja je binarno stablo.
Prebacivanje kriterijuma iz infiksne u postfiksnu notaciju(Algoritam)

Uvodimo mapu prioriteta(kljuc je operator a vrednost je prioritet), “!” ima najveci prioritet 4,  “&&” ima prioritet 3, “||” ima prioritet 2 i “(“ ima prioritet 1.
Takodje uvodimo brojac koji ce brojati uzastopno pojavljivanje obicne reci, to znaci da ukoliko imamo vrednost brojaca vecu od 0 znaci da se kriterijum pojavio uzastupno 2 ili vise puta a da izmedju nije bilo operatora (u specifikaciji se podrazumeva “||”).
	1.Iteriramo od prvog do poslednjeg stringa u kriterijumu
	2.Ukoliko naidjemo na levu zagradu stavimo je na stek i resetujemo brojac na 0
	3.Ukoliko naidjemo na desnu zagradu sve dok se na vrhu steka ne naidje na levu zagradu
                  skidamo element sa vrha steka i stavljamo u rezultujuci niz i resetujemo brojac na 0
	4.U slucaju da naidjemo na operatore “!”,”||” ili “&&” sve dok stek nije prazan i prioritet
                  vrha steka je veci ili jednak prioritetu trenutnog operatora u rezultujuci niz stavljamo
                  vrednost sa vrha steka, nakon cega stavljamo operator u rezultujuci niz i resetujemo brojac
	5.Ukoliko naidjemo na obicnu rec(kriterijum), kriterijum pretrage ubacujemo u rezultujuci
	   niz, takodje proveravamo ako je brojac veci od 0 dodajemo u rezultujuci niz i “||”, nakon
	   cega uvecavamo brojac
	6.Kada prodjemo kroz sve kriterijume u rezultujuci niz ubacujemo sve preostale elemente
	    sa steka
Kreiranje binarnog stabla (stablo parsiranja) – Algoritam
	1.Iteriramo kroz elemente niza kriterijuma koji je u postfiksnoj notaciji
	2.Ukoliko element nije operator kreiramo cvor stable i stavljamo na stek
	3.U suprotnom, ukoliko je element operator
		a. Ako je u pitanju “!” kreiramo cvor sa vrednoscu “!” a za levo dete stavljamo
		    element sa vrha steka, desno dete ostaje prazno(None)
		b. Ako je u pitanju neki drugi operator kreiramo cvor sa vrednoscu tog operatora
		    i kao levo i desno dete postavljamo prve dve vrednosti sa vrha steka
		c. Na stek stavljamo novokreirani cvor
	4.Kada se zavrsi iteriranje kroz elemente na vrhu steka se nalazi root cvor