Iskanje niza v besedilu

diplomsko delo

Sergej Pukšič (Avtor), Aleksander Vesel (Mentor)

Povzetek

Besedilo B in niz S sta zaporedji znakov iz abecede ... Pri problemu iskanja niza v besedilu želimo poiskati vse ponovitve niza S v besedilu B. V ta namen so v prvem poglavju diplomskega dela predstavljene teoretične osnove. Opisan je princip snovanja in ob tem predstavljen postopek ocenjevanja časovne in prostorske zahtevnosti algoritmov. Drugo poglavje je namenjeno teoretičnim osnovam, ki se pojavljajo pri problemu iskanja niza v besedilu. Predstavljena je definicija, nato so opisane lastnosti in zakonitosti, ki se pojavljajo tekom iskanja nizov v besedilu. Naslednja poglavja so namenjena predstavitvi treh algoritmov, ki se uporabljajo pri nalogah iskanja niza v besedilu. Opisane so njihove lastnosti, njihovo delovanje je predstavljeno z različnimi grafičnimi prikazi ter psevdokodo. Za vsakega izmed njih je prav tako predstavljena ocena časovne zahtevnosti.

Ključne besede

matematika;niz;besedilo;iskanje;ujemanje;algoritmi;končni avtomat;čas;zahtevnost;prostor;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2012
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[S. Pukšič]
UDK:	51(043.2)
COBISS:	19144456
Št. ogledov:	1560
Št. prenosov:	99
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	String matching
Sekundarni povzetek:	The text B and string S are sequences of characters from the alphabet ... The problem of string matching is to find all occurences of the string S in the text B. For this purpose the first chapter presents the theoretical basics. The design principle is described, while the evaluation of algorithm's time and space complexity is presented. The second chapter is devoted to theoretical foundations that are encoutered through the process of string matching. Definition and description of characteristics and principles that may arise during the string matching process is described. The following chapters are intended to present three algorithms that are used in string matching tasks. Described are their properties while their actions are presented with various graphical presentations and pseudocode. For each of them the evaluation of time complexity was also made.
Sekundarne ključne besede:	pattern;string;searching;matching;algorithm;naive;brute-force;Rabin-Karp;finite automata;time complexity;space;complexity;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	63 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19947