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

PRATNEMER, ANŽE (author), 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.

• Language: Slovenian
• Keywords: 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
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Publisher: [A. Pratnemer]
• Year: 2014
• Number of pages: 45 str.
• PID: 20.500.12556/RUL-29497
• COBISS.SI-ID: 1536026307
• Publication date in RUL: 18.09.2014

Licences

• License: CC BY-SA 2.5 SI, Creative Commons Attribution-ShareAlike 2.5 Slovenia
• Link: https://creativecommons.org/licenses/by-sa/2.5/si/deed.en
• Description: You are free to reproduce and redistribute the material in any medium or format. You are free to remix, transform, and build upon the material for any purpose, even commercially. You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original. You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

Secondary language

• Language: English
• Title: Analysis of the string searching algorithms with the ALGator system

Abstract

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.

• Keywords: 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