Iskanje niza v besedilu

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2012
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[S. Pukšič]
UDC:	51(043.2)
COBISS:	19144456
Views:	1560
Downloads:	99
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	String matching
Secondary abstract:	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.
Secondary keywords:	pattern;string;searching;matching;algorithm;naive;brute-force;Rabin-Karp;finite automata;time complexity;space;complexity;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	63 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19947