20.500.12556/RUL-29497 Analiza algoritmov za iskanje podnizov s pomočjo sistema ALGator diplomsko delo Analysis of the string searching algorithms with the ALGator system Iskanje vzorcev v besedilih je zelo pomembno opravilo v veliko vedah. S pomočjo računalniških programov je ta postopek hiter in učinkovit, vendar so za to potrebni optimizirani algoritmi oziroma postopki. V tem delu obravnavamo deset različnih algoritmov, med katerimi ima vsak svoje lastnosti in uporabnosti, od zahtevnosti implementacije, iskalnega časa do odvisnosti od porabe sistemskih zmogljivosti oziroma prostora. Zaradi želje po prikazu delovanja algoritmov v praksi je v delu prikazano iskanje v naprej določenih vzorcih, kot tudi čisto naključnih vzorcih v različno strukturiranih besedilih. Analiza je sestavljena iz primerjav najkrajšega iskalnega časa in povprečnega iskalnega časa, pri opisih algoritmov pa je povzeta še prostorska zahtevnost za vsak algoritem posebej. Algoritmi so implementirani in analizirani s pomočjo okolja za analizo algoritmov ALGator, razvitega z strani doc. dr. Tomaža Dobravca. Rezultati so primerjani na podlagi teoretičnih pričakovanj. Searching for patterns in texts is a very important task in numerous scientific fields. Using computer programs makes the procedure fast and efficient, however, it requires optimised algorithms or procedures. In this thesis we look at ten different algorithms with different characteristics and applications, from level of difficulty of implementation and search time to dependency on system capacity or storage usage. Because we wish to illustrate the practical operation of algorithms, we show how these algorithms search for specific patterns set in advance, as well as completely random patterns in variously structured texts. Analysis includes comparing the shortest search time and average search time, and we also present the storage usage of each individual algorithm. Algorithms are implemented and analysed using an algorithm analysis environment ALGator, developed by doc. dr. Tomaž Dobravc. Results are compared on the basis of theoretical expectations. vzorec iskanje v nizu Bruteforce Boyer-Moore Turbo-Boyer-Moore Rabin-Karp Knuth-Morris-Pratt Horsepool Berry-Ravindran Apostolico-Chrochemore Quick Search računalništvo visokošolski strokovni študij računalništvo in informatika diplomske naloge pattern search in a set brute-force Boyer-Moore Turbo-Boyer-Moore Rabin-Karp Knuth-Morris-Pratt Horsepool Berry-Ravindran Apostolico-Chrochemore Quick Search computer science computer and information science diploma true false false [A. Pratnemer] Slovenski jezik Angleški jezik Diplomsko delo/naloga 2014-09-18 13:30:00 2014-09-18 13:30:00 2024-08-12 15:09:08 0000-00-00 00:00:00 2014 0 0 45 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 14881 1536026307 63030273-20140912144911-Pratnemer.pdf 63030273-20140912144911-Pratnemer.pdf 1 E3DD7FF837F5317A985B77C92076F538 f6abe993c631d33cb2da967146e1131657c6314748b0d05775f6a2d9dd1b4cb5 4c79a51a-a1a8-11eb-a523-00155dcfd717 20.500.12556/rul/b1483f29-538b-46e9-9b9f-60c2ab72a7a4 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=29493 Fakulteta za računalništvo in informatiko 0 0 0