Predavanje 8 - Stringovi II

3. Pretrazivanje stringova

Problem: napisati algoritam (funkciju) koja ispituje pojavljuje li se manji string u vecem stringu.

Problemi ovakvog tipa su cesti u radu sa stringovima npr. svaki tekst editor sadrzi neki algoritam za pretrazivanje stringova.

Pretpostavke:

1. Brute-Force algoritam:

/* funkcija vraca indeks od kojeg pocinje manji string u vecem odnosno -1 ako string nije nadjen */ int pronadji(char* mali_string, char* veliki_string){ int i, j; for(i=0; veliki_string[i]!=0; i++) { for(j=0; mali_string[j]!=0; j++) if(veliki_string[i+j]!= mali_string[j]) break; if(mali_string[j]==0) return i; } /* string nismo nasli/ return -1; }

Analiza gornjeg algoritma
Osnovno pitanje koje se ovdje namece jest koliko je ovaj algoritam "dobar" tj. kolika je njegova slozenost.

Jedna ideja jest da se pokusa odrediti precizno vrijeme izvrsavanja programa unaprijed. Ovakav pristup moze biti vrlo kompliciran i zapravo nerjesiv iz ovih razloga:


Kao sto vidimo, drugaciji pristup je potreban u analizi algoritama. Najprije mi bi smo trebali strogo formalizirati (definirati) matematicki pojam algoritma . To je moguce, ali se mi time necemo baviti, vec cemo uzimati intuitivan pristup algoritmima koji stalno koristimo. Dakle kako izracunati slozenost algoritma?

Najprije treba odvojiti apstraktne operacije u algoritmu od njihove konkretne implementacije na danom racunalu (=operacijski sustav+hardware). Npr. u Brute Force algoritmu nas ce vise zanimati koliko se puta izvrsi ovaj dio koda
veliki_string[i+j]!= mali_string[j]
nego koliko traje izvrsavanje (u nanosekundama) odgovarajucih strojnih instrukcija u koje se prevodi taj kod. Mi brojimo apstraktne operacije: usporedjivanje, skok u programu, dijeljenje, zbrajanje, mnozenje i oduzimanje te usporedjivanje brojeva itd. Nismo zainteresirani kako su ove apstraktne operacije zapravo implementirane (strojni jezik).
Dakle realno vrijeme izvodjenja (eng. runing time) se odredjuje do na konstante koje ovise o konkretnoj realizaciji (programski jezik, operacijski sustav, hardware) iz broja apstraktnih operacija i vremena potrebnog za izvodnjenje pojedine strojne instrukcije za dano racunalo u danoj iskoristenosti sistemskih resursa. Npr. u Brute Force algoritmu, kako je duljina velikog stringa bila N, vrijeme izvodjenja dijela koda
for(i=0; veliki_string[i]!=0; i++)
je najvise (konstanta)N, gdje je N broj apstraktnih operacija, a (konstanta)>0 ovisi o implementaciji (tj. strojnom kodu racunala). Kao sto smo gore objasnili samu konstantu je tesko kontrolirati i za to nas zakljucak pisemo kao O(N).
U gornjoj recenici iskoristili smo rijec najvise, jer uzimajuci u obzir sve moguce ulazne podatke tj. parove mali_string, veliki_string, petlja se moze izvrsiti bilo koji broj puta izmedju 1 i N. Mi cemo u ovakvoj (matematickoj) analizi uvijek podrazumjevati najgori slucaj. Objasnimo notaciju O(N).

Pisemo g(N)=O(f(N)) ako postoji konstanta C>0 i N_0 prirodan broj t.d. |g(N)| < C f(N) za N> N_0.

Primjeri:
100N=O(N) 5N^2+2N-7=O(N^2) MN+7M+8N=O(MN)
Izracunajmo sada vrijeme izvodnjenja ili slozenost algoritma gore. Uocimo da je broj apstraktnih operacija potreban za Brute-Force je najvise N(2M+2), jer unutarnja petlja se izvrsi najvise M puta i unutar nje imamo jedno usporedjivanje if(veliki_string[i+j]!= mali_string[j]) break; dakle 2M apstraktnih operacija, dok vanjska petlja uz malu petlju sadrzi i usporedjivanje if(mali_string[j]==0) return i; i usporedjivanje u samoj petlji. Dakle slozenost je O(MN).
Primjedba: Apstraktne operacije nisu strogo definiran matematicki pojam i lako je pronaci malo modificiran nacin racunanja broj operacija operacija u nasem algoritmu da dobijemo broj razlicit od N(2M+2). Medjutim, sto je zajednicko bez obzira na nacin gledanja na apstraktne operacije jest da su one sve O(MN), a to je jedino vazno.

Ovako izracunata slozenost je za sve ulazne podatke tj. parove mali_string, veliki_string. U praksi ako npr. pretrazujemo tekst napisan na hrvatskom ili nekom drugom jeziku trazeci danu rijeci ili dio rijeci obicno se slozenost zapravo spusti na O(M+N). Radi se o tome da su stringovi napisani u alfabetu sa puno razlicitih znakova i za ocekivati je da u velikom dijelu slucajeva (tj. parova ulaznih podataka) u unutranjoj petlji je dovoljno samo provjera prvih nekoliko karaktera da ustanovimo nepodudaranje te da izadjemo iz unutarnje petlje. Dakle Brute-Force algoritam je zapravo dobar u vecini slucajeva.

Problem nastaje kada pretrazujemo (dugacak) tekst od samo nekoliko razlicitih karaktera npr. onaj koji sadrzi samo 0 i 1. Tada se dostize gornja granica slozenosti ovog algoritma. U tu svrhu postoje i algoritmi poput Knuth-Moriss-Pratt algoritma koji ima uvijek slozenost O(M+N), ali je znatno kompliciraniji nego ovaj naivan algoritam. Mi se necemo upustati u analizu ovog algoritma. Zainteresirani mogu ptogledati verziju u Pascalu u knjizi R Sedgewick, Algorithms, Princeton University, Second Edition.

Dakle postoji velika razlika izmedju empirijske i matematicke analize problema kojeg rjesavamo, koju treba uvijek imati na umu kod rjesavanja konkretnog problema u praksi. Kod rjesavanja konkretnog problema treba voditi racuna o vise faktora npr.

Sada cemo komentirati implementaciju Brute-Force algoritam u terminima standardne biblioteke i moguce probleme u vezi s tim.

2. rjesenje(lose rjesenje):

int pronadji(char* mali_string, char* veliki_string){ int i; for(i=0; i< strlen(veliki_string); i++) { if (strcmp(&veliki_string[i], mali_string)==0) return i; } return 0; }

3. rjesenje(lose ali malo bolje rjesenje):
Popravimo gornji kod.

int pronadji(char* mali_string, char* veliki_string){ int i; int duljina_velikog_stringa=strlen(veliki_string); for(i=0; i< duljina_velikog_stringa; i++) { if (strcmp(&veliki_string[i], mali_string)==0) return i; } return 0; }

Bolje rjesenje nego prethodno, medjutim ne tako dobro kao prvo jer opet bespotrebno povecavamo broj operacija racunajuci duljinu velikog stringa.


4. Sortiranje i pretrazivanje polja stringova

Problem:

Problemi ovakvog tipa su cesti u radu sa stringovima npr. rijeci u rijecniku su sortirane na ovaj nacin.

Koristit cemo:

Primjer:

#include <stdio.h> #include <stdlib.h> #include <string.h> /* funkcija cije ime prosljedujemo kao cetvrti argument u quicksort funkciji */ int usporedi(const void *i, const void *j){ return strcmp(*(char **)i, *(char **)j); } int main(int argc, char** argv ){ int i; char* kljuc="aa"; char** rezultat; /* obrisemo prvi argument sa liste koji je ime programa */ ++argv; /* smanjimo broj elemenata polja za jedan */ --argc; qsort(argv, argc, sizeof(char*), usporedi); for (i = 0; i < argc; i++) printf("%s\n", argv[i]); rezultat=(char**) bsearch(&kljuc, argv, argc, sizeof(char*), usporedi); if (rezultat) printf("Kljuc se pojavljuje kao element polja.\n"); else printf("Kljuc se ne pojavljuje kao element polja.\n"); }

5. Zadaci za vjezbu (tezi zadaci oznaceni zvijezdicom)

1. Napisite Brute-Force algoritam koristeci samo pokazivace.

2. Preradite program sa predavanja da sortira i pretrazuje cjelobrojne i realne nizove. Nadalje, napisite program koji sortira nizove u R^n koristeci leksikografski uredjaj.

3. Implementirajte svoju funkciju koja realizira binarno pretrazivanje iz sistemske biblioteke.

4. Implementirajte svoju funkciju koja realizira quicksort iz sistemske biblioteke.

5. Slozeni tip podatka sastoji se od imena i prezimena zaposlenika, njegovog JMBG-a, te broja od 1-10 koji predstavlja njegovu sifru. Zaposlenici su azurirani u bazi podataka koja je reprezentirana tekst datotekom u kojoj svaka linija izgleda ovako:

IME PREZIME JMBG broj od 1-10.
Napisite funkciju koja sortira uzlazno ovu bazu podataka. Ime datoteke se uzima sa komandne linije. Koji je uredjaj u pitanju?

6. Neka je dana sortirana baza podataka iz prethodnog primjera. Napisite program koji ucitava informacije o zaposleniku sa standardnog inputa, te u jednoj funkciji provjerava pojavljuje li se zaposlenik u bazi tako da vraca -1 ako nema zaposlenika u bazi odnosno broj retka u bazi ako ga je nasla, a u drugoj funkciji upisuje novog zapolenika u bazu.