Analiza algoritmov za iskanje podnizov s pomočjo sistema ALGator : diplomsko delo

PRATNEMER, ANŽE (avtor), Dobravec, Tomaž (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: 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
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Založnik: [A. Pratnemer]
• Leto izida: 2014
• Št. strani: 45 str.
• PID: 20.500.12556/RUL-29497
• COBISS.SI-ID: 1536026307
• Datum objave v RUL: 18.09.2014

Licence

• Licenca: CC BY-SA 2.5 SI, Creative Commons Priznanje avtorstva-Deljenje pod enakimi pogoji 2.5 Slovenija
• Povezava: https://creativecommons.org/licenses/by-sa/2.5/si/deed.sl
• Opis: Dovoljuje kopiranje in razširjanje vsebin v kakršnemkoli mediju in obliki. Dovoljuje remixanje, urejanje, predelava in vključevanje vsebine v lastna dela v vse namene, tudi komercialne. Primerno morate navesti avtorja, povezavo do licence in označiti spremembe, če so kakšne nastale. To lahko storite na kakršenkoli razumen način, vendar ne na način, ki bi namigoval na to, da dajalec licence podpira vas ali vašo uporabo dela. Če vsebino uredite, predelate (remixate) ali gradite na njej, morate svojo različico razširjati pod isto licenco kot izvirnik. Ne smete uporabiti pravnih določil ali tehničnih ukrepov, ki bi pravno omejili ali onemogočilo druge, da bi storili karkoli, kar licenca dovoli.

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Analysis of the string searching algorithms with the ALGator system

Izvleček

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.

• Ključne besede: 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